Statistical Phrase-Based Translation

2.2 Decoder

1. How does the phrase-based beam-search decoder build translations?
   Left to right as partial hypotheses: starting from the empty hypothesis, pick a sequence of untranslated foreign words and an English translation for them, append it to the output, mark the foreign words as covered and update the cost. The best complete hypothesis covering all foreign words is the output.
   • Koehn et al., 2003, Statistical Phrase-Based Translation (Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of ACL (HLT-NAACL 2003)), §2.2, p. 49
2. How are hypotheses organized and pruned in the phrase-based decoder?
   Stack \(m\) holds hypotheses with \(m\) foreign words translated; equivalent hypotheses are recombined. Stack size is still exponential, so each stack keeps only a beam of the best \(n\) hypotheses, ranked by cost so far plus a future cost estimate. Imperfect estimates cause search errors.
   • Koehn et al., 2003, Statistical Phrase-Based Translation (Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of ACL (HLT-NAACL 2003)), §2.2, p. 49
3. Why does the decoder need a future cost estimate, and how is it computed?
   Without it, hypotheses that have translated the easy words first look cheaper than ones that have tackled hard words. For each translation option, multiply its phrase probability by an LM estimate of the English phrase (unigram for the first word, bigram, then trigram); dynamic programming gives the cheapest cost for each of the \(n(n+1)/2\) spans of consecutive foreign words. Distortion is ignored. Gaps multiply their spans’ costs.
   • Koehn et al., 2003, Statistical Phrase-Based Translation (Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of ACL (HLT-NAACL 2003)), §2.2, p. 49
4. What is the time complexity of the phrase-based beam search, and what beam size sufficed?
   Translation options are linear in sentence length, so the search is quadratic in sentence length and linear in beam size. A beam of 100 was enough; larger beams changed few translations.
   • Koehn et al., 2003, Statistical Phrase-Based Translation (Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of ACL (HLT-NAACL 2003)), §2.2, p. 49