Vogal et al, COLING 1996

Citation

Vogel, S., Ney, H., & Tillmann, C. (1996). Hmm-based word alignment in statistical translation. In Proceedings of the 16th conference on Computational linguistics - Volume 2, COLING ’96, pp. 836–841, Stroudsburg, PA, USA. Association for Computational Linguistics.

Online version

ACM

Summary

Word Alignments map the word correspondence between two parallel sentences in different languages.

This work extends IBM models 1 and 2, which models lexical translation probabilities and absolute distortion probabilities, by also modeling relative distortion.

The relative distortion is modeled by applying a first-order HMM, where each alignment probabilities are dependent on the distortion of the previous alignment.

Previous work

IBM Model 1 defines the probability of a sentence $s_{1}^{J}$, with length $J$, being translated to a sentence $t_{1}^{I}$, with length $I$, with the alignment $a_{1}^{J}$ as:

$Pr(t,a|s)={\frac {\epsilon }{(J+1)^{I}}}\prod _{j=1}^{J}{tr(t_{j}|s_{a(j)})}$

Where the alignment $a_{1}^{J}$ is a function that maps each word $t_{j}$ to a word $s_{i}$, by their indexes. These alignments can be viewed as an object for indicating the corresponding words in a parallel text. We can see that the sentence translation probability $Pr(t,s)$, is decomposed into the product of the lexical translation probabilities $tr(t_{j}|s_{a(j)})$ of each word in the target $t_{1},...,t_{J}$ with the word that it is aligned to in the source $s_{a(j)}$. Additionally, target words that are not aligned with any source word are aligned with the null token, with the a lexical translation probability given by $tr(t_{j}|null)$. These are referred as null insertions. The normalizing factor ${\frac {\epsilon }{(I+1)^{J}}}$ ensures that $Pr(t,a|s)$ is a probability and is normalized over all possible alignments $a$ and all possible translations $t$.

One of the problems of the IBM Model 1 is that it is very weak to reordering, since $p(f,a|s)$ is calculated using only the lexical translation probabilities $tr(t|s)$. Because of this, if the model is presented with 2 translations candidates $t_{1}$ and $t_{2}$ with the same lexical translations, but with different reordering of the translated words, the model scores both translations with the same score.

Mixture-based Alignment models~(IBM Model 2) addresses this problem by modeling the absolute distortion in the word positioning between the 2 languages, introducing an alignment probability distribution $Pr_{a}(i|j,J,I)$, where $i$ and $j$ are the word positions in the source and target sentences. Thus the equation for $Pr(t,a|s)$ becomes:

$Pr(t,a|s)={\frac {\epsilon }{(J+1)^{I}}}\prod _{j=1}^{J}{tr(t_{j}|s_{a(j)})Pr_{a}(a(j)|j,J,I)}$

Where the alignment probability distribution $Pr_{a}(a(j)|j,J,I)$ models the probability of a word in the position $i$ in the source sentence of being reordered into the position $j$ in the target sentence.

Model

While IBM Model 2 attempts to model the absolute distortion of words in sentence pairs $Pr_{a}(i|j,J,I)$, alignments have a strong tendency to maintain the local neighborhood after translation.

This uses a first order Hidden Markov Model to restructure the alignment model $Pr(t,a|s)$ to include first order alignment dependencies. Thus:

$Pr(t,a|s)={\frac {\epsilon }{(I+1)^{J}}}\prod _{j=1}^{J}{tr(t_{j}|s_{a(j)})Pr_{a}(a(j)|a(j-1),I)}$

Where the alignment probability $Pr_{a}(a(j)|a(j-1),I)$ is calculated as:

$Pr_{a}(i|i',I)={\frac {c(i-i')}{\sum _{k=1}^{I}c(k-i')}}$

In this formulation, the distortion probability does not depend on the word positions but in the jump width (i-i').

Viterbi Alignment

The alignment probability $Pr(a|t,s)$ for a given sentence pair is given by:

$Pr(a|t,s)={\frac {Pr(t,a|s)}{Pr(t|s)}}$

The Viterbi alignment is the alignment with the highest $Pr(a|t,s)$. While in previous alignment models, the Viterbi alignment could be determined in polynomial time, by maximizing the alignment probability for each target word, due to the independence assumptions that are made, finding the optimum alignment for the HMM-based model is more complex, due to the first order dependencies between alignments. This can still be calculated in polynomial time, with complexity $O(I^{2}J)$, using the dynamic programming algorithm, similar to Viterbi Decoding proposed this work. This algorithm defines the partial alignment probability $Q(i,j)$, which is defined as

$Q(i,j)=tr(t|s)max_{i'=1}^{I}Pr_{a}(i|i',I)Q(i',j-1)$

$Q(i,j)$ can be seen as the Viterbi alignment from the partial target sentence from $t_{1}$ to $t_{j}$, that contains the word alignment from $t_{j}$ to $t_{i}$. This can be done because each word alignment is only dependent on the previous alignment.

Training and Results

Tests were performed using the following corpora:

Corpora	Language Pair	Words
Avalanche Bulletins	French-German	row 1, cell 3
Verbmobil Corpus	Spanish-English	row 2, cell 3
The EuTrans Corpus	German-English	row 3, cell 3