Alignment-Based Discriminative String Similarity

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 656–663, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Alignment-Based Discriminative String Similarity Shane Bergsma and Grzegorz Kondrak Department of Computing Science University of Alberta Edmonton, Alberta, Canada, T6G 2E8 {bergsma,kondrak}@cs.ualberta.ca Abstract A character-based measure of similarity is an important component of many natu- ral language processing systems, including approaches to transliteration, coreference, word alignment, spelling correction, and the identification of cognates in related vocabu- laries. We propose an alignment-based dis- criminative framework for string similarity. We gather features from substring pairs con- sistent with a character-based alignment of the two strings. This approach achieves exceptional performance; on nine separate cognate identification experiments using six language pairs, we more than double the pre- cision of traditional orthographic measures like Longest Common Subsequence Ratio and Dice’s Coefficient. We also show strong improvements over other recent discrimina- tive and heuristic similarity functions. 1 Introduction String similarity is often used as a means of quan- tifying the likelihood that two pairs of strings have the same underlying meaning, based purely on the character composition of the two words. Strube et al. (2002) use Edit Distance as a feature for de- termining if two words are coreferent. Taskar et al. (2005) use French-English common letter se- quences as a feature for discriminative word align- ment in bilingual texts. Brill and Moore (2000) learn misspelled-word to correctly-spelled-word similari- ties for spelling correction. In each of these exam- ples, a similarity measure can make use of the recur- rent substring pairings that reliably occur between words having the same meaning. Across natural languages, these recurrent sub- string correspondences are found in word pairs known as cognates: words with a common form and meaning across languages. Cognates arise ei- ther from words in a common ancestor language (e.g. light/Licht, night/Nacht in English/German) or from foreign word borrowings (e.g. trampo- line/toranporin in English/Japanese). Knowledge of cognates is useful for a number of applications, in- cluding sentence alignment (Melamed, 1999) and learning translation lexicons (Mann and Yarowsky, 2001; Koehn and Knight, 2002). We propose an alignment-based, discriminative approach to string similarity and evaluate this ap- proach on cognate identification. Section 2 de- scribes previous approaches and their limitations. In Section 3, we explain our technique for automati- cally creating a cognate-identification training set. A novel aspect of this set is the inclusion of competitive counter-examples for learning. Section 4 shows how discriminative features are created from a character- based, minimum-edit-distance alignment of a pair of strings. In Section 5, we describe our bitext and dictionary-based experiments on six language pairs, including three based on non-Roman alphabets. In Section 6, we show significant improvements over traditional approaches, as well as significant gains over more recent techniques by Ristad and Yiani- los (1998), Tiedemann (1999), Kondrak (2005), and Klementiev and Roth (2006). 2 Related Work String similarity is a fundamental concept in a va- riety of fields and hence a range of techniques 656 have been …

Content truncated to 500 words