IBM alignment models

IBM alignment models
Company type	Statistical models
Industry	Machine translation, Natural language processing
Founded	1988–1993
Founder	IBM researchers
Products	Statistical machine translation and alignment systems

The IBM alignment models represent a sequence of increasingly sophisticated frameworks applied in statistical machine translation for training both translation and alignment systems. These models begin with lexical translation probability estimation and progressively incorporate mechanisms for reordering and word duplication. Serving as the foundation for the majority of statistical machine translation architectures, they dominated the field from the early 1990s until the rise of neural machine translation. Their design offers a well-defined probabilistic approach with inference processes that remain mostly manageable.

Developed between 1988 and 1993, the IBM alignment models initially comprised five fundamental variants, with a sixth model introduced subsequently. Notably, the principal authors of the 1993 publication later became affiliated with the hedge fund Renaissance Technologies.

An overview of the six IBM models is as follows:

Model 1: lexical translation
Model 2: absolute alignment
Model 3: fertility-based alignment
Model 4: relative alignment
Model 5: addressing fixed deficiency
Model 6: integrates Model 4 with a HMM-based alignment through a log-linear framework

Mathematical setup

The IBM alignment models treat translation as a conditional probability problem. For each source-language sentence <math>f</math> (often referred to as "foreign"), the model simultaneously generates a target-language sentence <math>e</math> ("English") along with an alignment <math>a</math>. The objective is to estimate <math>p(e, a|f)</math>, which denotes the likelihood of producing the English sentence <math>e</math> together with alignment <math>a</math> given the foreign input <math>f</math>.

As the model versions advance, they accommodate increasingly complex alignment structures; Model 1 provides the most basic representation.

Word alignment

For any pair of sentences <math>(e, f)</math>, where <math>e</math> is English and <math>f</math> is foreign, an alignment associates each English word position from the set <math>\{1, ..., l_e\}</math> with a foreign word position in <math>\{0, 1, ..., l_f\}</math>. Here, zero signifies that an English word does not correspond to any foreign word. Consider this example:

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

Possible alignments include:

it -> ?
will -> ?
surely -> きっと
rain -> 雨
tomorrow -> 明日

Variations in alignments stem from syntactic differences and language-specific conventions; for example, English employs a dummy pronoun "it," whereas Japanese verbs encode tense differently. This can be expressed as:

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

Later models permit English words to link to multiple foreign words.

Statistical model

Model 1 establishes a probabilistic framework based on a lexical translation table containing entries <math>t(e_i | f_j)</math>, which quantify the probability that foreign word <math>f_j</math> translates into English word <math>e_i</math>.

Given a foreign sentence <math>f</math> of length <math>l_f</math>, the generative process is:

The length of the English sentence <math>l_e</math> is drawn uniformly from a predetermined range <math>[1, ..., N]</math>, independent of <math>f</math>.
An alignment function is selected uniformly at random from all possible mappings assigning each English position to either one foreign position or zero.
Each English word <math>e_i</math> is generated independently according to the probability distribution defined by <math>t(e_i | f_{a(i)})</math>, where <math>a(i)</math> is the aligned foreign position for word <math>e_i</math>.

This leads to the joint probability:

The simplifying assumptions in Model 1 facilitate closed-form solutions during parameter estimation.

Learning from a corpus

In scenarios where no dictionary is provided initially, but a parallel corpus of English and foreign sentence pairs <math>\{(e^{(k)}, f^{(k)})\}_k</math> exists without alignment annotations, the model approaches the task as follows:

Parameters held constant: foreign sentences <math>\{f^{(k)}\}_k</math>
Parameters to be estimated: translation probabilities <math>t(e_i | f_j)</math>
Observed data: English sentences <math>\{e^{(k)}\}_k</math>
Hidden variables: alignments <math>\{a^{(k)}\}_k</math>

This problem is tackled using the expectation–maximization algorithm (EM). Under certain simplifying assumptions, EM provides an efficient closed-form solution by maximizing:

<math display="block"> \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)}) \\ \text{subject to } \sum_x t'(e_x | f_y) = 1 \quad \forall y \end{cases} </math>

This optimization is performed using Lagrangian multipliers, leading to a simplified solution.

The EM procedure can be summarized as:

INPUT: parallel corpus of English-foreign sentence pairs <math>\{(e^{(k)}, f^{(k)})\}_k</math>
INITIALIZATION: translation probability matrix <math>t(e_x | f_y)</math>, commonly set uniformly or randomly with positive values, ensuring <math>\sum_x t(e_x|f_y) = 1</math> for each foreign word <math>y</math>.
ITERATE until convergence:

