A Constrained Viterbi Relaxation for Bidirectional Word Alignment
Yin-Wen Chang, Alexander M. Rush, John DeNero, Michael Collins · 2014
Bidirectional models of word alignment are an appealing alternative to post-hoc combinations of directional word aligners.Unfortunately, most bidirectional formulations are NP-Hard to solve, and a previous attempt to use a relaxationbased decoder yielded few exact solutions (6%).We present a novel relaxation for decoding the bidirectional model of DeNero and Macherey (2011).The relaxation can be solved with a modified version of the Viterbi algorithm.To find optimal solutions on difficult instances, we alternate between incrementally adding constraints and applying optimality-preserving coarse-to-fine pruning.The algorithm finds provably exact solutions on 86% of sentence pairs and shows improvements over directional models.