Fast Inference in Phrase Extraction Models with Belief Propagation

Modeling overlapping phrases in an alignment 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 propagation, with a gain in alignment quality stemming 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.