Fast Decoding and Optimal Decoding for Machine Translation

Fast Decoding and Optimal Decoding for Machine Translation Ulrich Germann � , Michael Jahr � , Kevin Knight � , Daniel Marcu � , and Kenji Yamada � � Information Sciences Institute � Department of Computer Science University of Southern California Stanford University 4676 Admiralty Way, Suite 1001 Stanford, CA 94305 Marina del Rey, CA 90292 jahr@cs.stanford.edu � germann,knight,marcu,kyamada � @isi.edu Abstract A good decoding algorithm is critical to the success of any statistical machine translation system. The decoder’s job is to find the translation that is most likely according to set of previously learned parameters (and a formula for combin- ing them). Since the space of possi- ble translations is extremely large, typ- ical decoding algorithms are only able to examine a portion of it, thus risk- ing to miss good solutions. In this pa- per, we compare the speed and out- put quality of a traditional stack-based decoding algorithm with two new de- coders: a fast greedy decoder and a slow but optimal decoder that treats de- coding as an integer-programming opti- mization problem. 1 Introduction A statistical MT system that translates (say) French sentences into English, is divided into three parts: (1) a language model (LM) that as- signs a probability P(e) to any English string, (2) a translation model (TM) that assigns a probability P(f � e) to any pair of English and French strings, and (3) a decoder. ously unseen sentenceThe decoder takes a previ- � and tries to find the � that maximizes P(e � f), or equivalently maximizes P(e) � P(f � e). Brown et al. (1993) introduced a series of TMs based on word-for-word substitution and re- ordering, but did not include a decoding algo- rithm. If the source and target languages are con- strained to have the same word order (by choice or through suitable pre-processing), then the lin- ear Viterbi algorithm can be applied (Tillmann et al., 1997). If re-ordering is limited to rotations around nodes in a binary tree, then optimal decod- ing can be carried out by a high-polynomial algo- rithm (Wu, 1996). For arbitrary word-reordering, the decoding problem is NP-complete (Knight, 1999). A sensible strategy (Brown et al., 1995; Wang and Waibel, 1997) is to examine a large subset of likely decodings and choose just from that. Of course, it is possible to miss a good translation this way. If the decoder returns e � but there exists some e for which P(e � f) � P(e � � f), this is called a search error. As Wang and Waibel (1997) re- mark, it is hard to know whether a search error has occurred—the only way to show that a decod- ing is sub-optimal is to actually produce a higher- scoring one. Thus, while decoding is a clear-cut optimiza- tion task in which every problem instance has a right answer, it is hard to come up with good answers quickly. This paper reports on mea- surements of speed, search errors, and translation quality in the context of …

Content truncated to 500 words