A fast implementation of the Consonant Class Matching method for automatic cognate detection in LingPy

LingPy’s LexStat class for cognate detection confuses those who want to apply it, since the name of the Python class is the same as the name of one of the methods the class provides, but the class can be used for other types of cognate detection as well. I recommend all users of LingPy that they give a read to our most recent tutorial on LingPy’s cognate detection method (List et al. 2018), since the three most important methods are discussed there in detail, namely the edit distance method for cognate detection, which makes use of the simple, normalized edit distance, the SCA method, based on the Sound-Class-Based Alignment algorithm (List 2014), and the LexStat method (ibid.). Applying these methods in LingPy is fairly simple and described in detail in our aforementioned tutorial. But LingPy offers an additional method for cognate detection that has the advantage of being extremely fast and thus especially suitable for exploratory data analysis of very large datasets. This method is called turchin in LingPy, named after the first author of a paper presenting the method (Turchin et al. 2010), but the method itself, which Turchin et al. name “Consonant Class Matching” method, goes originally back to Dolgopolsky (1964)), and has long since been implemented as a part of the STARLING software package (http://starling.rinet.ru/program.php).

The method is fairly simple. For a given wordlist with a certain number of concepts translated into a certain number of languages, all words are converted to consonant classes, following either Dolgopolsky’s original proposal (Dolgopolsky 1964) or later modifications (Kassian et al. 2015). After conversion, only the first two consonants of each word are compared, and the basic rule is that if two words match in their first two consonant classes, they should be considered as cognate. Attentive readers may now immediately ask: What do you do if words don’t have a consonant? To handle cases like this, the method has two specific additional rules to convert a word to its first two consonant classes. The first rule says that words starting with a vowel will be treated as if they started with a glottal stop and thus assigned the consonant class “H”. The second rule, which is not often mentioned in the literature, is that, if a word consists of only one vowel, the second consonant will also be rendered as a “H”.

Whether this is a good idea or not, is in fact not important. Previous tests have shown that the method in general does not yield too many false positives, but instead may miss many good cognates (List et al. 2017). That means that the method is rather conservative, at least as long as it is applied to words within the same concept slot. Even more important than its conservative behaviour (as linguists we always prefer false negatives over false positives), however, is that the method is extremely fast, and its complexity is linear: the amount of time we need to cluster words into cognate sets with the Consonant Class Matching method is directly proportional to the number of words in our sample. The reason for this is that the cognate-match criterion of the CCM method is transitive: if word A has the same consonant classes as word B, and word C has the same consonant classes as word B, word C must also have the same consonant classes as word A.

We can also say: the criterion by which we partition a couple of words into cognate sets is just their consonant classes themselves. The consonant classes can be directly used as the labels for the resulting clusters, since the criterion of cognate set assignment is identity in those classes. As a result, we can compute the clusters by simply computing the consonant classes per word in our data, which explains why the complexity is linear.

The problem with the turchin method in the LexStat class of LingPy is that the implementation is not linear in terms of complexity, since it internally uses a distance matrix for all word pairs in a slot in which words that are cognate according to the CCM criterion are given the distance 0 and the other words are given the distance 1. This distance matrix is then analysed with the UPGMA algorithm (Sokal and Michener 1958) or one of the other luster approaches offered by LingPy. While this will still be fast, since the clusters are always well-balanced, the method may easily break if you try to identify cognates across, say, 1000 languages with 200 concepts for each of them. This is not only due to the matrix-implementation in LingPy (which is not needed and was created in a time when I did not see that the CCM method has a linear solution), but also due to the complex operations and conversions that are done whenever you load a dataset into LingPy’s LexStat class.

Writing a workaround is in fact very easy, and presenting this workaround is exactly what I want to do in this blogpost. My hope is that we manage to add this to the next official release of LingPy so that users can profit from the very fast computation of cognate sets for large dataset, without having to wait for hours until the normal LexStat approaches yield (at times disappointing) results. In the following, I will illustrate in a step-by-step guide how cognate sets can be inferred with a linear implementation of the CCM method.

To get started, we import the LingPy library.

from lingpy import *

We then load our wordlist, which can be any wordlist in LingPy or CLDF format (Forkel et al. 2018). I will be lazy in this test and simply import the data from Kessler (2001), which is available from LingPy’s test suite.

from lingpy.tests.util import test_data
wl = Wordlist(test_data('KSL.qlc'))

We then make a function that converts a given tokenized sound sequence to its first two consonant classes, following the criteria mentioned above.

def to_ccm(tokens):
    cv = tokens2class(tokens, 'cv')
    cl = tokens2class(tokens, 'dolgo')
    dolgo = ''
    if cv[0] == 'V': 
        dolgo += 'H'
    else:
        dolgo += cl[0]
    for c, v in zip(cv[1:], cl[1:]):
        if c == 'C':
            dolgo += v
    if len(dolgo) == 1:
        dolgo += 'H'
    return dolgo[:2]

Now we just add a new column to our wordlist, but instead of adding only consonant classes, we add the concepts as well, since we want to make sure that cognates are only assigned inside a given concept slot. For this, we use the Wordlist.add_entries method, which can combine the information given in two and more columns and add it to a new column (but this application is a bit tricky and needs some practice if one wants to use it correctly).

wl.add_entries(
    'cog', 
    'tokens,concept', 
    lambda x, y : x[y[1]]+'-'+to_ccm(x[y[0]]))

Having calculated a new column that contains the name of the concept for each word plus its sound classes, we can conveniently use the Wordlist.renumber function in LingPy to convert the data in this column to integers. Note that we use the override keyword, since the original data already contains cognate sets in a column called cogid.

wl.renumber('cog', override=True)

To see whether we succeded, let us at the same time compute a little tree from the data. Don’t be scared: since Kessler’s data contains unrelated languages, and we use a very crude algorithm for cognate detection, the result will show a tree for the languages, even if there is no evidence for their relatedness.

wl.calculate('tree', ref='cogid')

Last not least, we print the tree in Ascii-Art on the terminal:

print(wl.tree.asciiArt())

And the result will look like this:

                    /-Navajo
          /edge.0--|
         |          \-Turkish
-root----|
         |          /-Hawaiian
         |         |
          \edge.4--|                    /-English
                   |          /edge.1--|
                   |         |          \-German
                    \edge.3--|
                             |          /-Albanian
                              \edge.2--|
                                        \-French

Obviously, this method should not be used to avoid that experts code or check the cognates, but it may turn out to be very useful for studies that want to quickly explore the signal in a certain dataset, and check whether it is worthwhile to compare a given set of languages further. In the future, I hope that I will find time to add this implementation of the CCM method to the lingpy package, to make it even easier for interested scholars to use it on their data.

References

Dolgopolsky, A. (1964): Gipoteza drevnejšego rodstva jazykovych semej Severnoj Evrazii s verojatnostej točky zrenija [A probabilistic hypothesis concering the oldest relationships among the language families of Northern Eurasia]. Voprosy Jazykoznanija 2. 53-63.

Forkel, R., J.-M. List, S. Greenhill, C. Rzymski, S. Bank, M. Cysouw, H. Hammarström, M. Haspelmath, G. Kaiping, and R. Gray (forthcoming): Cross-Linguistic Data Formats, advancing data sharing and re-use in comparative linguistics. Scientific Data . .

Kassian, A., M. Zhivlov, and G. Starostin (2015): Proto-Indo-European-Uralic comparison from the probabilistic point of view. The Journal of Indo-European Studies 43.3-4. 301-347.

Kessler, B. (2001): The significance of word lists. Statistical tests for investigating historical connections between languages. CSLI Publications: Stanford.

List, J.-M. (2014): Sequence comparison in historical linguistics. Düsseldorf University Press: Düsseldorf.

List, J.-M., S. Greenhill, and R. Gray (2017): The potential of automatic word comparison for historical linguistics. PLOS ONE 12.1. 1-18.

List, J.-M. , M. Walworth, S. J.  Greenhill, T. Tresoldi, and R. Forkel (2018): Sequence comparison in computational historical linguisticsJournal of Language Evolution. 3 (2). 130-144.

Sokal, R. and C. Michener (1958): A statistical method for evaluating systematic relationships. University of Kansas Scientific Bulletin 28. 1409-1438. 2.3. 130-144.

Turchin, P., I. Peiros, and M. Gell-Mann (2010): Analyzing genetic connections between languages by matching consonant classes. Journal of Language Relationship 3. 117-126.

Cite this article as: Johann-Mattis List, "A fast implementation of the Consonant Class Matching method for automatic cognate detection in LingPy," in Computer-Assisted Language Comparison in Practice, 01/10/2018, https://calc.hypotheses.org/477.

Author: Johann-Mattis List

Seit Anfang 2017 bin ich leitender Wissenschaftler am Max-Planck-Institut für Menschheitsgeschichte in Jena, in der Abteilung für sprachliche und kulturelle Evolution. In meiner Forschung nehme ich generell einen datenbasierten, empirischen und quantitativen Standpunkt in Bezug auf Sprachwandel und Sprachgeschichte ein, mit einem speziellen Fokus auf südostasiatischen Sprachen. Im Gegensatz zu rein computerbasierten Ansätzen versuche ich jedoch, meine Forschung nah an der traditionellen historischen Linguistik und der linguistischen Theorie auszurichten, weshalb ich einen computer-gestützten Ansatz im Gegensatz zu einem rein computer-basierten Ansatz verfolge.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.