Publications
Authors:
  • Mikhail Zaslavski , Marc Dymetman , Nicola Cancedda
Citation:
ACL-IJCNLP 2009 (Association for Computational Linguistics and International Joint Conference on Natural Language Processing), Suntec, Singapore, 2-7 August 2009
Abstract:
An efficient decoding algorithm is a crucial element of any statistical machine
translation system. Some researchers have noted certain similarities between SMT decoding and the famous Traveling Salesman Problem, in particular (Knight, 1999) has shown that any TSP instance may be mapped to a sub-case of a word-based SMT model, demonstrating NP-hardness of the decoding task. In this paper, we focus 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 powerful existing TSP solvers for SMT decoding. We test our approach on three datasets, where TSP-based decoders are compared to the popular beam-search algorithm. In all cases, our method provides
competitive or better performance.
Year:
2009
Report number:
2009/017