The Mathematics of Statistical Machine Translation: Parameter Estimation

In 1949, Warren Weaver wrote a visionary memorandum suggesting that translation could be viewed as a cryptography problem: a French text is simply English that has been "encoded" into French. If we have good methods for breaking codes, perhaps we can use them to translate.

Brown et al. turned this metaphor into a precise mathematical framework borrowed from Claude Shannon's information theory. The idea is called the noisy channel model: the speaker thinks in English (the source), the thought passes through a "noisy channel" that distorts it into French (the observed signal), and the translator's job is to recover the original English.

Mathematically, we want the English sentence ê that maximizes the posterior probability given the observed French f. By Bayes' theorem this decomposes into two independent pieces that can be modeled and trained separately.

This decomposition is elegant because it separates two very different skills. The language model P(e) knows nothing about French — it just knows what good English looks like, trained on mountains of English text. The translation model P(f|e) knows nothing about English grammar — it just models how English words get distorted into French words. Each can be improved independently, and together they produce translations.

Think of it as two expert consultants: one is a native English editor who ranks sentences by fluency, and the other is a bilingual cryptographer who scores how likely each English sentence is to produce the French you observed. The best translation satisfies both.

To compute P(f|e), we need to know which English word produced which French word. This word-level correspondence is called an alignment. For example, in the pair "the house" → "la maison", "the" aligns to "la" and "house" aligns to "maison."

But alignments are never given to us — they are hidden variables. Nobody manually drew arrows between millions of sentence pairs in the Hansard corpus. So the model must simultaneously learn the translation probabilities AND figure out the alignments. This is the classic chicken-and-egg problem: if we knew the alignments, we could count word pairs and estimate translation probabilities directly; if we knew the translation probabilities, we could pick the best alignment. We know neither.

The solution is the Expectation-Maximization (EM) algorithm, which iterates between guessing alignments (given current translation probabilities) and updating translation probabilities (given the guessed alignments), spiraling toward the answer.

Model 1 is the simplest possible translation model. It makes one radical assumption: word position doesn't matter. Every alignment — every possible way to connect French words to English words — is equally likely, regardless of where the words sit in their sentences.

This sounds absurd, but it's a deliberate simplification. By ignoring position, Model 1 has only one set of parameters to learn: the lexical translation probabilities t(f|e) — the probability that English word e translates to French word f. With this single assumption, the EM algorithm has a unique global optimum: no matter where you start, you converge to the same answer. No other IBM model has this guarantee.

The model also introduces a special NULL token: an imaginary English word at position 0 that "generates" French words with no English counterpart (like the French "ne" in negation, which has no single English equivalent).

Read this formula as a process: for each French word f_j, we don't know which English word produced it, so we sum over ALL possible English sources (including NULL). Each source contributes its translation probability t(f_j|e_i). Because we assume all alignments are equally likely, we just average. The product over j says: do this independently for every French word.

The EM algorithm for Model 1 is surprisingly simple. Start by setting every translation probability t(f|e) to the same value — a uniform guess. Then repeat two steps:

E-step (Expectation): For each sentence pair, use the current t(f|e) values to compute how much each English word is "responsible" for each French word. This gives fractional alignment counts — soft guesses about who translates whom.

M-step (Maximization): Collect all the fractional counts across the entire corpus and re-estimate each t(f|e) by normalizing: t(f|e) = count(f,e) / count(e). Words that co-occur in aligned positions get higher probability.

Each iteration increases the likelihood of the observed data. Model 1's convexity guarantees convergence to the global maximum — a rare luxury in machine learning.

Model 1 treats all alignments as equally probable — "la" could come from any English position. But in reality, the first French word usually comes from near the beginning of the English sentence. Model 2 adds an alignment probability a(i|j, l, m): the probability that French position j is aligned to English position i, given sentence lengths l (English) and m (French).

Think of it as adding a rubber band between corresponding positions. The first French word is gently pulled toward the beginning of the English sentence, the last toward the end. The model can still learn exceptions (French verb inversion, for instance), but now it has a position preference rather than uniform randomness.

