Paper: A Constrained Viterbi Relaxation for Bidirectional Word Alignment

ACL ID P14-1139
Title A Constrained Viterbi Relaxation for Bidirectional Word Alignment
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2014
Authors

Bidirectional models of word alignment are an appealing alternative to post-hoc combinations of directional word align- ers. Unfortunately, most bidirectional formulations are NP-Hard to solve, and a previous attempt to use a relaxation- based decoder yielded few exact solu- tions (6%). We present a novel relax- ation for decoding the bidirectional model of DeNero and Macherey (2011). The relaxation can be solved with a mod- ified version of the Viterbi algorithm. To find optimal solutions on difficult instances, we alternate between incre- mentally adding constraints and applying optimality-preserving coarse-to-fine prun- ing. The algorithm finds provably ex- act solutions on 86% of sentence pairs and shows improvements over directional models.