The Mathematics of Statistical Machine Translation: Parameter Estimation

A series of five statistical translation models (the IBM Models 1–5) with EM algorithms for estimating their parameters from pairs of sentences that are translations of each other, plus word-by-word alignments; trained on the French–English Canadian Hansards.

Simple statistical methods can be surprisingly successful: sentences could be aligned using only their lengths (in words or characters), without looking at the words. This paper goes on to align the words within aligned sentence pairs.

Their algorithms have minimal linguistic content (the only linguistic input was rules for finding sentence boundaries), yet they recover convincing alignments, so the alignments must come from the data itself.

Applying statistical and cryptanalytic techniques from communication theory to machine translation. Such efforts were soon abandoned for philosophical and theoretical reasons, but with computers “of a piece with today’s digital watch” they were doomed to computational starvation anyway.

To translate French \(\mathbf{f}\), choose \(\hat{\mathbf{e}} = \arg\max_{\mathbf{e}} \Pr(\mathbf{e}) \Pr(\mathbf{f} \mid \mathbf{e})\), from Bayes’ theorem, since \(\Pr(\mathbf{f})\) doesn’t depend on \(\mathbf{e}\). The view: a French speaker had an English sentence in mind and translated it; find that sentence.

No translator rifles through all English passages computing products of probabilities; intuitively they understand the French and then express its meaning. But formally \(\Pr(\mathbf{f} \mid \mathbf{e})\) is just an enormous table, and with the right values translations of arbitrarily high quality are possible. The real question is empirical: can good enough approximations be built?

The translation models are “prodigal”, spreading most probability over ill-formed strings, which doesn’t matter for \(\Pr(\mathbf{f} \mid \mathbf{e})\) (a constant factor doesn’t change the argmax). The two factors cooperate: the translation model favours English with the right words roughly in the right places, the language model favours well-formed English. Reversing a translation model would put too little probability on well-formed English.

An object indicating, for each French word, the English word(s) it arose from, drawn as connections. Every alignment is considered correct with some probability.

Written (Le programme a été mis en application | And the(1) program(2) has(3) been(4) implemented(5,6,7)).

The set of English words connected to a French word in an alignment (e.g. don’t have any money → sont démunis). French words connected to no English word are generated by the empty cept \(e_0\), placed by convention at position 0 (e.g. à in J’applaudis à la décision).

There are \(lm\) possible connections, so \(2^{lm}\) alignments in general. Restricting each French word to one English word (or \(e_0\)), as in the models, gives \((l + 1)^m\).

By summing over alignments: \(\Pr(\mathbf{f} \mid \mathbf{e}) = \sum_{\mathbf{a}} \Pr(\mathbf{f}, \mathbf{a} \mid \mathbf{e})\). Representing an alignment as \(a_1 \ldots a_m\), \(a_j = i\) if French word \(j\) connects to English word \(i\) (0 for none), the joint can be factored exactly (no approximation) as length × per-position alignment and word choices.

With the EM algorithm: guess parameters, compute expected counts (e.g. how often \(e\) connects to \(f\)) under the current model by weighting alignments by \(\Pr(\mathbf{a} \mid \mathbf{e}, \mathbf{f})\), re-normalize the counts into new parameters, and repeat, approaching a local maximum of the training-data likelihood.

model	adds
1	word translation \(t(f \mid e)\); all alignments equally likely
2	alignment probabilities \(a(i \mid j, m, l)\) by position
3	fertility \(n(\phi \mid e)\) and distortion \(d(j \mid i, m, l)\)
4	relative distortion of cepts, word classes
5	removes deficiency (places words only in vacancies)

Each serves as a stepping stone to train the next.

The length \(m\) has a small fixed probability \(\epsilon\); each French position connects to any of the \(l + 1\) English positions (including \(e_0\)) with equal probability; and the French word depends only on the English word it connects to: \(\Pr(\mathbf{f}, \mathbf{a} \mid \mathbf{e}) = \frac{\epsilon}{(l+1)^m} \prod_j t(f_j \mid e_{a_j})\). Word order doesn’t matter.

The sum over all \((l+1)^m\) alignments of a product factorizes into a product of sums: \(\Pr(\mathbf{f} \mid \mathbf{e}) = \frac{\epsilon}{(l+1)^m} \prod_{j=1}^{m} \sum_{i=0}^{l} t(f_j \mid e_i)\). So expected counts take time proportional to \(l + m\) per word pair, not \((l+1)^m\).

\(c(f \mid e; \mathbf{f}, \mathbf{e}) = \frac{t(f \mid e)}{t(f \mid e_0) + \ldots + t(f \mid e_l)} \times (\text{count of } f \text{ in } \mathbf{f}) \times (\text{count of } e \text{ in } \mathbf{e})\); new \(t(f \mid e)\) is the sum of these counts over the corpus, normalized over \(f\).

Its likelihood has a unique local maximum, so EM reaches the same solution from any starting point that avoids zeros (they started with all \(t(f \mid e)\) equal). Later models are initialized from earlier ones, so the final result doesn’t depend on the initial guess either.

