Understanding Artificial Intelligence
through Algorithmic Information Theory

    

Detecting Language Proximity through Compression

    

    

aiai.telecom-paris.fr

Excerpt1.png Excerpt2.png Intuitively, two texts T1 and T2, considered as mere strings, should share more information if they are written in the same language than when compared with a third text T3 written in a different language.
Excerpt3.png This is due to the greater redundancy if X and Y share many words.
Conditional complexity is the most natural way to measure information sharing. We expect:

    C(T1 | T2) << C(T1 | T3)
        C(T1 | T2) << C(T1 | T3)

For practical purposes, compression can be used as a proxy for complexity.
Using the Chain Rule, we can write:

        C(T1 | T2) > C(T1, T2) – C(T2)

Measuring the output of compressor Z as proxy for C and text concatenation instead of conjunction, we can estimate C(T1 | T2) by:

        length(Z(T1 + T2)) – length(Z(T2))
        length(Z(T1 + T2)) – length(Z(T2))

This measure of conditional complexity through joint compression may be used to represent the resemblance between objects such as texts.
        length(Z(T1 + T2)) – length(Z(T2))

LanguageTree.png In 2002, three scientists, Dario Benedetto, Emanuele Caglioti and Vittorio Loreto, were able to measure language proximity using a mere compressor such as Zip.

The language tree they could reconstruct with this estimate of conditional complexity matches the main language families that linguists stepwise developed during a century!
You might notice a couple of miclassifications, though.