Large-Scale Cognate Recovery

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 344–354, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Large-Scale Cognate Recovery David Hall and Dan Klein Computer Science Division University of California at Berkeley {dlwh,klein}@cs.berkeley.edu Abstract We present a system for the large scale in- duction of cognate groups. Our model ex- plains the evolution of cognates as a sequence of mutations and innovations along a phy- logeny. On the task of identifying cognates from over 21,000 words in 218 different lan- guages from the Oceanic language family, our model achieves a cluster purity score over 91%, while maintaining pairwise recall over 62%. 1 Introduction The critical first step in the reconstruction of an ancient language is the recovery of related cog- nate words in its descendants. Unfortunately, this process has largely been a manual, linguistically- intensive undertaking for any sizable number of de- scendant languages. The traditional approach used by linguists—the comparative method—iterates be- tween positing putative cognates and then identify- ing regular sound laws that explain correspondences between those words (Bloomfield, 1938). Successful computational approaches have been developed for large-scale reconstruction of phyloge- nies (Ringe et al., 2002; Daum´e III and Campbell, 2007; Daum´e III, 2009; Nerbonne, 2010) and an- cestral word forms of known cognate sets (Oakes, 2000; Bouchard-Cˆot´e et al., 2007; Bouchard-Cˆot´e et al., 2009), enabling linguists to explore deep his- torical relationships in an automated fashion. How- ever, computational approaches thus far have not been able to offer the same kind of scale for iden- tifying cognates. Previous work in cognate identi- fication has largely focused on identifying cognates in pairs of languages (Mann and Yarowsky, 2001; Lowe and Mazaudon, 1994; Oakes, 2000; Kondrak, 2001; Mulloni, 2007), with a few recent exceptions that can find sets in a handful of languages (Bergsma and Kondrak, 2007; Hall and Klein, 2010). While it may seem surprising that cognate de- tection has not successfully scaled to large num- bers of languages, the task poses challenges not seen in reconstruction and phylogeny inference. For instance, morphological innovations and irregular sound changes can completely obscure relationships between words in different languages. However, in the case of reconstruction, an unexplainable word is simply that: one can still correctly reconstruct its an- cestor using words from related languages. In this paper, we present a system that uses two generative models for large-scale cognate identi- fication. Both models describe the evolution of words along a phylogeny according to automatically learned sound laws in the form of parametric edit distances. The first is an adaptation of the genera- tive model of Hall and Klein (2010), and the other is a new generative model called PARSIM with con- nections to parsimony methods in computational bi- ology (Cavalli-Sforza and Edwards, 1965; Fitch, 1971). Our model supports simple, tractable infer- ence via message passing, at the expense of being unable to model some cognacy relationships. To help correct this deficiency, we also describe an ag- glomerative inference procedure for the …

Content truncated to 500 words