Optimal Beam Search for Machine Translation

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 210–221, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Optimal Beam Search for Machine Translation Alexander M. Rush Yin-Wen Chang MIT CSAIL, Cambridge, MA 02139, USA {srush, yinwen}@csail.mit.edu Michael Collins Department of Computer Science, Columbia University, New York, NY 10027, USA mcollins@cs.columbia.edu Abstract Beam search is a fast and empirically effective method for translation decoding, but it lacks formal guarantees about search error. We de- velop a new decoding algorithm that combines the speed of beam search with the optimal cer- tificate property of Lagrangian relaxation, and apply it to phrase- and syntax-based transla- tion decoding. The new method is efficient, utilizes standard MT algorithms, and returns an exact solution on the majority of transla- tion examples in our test data. The algorithm is 3.5 times faster than an optimized incremen- tal constraint-based decoder for phrase-based translation and 4 times faster for syntax-based translation. 1 Introduction Beam search (Koehn et al., 2003) and cube prun- ing (Chiang, 2007) have become the de facto decod- ing algorithms for phrase- and syntax-based trans- lation. The algorithms are central to large-scale machine translation systems due to their efficiency and tendency to produce high-quality translations (Koehn, 2004; Koehn et al., 2007; Dyer et al., 2010). However despite practical effectiveness, neither al- gorithm provides any bound on possible decoding error. In this work we present a variant of beam search decoding for phrase- and syntax-based translation. The motivation is to exploit the effectiveness and ef- ficiency of beam search, but still maintain formal guarantees. The algorithm has the following bene- fits: • In theory, it can provide a certificate of optimal- ity; in practice, we show that it produces opti- mal hypotheses, with certificates of optimality, on the vast majority of examples. • It utilizes well-studied algorithms and extends off-the-shelf beam search decoders. • Empirically it is very fast, results show that it is 3.5 times faster than an optimized incremental constraint-based solver. While our focus is on fast decoding for machine translation, the algorithm we present can be applied to a variety of dynamic programming-based decod- ing problems. The method only relies on having a constrained beam search algorithm and a fast uncon- strained search algorithm. Similar algorithms exist for many NLP tasks. We begin in Section 2 by describing constrained hypergraph search and showing how it generalizes translation decoding. Section 3 introduces a variant of beam search that is, in theory, able to produce a certificate of optimality. Section 4 shows how to improve the effectiveness of beam search by using weights derived from Lagrangian relaxation. Sec- tion 5 puts everything together to derive a fast beam search algorithm that is often optimal in practice. Experiments compare the new algorithm with several variants of beam search, cube pruning, A∗ search, and relaxation-based decoders on two trans- lation tasks. The optimal beam search algorithm is able to find exact solutions with certificates of opti- mality on 99% of …

Content truncated to 500 words