Chapter 24Machine Translation

The task that drove the field

Machine translation is the oldest application in this book and the one that paid for most of the machinery in it.

It is also the clearest place to see the whole arc at once. Every movement of this book was tried on translation first, and each new idea arrived because the previous one hit a specific wall.

Read that last column downwards. Each generation was ended by a limitation the next one addressed, which is exactly the shape Parts I to IV followed.

Two documents worth knowing about

In 1949 Warren Weaver circulated a memorandum proposing that translation be treated as decoding. His formulation was that a Russian text is really English, encoded in a strange script, and the job is to recover it.

That framing was premature by forty years, and then it turned out to be literally the right one. Section 1.2 is Weaver’s idea, written as an equation.

In 1966 the ALPAC report concluded that machine translation was slower, less accurate and more expensive than human translation, and recommended that funding stop. It largely did, for two decades.

The report was correct about the systems it examined and wrong about the prospect. It is worth knowing about for that reason. A negative evaluation of current systems is not a negative result about the problem, and the difference is easy to lose.

Translation as decoding

Weaver’s framing gives the objective directly. Given a foreign sentence $f$, find the English sentence $e$ that is most likely to have produced it:

$$\begin{equation} \hat{e} \;=\; \arg\max_{e} \; P(e \mid f). \label{eq:mt-argmax} \quad\text{(24.1)} \end{equation}$$

Apply Bayes’ rule and the denominator does not depend on $e$, so it drops:

$$\begin{equation} \hat{e} \;=\; \arg\max_{e} \; \frac{P(f \mid e)\,P(e)}{P(f)} \;=\; \arg\max_{e} \; \underbrace{P(f \mid e)}_{\text{translation model}} \; \underbrace{P(e)}_{\text{language model}} . \label{eq:noisychannel} \quad\text{(24.2)} \end{equation}$$

This is the noisy channel model, and the factorisation is the reason it worked.

$P(e)$ is a language model, which is Chapter 10 exactly. It can be estimated from monolingual English text, of which there is a great deal, and it is what makes the output fluent.

$P(f \mid e)$ is a translation model. It needs parallel text, which is scarce, and it is what makes the output faithful.

Splitting the problem this way means the scarce resource is only asked to do half the job. Fluency comes from cheap data, adequacy from expensive data, and the two are trained separately.

Learning to align

The translation model is the hard half, and the difficulty is stated in one sentence.

A parallel corpus tells you that two sentences mean the same thing. It does not tell you which word translates which.

That correspondence is alignment, and it is a hidden variable. Nobody annotated it, and any usable translation model needs it.

IBM Model 1

The IBM models estimate alignment and translation together, from sentence pairs alone.

Model 1 is the simplest of them, and its simplifying assumption is severe. Every alignment is a priori equally likely, so position carries no information at all.

That is plainly false about language. It is also what makes the model solvable in closed form at each step. Model 1’s output is the starting point for every model above it.

The estimation is expectation maximisation, and on a small corpus you can do it by hand.

Four sentence pairs

Here is the lecture’s corpus. English on the left, Swahili on the right.

Nobody has said which word translates which. There is no dictionary and no alignment annotation.

One wrinkle is worth noticing before we start. Swahili marks possession by noun class, so my is wangu with dog and cycle but yangu with house. A model that assumed one translation per word would already be wrong, and Model 1 does not assume that.

One iteration, by hand

Initialise $t(f \mid e)$ uniformly. With six Swahili words, every entry is $1/6 = 0.1667$.

Expectation.

For each Swahili word in a pair, split one unit of count over the English words in that pair, in proportion to the current $t(f \mid e)$:

$$\begin{equation} \delta(e, f) \;=\; \frac{t(f \mid e)}{\sum_{e' \in \mathbf{e}} t(f \mid e')} . \label{eq:model1-estep} \quad\text{(24.3)} \end{equation}$$

On the first pass the table is uniform and every pair has two English words, so every $\delta$ is exactly $0.5$. The first iteration cannot prefer anything. What it can do is count.

Maximisation.

Collect the counts and renormalise:

$$\begin{equation} t(f \mid e) \;=\; \frac{\operatorname{count}(e, f)} {\sum_{f'} \operatorname{count}(e, f')} . \label{eq:model1-mstep} \quad\text{(24.4)} \end{equation}$$

Look at what my collected. It occurred in three pairs, so it gathered $3.0$ units of count. Wangu appeared beside it twice and took $1.0$ of that. Every other word appeared once and took $0.5$.

That asymmetry is the entire seed. One pass of counting is enough to notice that wangu keeps company with my more than anything else does.

What repetition does

Repeat, and the preference compounds. Each iteration uses a slightly less uniform table, so the splits become slightly less even, so the next table is sharper still.

Nothing pushed those numbers except counting and renormalising, repeated ten times.

What it learned

After ten iterations, the best Swahili word for each English word:

Four of the five are settled, from four sentences and no supervision.

The row that does not settle

Now look at house. It sits at exactly $0.5000$ against both nyumba and yangu, and it stays there. At fifty iterations it is still $0.5000$ and $0.5000$.

