Greedy Decoding for Statistical Machine Translation in Almost Linear Time

Greedy Decoding for Statistical Machine Translation in Almost Linear Time Ulrich Germann USC Information Sciences Institute Marina del Rey, CA germann@isi.edu Abstract We present improvements to a greedy decod- ing algorithm for statistical machine translation that reduce its time complexity from at least cubic ( ����� when applied na¨ıvely) to prac- tically linear time1 without sacrificing trans- lation quality. We achieve this by integrat- ing hypothesis evaluation into hypothesis cre- ation, tiling improvements over the translation hypothesis at the end of each search iteration, and by imposing restrictions on the amount of word reordering during decoding. 1 Introduction Most of the current work in statistical machine translation builds on word replacement models developed at IBM in the early 1990s (Brown et al., 1990, 1993; Berger et al., 1994, 1996). Based on the conventions established in Brown et al. (1993), these models are commonly referred to as the (IBM) Models 1-5. One of the big challenges in building actual MT sys- tems within this framework is that of decoding: finding the translation candidate � that maximizes the translation probability � � � for the given input . Knight (1999) has shown the problem to be NP-complete. Due to the complexity of the task, practical MT sys- tems usually do not employ optimal decoders (that is, decoders that are guaranteed to find an optimal solution within the constraints of the framework), but rely on ap- proximative algorithms instead. Empirical evidence sug- gests that such algorithms can perform resonably well. For example, Berger et al. (1994), attribute only 5% of the translation errors of their Candide system, which uses 1Technically, the complexity is still  . However, the quadratic component has such a small coefficient that it does not have any noticable effect on the translation speed for all reasonable inputs. a restricted stack search, to search errors. Using the same evaluation metric (but different evaluation data), Wang and Waibel (1997) report search error rates of 7.9% and 9.3%, respectively, for their decoders. Och et al. (2001) and Germann et al. (2001) both im- plemented optimal decoders and benchmarked approxi- mative algorithms against them. Och et al. report word error rates of 68.68% for optimal search (based on a vari- ant of the A* algorithm), and 69.65% for the most re- stricted version of a decoder that combines dynamic pro- gramming with a beam search (Tillmann and Ney, 2000). Germann et al. (2001) compare translations obtained by a multi-stack decoder and a greedy hill-climbing al- gorithm against those produced by an optimal integer programming decoder that treats decoding as a variant of the traveling-salesman problem (cf. Knight, 1999). Their overall performance metric is the sentence error rate (SER). For decoding with IBM Model 3, they report SERs of about 57% (6-word sentences) and 76% (8-word sentences) for optimal decoding, 58% and 75% for stack decoding, and 60% and 75% for greedy decoding, which is the focus of this paper. All these numbers suggest that approximative algo- rithms are a feasible choice for practical …

Content truncated to 500 words