<math>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 <math>\lambda_y</math> normalizes so that <math>\sum_x t(e_x|f_y) = 1</math>.

OUTPUT: updated translation probabilities <math>t(e_x | f_y)</math>.

Here, <math>\delta</math> denotes the Dirac delta function, returning 1 when its arguments are identical and 0 otherwise. The indices represent:

<math>k</math>: sentence pair index; <math>i</math>: English word position; <math>j</math>: foreign word position; <math>x</math>: English vocabulary entry; <math>y</math>: foreign vocabulary entry.

Limitations

IBM Model 1 exhibits several notable constraints:

Lack of fluency modeling: It treats all permutations of an English sentence as equally probable translations of a given foreign sentence. Formally, for any rearrangement <math>e'</math> of an English sentence <math>e</math>, the conditional probabilities satisfy <math>p(e|f) = p(e'|f)</math>.
No preference for sentence length: Every possible English sentence length is considered equally likely, implying that the sum of probabilities over all English sentences of length <math>l</math> given a foreign sentence equals <math>\frac{1}{N}</math>, where N is the number of possible lengths.
Absence of explicit fertility representation: The model does not account for how many English words a foreign word typically produces; for example, German ja may be dropped in translation, while zum often corresponds to multiword phrases like to the or for the.

Model 2

Model 2 advances beyond Model 1 by incorporating alignment probabilities conditioned on sentence lengths. It defines a distribution <math>p_a(j | i, l_e, l_f)</math>, which captures the probability that the English word at position <math>i</math> aligns with the foreign word at position <math>j</math>, given English and foreign sentence lengths <math>l_e</math> and <math>l_f</math>.

The joint probability of an English sentence and alignment given a foreign sentence is expressed as: <math display="block">p(e, a|f) = \frac{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 remains applicable with closed-form updates adjusted to estimate these length-dependent alignment parameters. This enhancement enables more precise alignment modeling by incorporating structural information related to sentence length.

Model 3

IBM Model 3 tackles the challenge of fertility by estimating how many English words each foreign word typically generates through a fertility distribution: <math>n(\phi | f)</math>

This approach accounts for cases where words are omitted (<math>\phi=0</math>) as well as instances where a single source word produces multiple target words. To manage inserted terms (such as the English auxiliary do in negative constructions), Model 3 incorporates a distinct NULL token with its own fertility distribution: <math>n(\varnothing | NULL)</math>

The translation procedure expands into four phases, including a fertility stage that models NULL insertions depending on sentence length. The final phase is termed distortion rather than alignment, since identical alignments can yield different translations due to variations in word order.

Formally, Model 3 is defined as: <math display="block">P(S|E,A) = \prod_{i=1}^{I} \Phi_i! n(\Phi_i | e_i) * \prod_{j=1}^{J} t(f_j | e_{a_j}) * \prod_{j:a(j)\neq 0} d(j | a_j, I, J) \binom{J-\Phi_0}{\Phi_0} p_0^{\Phi_0} p_1^{J}</math>

In this expression, <math>\Phi_i</math> denotes the fertility of the English word <math>e_i</math>, while <math>I</math> and <math>J</math> represent the lengths of the target and source sentences respectively. By integrating fertility and insertion effects essential to real-world machine translation, this model substantially improves translation precision.

Model 4

IBM Model 4 enhances alignment by linking each word to the previously aligned word and considering the word classes of adjacent terms, effectively managing frequent reorderings encountered in translation (for example, adjective-noun swaps from Polish to English). Conditioning on word classes enables a lexicalized model that delivers superior alignment accuracy. Distortion probabilities are defined based on these classes for both initial and subsequent words within a cept, where every input word aligns with at least one output word.

However, Models 3 and 4 are flawed because they do not account for whether input positions were selected or reserved beyond sentence boundaries, leading to total probabilities of correct alignments that do not sum to one.

Model 5

IBM Model 5 addresses the limitations of Model 4 by introducing additional training parameters. Unlike Models 3 and 4, it guarantees that output words occupy only unassigned positions by monitoring available slots during alignment. Its distortion model remains similar but operates based on these free positions.

Alignment frameworks featuring first-order dependencies such as HMM and IBM Models 4 and 5 outperform other approaches. The HMM model predicts distances between source positions, whereas Model 4 emphasizes target positions. To capitalize on both methods, Model 6 combines HMM and Model 4 using a log-linear framework with an interpolation parameter weighting their contributions.

This log-linear integration accommodates differences in probability scales between models, thereby improving alignment performance for statistical machine translation.