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

ACL ID D13-1110
Title Efficient Left-to-Right Hierarchical Phrase-Based Translation with Improved Reordering
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2013
Authors

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 toO(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 f...