Feature-Based Alignment Analyses with LingPy and CLTS (2)

Having seen how we can obtain a simple scorer derived from the feature system in CLTS (List et al. 2019) in last month’s post, what is missing now, in order to use the scorer for alignment analyses, is an alignment function which can take the scorer as an argument. If one does not have higher ambitions with respect to the alignment function itself, this step can be achieved in a very straightforward way with help of LingPy’s (List et al. 2018) nw_align() or sw_align() method. As can be seen from the documentation, this method takes as input two sequences (i.e., lists of sounds), along with a scoring function. Obviously, all we need to do now is to create our specific scorer based on the CLTS features, and then pass this scoring function along with our sequences to the function.

Let’s test this by writing a small function that takes two sequences as input and then (a) creates the scorer using the procedure we illustrated in the preceding post, and (b) aligns the sequences, using either the Needleman-Wunsch algorithm (Needleman and Wunsch 1970) for global alignment, or the Smith-Waterman algorithm (Smith and Waterman 1981) for local alignment. We start by importing the malign package of LingPy which offers simple alignment methods, as well as LingPy proper, and adding this to the start of our file features.py which we used last time.

from lingpy.algorithm.cython import malign

We can now define our alignment function. Following general LingPy nomenclature, we distinguish between global and local alignment as different alignment modes (see List 2014 for details on alignment modes). We just write this function below the functions for scoring elements and for creating the scorer in our script.

def feature_align(seqA, seqB, mode='global', gap=-1): 
    if mode == 'global': 
        align = malign.nw_align 
    elif mode == 'local': 
        align = malign.sw_align
    scorer = get_scorer(list(set(seqA+seqB)))
    return align(seqA, seqB, scorer, gap)

In order to run this function, we must input the data as a list. This can be done by splitting IPA sequences with help of LingPy’s ipa2tokens function, or by using software specifically devoted to segmentation, such as the segments package, that uses orthography profiles to split data into segments (Mora and Cysouw 2018), of which I recently produced a JavaScript version for demonstration purposes, called SegmentsJS.

For a first test, we simply segment the data directly.

seqA = 'tʰ ɔ x t ɐ'.split()
seqB = 'd ɔː t ə r'.split()
almA, almB, score = feature_align(seqA, seqB)
print('\t'.join(almA))
print('\t'.join(almB))
print('{0:.2f}'.format(score))

From the output, we can see, that the method correctly aligns the two sequences.

tʰ  ɔ   x   t   ɐ   -
d   ɔː  -   t   ə   r
-1.00

What you may find to be strange is the negative score for this alignment. But as the alignment itself is correct, we do not need to worry about this too much. The alignment has two gaps, and our gap penalty is -1. This will result in a score of -2 for the gaps alone. Since each perfect match scores with 1 as well, and we have only one perfect match, the rest of the scores cannot outweigh the penalties introduced by the gap score. This shows, as we will try to look at in a follow-up post, that we need to re-design our scoring function to account more properly for the specific needs of alignment algorithms.

But let us now make a general test of the feature-based alignment method by using it to align all the sequences in a benchmark. Here, we use the benchmark proposed by Covington (1996), which is available from the Benchmark Database of Phonetic Alignments (BDPA, List and Prokić 2014). We use this dataset for convenience, because it is small, and can therefore easily be added to a GitHub Gist repository. Interested users can easily obtain the more elaborated and larger benchmark data from the BDPA and test the algorithm on more and more challenging datasets.

To load the data from the benchmark, we first download the data and extract the file covington.psa, which contains the alignments in the “PSA” format that LingPy uses for partial alignments. This format is outdated for different reasons. First, because the main interest of LingPy’s algorithms has now shifted to cognate detection and multiple alignments, and pairwise alignments are no more considered the key task of the library. Second, with new standards such as CLDF (Forkel et al. 2018), we are generally re-evaluating the usefulness of formats that are too idiosyncratic. Third, with LingPy’s wordlist format, that has been offering for a long time now the possibility to store multiple alignments, and to also edit them with the EDICTOR tool (List 2017), we do no longer need specific formats, but could render the same data without problem in a multi-lingual wordlist, even if it only consists of aligned pairs.
But since LingPy has not yet abandoned the PSA format and can readily read it, we can use it now to read in the file, align the data, and check if the alignment matches the gold standard. To evaluate the alignments, we simply score the number of perfect alignments which are identical with the gold standard.