Alignment probabilities \(a(i \mid j, m, l)\) depending on the positions and the two lengths, so word order matters. The same sum–product interchange still applies: \(\Pr(\mathbf{f} \mid \mathbf{e}) = \epsilon \prod_j \sum_i t(f_j \mid e_i)\, a(i \mid j, m, l)\). Model 1 is Model 2 with \(a\) fixed at \(1/(l+1)\).

Compute alignment probabilities with the old model but collect counts as appropriate for the new one, e.g. initialize Model 2 by using Model 1 to weight alignments while counting position statistics.

The most probable alignment \(V(\mathbf{f} \mid \mathbf{e})\). For Models 1 and 2, choose each \(a_j\) independently to maximize \(t(f_j \mid e_{a_j})\, a(a_j \mid j, m, l)\); for general models no practical exact algorithm is known.

The number of French words an English word connects to in an alignment: the usually gives one word (le, la, l’) but sometimes none; only gives one (seulement), two (ne … que) or none. Models 3–5 parameterize fertility directly.

For each English word choose a fertility and a list of French words (its tablet; together, the tableau), then permute the tableau’s words into a French string. Several (tableau, permutation) pairs can give the same French string and alignment.

Fertility \(n(\phi \mid e)\), translation \(t(f \mid e)\), distortion \(d(j \mid i, m, l)\) (French position given English position and lengths), and \(p_0, p_1\) for the empty cept.

After the real words are generated, each of them may require an extraneous word with probability \(p_1\), connected to \(e_0\); so the number of empty-cept words \(\phi_0\) grows with sentence length, and these words are spread uniformly over the remaining positions.

Fertility prevents exchanging the sum over alignments with the product, so expectations are summed over a small set of probable alignments: start from the best Model 2 alignment, hill-climb by moves (change one \(a_j\)) and swaps (exchange two), and include the neighbours of the result (plus “pegged” variants for each connection).

It wastes probability on objects that aren’t French strings. Models 3 and 4 place each word independently, so several words can land in one position and others stay empty (“generalized strings”). It’s the price of simplicity.

They give the same probability to “Je n’ai pas de stylo” and the scrambled “Je pas ai ne de stylo” as translations of “I do not have a pen”. This hardly matters, since the models are only used to predict English given real French and need be accurate only up to a constant factor.

Phrases tend to move as units, but Model 3 moves each word independently, so moving a long phrase is much less likely than a short one. Model 4 makes placement relative: the head (leftmost word) of a cept is placed relative to the center of the previous cept, and other words relative to the previous word of the same cept.

Head displacement probabilities depend on word classes of the previous English cept and the French word (50 classes each, from a mutual-information clustering). Trained values: \(d_1(-1 \mid A(\text{government’s}), B(\text{développement})) = 0.80\) vs 0.02 for \(+1\).

Non-head words are placed relative to the previous word of the cept, in order. Implemented → mis en application stays contiguous, while not → ne … pas usually has a verb in between, so \(d_{>1}(2 \mid B(pas))\) is large (0.68).

Each word must be placed in a vacant position: distortion is expressed in terms of the number of vacancies, leaving room for the cept’s remaining words. It is powerful but unwieldy, “led to the battlefield by its weaker but more agile brethren” Models 2–4, which supply its probable alignments.

On about 1.8 million Hansard sentence pairs, with 12 EM iterations in which each model was initialized from the previous one, starting with every \(t(f \mid e)\) equal. Only about 1% of word pairs ever co-occur, and translation probabilities below a threshold were pruned, leaving about 39 French words per English word.

Not because Model 3 is worse, but because it is deficient: most of its probability is squandered on objects that aren’t strings of French words.

Nodding has large fertility (il fait signe que oui, hoche la tête…); should rarely has fertility above 1 but spreads over many forms of devoir; the usually gives le/la/les/l’ but has fertility 0 about 14% of the time; farmers typically has fertility 2, producing agriculteurs plus an article.

No: they reflect the training data. \(t(\text{le} \mid \text{the})\) was 0.497 here vs 0.610 in an earlier experiment with 40,000 sentence pairs and the 9,000 most common words.

Training discovers multi-word correspondences from scratch: Speaker learned to produce the article too, and starred was connected to exactly the right four words, starting from all French words being equally likely translations.

Without long-range constraints, probability on well-formed French shrinks exponentially with English length, so \(\Pr(\mathbf{e})\Pr(\mathbf{f} \mid \mathbf{e})\) unduly favours short English. Multiplying by \(c^l\) for an empirical \(c\) treats the symptom, not the disease.

Re-estimate parameters from the single most probable alignment of each pair instead of expectations. Each step makes the current Viterbi alignments more probable, and probability can’t exceed 1, so it converges, in a finite number of steps since there are finitely many alignments.

There are about 42,000 one-word cepts but over 1.7 billion two-word and 74 trillion three-word candidates. Promote a sequence only when its translations differ from what its words predict: high and dry → échoué or en plan, not haut et sec.

Every letter sequence is a separate word, so the 5 forms of eat must be linked to the 39 forms of manger, most never seen. They planned invertible inflectional analysis (root + ending, e.g. mange → manger + 13spres) to cut the French vocabulary by about half.