Source-Side Left-to-Right or Target-Side Left-to-Right? An Empirical Comparison of Two Phrase-Based Decoding Algorithms

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1495–1499 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Source-Side Left-to-Right or Target-Side Left-to-Right? An Empirical Comparison of Two Phrase-Based Decoding Algorithms Yin-Wen Chang Google Research, New York yinwen@google.com Michael Collins∗ Google Research, New York mjcollins@google.com Abstract This paper describes an empirical study of the phrase-based decoding algorithm pro- posed by Chang and Collins (2017). The algorithm produces a translation by pro- cessing the source-language sentence in strictly left-to-right order, differing from commonly used approaches that build the target-language sentence in left-to-right order. Our results show that the new al- gorithm is competitive with Moses (Koehn et al., 2007) in terms of both speed and BLEU scores. 1 Introduction Phrase-based models (Koehn et al., 2003; Och and Ney, 2004) have until recently been a state- of-the-art method for statistical machine transla- tion, and Moses (Koehn et al., 2007) is one of the most used phrase-based translation systems. Moses uses a beam search decoder based on a dy- namic programming algorithm that constructs the target-language sentence from left to right (Koehn et al., 2003). Neural machine translation systems (Kalchbrenner and Blunsom, 2013; Cho et al., 2014; Sutskever et al., 2014), which have given impressive improvements over phrase-based sys- tems, also typically use models and decoders that construct the target-language string in strictly left- to-right order. Recently, Chang and Collins (2017) proposed a phrase-based decoding algorithm that processes the source-language string in strictly left-to-right order. Reordering is implemented by maintaining multiple sub-strings in the target-language, with phrases being used to extend these sub-strings by various operations (see Section 2 for a full descrip- tion). With a fixed distortion limit on reordering, ∗On leave from Columbia University. the time complexity of the algorithm is linear in terms of sentence length, and is polynomial time in other factors. Chang and Collins (2017) present the algorithm and give a proof of its time complexity, but do not describe experiments, leaving an open question of whether the algorithm is useful in practice. This paper complements the original paper by studying the algorithm empirically. In addition to an exact dynamic programming implementation, we study the use of beam search with the algorithm, and an- other pruning method that restricts the maximum number of target-language strings maintained at any point. The experiments show that the algo- rithm is competitive with Moses in terms of both speed and translation quality (BLEU score). The new decoding algorithm is of interest for a few reasons. While the experiments in this pa- per are with phrase-based translation systems, the method could potentially be extended to neural translation, for example with an attention-based model that is in some sense monotonic (left-to- right). The decoder may be relevant to work on si- multaneous translation (He et al., 2016). The ideas may be applicable to string-to-string transduction problems other than machine translation. 2 A Sketch of the Decoding Algorithm of Chang and Collins (2017) This section gives a sketch of …

Content truncated to 500 words