psa = PSA('covington.psa')
scores = []
for i, (seqA, seqB) in enumerate(psa.tokens):
almA, almB, score = feature_align(seqA, seqB)
if almA == psa.alignments[i][0] and almB == psa.alignments[i][1]:
    scores += [1]
else:
    scores += [0]
print('{0:.2f}'.format(sum(scores)/len(scores)))

As we can see from the output, the algorithm reaches a score of 0.82, that is, 82% of the alignments are identical with the gold standard. In total, these are 67 out of 82 alignments in the benchmark. With this score, the feature-based alignment in this form shows a very mediocre performance, as we can see when comparing with scores reported for other alignment algorithms, specifically SCA (List 2014) with 80 perfect alignments (98%), Kondrak’s ALINE (Kondrak 2000 with 78 perfect alignments (95%), or Covington’s algorithm (1996) with 68.8 perfect alignments (84%).

From these results, we can thus see what was already mentioned in last month’s post: by simply computing the Hamming distances of distinctive feature systems, we do not necessarily arrive at linguistically meaningful alignments, similarities, or distances. In a follow-up blog post, I will try to show what we can do to cope with the problems introduced by naive Hamming distances for feature vectors. The code accompanying this post is again available in form of a GitHub Gist repository.

References

List, Johann-Mattis and Anderson, Cormac and Tresoldi, Tiago and Rzymski, Christoph and Greenhill, Simon and Forkel, Robert (2019): Cross-Linguistic Transcription Systems. Jena:Max Planck Institute for the Science of Human History.

Covington, Michael A. (1996): An algorithm to align words for historical comparison. Computational Linguistics 22.4. 481-496.

Forkel, Robert and List, Johann-Mattis and Greenhill, Simon J. and Rzymski, Christoph and Bank, Sebastian and Cysouw, Michael and Hammarström, Harald and Haspelmath, Martin and Kaiping, Gereon A. and Gray, Russell D. (2018): Cross-Linguistic Data Formats, advancing data sharing and re-use in comparative linguistics. Scientific Data 5.180205. 1-10.

Kondrak, Grzegorz (2000): A new algorithm for the alignment of phonetic sequences. In: Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. 288-295.

List, Johann-Mattis and Greenhill, Simon and Tresoldi, Tiago and Forkel, Robert (2018): LingPy. A Python library for quantitative tasks in historical linguistics. Version 2.6.4. Max Planck Institute for the Science of Human History. Jena: http://lingpy.org.

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

List, J.-M. and Prokić, Jel (2014): A benchmark database of phonetic alignments in historical linguistics and dialectology. In: Proceedings of the Ninth International Conference on Language Resources and Evaluation. 288-294.

List, Johann-Mattis (2017): A web-based interactive tool for creating, inspecting, editing, and publishing etymological datasets. In: Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics. System Demonstrations. 9-12.

Moran, Steven and Cysouw, Michael (2018): The Unicode Cookbook for Linguists: Managing writing systems using orthography profiles. Berlin:Language Science Press.

Needleman, Saul B. and Wunsch, Christan D. (1970): A gene method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48. 443-453.

Smith, T. F. and Waterman, M. S. (1981): Identification of common molecular subsequences. Journal of Molecular Biology 1. 195-197.

Cite this article as: Johann-Mattis List, "Feature-Based Alignment Analyses with LingPy and CLTS (2)," in Computer-Assisted Language Comparison in Practice, 16/09/2019, https://calc.hypotheses.org/1971.

This entry was posted in Code and tagged , , on by .

About 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.