📄 Fast Decoding and Optimal Decoding for Machine Translation

Summary

Statistical MT needs a decoder that searches for the English string, plus an alignment, that scores highest under a language model and a translation model. Here the translation model is IBM Model 4. With arbitrary word reordering this search is NP-complete, so practical decoders explore only part of the space and may commit search errors that cannot easily be detected. The authors compare three decoders:

• a multistack decoder modeled on the Brown et al. (1995) Model 3 design;
• a new greedy decoder that begins with a word-by-word English gloss and keeps improving it through local edits;
• a new optimal decoder that turns decoding into a traveling-salesman-style integer program and hands it to a generic IP solver.

They test on 505 French sentences of lengths 6 to 20 and measure speed, search optimality and human-judged translation quality. The IP decoder finds provably best answers but is very slow. The greedy decoder is far faster and loses only a little accuracy. Most translation errors come from the models rather than the search. This matters because it shows where effort will pay off: better models, not more exhaustive search.

Key points

• Test set: 505 sentences spread evenly over lengths 6, 8, 10, 15 and 20. Table 1 uses subsets of 101 sentences and a bigram LM. Table 2 uses a trigram LM.

• Speed and search errors with a bigram LM (seconds per sentence):

  Length	IP	Stack	Greedy
  6	47.50 s, 0 search errors	0.79 s, 5 search errors	0.07 s, 18 search errors
  8	499.00 s, 0 search errors	5.67 s, 20 search errors	2.66 s, 43 search errors

  Translation error counts are nearly identical across decoders: 57/58/60 at length 6 and 76/75/75 at length 8.

• Trigram results: the stack decoder needs about 2000 s per sentence at length 15. The speed-tuned greedy variants run at roughly a second or less, are at least ten times faster, and lose only a little accuracy.

• Multistack design: there is one stack per subset of consumed input words, so hypotheses only compete against others covering the same input. Four operations build hypotheses: Add, AddZfert, Extend and AddNull.

• Cost of zero-fertility words: with a 40,000-word vocabulary, AddZfert is 400,000 times costlier than AddNull. The authors prune it by allowing only frequent, likely-infertile words and only insertions that raise the hypothesis score.

Interesting ideas

• I1. Six-way error taxonomy: each output is classified as no error, pure model error, deadly search error, fortuitous search error, harmless search error or compound error. This separates search failures from modeling failures and fits any system that pairs an approximate search with an imperfect scoring model.
• I2. Exact solver as a debugging oracle: a slow exact decoder lets you count the search errors of fast heuristic decoders. The authors also used it to find bugs and to design new greedy operations by reading error logs. The approach transfers to parsers, taggers or any heuristic optimizer.
• I3. Start from a cheap guess and refine: the greedy decoder begins from a crude gloss and applies local edits under a time limit, which makes it an anytime algorithm. This gives a tunable speed/quality knob that is useful in latency-sensitive applications.
• I4. Fair competition between partial hypotheses: shorter hypotheses naturally look more probable, so the decoder keeps a separate stack per coverage set rather than one global queue. This general fix for length bias applies to any beam or best-first search.
• I5. Reformulating decoding as integer programming: casting decoding as a TSP-like integer program gives provable optimality for free. Adding one constraint yields the second-best output, and flipping the objective yields the worst one, which makes the formulation a handy analysis tool.