A Constrained Viterbi Relaxation for Bidirectional Word Alignment

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1481–1490, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Constrained Viterbi Relaxation for Bidirectional Word Alignment Yin-Wen Chang Alexander M. Rush MIT CSAIL, Cambridge, MA 02139 {yinwen,srush}@ csail.mit.edu John DeNero UC Berkeley, Berkeley, CA 94720 denero@ cs.berkeley.edu Michael Collins Columbia University, New York, NY 10027 mcollins@ cs.columbia.edu Abstract 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. 1 Introduction Word alignment is a critical first step for build- ing statistical machine translation systems. In or- der to ensure accurate word alignments, most sys- tems employ a post-hoc symmetrization step to combine directional word aligners, such as IBM Model 4 (Brown et al., 1993) or hidden Markov model (HMM) based aligners (Vogel et al., 1996). Several authors have proposed bidirectional mod- els that incorporate this step directly, but decoding under many bidirectional models is NP-Hard and finding exact solutions has proven difficult. In this paper, we describe a novel Lagrangian- relaxation based decoder for the bidirectional model proposed by DeNero and Macherey (2011), with the goal of improving search accuracy. In that work, the authors implement a dual decomposition-based decoder for the problem, but are only able to find exact solutions for around 6% of instances. Our decoder uses a simple variant of the Viterbi algorithm for solving a relaxed version of this model. The algorithm makes it easy to re- introduce constraints for difficult instances, at the cost of increasing run-time complexity. To offset this cost, we employ optimality-preserving coarse- to-fine pruning to reduce the search space. The pruning method utilizes lower bounds on the cost of valid bidirectional alignments, which we obtain from a fast, greedy decoder. The method has the following properties: • It is based on a novel relaxation for the model of DeNero and Macherey (2011), solvable with a variant of the Viterbi algorithm. • To find optimal solutions, it employs an effi- cient strategy that alternates between adding constraints and applying pruning. • Empirically, it is able to find exact solutions on 86% of sentence pairs and is significantly faster than general-purpose solvers. We begin in Section 2 by formally describing the directional word alignment problem. Section 3 describes a preliminary bidirectional model us- ing full agreement constraints and a Lagrangian relaxation-based solver. Section 4 modifies this model to include adjacency constraints. Section 5 describes an extension to …

Content truncated to 500 words