Lacoste-Julien et al, NAACL 2006

Being edited by Rui Correia

Citation

Simon Lacoste-Julien, Ben Taskar, Dan Klein, and Michael I. Jordan. Word alignment via quadratic assignment. In Human Language Technology–North American Association for Computational Linguistics, New York, NY, 2006. On-line

Summary

In this paper the authors address two major limitations of Taskar et al. (2005) paper on discriminative word alignment methods: fertility and first-order interactions.

The authors propose methods to extend that discriminative approach to word alignment in order to allow fertility modeling and to capture first-order interactions between alignments of consecutive words. By allowing to capture phenomena such as monotonicity, local inversion and contiguos fertility trends (highly informative for alignment) the authors enhance the expressive power of the baseline discriminative approach, while remaining computationally efficient.

Their best result consists of a relative AER reduction of 25 % over the baseline discriminative formulation. The authors claim their contribution to be particularly promising for phrase-based systems since they perform better with higher recall on the task.

Baseline Method

The baseline method used in this paper, as already mentioned, is a discriminative approach to word alignments by Taskar et al. (2005). In this model, nodes $V^{s}$ and $V^{t}$ correspond to words in the source and target language, respectively, and edges $\varepsilon =\{jk:j\in V^{s},k\in V^{t}\}$ correspond to alignments between words. The edge weights $s_{jk}$ represent the degree to which word $j$ in one sentence can be translated using word $k$ in the other sentence. The predicted alignments are then chosen by maximizing the sum of the edge scores, which can be formulated in linear programming as:

$\max _{0\leq z\leq 1}\sum _{jk\in \varepsilon }s_{jk}z_{jk}$

      $s.t.\sum _{j\in V^{s}}z_{jk}\leq 1,\forall k\in V^{t};$

          $\sum _{k\in V^{t}}z_{jk}\leq 1,\forall j\in V^{s},$

where $z_{jk}$ are relaxations of the binary variables that indicate if $j$ is assigned to $k$.

Fertility

In the baseline model, a word could only align to at most one word in the translation. This limitation implies that cases such as backbone and épine dorsal (in French) can not be inferred. To solve this problem, one could simply increase the right hand side for the constraints in the baseline model from $1$ to $D$, where $D$ is the maximum allowed fertility. However, this would cause that maximum weight solutions would have either all words with fertility $0$ or $D$.

Instead, the authors defined a means of encouraging the common case of low fertility, allowing only higher fertilities when it is licensed, introducing penalties in the model for those high fertilities. Those penalties are modeled introducing variables $z_{dj\bullet }$ and $z_{d\bullet k}$ (meaning that node $j$ (or $k$) has fertility of at least $d$). Subsequently, the model formulation in linear programming comes as:

$\max _{0\leq z\leq 1}\sum _{jk\in \varepsilon }{s_{jk}z_{jk}}-\sum _{j\in V^{s},2\leq d\leq D}{s_{dj\bullet }z_{dj\bullet }}-\sum _{k\in V^{t},2\leq d\leq D}{s_{d\bullet k}z_{d\bullet k}}$

      $s.t.\sum _{j\in V^{s}}z_{jk}\leq 1+\sum _{2\leq d\leq D}{z_{d\bullet k}},\forall k\in V^{t};$

          $\sum _{k\in V^{t}}z_{jk}\leq 1+\sum _{2\leq d\leq D}{z_{dj\bullet }},\forall j\in V^{s},$

where $\sum _{2\leq d\leq D}{s_{dj\bullet }z_{dj\bullet }}$ represents the penalty for fertility of node $j$, and each $s_{dj\bullet }\geq 0$ is the penalty increment from increasing the fertility from $d-1$ to $d$.

First-Order Interaction

The second major limitation of the baseline model this paper addresses is the fact that the edges only interact indirectly through the competition induced by the constraints, in contrast with directly modeling correlations between alignments of consecutive words (such as in Vogal et al, COLING 1996).

The authors suggest this can be accomplished by modeling the common local alignment configurations by adding bonuses for pairs of edges, considering three examples:

• encourage strictly monotonic alignments
• local inversion of nouns and adjectives
• a word in one language can be translated as a phrase in the other language

Formally, variables named $z_{jklm}$, along with correspondent scores $s_{jklm}$ , are added to the model indicating whether both edges $jk$ and $lm$ are in the alignment. Additionally, the pair of constraints $z_{jklm}\leq z_{jk}$ and $z_{jklm}\leq z_{lm}$ is added to reinforce the semantics $z_{jklm}=z_{jk}z_{lm}$. In linear programming:

$\max _{0\leq z\leq 1}\sum _{jk\in \varepsilon }{s_{jk}z_{jk}}+\sum _{jklm\in Q}{s_{jklm}z_{jklm}}$

      $s.t.\sum _{j\in V^{s}}z_{jk}\leq 1,\forall k\in V^{t};$

          $\sum _{k\in V^{t}}z_{jk}\leq 1,\forall j\in V^{s};$

          $z_{jklm}\leq z_{jk},z_{jklm}\leq z_{lm},\forall jklm\in Q,$

where $Q=\{jklm:|j-l|\leq 1,|k.m|\leq 1\}$.

Experimental Results

The authors used the English-French Hansards dataset to apply their models, comparing the baseline method with successive augmentations, achieving a 25% AER improvement over the baseline. The figure below show the Precision, Recall and Alignment Error Rate for the baseline model alone (M), baseline and fertility (M + F), baseline and interactions (M +Q), baseline, fertility and interactions (M + F + Q) and adding the IBM Model 4 predictions (M + F + Q + IBM4).