IBM alignment models

Short description: Sequence of models in statistical machine translation

IBM alignment models are a sequence of increasingly complex models used in statistical machine translation to train a translation model and an alignment model, starting with lexical translation probabilities and moving to reordering and word duplication. They underpinned the majority of statistical machine translation systems for almost twenty years starting in the early 1990s, until neural machine translation began to dominate. These models offer principled probabilistic formulation and (mostly) tractable inference.

The original work on statistical machine translation at IBM proposed five models, and a model 6 was proposed later. The sequence of the six models can be summarized as:

• Model 1: lexical translation
• Model 2: additional absolute alignment model
• Model 3: extra fertility model
• Model 4: added relative alignment model
• Model 5: fixed deficiency problem.
• Model 6: Model 4 combined with a HMM alignment model in a log linear way

Mathematical setup

The IBM alignment models translation as a conditional probability model. For each source-language ("foreign") sentence [math]\displaystyle{ f }[/math], we generate both a target-language ("English") sentence [math]\displaystyle{ e }[/math] and an alignment [math]\displaystyle{ a }[/math]. The problem then is to find a good statistical model for [math]\displaystyle{ p(e, a|f) }[/math], the probability that we would generate English language sentence [math]\displaystyle{ e }[/math] and an alignment [math]\displaystyle{ a }[/math] given a foreign sentence [math]\displaystyle{ f }[/math].

The meaning of an alignment grows increasingly complicated as the model version number grew. See Model 1 for the most simple and understandable version.

Model 1

Word alignment

Given any foreign-English sentence pair [math]\displaystyle{ (e, f) }[/math], an alignment for the sentence pair is a function of type [math]\displaystyle{ \{1, ., ..., l_e\} \to \{0, 1, ., ..., l_f\} }[/math]. That is, we assume that the English word at location [math]\displaystyle{ i }[/math] is "explained" by the foreign word at location [math]\displaystyle{ a(i) }[/math]. 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 [math]\displaystyle{ \{1, ., ..., l_e\} \to \{0, 1, ., ..., l_f\} }[/math].

Future models will allow one English world 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 [math]\displaystyle{ t(e_i | f_j) }[/math], which can be interpreted as saying "the foreign word [math]\displaystyle{ f_j }[/math] is translated to the English word [math]\displaystyle{ e_i }[/math] with probability [math]\displaystyle{ t(e_i | f_j) }[/math]".

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

Together, we have the probability[math]\displaystyle{ p(e, a|f) = \frac{1/N}{(1+l_f)^{l_e}}\prod_{i=1}^{l_e} t(e_i | f_{a(i)}) }[/math]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 [math]\displaystyle{ \{(e^{(k)}, f^{(k)})\}_k }[/math] (without alignment information), then the model can be cast into the following form:

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

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:[math]\displaystyle{ \begin{cases} \max_{t'} \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'(e_x | f_y) = 1 \quad \forall y \end{cases} }[/math]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 [math]\displaystyle{ \{(e^{(k)}, f^{(k)})\}_k }[/math]

INITIALIZE. matrix of translations probabilities [math]\displaystyle{ t(e_x | f_y) }[/math].

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

LOOP. until [math]\displaystyle{ t(e_x | f_y) }[/math] converges:

[math]\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'}t(e_i^{(k)}|f_{j'}^{(k)})} }[/math]

where each [math]\displaystyle{ \lambda_y }[/math] is a normalization constant that makes sure each [math]\displaystyle{ \sum_x t(e_x|f_y) = 1 }[/math].

RETURN. [math]\displaystyle{ t(e_x | f_y) }[/math].

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

[math]\displaystyle{ k }[/math] ranges over English-foreign sentence pairs in corpus;

[math]\displaystyle{ i }[/math] ranges over words in English sentences;

[math]\displaystyle{ j }[/math] ranges over words in foreign language sentences;

[math]\displaystyle{ x }[/math] ranges over the entire vocabulary of English words in the corpus;

