An Expectation Maximisation Algorithm for Automated Cognate Detection (2020)

Abstract: In historical linguistics, cognate detection is the task of determining whether sets of words have common etymological roots. Inspired by the comparative method used by human linguists, we develop a system for automated cognate detection that frames the task as an inference problem for a general statistical model consisting of observed data (potentially cognate pairs of words), latent variables (the cognacy status of pairs) and unknown global parameters (which sounds correspond between languages). We then give a specific instance of such a model along with an expectation-maximisation algorithm to infer its parameters. We evaluate our system on a corpus of 8140 cognate sets, finding the performance of our method to be comparable to the state of the art. We additionally carry out qualitative analysis demonstrating advantages it has over existing systems. We also suggest several ways our work could be extended within the general theoretical framework we propose.

## introduction in historical linguistics, two words are deemed cognate if they share a root in a parent language, for example german 'nacht' and english 'night' which both originate from proto-indo-european *nók w ts. the task of cognate detection is interesting in its own right, but is also an important part of the larger task of proto-language reconstruction. as described in @xcite , the comparative method used by historical linguists to reconstruct an ancestral language from a set of potentially cognate words in daughter languages consists of three steps: assembling cognates, establishing sound correspondences and reconstructing proto-sounds. automation of this method is made challenging by the fact that "the comparative linguist typically jumps back and forth among these steps" because of a mutual dependence between cognacy judgements and hypothesised sound correspondences. whether two words should be deemed cognate depends on whether the sounds in them correspond according to known rules for the languages. for instance, the t and ts sounds in english and german are known to correspond, which is evidence for "tooth" and "zahn" being cognate. but sound correspondence rules are themselves theorised based on which sounds coincide in known cognate pairs. therefore a linguist must iteratively adapt their hypotheses about which words are cognate and which sounds correspond until they can reach a definite conclusion. existing approaches to automated cognate detection (acd) fail to fully capture this idea of dealing with mutual dependence using an iterative method. some early approaches are not iterative at all, while several more recent methods are iterative to some extent but either only carry out a small fixed number of iterations or use incomplete and ad hoc methods to update sound correspondences based on tentative cognacy judgements. in this paper we design and implement an iterative algorithm that uses the method of expectation maximisation for statistical inference, which is close to historical linguists' method of updating sound correspondences in one iteration based on cognacy judgements from the previous iteration. this probabilistic approach is the main novel feature of our work, but we also build on existing approaches in other ways. other than the work of @xcite , previous computational methods generally use little linguistic theory as a basis for making cognate judgements; in contrast, our model uses phonological features as a factor in determining how likely phones are to correspond. we also use a new method of clustering to turn cognate judgements between pairs of words into sets of cognates from multiple languages. we evaluate our system on a dataset consisting of 8140 cognate sets partitioned into 10 typological groups originated by @xcite . ## related work several approaches to acd exist, with a review of the majority given in @xcite . most of these have the same overall structure: given a list of sets of possible cognates, they align words using some metric (typically based on the phones that make up the words) and use some function of scores of alignments to judge cognacy. the alignment process generally uses methods from bioinformatics such as the needleman-wunsch algorithm @xcite . normalised edit distance @xcite ) (ned) performs alignment using a manually specified distance matrix for phones. it has been used with a simple binary measure (distance only depends on whether or not two phones are the same) and more complex measures. this was a relatively early method and is not iterative. @xcite discuss two methods that do not use alignment. consonant class matching (ccm) @xcite is a very simple approach: it determines whether words are cognate based on whether their first consonants fall into the same sound classes. on the other hand, the system of @xcite is more complex; it uses similarity as measured by other methods such as those below as a feature source for classification of cognacy using support vector machines (svms). the online pointwise mutual information method @xcite (pmi) is similar to ours in that it performs alignment with a distance matrix for pairs of phones which is adjusted iteratively. however, they do not update weights in a probabilistic way based on tentative cognacy probabilities at each iteration in the same way as us. we take into account all pairs of possible cognates in the dataset weighted by their estimated cognacy probability; in comparison they use a fixed set of cognate words deemed to be probably cognate, and these are treated uniformly. they also do not set weights in a linguistically motivated way. the system of @xcite is similar to pmi, but using the lz78 algorithm @xcite to produce weights instead of pmi scores. @xcite describes another similar algorithm. we use the lexstat algorithm @xcite as a baseline in evaluation of our system. lexstat is partially iterative: it uses a simple heuristic to determine which pairs of words are definitely cognate and then sets weights for an alignment step based on those. in contrast, our system can iterate indefinitely rather than just twice. unlike methods such as pmi, lexstat does use linguistic theory in judging cognacy of word pairs. rather than computing distance between individual phones, it groups phones into sound classes (by place and manner of articulation) and then considers combinations of sound classes and prosodic contexts as the segments used for alignment. the use of sound classes is similar to our framework with phonological features, although ours is in some ways more general. prosodic context is not taken into account by our system and could be a future extension. overall, the primary difference between our system and previous work is the way in which we adjust parameters for how likely two sounds are to correspond based on intermediate estimates of cognacy probabilities. producing theories about which sounds correspond based on cognacy judgements is a key part of the method followed by human linguists, but many existing automated methods do not do this at all. those that do often only make a limited number of adjustments, or lack theoretical justification for the approach used. in contrast, in our system this process has equal status to the inference step in the opposite direction, and has a rigorous probabilistic interpretation within the expectation-maximisation framework. the probabilistic framework used also has the benefit of allowing easier identification of limitations of the system, such as cases where unrealistic assumptions of independence are made. a key element of our system that enables this approach is the fact that we separately model the processes of generating two cognate words from a common ancestor and two non-cognates from different ancestors. in comparison, previous work implicitly models only the former. ## conclusions in this paper, we formalised the task of cognate detection as inference in a general statistical model, defined a specific example of such a model, and then designed and implemented an expectationmaximisation algorithm for that model. we evaluated its performance on an existing dataset, finding it to be comparable with the current state of the art. we also evaluated it qualitatively to demonstrate advantages it has over existing systems, such as greater flexibility on challenging datasets. there are many ways this system could be extended by future work. the word-level model of cognacy could be made more sophisticated in various regards; one that appears especially promising from our qualitative evaluation would be to give different weights to pairs of aligned phones depending on the position they come in the word or on neighbouring phones, which would improve the system's ability to capture conditioned sound changes @xcite . a larger change would be to modify the system to perform cognate detection and phylogenetic reconstruction of taxon families simultaneously. this could significantly increase the performance of the system, since many of the errors observed here could be avoided by using information about taxon families. it would also build on our approach of mimicking the method of a human linguist by going from iteratively alternating between making cognate judgements and determining sound correspondences to iteratively alternating between those steps and reconstruction of language family trees.