Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 72–82, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation Alexander M. Rush MIT CSAIL, Cambridge, MA 02139, USA srush@csail.mit.edu Michael Collins Department of Computer Science, Columbia University, New York, NY 10027, USA mcollins@cs.columbia.edu Abstract We describe an exact decoding algorithm for syntax-based statistical translation. The ap- proach uses Lagrangian relaxation to decom- pose the decoding problem into tractable sub- problems, thereby avoiding exhaustive dy- namic programming. The method recovers ex- act solutions, with certificates of optimality, on over 97% of test examples; it has compa- rable speed to state-of-the-art decoders. 1 Introduction Recent work has seen widespread use of syn- chronous probabilistic grammars in statistical ma- chine translation (SMT). The decoding problem for a broad range of these systems (e.g., (Chiang, 2005; Marcu et al., 2006; Shen et al., 2008)) corresponds to the intersection of a (weighted) hypergraph with an n-gram language model.1 The hypergraph rep- resents a large set of possible translations, and is created by applying a synchronous grammar to the source language string. The language model is then used to rescore the translations in the hypergraph. Decoding with these models is challenging, largely because of the cost of integrating an n-gram language model into the search process. Exact dy- namic programming algorithms for the problem are well known (Bar-Hillel et al., 1964), but are too ex- pensive to be used in practice.2 Previous work on decoding for syntax-based SMT has therefore been focused primarily on approximate search methods. This paper describes an efficient algorithm for ex- act decoding of synchronous grammar models for translation. We avoid the construction of (Bar-Hillel 1This problem is also relevant to other areas of statistical NLP, for example NL generation (Langkilde, 2000). 2E.g., with a trigram language model they run in O(|E|w6) time, where |E| is the number of edges in the hypergraph, and w is the number of distinct lexical items in the hypergraph. et al., 1964) by using Lagrangian relaxation to de- compose the decoding problem into the following sub-problems: 1. Dynamic programming over the weighted hy- pergraph. This step does not require language model integration, and hence is highly efficient. 2. Application of an all-pairs shortest path al- gorithm to a directed graph derived from the weighted hypergraph. The size of the derived directed graph is linear in the size of the hyper- graph, hence this step is again efficient. Informally, the first decoding algorithm incorporates the weights and hard constraints on translations from the synchronous grammar, while the second decod- ing algorithm is used to integrate language model scores. Lagrange multipliers are used to enforce agreement between the structures produced by the two decoding algorithms. In this paper we first give background on hyper- graphs and the decoding problem. We then describe our decoding algorithm. The algorithm uses a sub- gradient method to minimize a dual function. The dual corresponds to a particular linear …

Content truncated to 500 words