[math]\displaystyle{ y }[/math] 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 [math]\displaystyle{ (e, f) }[/math], any permutation of the English sentence is equally likely: [math]\displaystyle{ p(e|f) = p(e'|f) }[/math] for any permutation of the English sentence [math]\displaystyle{ e }[/math] into [math]\displaystyle{ e' }[/math].
• No length preference: The probability of each length of translation is equal: [math]\displaystyle{ \sum_{e\text{ has length }l}p(e|f) = \frac 1N }[/math] for any [math]\displaystyle{ l \in \{1, 2, ..., N\} }[/math].
• 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 [math]\displaystyle{ p_a(j |i, l_e, l_f) }[/math], meaning "the probability that English word [math]\displaystyle{ i }[/math] is aligned to foreign word [math]\displaystyle{ j }[/math], when the English sentence is of length [math]\displaystyle{ l_e }[/math], and the foreign sentence is of length [math]\displaystyle{ l_f }[/math]".

The rest of Model 1 is unchanged. With that, we have [math]\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) }[/math]The EM algorithm can still be solved in closed-form, giving the following algorithm:[math]\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'}t(e_i^{(k)}|f_{j'}^{(k)})p_a(j' | i, l_e, l_f)} }[/math][math]\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'}t(e_i^{(k)}|f_{j'}^{(k)})p_a(j' | i, l_e, l_f)} }[/math]where [math]\displaystyle{ \lambda }[/math] 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:

[math]\displaystyle{ n(\phi \lor f) }[/math]

For each foreign word [math]\displaystyle{ j }[/math], such distribution indicates to how many output words [math]\displaystyle{ \phi }[/math] it usually translates. This model deals with dropping input words because it allows [math]\displaystyle{ \phi=0 }[/math]. 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:

[math]\displaystyle{ n(\varnothing \lor NULL) }[/math]

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:

[math]\displaystyle{ P(S\mid E,A)=\prod_{i=1}^{I} \Phi_i!n(\Phi \mid e_j)*\prod_{j=1}^{J}t(f_j \mid e_{a_j})*\prod_{j:a(j)\neq 0}^{J}d(j | a_j, I, J)\binom{J-\Phi_0}{\Phi_0} p_0^{\Phi_0}p_1^J }[/math]

where [math]\displaystyle{ \Phi_i }[/math] represents the fertility of [math]\displaystyle{ e_i }[/math], each source word [math]\displaystyle{ s }[/math] is assigned a fertility distribution [math]\displaystyle{ n }[/math], and [math]\displaystyle{ I }[/math] and [math]\displaystyle{ J }[/math] 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: [math]\displaystyle{ d_1(j-\odot_{[i-1]}\lor A(f_{[i-1]}),B(e_j)) }[/math]

For additional words: [math]\displaystyle{ d_1(j-\pi_{i,k-1}\lor B(e_j)) }[/math]

where [math]\displaystyle{ A(f) }[/math] and [math]\displaystyle{ B(e) }[/math] functions map words to their word classes, and [math]\displaystyle{ e_{j} }[/math] and [math]\displaystyle{ f_{[i-1]} }[/math] are distortion probability distributions of the words. The cept is formed by aligning each input word [math]\displaystyle{ f_i }[/math] 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 [math]\displaystyle{ v_j }[/math] 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: [math]\displaystyle{ d_1(v_j\lor B(e_j),v_{\odot i-1},v_{max}) }[/math]

For additional words: [math]\displaystyle{ d_1(v_{j}-v_{\pi_{i,k-1}}\lor B(e_j),v_{max'}) }[/math]

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:

[math]\displaystyle{ p_6(f,a\lor e)= \frac{p_4(f,a\lor e)^\alpha*p_{HMM}(f,a\lor e)}{\sum_{a',f'} p_4(f',a'\lor e)^\alpha*p_{HMM}(f',a'\lor e)} }[/math]

where the interpolation parameter [math]\displaystyle{ \alpha }[/math] 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 [math]\displaystyle{ p_k (f, a \mid e) }[/math] with [math]\displaystyle{ k=1,2,\dotsc,K }[/math] as:

[math]\displaystyle{ p_6(f,a\lor e)=\frac{\prod_{k=1}^{K}p_k(f,a\lor e)^{\alpha_{k}}}{\sum_{a',f'}\prod_{k=1}^{K}p_k(f',a'\mid e)^{\alpha_{k}}} }[/math]

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