Empirical Lower Bounds on the Complexity of Translational Equivalence

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 977–984, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Empirical Lower Bounds on the Complexity of Translational Equivalence ∗ Benjamin Wellington Computer Science Dept. New York University New York, NY 10003 {lastname}@cs.nyu.edu Sonjia Waxmonsky Computer Science Dept. University of Chicago† Chicago, IL, 60637 wax@cs.uchicago.edu I. Dan Melamed Computer Science Dept. New York University New York, NY, 10003 {lastname}@cs.nyu.edu Abstract This paper describes a study of the pat- terns of translational equivalence exhib- ited by a variety of bitexts. The study found that the complexity of these pat- terns in every bitext was higher than sug- gested in the literature. These findings shed new light on why “syntactic” con- straints have not helped to improve statis- tical translation models, including finite- state phrase-based models, tree-to-string models, and tree-to-tree models. The paper also presents evidence that inver- sion transduction grammars cannot gen- erate some translational equivalence rela- tions, even in relatively simple real bi- texts in syntactically similar languages with rigid word order. Instructions for replicating our experiments are at http://nlp.cs.nyu.edu/GenPar/ACL06 1 Introduction Translational equivalence is a mathematical rela- tion that holds between linguistic expressions with the same meaning. The most common explicit rep- resentations of this relation are word alignments between sentences that are translations of each other. The complexity of a given word alignment can be measured by the difficulty of decomposing it into its atomic units under certain constraints de- tailed in Section 2. This paper describes a study of the distribution of alignment complexity in a variety of bitexts. The study considered word alignments both in isolation and in combination with independently generated parse trees for one or both sentences in each pair. Thus, the study ∗ Thanks to David Chiang, Liang Huang, the anonymous reviewers, and members of the NYU Proteus Project for help- ful feedback. This research was supported by NSF grant #’s 0238406 and 0415933. † SW made most of her contribution while at NYU. is relevant to finite-state phrase-based models that use no parse trees (Koehn et al., 2003), tree-to- string models that rely on one parse tree (Yamada and Knight, 2001), and tree-to-tree models that rely on two parse trees (Groves et al., 2004, e.g.). The word alignments that are the least complex on our measure coincide with those that can be generated by an inversion transduction grammar (ITG). Following Wu (1997), the prevailing opin- ion in the research community has been that more complex patterns of word alignment in real bitexts are mostly attributable to alignment errors. How- ever, the experiments in Section 3 show that more complex patterns occur surprisingly often even in highly reliable alignments in relatively simple bi- texts. As discussed in Section 4, these findings shed new light on why “syntactic” constraints have not yet helped to improve the accuracy of statisti- cal machine translation. Our study used two kinds of data, each con- trolling a different confounding variable. First, we …

Content truncated to 500 words