Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 333–341, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem Mikhail Zaslavskiy∗ Marc Dymetman Nicola Cancedda Mines ParisTech, Institut Curie Xerox Research Centre Europe 77305 Fontainebleau, France 38240 Meylan, France mikhail.zaslavskiy@ensmp.fr {marc.dymetman,nicola.cancedda}@xrce.xerox.com Abstract An efficient decoding algorithm is a cru- cial element of any statistical machine translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Sales- man Problem; in particular (Knight, 1999) has shown that any TSP instance can be mapped to a sub-case of a word-based SMT model, demonstrating NP-hardness of the decoding task. In this paper, we fo- cus on the reverse mapping, showing that any phrase-based SMT decoding problem can be directly reformulated as a TSP. The transformation is very natural, deepens our understanding of the decoding problem, and allows direct use of any of the pow- erful existing TSP solvers for SMT de- coding. We test our approach on three datasets, and compare a TSP-based de- coder to the popular beam-search algo- rithm. In all cases, our method provides competitive or better performance. 1 Introduction Phrase-based systems (Koehn et al., 2003) are probably the most widespread class of Statistical Machine Translation systems, and arguably one of the most successful. They use aligned sequences of words, called biphrases, as building blocks for translations, and score alternative candidate trans- lations for the same source sentence based on a log-linear model of the conditional probability of target sentences given the source sentence: p(T, a|S) = 1 ZS exp � k λkhk(S, a, T) (1) where the hk are features, that is, functions of the source string S, of the target string T, and of the ∗ This work was conducted during an internship at XRCE. alignment a, where the alignment is a representa- tion of the sequence of biphrases that where used in order to build T from S; The λk’s are weights and ZS is a normalization factor that guarantees that p is a proper conditional probability distri- bution over the pairs (T, A). Some features are local, i.e. decompose over biphrases and can be precomputed and stored in advance. These typ- ically include forward and reverse phrase condi- tional probability features log p(˜t|˜s) as well as log p(˜s|˜t), where ˜s is the source side of the biphrase and ˜t the target side, and the so-called “phrase penalty” and “word penalty” features, which count the number of phrases and words in the alignment. Other features are non-local, i.e. depend on the order in which biphrases appear in the alignment. Typical non-local features include one or more n-gram language models as well as a distortion feature, measuring by how much the order of biphrases in the candidate translation de- viates from their order in the source sentence. Given such a model, where the λi’s have been tuned on a development set in order to minimize some error …

Content truncated to 500 words