QED

Op 7 september van dit jaar werd prof. dr. Paul Vitányi van het CWI tot Ridder in de Orde van de Nederlandse Leeuw benoemd. Professor Johan van Benthem van de UvA zei toen over hem:

Een dergelijk veelzijdig talent, waarbij een diep theoreticus meteen tot een innovatieve praktijk weet te komen is schaars, en dient gekoesterd te worden in een kenniseconomie als de onze.

Net de dag tevoren had ik besloten om een artikel voor PC-Active te schrijven over de theoretische concepten waarin Vitányi specialist is: Kolmogorov-complexiteit en informatie-afstand. Ik wilde in dit artikel vooral laten zien dat deze fundamentele concepten heel wat praktische toepassingen hebben. Het artikel uit mijn Denkwerk-rubriek is nu gepubliceerd in het decembernummer dat sinds vrijdag in de winkel ligt.

In het artikel bespreek ik vooral het werk van Ming Li, Paul Vitányi en Rudi Cilibrasi. In 2003 haalden zij de pers met het nieuws dat een compressieprogramma volstaat om het verschil tussen klassieke muziek, jazz en rock te herkennen. Dezelfde techniek laat echter ook toe om de auteurs van teksten te herkennen of de oorsprong van verschillende talen te onderzoeken. Iedereen kan zelf ook toepassingen uitproberen met de software CompLearn van Cilibrasi, die gratis te downloaden is voor Windows en Linux. De software heeft ook een online demo.

Het leuke aan dit onderzoek is dat je het kan illustreren met programma’s die iedere computergebruiker kent: compressieprogramma’s zoals Winzip om bestanden te verkleinen. De Kolmogorov-complexiteit van een reeks tekens is immers de theoretische ondergrens van mogelijke compressies: geen enkel bestaand of nog te ontwikkelen compressieprogramma kan beter comprimeren. We kunnen de Kolmogorov-complexiteit van een tekenreeks echter nooit perfect berekenen. Als we in de praktijk willen gebruik maken van de Kolmogorov-complexiteit, kunnen we ze dus benaderen door bestaande compressie-algoritmes, zoals WinZip onder Windows en gzip of bzip2 onder Linux. Op basis van de Kolmogorov-complexiteit van twee tekenreeksen kunnen we de informatie-afstand berekenen: een maat voor de gelijkenis tussen de twee reeksen. Wanneer we hier de complexiteit benaderen door compressie, bekomen we de compressie-afstand.

Op deze manier kan je automatisch de taal van een tekst achterhalen. Daarvoor moeten we beginnen met een verzameling van lange tekstbestanden, elk in een taal die we kennen. We comprimeren al deze bestanden en noteren de lengte van elk gecomprimeerd bestand. Daarna introduceren we een nieuw tekstbestand in een nog niet bepaalde taal. We voegen dit bestand toe aan elk van de ongecomprimeerde tekstbestanden met de bekende talen en comprimeren het resultaat. We noteren het verschil dat het toevoegen van het onbekende bestand aan elk bestand oplevert bij compressie.

Hoe kleiner het verschil, hoe waarschijnlijker de talen identiek zijn. Het compressieprogramma maakt namelijk gebruik van tekstsequenties die meerdere keren voorkomen om ze compacter voor te stellen. Wanneer we een tekst in het Engels toevoegen aan een andere tekst in het Engels, kan het compressieprogramma daardoor het bestand efficiënter comprimeren dan een Nederlandse tekst toegevoegd aan een Engelse.

Op dezelfde manier kunnen we bestandsformaten herkennen, de auteurs van teksten, muziekgenres, de componisten van muziek, de betekenis van woorden en gelijkenissen tussen DNA van verschillende diersoorten. Zelfs plagiaat kunnen we zo opsporen. In het artikel in PC-Active bespreek ik uitgebreid deze toepassingen. Hieronder vind je een door Complearn gegenereerde boomvoorstelling van de gelijkenissen tussen alle artikels die ik voor PC-Active geschreven heb en een aantal artikels voor Linux Magazine en NetOpus. Klik erop voor een gedetailleerde weergave:

We zien duidelijk dat mijn artikels met Linux-nieuws afgescheiden zijn van mijn Denkwerk-artikels. De artikels voor NetOpus staan ook in hun eigen regio. De twee artikels over kunstmatige intelligentie staan tussen de Denkwerk-artikels. Inhoudelijk, vormelijk en qua lengte komen die artikels inderdaad dicht bij mijn Denkwerk-artikels, dus dat kan kloppen. Ze staan zelfs vlakbij het Denkwerk-artikel over Deep Fritz, een onderwerp dat dicht bij AI aanleunt. We zien overigens dat de twee artikels over AI aan dezelfde knoop hangen, evenals de twee Denkwerk-artikels over A New Kind of Science en de twee Denkwerk-artikels over kwantumcomputers. En dat allemaal wordt automatisch berekend zonder semantische analyse van de teksten. Een mooie praktische en verrassende toepassing van diepe theoretische concepten. In PC-Active vind je meer van dat soort boomvoorstellingen.