Forest Rescoring: Faster Decoding with Integrated Language Models

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 144–151, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Forest Rescoring: Faster Decoding with Integrated Language Models ∗ Liang Huang University of Pennsylvania Philadelphia, PA 19104 lhuang3@cis.upenn.edu David Chiang USC Information Sciences Institute Marina del Rey, CA 90292 chiang@isi.edu Abstract Efficient decoding has been a fundamental problem in machine translation, especially with an integrated language model which is essential for achieving good translation quality. We develop faster approaches for this problem based on k-best parsing algo- rithms and demonstrate their effectiveness on both phrase-based and syntax-based MT systems. In both cases, our methods achieve significant speed improvements, often by more than a factor of ten, over the conven- tional beam-search method at the same lev- els of search error and translation accuracy. 1 Introduction Recent efforts in statistical machine translation (MT) have seen promising improvements in out- put quality, especially the phrase-based models (Och and Ney, 2004) and syntax-based models (Chiang, 2005; Galley et al., 2006). However, efficient de- coding under these paradigms, especially with inte- grated language models (LMs), remains a difficult problem. Part of the complexity arises from the ex- pressive power of the translation model: for exam- ple, a phrase- or word-based model with full reorder- ing has exponential complexity (Knight, 1999). The language model also, if fully integrated into the de- coder, introduces an expensive overhead for main- taining target-language boundary words for dynamic ∗ The authors would like to thank Dan Gildea, Jonathan Graehl, Mark Johnson, Kevin Knight, Daniel Marcu, Bob Moore and Hao Zhang. L. H. was partially supported by NSF ITR grants IIS-0428020 while visiting USC/ISI and EIA- 0205456 at UPenn. D. C. was partially supported under the GALE/DARPA program, contract HR0011-06-C-0022. programming (Wu, 1996; Och and Ney, 2004). In practice, one must prune the search space aggres- sively to reduce it to a reasonable size. A much simpler alternative method to incorporate the LM is rescoring: we first decode without the LM (henceforth −LM decoding) to produce a k-best list of candidate translations, and then rerank the k-best list using the LM. This method runs much faster in practice but often produces a considerable number of search errors since the true best translation (taking LM into account) is often outside of the k-best list. Cube pruning (Chiang, 2007) is a compromise be- tween rescoring and full-integration: it rescores k subtranslations at each node of the forest, rather than only at the root node as in pure rescoring. By adapt- ing the k-best parsing Algorithm 2 of Huang and Chiang (2005), it achieves significant speed-up over full-integration on Chiang’s Hiero system. We push the idea behind this method further and make the following contributions in this paper: • We generalize cube pruning and adapt it to two systems very different from Hiero: a phrase- based system similar to Pharaoh (Koehn, 2004) and a tree-to-string system (Huang et al., 2006). • We also devise a faster variant of cube …

Content truncated to 500 words