Two Improvements to Left-to-Right Decoding for Hierarchical Phrase-based Machine Translation

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 221–226, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Two Improvements to Left-to-Right Decoding for Hierarchical Phrase-based Machine Translation Maryam Siahbani and Anoop Sarkar School of Computing Science Simon Fraser University Burnaby BC. Canada msiahban,anoop@cs.sfu.ca Abstract Left-to-right (LR) decoding (Watanabe et al., 2006) is promising decoding algorithm for hierarchical phrase-based translation (Hiero) that visits input spans in arbitrary order producing the output translation in left to right order. This leads to far fewer language model calls, but while LR decod- ing is more efficient than CKY decoding, it is unable to capture some hierarchical phrase alignments reachable using CKY decoding and suffers from lower transla- tion quality as a result. This paper in- troduces two improvements to LR decod- ing that make it comparable in translation quality to CKY-based Hiero. 1 Introduction Hierarchical phrase-based translation (Hi- ero) (Chiang, 2007) uses a lexicalized syn- chronous context-free grammar (SCFG) extracted from word and phrase alignments of a bitext. De- coding for Hiero is typically done with CKY-style decoding with time complexity O(n3) for source input with n words. Computing the language model score for each hypothesis within CKY de- coding requires two histories, the left and the right edge of each span, due to the fact that the target side is built inside-out from sub-spans (Heafield et al., 2011; Heafield et al., 2013). LR-decoding algorithms exist for phrase- based (Koehn, 2004; Galley and Manning, 2010) and syntax-based (Huang and Mi, 2010; Feng et al., 2012) models and also for hierarchical phrase- based models (Watanabe et al., 2006; Siahbani et al., 2013), which is our focus in this paper. Watanabe et al. (2006) first proposed left-to- right (LR) decoding for Hiero (LR-Hiero hence- forth) which uses beam search and runs in O(n2b) in practice where n is the length of source sentence and b is the size of beam (Huang and Mi, 2010). To simplify target generation, SCFG rules are con- strained to be prefix-lexicalized on target side aka Griebach Normal Form (GNF). Throughout this paper we abuse the notation for simplicity and use the term GNF grammars for such SCFGs. This constraint drastically reduces the size of gram- mar for LR-Hiero in comparison to Hiero gram- mar (Siahbani et al., 2013). However, the orig- inal LR-Hiero decoding algorithm does not per- form well in comparison to current state-of-the-art Hiero and phrase-based translation systems. Siah- bani et al. (2013) propose an augmented version of LR decoding to address some limitations in the original LR-Hiero algorithm in terms of transla- tion quality and time efficiency. Although, LR-Hiero performs much faster than Hiero in decoding and obtains BLEU scores com- parable to phrase-based translation system on some language pairs, there is still a notable gap be- tween CKY-Hiero and LR-Hiero (Siahbani et al., 2013). We show in this paper using instructive ex- amples that CKY-Hiero can capture some complex phrasal re-orderings that are observed in language pairs such as …

Content truncated to 500 words