IBM alignment models

Model 1

Word alignment

Given any foreign-English sentence pair ${\displaystyle (e,f)}$, an alignment for the sentence pair is a function of type ${\displaystyle \{1,.,...,l_e\}\to \{0,1,.,...,l_f\}}$. That is, we assume that the English word at location ${\displaystyle i}$ is "explained" by the foreign word at location ${\displaystyle a(i)}$. For example, consider the following pair of sentences

It will surely rain tomorrow -- 明日 は きっと 雨 だ

We can align some English words to corresponding Japanese words, but not everyone:

it -> ?

will -> ?

surely -> きっと

rain -> 雨

tomorrow -> 明日

This in general happens due to the different grammar and conventions of speech in different languages. English sentences require a subject, and when there is no subject available, it uses a dummy pronoun it. Japanese verbs do not have different forms for future and present tense, and the future tense is implied by the noun 明日 (tomorrow). Conversely, the topic-marker は and the grammar word だ (roughly "to be") do not correspond to any word in the English sentence. So, we can write the alignment as

1-> 0; 2 -> 0; 3 -> 3; 4 -> 4; 5 -> 1

where 0 means that there is no corresponding alignment.

Thus, we see that the alignment function is in general a function of type ${\displaystyle \{1,.,...,l_e\}\to \{0,1,.,...,l_f\}}$.

Future models will allow one English word to be aligned with multiple foreign words.

Statistical model

Given the above definition of alignment, we can define the statistical model used by Model 1:

• Start with a "dictionary". Its entries are of form ${\displaystyle t(e_i|f_j)}$, which can be interpreted as saying "the foreign word ${\displaystyle f_j}$ is translated to the English word ${\displaystyle e_i}$ with probability ${\displaystyle t(e_i|f_j)}$".

• After being given a foreign sentence ${\displaystyle f}$ with length ${\displaystyle l_f}$, we first generate an English sentence length ${\displaystyle l_e}$ uniformly in a range ${\displaystyle Uniform[1,2,...,N]}$. In particular, it does not depend on ${\displaystyle f}$ or ${\displaystyle l_f}$.
• Then, we generate an alignment uniformly in the set of all possible alignment functions ${\displaystyle \{1,.,...,l_e\}\to \{0,1,.,...,l_f\}}$.
• Finally, for each English word ${\displaystyle e_1,e_2,...e_{l_e}}$, generate each one independently of every other English word. For the word ${\displaystyle e_i}$, generate it according to ${\displaystyle t(e_i|f_{a(i)})}$.

Together, we have the probability$${\displaystyle p(e,a|f)=\frac{1/N}{(1+l_f{)}^{l_e}}\prod _{i=1}^{l_e}t(e_i|f_{a(i)})}$$IBM Model 1 uses very simplistic assumptions on the statistical model, in order to allow the following algorithm to have closed-form solution.

Learning from a corpus

If a dictionary is not provided at the start, but we have a corpus of English-foreign language pairs ${\displaystyle \{(e^{(k)},f^{(k)}){\}}_k}$ (without alignment information), then the model can be cast into the following form:

• fixed parameters: the foreign sentences ${\displaystyle \{f^{(k)}{\}}_k}$.
• learnable parameters: the entries of the dictionary ${\displaystyle t(e_i|f_j)}$.
• observable variables: the English sentences ${\displaystyle \{e^{(k)}{\}}_k}$.
• latent variables: the alignments ${\displaystyle \{a^{(k)}{\}}_k}$

