Finding Cognate Groups Using Phylogenies

David Leo Wright Hall, Dan KleinACL 2010 · OpenReview

Abstract

A central problem in historical linguistics is the identification of historically related cognate words. We present a generative phylogenetic model for automatically inducing cognate group structure from unaligned word lists. Our model represents the process of transformation and transmission from ancestor word to daughter word, as well as the alignment between the words lists of the observed languages. We also present a novel method for simplifying complex weighted automata created during inference to counteract the otherwise exponential growth of message sizes. On the task of identifying cognates in a dataset of Romance words, our model significantly outperforms a baseline approach, increasing accuracy by as much as 80%. Finally, we demonstrate that our automatically induced groups can be used to successfully reconstruct ancestral words.

Introduction

The comparative method in historical linguistics relies on identifying cognates—words across different languages that descend from a common ancestor. This process is fundamental to reconstructing proto-languages and mapping linguistic evolution. However, a significant computational challenge exists: learning sound-change rules requires known cognate sets, while identifying cognates requires knowledge of sound-change rules. Most automated approaches bypass this by assuming cognate groups are pre-labeled. This work addresses the task of inducing these groups automatically from unaligned word lists.

Generative Phylogenetic Model

We propose a generative model that decomposes the problem into three distinct subprocesses:

  1. Survival: A "death tree" model using Bernoulli variables determines the probability of a word's survival or extinction from an ancestor to a daughter language. This captures the intuition that related languages share more cognates.
  2. Evolution: Phonological changes are modeled as branch-specific edit distances using Weighted Finite State Transducers (WFSTs), capturing probabilities for insertions, deletions, and substitutions.
  3. Alignment: The model "un-scrambles" flat word lists to identify correspondences across languages, determining which word in one language corresponds to another in a sibling language.
The generative phylogenetic model architecture, illustrating the Survival, Evolution, and Alignment components.

Message Approximation

Inference via message passing on phylogenetic trees involves distributions over strings represented as automata. Because transducer composition causes exponential state growth, we introduce a lossy minimization technique. We approximate complex automata with simpler topologies, such as "anchored unigrams" (which account for phoneme position), by minimizing KL divergence. This ensures computational tractability without sacrificing critical linguistic information.

Experimental Results

The model was evaluated on a dataset of 583 cognate sets from Romance languages (Portuguese, Italian, Spanish, and Latin). Latin was treated as unobserved to simulate realistic scenarios where ancestral forms are unknown.

Performance comparison of various model configurations against a heuristic baseline. The 'Learned Anchored Unigrams' configuration achieves the highest accuracy.

As shown in the results table, our model significantly outperforms the standard heuristic baseline (Dice’s coefficient). Specifically, the "Learned Anchored Unigrams" configuration achieved a 90.3% pairwise accuracy and 86.6% exact match rate, compared to the baseline's 48.1% and 35.4%, respectively. The model also proved robust on partial datasets, nearly doubling the baseline F1 score. Furthermore, the automatically induced groups were high-quality enough to reconstruct ancestral Latin words with an average edit distance of 3.8, very close to the 3.0 achieved using gold-standard human labels.

Conclusion

By leveraging phylogenetic constraints and regularities in sound change, our model successfully induces high-quality cognate groups from raw data. The results demonstrate that phylogeny is a powerful constraint for disambiguating linguistic relationships. Future work will address linguistic borrowings and more complex, context-dependent phonological rules.

Summary updated

Abstract

A central problem in historical linguistics is the identification of historically related cognate words. We present a generative phylogenetic model for automatically inducing cognate group structure from unaligned word lists. Our model represents the process of transformation and transmission from ancestor word to daughter word, as well as the alignment between the words lists of the observed languages. We also present a novel method for simplifying complex weighted automata created during inference to counteract the otherwise exponential growth of message sizes. On the task of identifying cognates in a dataset of Romance words, our model significantly outperforms a baseline approach, increasing accuracy by as much as 80%. Finally, we demonstrate that our automatically induced groups can be used to successfully reconstruct ancestral words.
BibTeX
@inproceedings{hall2010finding,
  author = {David Leo Wright Hall and Dan Klein},
  title = {{Finding Cognate Groups Using Phylogenies}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=S1WhSog_ZS},
}
Figure