Fast Inference in Phrase Extraction Models with Belief Propagation

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 29–38, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Fast Inference in Phrase Extraction Models with Belief Propagation David Burkett and Dan Klein Computer Science Division University of California, Berkeley {dburkett,klein}@cs.berkeley.edu Abstract Modeling overlapping phrases in an align- ment model can improve alignment quality but comes with a high inference cost. For example, the model of DeNero and Klein (2010) uses an ITG constraint and beam-based Viterbi decoding for tractability, but is still slow. We first show that their model can be approximated using structured belief propaga- tion, with a gain in alignment quality stem- ming from the use of marginals in decoding. We then consider a more flexible, non-ITG matching constraint which is less efficient for exact inference but more efficient for BP. With this new constraint, we achieve a relative error reduction of 40% in F5 and a 5.5x speed-up. 1 Introduction Modern statistical machine translation (MT) sys- tems most commonly infer their transfer rules from word-level alignments (Koehn et al., 2007; Li and Khudanpur, 2008; Galley et al., 2004), typically using a deterministic heuristic to convert these to phrase alignments (Koehn et al., 2003). There have been many attempts over the last decade to develop model-based approaches to the phrase alignment problem (Marcu and Wong, 2002; Birch et al., 2006; DeNero et al., 2008; Blunsom et al., 2009). How- ever, most of these have met with limited success compared to the simpler heuristic method. One key problem with typical models of phrase alignment is that they choose a single (latent) segmentation, giving rise to undesirable modeling biases (DeNero et al., 2006) and reducing coverage, which in turn reduces translation quality (DeNeefe et al., 2007; DeNero et al., 2008). On the other hand, the extrac- tion heuristic identifies many overlapping options, and achieves high coverage. In response to these effects, the recent phrase alignment work of DeNero and Klein (2010) mod- els extraction sets: collections of overlapping phrase pairs that are consistent with an underlying word alignment. Their extraction set model is empirically very accurate. However, the ability to model over- lapping – and therefore non-local – features comes at a high computational cost. DeNero and Klein (2010) handle this in part by imposing a structural ITG constraint (Wu, 1997) on the underlying word alignments. This permits a polynomial-time algo- rithm, but it is still O(n6), with a large constant factor once the state space is appropriately enriched to capture overlap. Therefore, they use a heavily beamed Viterbi search procedure to find a reason- able alignment within an acceptable time frame. In this paper, we show how to use belief propagation (BP) to improve on the model’s ITG-based struc- tural formulation, resulting in a new model that is simultaneously faster and more accurate. First, given the model of DeNero and Klein (2010), we decompose it into factors that admit an efficient BP approximation. BP is an inference technique that …

Content truncated to 500 words