That is not a failure of EM. It is EM being honest.

House occurs in exactly one sentence pair, beside nyumba and yangu. Nothing anywhere else in the corpus distinguishes those two words. My correctly pushes both of them down, and pushes them down equally, to $0.0074$ each.

So house inherits both in equal measure. The data contains a tie and the model reports a tie. A model that broke it would be inventing something.

One more sentence

Add a fifth pair, his house and nyumba wake. Now house meets nyumba twice and yangu once, which is the only new information, and it is enough.

The tie resolves, and something else moves with it. $t(\mathit{yangu} \mid \mathit{my})$ rises from $0.0391$ to $0.2335$, which is more correct. Yangu really is Swahili for my, in the noun class house belongs to. Freeing house from the tie let that evidence reach my.

One sentence pair did that. It is the argument for parallel corpus size in miniature, and it is why statistical translation waited for the Canadian Hansard and the European Parliament proceedings.

Try it yourself. code/worked_examples/ibm_model1.py produces every table in this section. --step shows one iteration with every posterior and count, --learned prints the final table and the tie, --extra adds the fifth pair, and --pair "my dog" "mbwa wangu" traces the alignment of one sentence.

Run it in ColabNotebookSource

Models 2 to 5

The higher IBM models relax Model 1’s assumptions one at a time.

Model 2 adds a distortion term, so alignment probability depends on position. Model 3 adds fertility, the number of foreign words one English word produces. Models 4 and 5 refine the distortion further.

Each addition is a correction to a specific falsehood in Model 1, and each is initialised from the model below it. That staircase is itself worth noticing: a wrong but solvable model, used to bootstrap a right but unsolvable one.

Phrases, not words

Word-level translation has a limitation no amount of better alignment fixes. Languages do not correspond word for word.

Idioms translate as units. Verb particles separate. Some languages need three words where another needs one. A model whose unit is the word cannot express any of that.

Phrase-based translation takes contiguous word sequences as the unit, and it was the state of the art from roughly 1999 to 2014.

The pipeline has three steps, and the first is the interesting one.

Align in both directions. Run Model 1 English to foreign and foreign to English. The two alignments disagree, because each is a many-to-one map in a different direction.

Symmetrise. Take the intersection of the two alignments as a high-precision core. Then grow it outward with the union, under heuristics about which neighbouring points may be added.

Extract. Any pair of contiguous spans consistent with the symmetrised alignment becomes a phrase pair, and its probability comes from counting.

The result is a phrase table, and its size is its character. Millions of entries, each a short span with a probability, memorised from the corpus.

That is also its ceiling. A phrase table generalises only to phrases it has seen. It has no notion that two phrases are similar, which is precisely the complaint Chapter 11 made about count tables in general.

The neural turn

In 2014 the unit changed again, from the phrase to the whole sequence.

An encoder-decoder model reads the source sentence with one recurrent network, compresses it into a vector, and generates the target with another .

Everything that made this work is in Part III. The encoder is Chapter 12’s recurrence, usually gated as in Chapter 13. The decoder is a conditional language model, trained with the cross-entropy of Chapter 11.

Two things changed at once. There is no phrase table, so no memorised inventory, and the model generalises through the geometry of its embeddings. And the whole system is trained end to end on one objective.

The bottleneck, and the fix

The weakness was structural and was noticed immediately. The entire source sentence has to fit in one fixed-size vector.

Short sentences were fine. Long ones degraded badly, and the degradation got worse with length in a way that had an obvious cause.

The fix is Chapter 16’s opening story . Let the decoder look back at all the encoder states and learn a weighting over them at each output step.

It is worth seeing what that weighting is. It is a soft alignment, learned by gradient descent, computed fresh at every output position.

Which is to say attention is IBM Model 1’s hidden variable, arrived at from the other end. The statistical models estimated alignment with EM and used it to build a table. The neural model learns it as a by-product of translating, and never writes it down.

Where it went

The transformer removed the recurrence and kept the attention, and translation was its first task .

One later result is worth naming because it is not obvious.

Train a single multilingual model on many language pairs, with a token saying which target language is wanted. It can then translate between pairs it never saw during training.

That is zero-shot translation. It only makes sense if the model has built something like a shared representation across languages, which nobody asked it to do.

What translation shows about the rest

Translation is the book in one task.

Counting words gives you a translation model. Adding a hidden variable gives you alignment. Adding phrases gives you local context. Replacing tables with vectors gives you generalisation. Adding attention removes the bottleneck. Removing the recurrence gives you the transformer.

Each step in that list is a chapter of this book, and each was taken because the previous step had a named limitation.

The evaluation story runs alongside it. BLEU, in Chapter 21, was invented for translation and carries its assumptions: a reference translation exists, and overlap with it is a proxy for quality. Chapter 21 showed exactly where that proxy fails, using a paraphrase.

Further reading.

is the IBM models paper and the mathematics is more readable than its reputation suggests. introduced sequence to sequence learning and added attention to it. is the transformer, whose experiments are translation experiments. cover the whole arc with more attention to the statistical models.