Paper: Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem

ACL ID P09-1038
Title Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2009
Authors

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 alg...