Non-Monotonic Sentence Alignment via Semisupervised Learning

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 622–630, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Non-Monotonic Sentence Alignment via Semisupervised Learning Xiaojun Quan, Chunyu Kit and Yan Song Department of Chinese, Translation and Linguistics City University of Hong Kong, HKSAR, China {xiaoquan,ctckit,[yansong]}@[student.]cityu.edu.hk Abstract This paper studies the problem of non- monotonic sentence alignment, motivated by the observation that coupled sentences in real bitexts do not necessarily occur monotonically, and proposes a semisuper- vised learning approach based on two as- sumptions: (1) sentences with high affinity in one language tend to have their counter- parts with similar relatedness in the other; and (2) initial alignment is readily avail- able with existing alignment techniques. They are incorporated as two constraints into a semisupervised learning framework for optimization to produce a globally op- timal solution. The evaluation with real- world legal data from a comprehensive legislation corpus shows that while exist- ing alignment algorithms suffer severely from non-monotonicity, this approach can work effectively on both monotonic and non-monotonic data. 1 Introduction Bilingual sentence alignment is a fundamental task to undertake for the purpose of facilitating many important natural language processing ap- plications such as statistical machine translation (Brown et al., 1993), bilingual lexicography (Kla- vans et al., 1990), and cross-language informa- tion retrieval (Nie et al., 1999). Its objective is to identify correspondences between bilingual sen- tences in given bitexts. As summarized by Wu (2010), existing sentence alignment techniques rely mainly on sentence length and bilingual lex- ical resource. Approaches based on the former perform effectively on cognate languages but not on the others. For instance, the statistical cor- relation of sentence length between English and Chinese is not as high as that between two Indo- European languages (Wu, 1994). Lexicon-based approaches resort to word correspondences in a bilingual lexicon to match bilingual sentences. A few sentence alignment methods and tools have also been explored to combine the two. Moore (2002) proposes a multi-pass search procedure us- ing both sentence length and an automatically- derived bilingual lexicon. Hunalign (Varga et al., 2005) is another sentence aligner that combines sentence length and a lexicon. Without a lexicon, it backs off to a length-based algorithm and then automatically derives a lexicon from the align- ment result. Soon after, Ma (2006) develops the lexicon-based aligner Champollion, assuming that different words have different importance in align- ing two sentences. Nevertheless, most existing approaches to sen- tence alignment follow the monotonicity assump- tion that coupled sentences in bitexts appear in a similar sequential order in two languages and crossings are not entertained in general (Langlais et al., 1998; Wu, 2010). Consequently the task of sentence alignment becomes handily solvable by means of such basic techniques as dynamic pro- gramming. In many scenarios, however, this pre- requisite monotonicity cannot be guaranteed. For example, bilingual clauses in legal bitexts are of- ten coordinated in a way not to keep the same clause order, demanding fully or partially crossing pairings. Figure 1 …

Content truncated to 500 words