Word Alignment via Quadratic Assignment

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 112–119, New York, June 2006. c⃝2006 Association for Computational Linguistics Word Alignment via Quadratic Assignment Simon Lacoste-Julien UC Berkeley, Berkeley, CA 94720 slacoste@cs.berkeley.edu Ben Taskar UC Berkeley, Berkeley, CA 94720 taskar@cs.berkeley.edu Dan Klein UC Berkeley, Berkeley, CA 94720 klein@cs.berkeley.edu Michael I. Jordan UC Berkeley, Berkeley, CA 94720 jordan@cs.berkeley.edu Abstract Recently, discriminative word alignment methods have achieved state-of-the-art accuracies by extend- ing the range of information sources that can be easily incorporated into aligners. The chief advan- tage of a discriminative framework is the ability to score alignments based on arbitrary features of the matching word tokens, including orthographic form, predictions of other models, lexical context and so on. However, the proposed bipartite match- ing model of Taskar et al. (2005), despite being tractable and effective, has two important limita- tions. First, it is limited by the restriction that words have fertility of at most one. More impor- tantly, first order correlations between consecutive words cannot be directly captured by the model. In this work, we address these limitations by enrich- ing the model form. We give estimation and infer- ence algorithms for these enhancements. Our best model achieves a relative AER reduction of 25% over the basic matching formulation, outperform- ing intersected IBM Model 4 without using any overly compute-intensive features. By including predictions of other models as features, we achieve AER of 3.8 on the standard Hansards dataset. 1 Introduction Word alignment is a key component of most end- to-end statistical machine translation systems. The standard approach to word alignment is to construct directional generative models (Brown et al., 1990; Och and Ney, 2003), which produce a sentence in one language given the sentence in another lan- guage. While these models require sentence-aligned bitexts, they can be trained with no further super- vision, using EM. Generative alignment models do, however, have serious drawbacks. First, they require extensive tuning and processing of large amounts of data which, for the better-performing models, is a non-trivial resource requirement. Second, condi- tioning on arbitrary features of the input is difficult; for example, we would like to condition on the or- thographic similarity of a word pair (for detecting cognates), the presence of that pair in various dic- tionaries, the similarity of the frequency of its two words, choices made by other alignment systems, and so on. Recently, Moore (2005) proposed a discrimina- tive model in which pairs of sentences (e, f) and proposed alignments a are scored using a linear combination of arbitrary features computed from the tuples (a, e, f). While there are no restrictions on the form of the model features, the problem of find- ing the highest scoring alignment is very difficult and involves heuristic search. Moreover, the param- eters of the model must be estimated using averaged perceptron training (Collins, 2002), which can be unstable. In contrast, Taskar et al. (2005) cast word alignment as a maximum weighted matching prob- lem, in which …

Content truncated to 500 words