Sampling Alignment Structure under a Bayesian Translation Model

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 314–323, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Sampling Alignment Structure under a Bayesian Translation Model John DeNero, Alexandre Bouchard-Cˆot´e and Dan Klein Computer Science Department University of California, Berkeley {denero, bouchard, klein}@cs.berkeley.edu Abstract We describe the first tractable Gibbs sam- pling procedure for estimating phrase pair frequencies under a probabilistic model of phrase alignment. We propose and evalu- ate two nonparametric priors that successfully avoid the degenerate behavior noted in previ- ous work, where overly large phrases mem- orize the training data. Phrase table weights learned under our model yield an increase in BLEU score over the word-alignment based heuristic estimates used regularly in phrase- based translation systems. 1 Introduction In phrase-based translation, statistical knowledge of translation equivalence is primarily captured by counts of how frequently various phrase pairs occur in training bitexts. Since bitexts do not come seg- mented and aligned into phrase pairs, these counts are typically gathered by fixing a word alignment and applying phrase extraction heuristics to this word-aligned training corpus. Alternatively, phrase pair frequencies can be learned via a probabilistic model of phrase alignment, but this approach has presented several practical challenges. In this paper, we address the two most signifi- cant challenges in phrase alignment modeling. The first challenge is with inference: computing align- ment expectations under general phrase models is #P-hard (DeNero and Klein, 2008). Previous phrase alignment work has sacrificed consistency for effi- ciency, employing greedy hill-climbing algorithms and constraining inference with word alignments (Marcu and Wong, 2002; DeNero et al., 2006; Birch et al., 2006). We describe a Gibbs sampler that con- sistently and efficiently approximates expectations, using only polynomial-time computable operators. Despite the combinatorial complexity of the phrase alignment space, our sampled phrase pair expecta- tions are guaranteed to converge to the true poste- rior distributions under the model (in theory) and do converge to effective values (in practice). The second challenge in learning phrase align- ments is avoiding a degenerate behavior of the gen- eral model class: as with many models which can choose between large and small structures, the larger structures win out in maximum likelihood estima- tion. Indeed, the maximum likelihood estimate of a joint phrase alignment model analyzes each sen- tence pair as one large phrase with no internal struc- ture (Marcu and Wong, 2002). We describe two non- parametric priors that empirically avoid this degen- erate solution. Fixed word alignments are used in virtually ev- ery statistical machine translation system, if not to extract phrase pairs or rules directly, then at least to constrain the inference procedure for higher-level models. We estimate phrase translation features consistently using an inference procedure that is not constrained by word alignments, or any other heuris- tic. Despite this substantial change in approach, we report translation improvements over the standard word-alignment-based heuristic estimates of phrase table weights. We view this result as an important step toward building fully model-based translation systems that rely on fewer …

Content truncated to 500 words