Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation

Proceedings of NAACL-HLT 2018, pages 1314–1324 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation Matt Post and David Vilar Amazon Research Berlin, Germany Abstract The end-to-end nature of neural machine translation (NMT) removes many ways of manually guiding the translation process that were available in older paradigms. Recent work, however, has introduced a new capa- bility: lexically constrained or guided de- coding, a modification to beam search that forces the inclusion of pre-specified words and phrases in the output. However, while theoret- ically sound, existing approaches have com- putational complexities that are either linear (Hokamp and Liu, 2017) or exponential (An- derson et al., 2017) in the number of con- straints. We present an algorithm for lexi- cally constrained decoding with a complex- ity of O(1) in the number of constraints. We demonstrate the algorithm’s remarkable abil- ity to properly place these constraints, and use it to explore the shaky relationship between model and BLEU scores. Our implementation is available as part of SOCKEYE. 1 Introduction One appeal of the phrase-based statistical ap- proach to machine translation (Koehn et al., 2003) was that it provided control over system output. For example, it was relatively easy to incorporate domain-specific dictionaries, or to force a transla- tion choice for certain words. These kinds of in- terventions were useful in a range of settings, in- cluding interactive machine translation or domain adaptation. In the new paradigm of neural ma- chine translation (NMT), these kinds of manual interventions are much more difficult, and a lot of time has been spent investigating how to restore them (cf. Arthur et al. (2016)). At the same time, NMT has also provided new capabilities. One interesting recent innovation is lexically constrained decoding, a modification to beam search that allows the user to specify words No one has the intention of building a wall. “errichten” Niemand hat die Absicht, eine Mauer zu bauen. “No one has the intention, a wall to build.” Niemand hat die Absicht, eine Mauer zu errichten. “No one has the intention, a wall to construct.” “Keiner” “Keiner” "errichten” Keiner hat die Absicht, eine Mauer zu bauen. “No one has the intention, a wall to build.” Keiner hat die Absicht, eine Mauer zu errichten. “No one has the intention, a wall to construct.” Figure 1: An example translating from English to Ger- man. The first translation is unconstrained, whereas the remaining ones have one or two constraints im- posed. A word-for-word translation of the German output has been provided for the convenience of non- German speaking readers. and phrases that must appear in the system output (Figure 1). Two algorithms have been proposed for this: grid beam search (Hokamp and Liu, 2017, GBS) and constrained beam search (Ander- son et al., 2017, CBS). These papers showed that these algorithms do a good job automatically plac- ing constraints and improving results in tasks such as simulated post-editing, domain adaptation, and …

Content truncated to 500 words