A Geometric Approach to Mapping Bitext Correspondence

A Geometric Approach to Mapping Bitext Correspondence I. Dan Melamed Dept. of Computer and Information Science University of Pennsylvania Philadelphia, PA, 19104, U.S.A. melamed©unagi, cis. upenn, edu Abstract The first step in most corpus-based mul- tilingual NLP work is to construct a de- tailed map of the correspondence between a text and its translation. Several auto- matic methods for this task have been pro- posed in recent years. "Yet even the best of these methods can err by several typeset pages. The Smooth Injective Map Recog- nizer (SIMR) is a new bitext mapping al- gorithm. SIMR's errors are smaller than those of the previous front-runner by more than a factor of 4. Its robustness has en- abled new commercial-quality applications. The greedy nature of the algorithm makes it independent of memory resources. Unlike other bitext mapping algorithms, SIMR al- lows crossing correspondences to account for word order differences. Its output can be converted quickly and easily into a sen- tence alignment. SIMR's output has been used to align more than 200 megabytes of the Canadian Hansards for publication by the Linguistic Data Consortium. 1. Introduction The first step in most corpus-based multilin- gual NLP work is to construct a detailed map of the correspondence between a text and its translation (a bitext map). Several auto- matic methods have been proposed for this task in recent years. However, most of these methods address only the sub-problem of align- ment (Catizone et al. 1989, Brown et al. 1991, Gale & Church 1991, Debili & Sammouda 1992, Simard et al. 1992, Kay & RSscheisen 1993, Wu 1994). Alignment algorithms assume the availability of text unit boundary information and their output has less expressive power than a gen- eral bitext map. The only published solution to the more difficult general bitext mapping problem (Church 1993) can err by several typeset pages. Such frailty can expose lexicographers and ter- minologists to spurious concordances, feed noisy training data into statistical translation models, and degrade the performance of corpus-based ma- chine translation. Some multilingual NLP tasks, such as automatic validation of terminological con- sistency (Macklovitch 1995) and automatic detec- tion of omissions in translations (implemented for the first time in (Melamed 1996)), have been tech- nologically impossible until now, because they are highly sensitive to large errors in the bitext map. The Smooth Injective Map Recognizer (SIMR) is a greedy algorithm for mapping bitext correspondence. SIMR borrows several insights from previous work. Like Gale & Church (1991) and Brown et al. (1991), SIMR relies on the high correlation between the lengths of mutual trans- lations. Like char_.align (Church 1993), SIMR infers bitext maps from likely points of correspon- dence between the two texts, points that are plot- ted in a two-dimensional space of possibilities. Un- like previous methods, SIMR searches for only a handful of points of correspondence at a time. Each set of correspondence points is found in two steps. First, SIMR generates a number of possible points of correspondence between the two texts, as described …

Content truncated to 500 words