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 show how to extend a discriminative approach to word alignment to allow fertility modeling and to capture first-order interactions between alignments of consecutive words, enhancing the expressive power of the discriminative approach. Allowing to capture phenomena of monotonicity, local inversion and contiguos fertility trends - phenomena that are highly informative for alignment. They do so while remaining computationally efficient.

Their best models achieves a relative AER reduction of 25 % over the basic matching formulation, beating intersected IBM Model 4 without the use of any compute-intensive features. 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 authors base their work in a previous 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 wights $s_{jk}$ represent the degree to which word $j$ in one sentence cans 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 previously mentioned baseline model, a word can align to at most one word in the translation, which is not the proper solution in cases such as backbone and épine dorsal (in French). The first approach that came to ones mind would be to 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$.

The authors defined instead a means of encouraging the common case of low fertility, allowing only higher fertilities when it is licensed, introducing penalties in the model for higher fertilities. That penalties is modeled introducing variables $z_{dj\bullet }$ and $z_{d\bullet k}$ (meaning that node $j$ (or $k$) has fertility of at least $d$). 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$, where 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 though 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}$, are correspondent scores $s_{jklm}$, are added to the model indicating whether both edge $jk$ and $lm$ are in the alignment. Additionally, the pair of constraints $z_{jklm}\leq z_{jk}$ and $z_{jklm}\leq z_{lm}$ are 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

HMM MUC-6