Simple Effective Decipherment via Combinatorial Optimization

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 313–321, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Simple Effective Decipherment via Combinatorial Optimization Taylor Berg-Kirkpatrick and Dan Klein Computer Science Division University of California at Berkeley {tberg, klein}@cs.berkeley.edu Abstract We present a simple objective function that when optimized yields accurate solutions to both decipherment and cognate pair identifica- tion problems. The objective simultaneously scores a matching between two alphabets and a matching between two lexicons, each in a different language. We introduce a simple coordinate descent procedure that efficiently finds effective solutions to the resulting com- binatorial optimization problem. Our system requires only a list of words in both languages as input, yet it competes with and surpasses several state-of-the-art systems that are both substantially more complex and make use of more information. 1 Introduction Decipherment induces a correspondence between the words in an unknown language and the words in a known language. We focus on the setting where a close correspondence between the alphabets of the two languages exists, but is unknown. Given only two lists of words, the lexicons of both languages, we attempt to induce the correspondence between alphabets and identify the cognates pairs present in the lexicons. The system we propose accomplishes this by defining a simple combinatorial optimiza- tion problem that is a function of both the alphabet and cognate matchings, and then induces correspon- dences by optimizing the objective using a block co- ordinate descent procedure. There is a range of past work that has var- iously investigated cognate detection (Kondrak, 2001; Bouchard-Cˆot´e et al., 2007; Bouchard-Cˆot´e et al., 2009; Hall and Klein, 2010), character-level decipherment (Knight and Yamada, 1999; Knight et al., 2006; Snyder et al., 2010; Ravi and Knight, 2011), and bilingual lexicon induction (Koehn and Knight, 2002; Haghighi et al., 2008). We consider a common element, which is a model wherein there are character-level correspondences and word-level correspondences, with the word matching parame- terized by the character one. This approach sub- sumes a range of past tasks, though of course past work has specialized in interesting ways. Past work has emphasized the modeling as- pect, where here we use a parametrically simplistic model, but instead emphasize inference. 2 Decipherment as Two-Level Optimization Our method represents two matchings, one at the al- phabet level and one at the lexicon level. A vector of variables x specifies a matching between alphabets. For each character i in the source alphabet and each character j in the target alphabet we define an indi- cator variable xij that is on if and only if character i is mapped to character j. Similarly, a vector y rep- resents a matching between lexicons. For word u in the source lexicon and word v in the target lexicon, the indicator variable yuv denotes that u maps to v. Note that the matchings need not be one-to-one. We define an objective function on the matching variables as follows. Let EDITDIST(u, v; x) …

Content truncated to 500 words