Efficient Multi-Pass Decoding for Synchronous Context Free Grammars

Proceedings of ACL-08: HLT, pages 209–217, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Efficient Multi-pass Decoding for Synchronous Context Free Grammars Hao Zhang and Daniel Gildea Computer Science Department University of Rochester Rochester, NY 14627 Abstract We take a multi-pass approach to ma- chine translation decoding when using syn- chronous context-free grammars as the trans- lation model and n-gram language models: the first pass uses a bigram language model, and the resulting parse forest is used in the second pass to guide search with a trigram lan- guage model. The trigram pass closes most of the performance gap between a bigram de- coder and a much slower trigram decoder, but takes time that is insignificant in comparison to the bigram pass. An additional fast de- coding pass maximizing the expected count of correct translation hypotheses increases the BLEU score significantly. 1 Introduction Statistical machine translation systems based on synchronous grammars have recently shown great promise, but one stumbling block to their widespread adoption is that the decoding, or search, problem during translation is more computationally demanding than in phrase-based systems. This com- plexity arises from the interaction of the tree-based translation model with an n-gram language model. Use of longer n-grams improves translation results, but exacerbates this interaction. In this paper, we present three techniques for attacking this problem in order to obtain fast, high-quality decoders. First, we present a two-pass decoding algorithm, in which the first pass explores states resulting from an integrated bigram language model, and the sec- ond pass expands these states into trigram-based states. The general bigram-to-trigram technique is common in speech recognition (Murveit et al., 1993), where lattices from a bigram-based decoder are re-scored with a trigram language model. We ex- amine the question of whether, given the reordering inherent in the machine translation problem, lower order n-grams will provide as valuable a search heuristic as they do for speech recognition. Second, we explore heuristics for agenda-based search, and present a heuristic for our second pass that combines precomputed language model infor- mation with information derived from the first pass. With this heuristic, we achieve the same BLEU scores and model cost as a trigram decoder with es- sentially the same speed as a bigram decoder. Third, given the significant speedup in the agenda-based trigram decoding pass, we can rescore the trigram forest to maximize the expected count of correct synchronous constituents of the model, us- ing the product of inside and outside probabilities. Maximizing the expected count of synchronous con- stituents approximately maximizes BLEU. We find a significant increase in BLEU in the experiments, with minimal additional time. 2 Language Model Integrated Decoding for SCFG We begin by introducing Synchronous Context Free Grammars and their decoding algorithms when an n-gram language model is integrated into the gram- matical search space. A synchronous CFG (SCFG) is a set of context- free rewriting rules for recursively generating string pairs. Each synchronous rule is a pair of CFG rules 209 with the nonterminals on …

Content truncated to 500 words