Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 26–37, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation Yin-Wen Chang MIT CSAIL Cambridge, MA 02139, USA yinwen@csail.mit.edu Michael Collins Department of Computer Science, Columbia University, New York, NY 10027, USA mcollins@cs.columbia.edu Abstract This paper describes an algorithm for exact decoding of phrase-based translation models, based on Lagrangian relaxation. The method recovers exact solutions, with certificates of optimality, on over 99% of test examples. The method is much more efficient than ap- proaches based on linear programming (LP) or integer linear programming (ILP) solvers: these methods are not feasible for anything other than short sentences. We compare our method to MOSES (Koehn et al., 2007), and give precise estimates of the number and mag- nitude of search errors that MOSES makes. 1 Introduction Phrase-based models (Och et al., 1999; Koehn et al., 2003; Koehn et al., 2007) are a widely-used approach for statistical machine translation. The decoding problem for phrase-based models is NP- hard1; because of this, previous work has generally focused on approximate search methods, for exam- ple variants of beam search, for decoding. This paper describes an algorithm for exact decoding of phrase-based models, based on La- grangian relaxation (Lemar´echal, 2001). The core of the algorithm is a dynamic program for phrase- based translation which is efficient, but which allows some ill-formed translations. More specifically, the dynamic program searches over the space of transla- tions where exactly N words are translated (N is the number of words in the source-language sen- tence), but where some source-language words may be translated zero times, or some source-language words may be translated more than once. La- grangian relaxation is used to enforce the constraint 1We refer here to the phrase-based models of (Koehn et al., 2003; Koehn et al., 2007), considered in this paper. Other vari- ants of phrase-based models, which allow polynomial time de- coding, have been proposed, see the related work section. that each source-language word should be translated exactly once. A subgradient algorithm is used to op- timize the dual problem arising from the relaxation. The first technical contribution of this paper is the basic Lagrangian relaxation algorithm. By the usual guarantees for Lagrangian relaxation, if this algo- rithm converges to a solution where all constraints are satisfied (i.e., where each word is translated ex- actly once), then the solution is guaranteed to be optimal. For some source-language sentences how- ever, the underlying relaxation is loose, and the algo- rithm will not converge. The second technical con- tribution of this paper is a method that incrementally adds constraints to the underlying dynamic program, thereby tightening the relaxation until an exact solu- tion is recovered. We describe experiments on translation from Ger- man to English, using phrase-based models trained by MOSES (Koehn et al., 2007). The method recovers exact solutions, with certificates of opti- mality, on over 99% of test examples. On over 78% …

Content truncated to 500 words