Hierarchical Search for Word Alignment

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 157–166, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Hierarchical Search for Word Alignment Jason Riesa and Daniel Marcu Information Sciences Institute Viterbi School of Engineering University of Southern California {riesa, marcu}@isi.edu Abstract We present a simple yet powerful hier- archical search algorithm for automatic word alignment. Our algorithm induces a forest of alignments from which we can efficiently extract a ranked k-best list. We score a given alignment within the forest with a flexible, linear discrimina- tive model incorporating hundreds of fea- tures, and trained on a relatively small amount of annotated data. We report re- sults on Arabic-English word alignment and translation tasks. Our model out- performs a GIZA++ Model-4 baseline by 6.3 points in F-measure, yielding a 1.1 BLEU score increase over a state-of-the-art syntax-based machine translation system. 1 Introduction Automatic word alignment is generally accepted as a first step in training any statistical machine translation system. It is a vital prerequisite for generating translation tables, phrase tables, or syn- tactic transformation rules. Generative alignment models like IBM Model-4 (Brown et al., 1993) have been in wide use for over 15 years, and while not perfect (see Figure 1), they are completely un- supervised, requiring no annotated training data to learn alignments that have powered many current state-of-the-art translation system. Today, there exist human-annotated alignments and an abundance of other information for many language pairs potentially useful for inducing ac- curate alignments. How can we take advantage of all of this data at our fingertips? Using fea- ture functions that encode extra information is one good way. Unfortunately, as Moore (2005) points out, it is usually difficult to extend a given genera- tive model with feature functions without chang- ing the entire generative story. This difficulty Sentence 1 the five previous tests have been limited to the target missile and one other body . ����������� �� ���� ���� ������� ���������� ��� ������� ���������� ����� � � ��� ���� � 1 Figure 1: Model-4 alignment vs. a gold stan- dard. Circles represent links in a human-annotated alignment, and black boxes represent links in the Model-4 alignment. Bold gray boxes show links gained after fully connecting the alignment. has motivated much recent work in discriminative modeling for word alignment (Moore, 2005; Itty- cheriah and Roukos, 2005; Liu et al., 2005; Taskar et al., 2005; Blunsom and Cohn, 2006; Lacoste- Julien et al., 2006; Moore et al., 2006). We present in this paper a discriminative align- ment model trained on relatively little data, with a simple, yet powerful hierarchical search proce- dure. We borrow ideas from both k-best pars- ing (Klein and Manning, 2001; Huang and Chi- ang, 2005; Huang, 2008) and forest-based, and hierarchical phrase-based translation (Huang and Chiang, 2007; Chiang, 2007), and apply them to word alignment. Using a foreign string and an English parse tree as input, we formulate a bottom-up search on the parse tree, with the structure of the tree …

Content truncated to 500 words