Exact Decoding for Phrase-Based Statistical Machine Translation

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1237–1249, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Exact Decoding for Phrase-Based Statistical Machine Translation Wilker Aziz† Marc Dymetman‡ Lucia Specia† †Department of Computer Science, University of Sheffield, UK W.Aziz@sheffield.ac.uk L.Specia@sheffield.ac.uk ‡Xerox Research Centre Europe, Grenoble, France Marc.Dymetman@xrce.xerox.com Abstract The combinatorial space of translation derivations in phrase-based statistical ma- chine translation is given by the intersec- tion between a translation lattice and a tar- get language model. We replace this in- tractable intersection by a tractable relax- ation which incorporates a low-order up- perbound on the language model. Exact optimisation is achieved through a coarse- to-fine strategy with connections to adap- tive rejection sampling. We perform ex- act optimisation with unpruned language models of order 3 to 5 and show search- error curves for beam search and cube pruning on standard test sets. This is the first work to tractably tackle exact opti- misation with language models of orders higher than 3. 1 Introduction In Statistical Machine Translation (SMT), the task of producing a translation for an input string x = ⟨x1, x2, . . . , xI⟩ is typically associated with find- ing the best derivation d∗ compatible with the in- put under a linear model. In this view, a derivation is a structured output that represents a sequence of steps that covers the input producing a translation. Equation 1 illustrates this decoding process. d∗ = argmax d∈D(x) f(d) (1) The set D(x) is the space of all derivations com- patible with x and supported by a model of trans- lational equivalences (Lopez, 2008). The func- tion f(d) = Λ · H(d) is a linear parameteri- sation of the model (Och, 2003). It assigns a real-valued score (or weight) to every derivation d ∈ D(x), where Λ ∈ Rm assigns a relative importance to different aspects of the derivation independently captured by m feature functions H(d) = ⟨H1(d), . . . , Hm(d)⟩ ∈ Rm. The fully parameterised model can be seen as a discrete weighted set such that feature func- tions factorise over the steps in a derivation. That is, Hk(d) = � e∈d hk(e), where hk is a (local) feature function that assesses steps independently and d = ⟨e1, e2, . . . , el⟩ is a sequence of l steps. Under this assumption, each step is assigned the weight w(e) = Λ·⟨h1(e), h2(e), . . . , hm(e)⟩. The set D is typically finite, however, it contains a very large number of structures — exponential (or even factorial, see §2) with the size of x — making exhaustive enumeration prohibitively slow. Only in very restricted cases combinatorial optimisation techniques are directly applicable (Tillmann et al., 1997; Och et al., 2001), thus it is common to resort to heuristic techniques in order to find an approxi- mation to d∗ (Koehn et al., 2003; Chiang, 2007). Evaluation exercises indicate that approximate search algorithms work well in practice (Bojar et al., 2013). …

Content truncated to 500 words