Undirected Machine Translation with Discriminative Reinforcement Learning

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 10–19, Gothenburg, Sweden, April 26-30 2014. c⃝2014 Association for Computational Linguistics Undirected Machine Translation with Discriminative Reinforcement Learning Andrea Gesmundo Google Inc. andrea.gesmundo@gmail.com James Henderson Xerox Research Centre Europe james.henderson@xrce.xerox.com Abstract We present a novel Undirected Machine Translation model of Hierarchical MT that is not constrained to the standard bottom- up inference order. Removing the order- ing constraint makes it possible to condi- tion on top-down structure and surround- ing context. This allows the introduc- tion of a new class of contextual features that are not constrained to condition only on the bottom-up context. The model builds translation-derivations efficiently in a greedy fashion. It is trained to learn to choose jointly the best action and the best inference order. Experiments show that the decoding time is halved and forest- rescoring is 6 times faster, while reaching accuracy not significantly different from state of the art. 1 Introduction Machine Translation (MT) can be addressed as a structured prediction task (Brown et al., 1993; Ya- mada and Knight, 2001; Koehn et al., 2003). MT’s goal is to learn a mapping function, f, from an in- put sentence, x, into y = (t, h), where t is the sentence translated into the target language, and h is the hidden correspondence structure (Liang et al., 2006). In Hierarchical MT (HMT) (Chi- ang, 2005) the hidden correspondence structure is the synchronous-tree composed by instantiations of synchronous rules from the input grammar, G. Statistical models usually define f as: f(x) = arg maxy∈Y Score(x, y), where Score(x, y) is a function whose parameters can be learned with a specialized learning algorithm. In MT applica- tions, it is not possible to enumerate all y ∈ Y. HMT decoding applies pruning (e.g. Cube Prun- ing (Huang and Chiang, 2005)), but even then HMT has higher complexity than Phrase Based MT (PbMT) (Koehn et al., 2003). On the other hand, HMT improves over PbMT by introducing the possibility of exploiting a more sophisticated reordering model not bounded by a window size, and producing translations with higher syntactic- semantic quality. In this paper, we present the Undirected Machine Translation (UMT) frame- work, which retains the advantages of HMT and allows the use of a greedy decoder whose com- plexity is lower than standard quadratic beam- search PbMT. UMT’s fast decoding is made possible through even stronger pruning: the decoder chooses a sin- gle action at each step, never retracts that action, and prunes all incompatible alternatives to that ac- tion. If this extreme level of pruning was ap- plied to the CKY-like beam-decoding used in stan- dard HMT, translation quality would be severely degraded. This is because the bottom-up infer- ence order imposed by CKY-like beam-decoding means that all pruning decisions must be based on a bottom-up approximation of contextual features, which leads to search errors that affect the qual- ity of reordering and lexical-choice (Gesmundo and Henderson, 2011). UMT solves this problem by …

Content truncated to 500 words