Better Word Alignments with Supervised ITG Models

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 923–931, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Better Word Alignments with Supervised ITG Models Aria Haghighi, John Blitzer, John DeNero and Dan Klein Computer Science Division, University of California at Berkeley { aria42,blitzer,denero,klein }@cs.berkeley.edu Abstract This work investigates supervised word align- ment methods that exploit inversion transduc- tion grammar (ITG) constraints. We con- sider maximum margin and conditional like- lihood objectives, including the presentation of a new normal form grammar for canoni- calizing derivations. Even for non-ITG sen- tence pairs, we show that it is possible learn ITG alignment models by simple relaxations of structured discriminative learning objec- tives. For efficiency, we describe a set of prun- ing techniques that together allow us to align sentences two orders of magnitude faster than naive bitext CKY parsing. Finally, we intro- duce many-to-one block alignment features, which significantly improve our ITG models. Altogether, our method results in the best re- ported AER numbers for Chinese-English and a performance improvement of 1.1 BLEU over GIZA++ alignments. 1 Introduction Inversion transduction grammar (ITG) con- straints (Wu, 1997) provide coherent structural constraints on the relationship between a sentence and its translation. ITG has been extensively explored in unsupervised statistical word align- ment (Zhang and Gildea, 2005; Cherry and Lin, 2007a; Zhang et al., 2008) and machine translation decoding (Cherry and Lin, 2007b; Petrov et al., 2008). In this work, we investigate large-scale, discriminative ITG word alignment. Past work on discriminative word alignment has focused on the family of at-most-one-to-one matchings (Melamed, 2000; Taskar et al., 2005; Moore et al., 2006). An exception to this is the work of Cherry and Lin (2006), who discrim- inatively trained one-to-one ITG models, albeit with limited feature sets. As they found, ITG approaches offer several advantages over general matchings. First, the additional structural con- straint can result in superior alignments. We con- firm and extend this result, showing that one-to- one ITG models can perform as well as, or better than, general one-to-one matching models, either using heuristic weights or using rich, learned fea- tures. A second advantage of ITG approaches is that they admit a range of training options. As with general one-to-one matchings, we can optimize margin-based objectives. However, unlike with general matchings, we can also efficiently com- pute expectations over the set of ITG derivations, enabling the training of conditional likelihood models. A major challenge in both cases is that our training alignments are often not one-to-one ITG alignments. Under such conditions, directly training to maximize margin is unstable, and train- ing to maximize likelihood is ill-defined, since the target alignment derivations don’t exist in our hy- pothesis class. We show how to adapt both margin and likelihood objectives to learn good ITG align- ers. In the case of likelihood training, two innova- tions are presented. The simple, two-rule ITG grammar exponentially over-counts certain align- ment structures relative to others. Because of this, Wu (1997) and …

Content truncated to 500 words