Efficient Left-to-Right Hierarchical Phrase-Based Translation with Improved Reordering

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1089–1099, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Efficient Left-to-Right Hierarchical Phrase-based Translation with Improved Reordering Maryam Siahbani, Baskaran Sankaran, Anoop Sarkar Simon Fraser University Burnaby BC. CANADA {msiahban,baskaran,anoop}@cs.sfu.ca Abstract Left-to-right (LR) decoding (Watanabe et al., 2006b) is a promising decoding algorithm for hierarchical phrase-based translation (Hiero). It generates the target sentence by extending the hypotheses only on the right edge. LR de- coding has complexity O(n2b) for input of n words and beam size b, compared to O(n3) for the CKY algorithm. It requires a single lan- guage model (LM) history for each target hy- pothesis rather than two LM histories per hy- pothesis as in CKY. In this paper we present an augmented LR decoding algorithm that builds on the original algorithm in (Watanabe et al., 2006b). Unlike that algorithm, using experi- ments over multiple language pairs we show two new results: our LR decoding algorithm provides demonstrably more efficient decod- ing than CKY Hiero, four times faster; and by introducing new distortion and reordering fea- tures for LR decoding, it maintains the same translation quality (as in BLEU scores) ob- tained phrase-based and CKY Hiero with the same translation model. 1 Introduction Hiero (Chiang, 2007) models translation using a lex- icalized synchronous context-free grammar (SCFG) extracted from word aligned bitexts. Typically, CKY-style decoding is used for Hiero with time complexity O(n3) for source input with n words. Scoring the target language output using a lan- guage model within CKY-style decoding requires two histories per hypothesis, one on the left edge of each span and one on the right, due to the fact that the target side is not generated in left to right order, but rather built bottom-up from sub-spans. This leads to complex problems in efficient lan- guage model integration and requires state reduc- tion techniques (Heafield et al., 2011; Heafield et al., 2013). The size of a Hiero SCFG grammar is typically larger than phrase-based models extracted from the same data creating challenges in rule ex- traction and decoding time especially for larger datasets (Sankaran et al., 2012). In contrast, the LR-decoding algorithm could avoid these shortcomings such as faster time com- plexity, reduction in the grammar size and the sim- plified left-to-right language model scoring. means LR decoding has the potential to replaceIt CKY decoding for Hiero. Despite these attractive properties, we show that the original LR-Hiero de- coding proposed by (Watanabe et al., 2006b) does not perform to the same level of the standard CKY Hiero with cube pruning (see Table 3). In addition, the current LR decoding algorithm does not obtain BLEU scores comparable to phrase-based or CKY- based Hiero models for different language pairs (see Table 4). In this paper we propose modifications to the LR decoding algorithm that addresses these limi- tations and provides, for the first time, a true alterna- tive to the standard CKY Hiero algorithm that uses left-to-right decoding. We …

Content truncated to 500 words