A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit

A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit Yin-Wen Chang Google Research, New York yinwen@google.com Michael Collins∗ Google Research, New York mjcollins@google.com Abstract Decoding of phrase-based translation mod- els in the general case is known to be NP- complete, by a reduction from the traveling salesman problem (Knight, 1999). In practice, phrase-based systems often impose a hard distortion limit that limits the movement of phrases during translation. However, the im- pact on complexity after imposing such a con- straint is not well studied. In this paper, we describe a dynamic programming algorithm for phrase-based decoding with a fixed dis- tortion limit. The runtime of the algorithm is O(nd!lhd+1) where n is the sentence length, d is the distortion limit, l is a bound on the number of phrases starting at any position in the sentence, and h is related to the maximum number of target language translations for any source word. The algorithm makes use of a novel representation that gives a new perspec- tive on decoding of phrase-based models. 1 Introduction Phrase-based translation models (Koehn et al., 2003; Och and Ney, 2004) are widely used in statisti- cal machine translation. The decoding problem for phrase-based translation models is known to be dif- ficult: the results from Knight (1999) imply that in the general case decoding of phrase-based transla- tion models is NP-complete. The complexity of phrase-based decoding comes from reordering of phrases. In practice, however, various constraints on reordering are often imposed in phrase-based translation systems. A common constraint is a “distortion limit”, which places a hard constraint on how far phrases can move. The com- plexity of decoding with such a distortion limit is an open question: the NP-hardness result from Knight ∗On leave from Columbia University. (1999) applies to a phrase-based model with no dis- tortion limit. This paper describes an algorithm for phrase- based decoding with a fixed distortion limit whose runtime is linear in the length of the sentence, and for a fixed distortion limit is polynomial in other fac- tors. More specifically, for a hard distortion limit d, and sentence length n, the runtime is O(nd!lhd+1), where l is a bound on the number of phrases start- ing at any point in the sentence, and h is related to the maximum number of translations for any word in the source language sentence. The algorithm builds on the insight that de- coding with a hard distortion limit is related to the bandwidth-limited traveling salesman problem (BTSP) (Lawler et al., 1985). The algorithm is eas- ily amenable to beam search. It is quite different from previous methods for decoding of phrase-based models, potentially opening up a very different way of thinking about decoding algorithms for phrase- based models, or more generally for models in sta- tistical NLP that involve reordering. 2 Related Work Knight (1999) proves that decoding of word-to-word translation models is NP-complete, assuming that there is no hard limit on distortion, through a reduc- tion from the traveling salesman …

Content truncated to 500 words