A Comparison of Syntactically Motivated Word Alignment Spaces

A Comparison of Syntactically Motivated Word Alignment Spaces Colin Cherry Department of Computing Science University of Alberta Edmonton, AB, Canada, T6G 2E8 colinc@cs.ualberta.ca Dekang Lin Google Inc. 1600 Amphitheatre Parkway Mountain View, CA, USA, 94043 lindek@google.com Abstract This work is concerned with the space of alignments searched by word alignment systems. We focus on situations where word re-ordering is limited by syntax. We present two new alignment spaces that limit an ITG according to a given depen- dency parse. We provide D-ITG grammars to search these spaces completely and without redundancy. We conduct a care- ful comparison of five alignment spaces, and show that limiting search with an ITG reduces error rate by 10%, while a D-ITG produces a 31% reduction. 1 Introduction Bilingual word alignment finds word-level corre- spondences between parallel sentences. The task originally emerged as an intermediate result of training the IBM translation models (Brown et al., 1993). These models use minimal linguistic intuitions; they essentially treat sentences as flat strings. They remain the dominant method for word alignment (Och and Ney, 2003). There have been several proposals to introduce syntax into word alignment. Some work within the framework of synchronous grammars (Wu, 1997; Melamed, 2003), while others create a generative story that includes a parse tree provided for one of the sen- tences (Yamada and Knight, 2001). There are three primary reasons to add syntax to word alignment. First, one can incorporate syntac- tic features, such as grammar productions, into the models that guide the alignment search. Second, movement can be modeled more naturally; when a three-word noun phrase moves during translation, it can be modeled as one movement operation in- stead of three. Finally, one can restrict the type of movement that is considered, shrinking the num- ber of alignments that are attempted. We investi- gate this last advantage of syntactic alignment. We fix an alignment scoring model that works equally well on flat strings as on parse trees, but we vary the space of alignments evaluated with that model. These spaces become smaller as more linguistic guidance is added. We measure the benefits and detriments of these constrained searches. Several of the spaces we investigate draw guid- ance from a dependency tree for one of the sentences. We will refer to the parsed lan- guage as English and the other as Foreign. Lin and Cherry (2003) have shown that adding a dependency-based cohesion constraint to an align- ment search can improve alignment quality. Un- fortunately, the usefulness of their beam search solution is limited: potential alignments are con- structed explicitly, which prevents a perfect search of alignment space and the use of algorithms like EM. However, the cohesion constraint is based on a tree, which should make it amenable to dy- namic programming solutions. To enable such techniques, we bring the cohesion constraint in- side the ITG framework (Wu, 1997). andZhang and Gildea (2004) compared Yamada Knight’s (2001) tree-to-string alignment model to ITGs. They concluded that methods like ITGs, which create a tree during …

Content truncated to 500 words