In this form, this is exactly the kind of problem solved by expectation–maximization algorithm. Due to the simplistic assumptions, the algorithm has a closed-form, efficiently computable solution, which is the solution to the following equations:$${\displaystyle \{\begin{array}{l}\underset{t^{\prime }}{max}\sum _k\sum _i\sum _{a^{(k)}}t(a^{(k)}|e^{(k)},f^{(k)})\ln t(e_i^{(k)}|f_{a^{(k)}(i)}^{(k)})\\ \sum _x{t}^{\prime }(e_x|f_y)=1\mathrm{\forall }y\end{array}}$$This can be solved by Lagrangian multipliers, then simplified. For a detailed derivation of the algorithm, see chapter 4 and.

In short, the EM algorithm goes as follows:

INPUT. a corpus of English-foreign sentence pairs ${\displaystyle \{(e^{(k)},f^{(k)}){\}}_k}$

INITIALIZE. matrix of translations probabilities ${\displaystyle t(e_x|f_y)}$.

This could either be uniform or random. It is only required that every entry is positive, and for each ${\displaystyle y}$, the probability sums to one: ${\displaystyle \sum _{x}t(e_x|f_y)=1}$.

LOOP. until ${\displaystyle t(e_x|f_y)}$ converges:

${\displaystyle t(e_x|f_y)\leftarrow \frac{t(e_x|f_y)}{{\lambda }_y}\sum _{k,i,j}\frac{\delta (e_x,e_i^{(k)})\delta (f_y,f_j^{(k)})}{\sum _{j^{\prime }}t(e_i^{(k)}|f_{j^{\prime }}^{(k)})}}$

where each ${\displaystyle {\lambda }_y}$ is a normalization constant that makes sure each ${\displaystyle \sum _{x}t(e_x|f_y)=1}$.

RETURN. ${\displaystyle t(e_x|f_y)}$.

In the above formula, ${\displaystyle \delta }$ is the Dirac delta function -- it equals 1 if the two entries are equal, and 0 otherwise. The index notation is as follows:

${\displaystyle k}$ ranges over English-foreign sentence pairs in corpus;

${\displaystyle i}$ ranges over words in English sentences;

${\displaystyle j}$ ranges over words in foreign language sentences;

${\displaystyle x}$ ranges over the entire vocabulary of English words in the corpus;

${\displaystyle y}$ ranges over the entire vocabulary of foreign words in the corpus.

Limitations

There are several limitations to the IBM model 1.

• No fluency: Given any sentence pair ${\displaystyle (e,f)}$, any permutation of the English sentence is equally likely: ${\displaystyle p(e|f)=p(e^{\prime }|f)}$ for any permutation of the English sentence ${\displaystyle e}$ into ${\displaystyle e^{\prime }}$.
• No length preference: The probability of each length of translation is equal: ${\displaystyle \sum _{e\text{ has length }l}p(e|f)=\frac{1}{N}}$ for any ${\displaystyle l\in \{1,2,...,N\}}$.
• Does not explicitly model fertility: some foreign words tend to produce a fixed number of English words. For example, for German-to-English translation, ja is usually omitted, and zum is usually translated to one of to the, for the, to a, for a.

Model 2

Model 2 allows alignment to be conditional on sentence lengths. That is, we have a probability distribution ${\displaystyle p_a(j|i,l_e,l_f)}$, meaning "the probability that English word ${\displaystyle i}$ is aligned to foreign word ${\displaystyle j}$, when the English sentence is of length ${\displaystyle l_e}$, and the foreign sentence is of length ${\displaystyle l_f}$".

The rest of Model 1 is unchanged. With that, we have $${\displaystyle p(e,a|f)=1/N\prod _{i=1}^{l_e}t(e_i|f_{a(i)})p_a(a(i)|i,l_e,l_f)}$$The EM algorithm can still be solved in closed-form, giving the following algorithm:$${\displaystyle t(e_x|f_y)\leftarrow \frac{1}{{\lambda }_y}\sum _{k,i,j}\frac{t(e_i^{(k)}|f_j^{(k)})p_a(j|i,l_e,l_f)\delta (e_x,e_i^{(k)})\delta (f_y,f_j^{(k)})}{\sum _{j^{\prime }}t(e_i^{(k)}|f_{j^{\prime }}^{(k)})p_a(j^{\prime }|i,l_e,l_f)}}$$$${\displaystyle p_a(j|i,l_e,l_f)\leftarrow \frac{1}{{\lambda }_{i,l_e,l_f}}\sum _k\frac{t(e_i^{(k)}|f_j^{(k)})p_a(j|i,l_e,l_f)\delta (e_x,e_i^{(k)})\delta (f_y,f_j^{(k)})\delta (l_e,l_e^{(k)})\delta (l_f,l_f^{(k)})}{\sum _{j^{\prime }}t(e_i^{(k)}|f_{j^{\prime }}^{(k)})p_a(j^{\prime }|i,l_e,l_f)}}$$where ${\displaystyle \lambda }$ are still normalization factors. See section 4.4.1 of for a derivation and an algorithm.

Model 3

The fertility problem is addressed in IBM Model 3. The fertility is modeled using probability distribution defined as:

${\displaystyle n(\varphi \vee f)}$

For each foreign word ${\displaystyle j}$, such distribution indicates to how many output words ${\displaystyle \varphi }$ it usually translates. This model deals with dropping input words because it allows ${\displaystyle \varphi =0}$. But there is still an issue when adding words. For example, the English word do is often inserted when negating. This issue generates a special NULL token that can also have its fertility modeled using a conditional distribution defined as:

${\displaystyle n(\varnothing \vee NULL)}$

The number of inserted words depends on sentence length. This is why the NULL token insertion is modeled as an additional step: the fertility step. It increases the IBM Model 3 translation process to four steps:

The last step is called distortion instead of alignment because it is possible to produce the same translation with the same alignment in different ways. For example, in the above example, we have another way to get the same alignment:

• ja NULL nie pôjde tak do do domu
• I do not go the to house
• I do not go to the house

IBM Model 3 can be mathematically expressed as:

${\displaystyle P(S\mid E,A)=\prod _{i=1}^I{\mathrm{\Phi }}_i!n(\mathrm{\Phi }\mid e_j)\ast \prod _{j=1}^{J}t(f_j\mid e_{a_j})\ast \prod _{j:a(j)\ne 0}^{J}d(j|a_j,I,J)(\genfrac{}{}{0ex}{}{J-{\mathrm{\Phi }}_0}{{\mathrm{\Phi }}_0})p_0^{{\mathrm{\Phi }}_0}{p}_1^J}$

where ${\displaystyle {\mathrm{\Phi }}_i}$ represents the fertility of ${\displaystyle e_i}$, each source word ${\displaystyle s}$ is assigned a fertility distribution ${\displaystyle n}$, and ${\displaystyle I}$ and ${\displaystyle J}$ refer to the absolute lengths of the target and source sentences, respectively.

See section 4.4.2 of for a derivation and an algorithm.

Model 4

In IBM Model 4, each word is dependent on the previously aligned word and on the word classes of the surrounding words. Some words tend to get reordered during translation more than others (e.g. adjective–noun inversion when translating Polish to English). Adjectives often get moved before the noun that precedes them. The word classes introduced in Model 4 solve this problem by conditioning the probability distributions of these classes. The result of such distribution is a lexicalized model. Such a distribution can be defined as follows:

For the initial word in the cept: ${\displaystyle d_1(j-{\odot }_{[i-1]}\vee A(f_{[i-1]}),B(e_j))}$

For additional words: ${\displaystyle d_1(j-{\pi }_{i,k-1}\vee B(e_j))}$

where ${\displaystyle A(f)}$ and ${\displaystyle B(e)}$ functions map words to their word classes, and ${\displaystyle e_j}$ and ${\displaystyle f_{[i-1]}}$ are distortion probability distributions of the words. The cept is formed by aligning each input word ${\displaystyle f_i}$ to at least one output word.

Both Model 3 and Model 4 ignore if an input position was chosen and if the probability mass was reserved for the input positions outside the sentence boundaries. It is the reason for the probabilities of all correct alignments not sum up to unity in these two models (deficient models).

Model 5

IBM Model 5 reformulates IBM Model 4 by enhancing the alignment model with more training parameters in order to overcome the model deficiency. During the translation in Model 3 and Model 4 there are no heuristics that would prohibit the placement of an output word in a position already taken. In Model 5 it is important to place words only in free positions. It is done by tracking the number of free positions and allowing placement only in such positions. The distortion model is similar to IBM Model 4, but it is based on free positions. If ${\displaystyle v_j}$ denotes the number of free positions in the output, the IBM Model 5 distortion probabilities would be defined as:

For the initial word in the cept: ${\displaystyle d_1(v_j\vee B(e_j),v_{\odot i-1},v_{max})}$

For additional words: ${\displaystyle d_1(v_j-v_{{\pi }_{i,k-1}}\vee B(e_j),v_{ma{x}^{\prime }})}$

The alignment models that use first-order dependencies like the HMM or IBM Models 4 and 5 produce better results than the other alignment methods. The main idea of HMM is to predict the distance between subsequent source language positions. On the other hand, IBM Model 4 tries to predict the distance between subsequent target language positions. Since it was expected to achieve better alignment quality when using both types of such dependencies, HMM and Model 4 were combined in a log-linear manner in Model 6 as follows:

${\displaystyle p_6(f,a\vee e)=\frac{p_4(f,a\vee e{)}^{\alpha }\ast p_{HMM}(f,a\vee e)}{\sum _{a^{\prime },f^{\prime }}{p}_4(f^{\prime },a^{\prime }\vee e{)}^{\alpha }\ast p_{HMM}(f^{\prime },a^{\prime }\vee e)}}$

where the interpolation parameter ${\displaystyle \alpha }$ is used in order to count the weight of Model 4 relatively to the hidden Markov model. A log-linear combination of several models can be defined as ${\displaystyle p_k(f,a\mid e)}$ with ${\displaystyle k=1,2,\dots ,K}$ as:

${\displaystyle p_6(f,a\vee e)=\frac{\prod _{k=1}^K{p}_k(f,a\vee e{)}^{{\alpha }_k}}{\sum _{a^{\prime },f^{\prime }}\prod _{k=1}^K{p}_k(f^{\prime },a^{\prime }\mid e{)}^{{\alpha }_k}}}$

The log-linear combination is used instead of linear combination because the ${\displaystyle P_r(f,a\mid e)}$ values are typically different in terms of their orders of magnitude for HMM and IBM Model 4.