Alignment of Shared Forests for Bilingual Corpora

Alignment of Shared Forests for Bilingual Corpora Adam Meyers, Roman Yangarber, Ralph Grishman New York lJlfiv<;rsity 715 Broadway, 7th 1+1oo, ', NY, NY 10003, USA meyers/roman/grishman@cs, nyu. edu Abstract Research in example-based machine translation (F,I~MT) has been hampered by the lack of efficient tree alignment al- gorithms for bilingual corpora. *ghis pa- per <lescribes an alignment algorithm for F,I~MT whose running time is quadratic in tile size of the input parse trees. 'Phe algorithm uses dynamic programming to score all possible matching nodes be- tween structure-sharing trees or forests. We describe the algorithm, various opti- mizations, and onr implementation. 1 Introduction The development of a glachine translation (MT) system re<luires the lengthy manual preparation of bilingual lexicons an(t transfer rules. I{esearch over the past few years using parallel senten<:e- aligned bilingual corpora sugg{'.sts ways in which this manual effort <'an be partly replaced by corpus-based training. Some o1' l;his research has treated the sentenees as unstructured word sequences to be aligned; this work has primar- ily involved the acquisition of bilingual lexical correspondences (Chen, 1993), although there has also been a,n attempt to create a full MT system based on such trcat, ment (Brown et al., 1993). I{ecently, several groul)S have been ex- ploring the possibility of aligning t)arMlel syn- tacticalhj analyzed sentences fr<)m the source and target languages (el. (Sate and Nagao, 1990), (Klawms and Tzoukermann, 1990), (Grishman and Kosaka, 1992), (Kaji et al., 1992), (Mat- sumoto et al., 11993) and (Grishman, 11994)). Tiffs offers the potential for acquiring not j ust lcx- ical but also structural correspondences between the two languages, q'he specific goal in aligning syntax trees is to identify tile (:orresponding tree fragments in the source and target trees. By pro- cessing a. substantial corpus, a large set of such corresponding fragments can be collected. These (:an then serve as the example base for a form of examph;-based MT (of. (Nagao, 198d), (Sate and Nagao, 1990), (IG\ii et al., 1992), (Matsumoto <% al., 19!)3) and (leuruse and lida, 1994)). This approach requires a fast tree alignment teehuiqu<~; research has I)een ham/)ered by the lack of efli<:icnt algorithms. This pa,per des<:ril/cs an efficient al- gorithm for bilingual tree alignment. 2 Our Approach For each input sent;ellee our parser t)rodlmes a set of trees, corresponding to each possible syntactic analysis. O.r parse trees are transformed illl, O a "regularized" format, to represent the l)redicate - Argument structure. For each senten<:e, the out put of the parser is a stru(:tm:e-sharing tbrest. An example of strltetllre sharing I:)etween two ila, rse trees <ff l,}le same input senten('.e is shown in Fig are 1. We apply the parser to the source and target sentences, using a Spanish and an F, nglish grain mar, respeetbely. The resulting sets of structure- shin:lug parse trees form the input to the alignment procedure. Our alignment program employs dynamic programming I algorithms, which are described in detail in later sect;ions. The program begins a.t the roots of the source and target trees, and 1)roeeeds top down …

Content truncated to 500 words