Models 1 and 2 assume each French word comes from exactly one English word. But translation isn't one-to-one. The English word "not" might produce two French words: "ne...pas." The German "Kindergarten" is one word but translates to two English words.

Model 3 introduces fertility φ(e): the number of French words that English word e produces. An English word with fertility 0 contributes nothing to the French sentence (it's "dropped"). Fertility 1 is normal one-to-one translation. Fertility 2 or more means the word "expands" into a phrase.

Picture each English word as a seed that can sprout zero, one, or several French seedlings. The fertility probability n(φ|e) tells us how many seedlings each seed typically produces. After sprouting, each seedling is independently translated (using t(f|e)) and then positioned (using a distortion probability d(j|i,l,m) that replaces Model 2's alignment probability).

Model 4 observes that phrases tend to move as units. If "ne...pas" is generated from "not", the two French words should land near each other, not scatter randomly. Model 4 replaces Model 3's absolute distortion with a relative distortion model: the position of each French word depends on where the previous aligned word landed. It also introduces word classes — groups of words with similar syntactic behavior — to share statistical strength across rare words.

Think of relative distortion like a caravan: the first word in a phrase sets the direction, and subsequent words follow nearby. Absolute distortion (Model 3) was like dropping each word randomly on a map; relative distortion means they travel together.

Model 5 addresses a technical flaw in Models 3 and 4 called deficiency: these models waste probability mass on impossible events (like placing two French words in the same position). Model 5 corrects this by tracking which positions are already occupied, placing words only into vacant slots. It's the mathematically cleanest model but offers only marginal translation improvement over Model 4.

To understand how the models work, it helps to think of translation as a story the model tells about how a French sentence was "generated" from an English one. Here is Model 3's story, step by step:

Step 1 — Fertility: For each English word e_i, choose its fertility φ_i from n(φ|e_i). This decides how many French words each English word will produce.

Step 2 — NULL insertion: Decide how many extra French words come from NULL (words with no English source). These are distributed uniformly.

Step 3 — Lexical translation: For each "slot" created by fertility, independently choose a French word from t(f|e_i).

Step 4 — Distortion: Assign each generated French word to a position in the French sentence using d(j|i,l,m).

The probability of the entire French sentence is the product of all these choices. Training means finding the parameters (n, t, d) that maximize this probability across all sentence pairs in the corpus.

Once we've trained the model, a key application is finding the most probable alignment between a sentence pair — which English word most likely produced which French word. For Model 1, this is trivial: each French word independently picks its most probable English source. For Model 2, it's still independent per French word (just pick the i that maximizes a(i|j,l,m)·t(f_j|e_i)).

For Models 3–5, finding the optimal alignment is NP-hard in general because fertility couples the decisions. Brown et al. use a hill-climbing heuristic: start from the Model 2 Viterbi alignment, then try local moves (swapping two alignment links, moving one link) until no move improves the probability. This is suboptimal in theory but works well in practice — the resulting alignments "account well for the word-by-word relationships," as the authors note.

The IBM models didn't just improve translation — they created a new field. Before this paper, machine translation was a rules-based craft. After it, MT became a data-driven science. The key principles survive in modern neural translation:

The noisy channel decomposition taught the field to think about translation probabilistically. Even seq2seq models estimate P(target|source), a direct descendant of P(f|e).

Word alignment became the backbone of phrase-based SMT (the dominant paradigm from 2003–2016) and inspired the attention mechanism in neural models — which is, at its core, a soft, learned alignment.

The EM training framework — learning from data without explicit supervision — remains foundational. BERT's masked language modeling, GPT's next-token prediction, and contrastive learning all share the DNA of learning from structure in unlabeled data.

Each IBM model adds exactly one idea to the previous one, forming a staircase of increasing realism. Model 1 is the foundation — lexical translation only, globally optimal. Model 2 adds positional preference. Model 3 adds fertility. Model 4 adds phrase-level reordering. Model 5 fixes probability deficiency. Each model is initialized from the one below it, inheriting its predecessor's knowledge and refining it.