Informaticus Paul Vitányi ziet zijn theorie in rap tempo praktijk worden.
Dit artikel is gepubliceerd in NRC Handelsblad, 8 september 2007
“Ik ben in eerste instantie theoretisch informaticus, maar in tweede instantie vind ik het geweldig als je die theorie kunt toepassen.”
Daarover heeft hij geen klagen, want het aantal toepassingen van zijn complexiteitstheorie is sinds het jaar 2000 wereldwijd explosief toegenomen. Het begon met een computerprogramma dat soorten op grond van hun DNA classificeert in een evolutionaire stamboom. Daarna volgden talen gerangschikt in taalbomen, muziekstukken geclassificeerd naar componist en literatuur geclusterd naar de schrijver. En dat allemaal zonder dat het programma ook maar een flauw benul heeft van muziek, literatuur of biologie. Zo onderscheidt de computer fragiele Chopin-sonates niet alleen van jazzy Miles Davis-beats, maar ook van meer verwante Debussy-composities, zonder iets te weten van ritmes, toonhoogten of melodie. De crux zit in een wiskundige vergelijking van de complexiteit van digitale bestanden.
Prof. dr. ir. Paul Vitányi (63) verdiept zich aan het Amsterdamse Centrum voor Wiskunde en Informatica (CWI) al drie decennia in de vraag hoe je de complexiteit van informatie en berekeningen zo precies mogelijk wiskundig beschrijft. En vervolgens in de vraag hoe computers slim kunnen redeneren met die complexe informatie. Ter ere van zijn werk organiseerde het CWI gisteren [vrijdag 7 september] een middag waarin drie toonaangevende collega-informatici, waaronder de Amerikaanse Turingprijswinnaar (een soort Nobelprijs voor de informatica) Andrew Yao lezingen hielden. Tevens ontving Vitányi tijdens het symposium een koninklijke onderscheiding: hij werd benoemd tot Ridder in de Orde van de Nederlandse Leeuw.
Samen met de Canadees Ming Li schreef Vitányi in 1993 de informaticabestseller Introduction to Kolmogorov complexity and its applications, waarvan begin 2008 de derde druk verschijnt. Als je beeld, geluid of tekst codeert in enen en nullen, dan is de Kolmogorovcomplexiteit de lengte van het kortste programma dat dat stuk informatie beschrijft. Stel dat je een bestand hebt bestaande uit honderdduizend nullen. Dan is het kortste programma om dit te beschrijven een stuk korter dan het oorspronkelijke bestand. Het kortste programma hoeft alleen maar te zeggen: ‘print honderdduizend nullen’. Dit bestand heeft een lage Kolmogorovcomplexiteit.
Maar als je honderdduizend maal een muntstuk opgooit, en achter elkaar noteert of je ‘kop’ (1) of ‘munt’ (0) krijgt, dan kun je het resultaat vrijwel nooit comprimeren. Het resultaat is zuivere willekeur. De kortste beschrijving is precies de oorspronkelijke reeks van nullen en enen – geen bit korter. Dan is de Kolmogorovcomplexiteit exact de lengte van de oorspronkelijke rij. De Rus Andrei Kolmogorov (1903-1987) dacht dat zijn wiskundige definitie onbruikbaar zou zijn, maar Vitányi, Li en anderen hebben laten zien dat het aantal toepassingen legio is.
Vitányi: “De Kolmogorovcomplexiteit is in de praktijk onberekenbaar. Maar het bijzondere is dat we hebben laten zien dat er toepassingen zijn waarvoor goede compressieprogramma’s een resultaat leveren dat waarschijnlijk nauwelijks afwijkt van de theoretische Kolmogorovwaarde.”
Lui
Paul Vitányi werd in 1944 geboren in Hongarije – “en dus ben ik automatisch niet-links” – uit een Hongaarse vader en een Nederlandse moeder. Op zijn tweede verhuisde hij naar Nederland. In de jaren vijftig en zestig waren het boeken als Giant brains (1949) van Edmund Callis Berkeley, het vertaalde Menselijk en machinaal denken (1964) van de Duitse ingenieur Karl Steinbuch en Cybernetics – Or the control and communication in the animal and the machine (1948) van de Amerikaanse wiskundige Norbert Wiener die hem intrigeerden.
“Cybernetica – dat wou ik studeren. Het dichtste wat daar in die tijd bij in de buurt kwam, was een studie elektrotechniek in Delft, met als specialisatie computers. Dat ging ik studeren. Maar ik was lui. Ik lag liever in bed dan ’s ochtends naar collega te gaan. En verplichte practica lopen vond ik ook erg vermoeiend. Na een tijdje dacht ik: ik kan beter wiskunde gaan doen, dan hoef ik helemaal geen colleges en practica meer te lopen. Dan kan ik gewoon thuis nadenken.”
Hij zou cum laude als wiskundige afgestudeerd zijn, ware het niet dat Delft – op de golf van de universitaire democratiseringsbeweging van de jaren zestig – het cum laude net had afgeschaft. Te elitair.
Van bescheidenheid heeft de Amsterdamse informaticus weinig last. Collega Ming Li zei in 2004 over Vitányi: “Paul heeft overal een sterke mening over, en met goede redenen.” Ronald de Wolf promoveerde 2001 cum laude bij Vitányi. Per e-mail laat hij vanuit Japan weten over zijn promotor: “Als mens is hij kleurrijk, erudiet, overal op de wereld geweest, kent iedereen, zit vol anekdotes en goede adviezen, sterke meningen, en dus niet altijd politiek correct.”
Anekdotes vertelt de flamboyante Vitányi inderdaad graag. “In 1969 studeerde ik nog in Delft. In mei van dat jaar zat ik een keer in Amsterdam buiten bier te drinken bij café Hoppe aan het Spui, toen ik opeens een boel studenten het Maagdenhuis zag binnengaan. Het begin van de Maagdenhuisbezetting. Het leek me leuk daar bij te zijn, en dus ben ik achter ze aan gegaan. Ik heb er twee dagen en nachten doorgebracht, maar toen was de bezetting nog bezig. Het probleem was dat ik in Delft een computer had gereserveerd voor mijn afstudeerwerk. Mijn afstudeerhoogleraar Van der Poel had voor zijn studenten een eigen computer. Heel uitzonderlijk in die tijd. Maar die moest je wel een paar weken van te voren reserveren. En dan mocht je er een paar uur op werken. Ik trok in het Maagdenhuis op met een paar sociologen. Het was allemaal erg amusant, maar ik wilde toch mijn programmeerwerk gaan doen. Dus zei ik tegen ze: ‘sorry, ik moet gaan, want ik heb een afspraak met een computer’. Dat vonden ze heel vreemd. Via een soort sluiproute kon ik uit het Maagdenhuis ontsnappen.”
Hij studeerde af op het terrein van de cellulaire automaten. Het was in die tijd dat hij voor de eerste en voor de laatste keer – hij vertelt het met zichtbare trots – een studieboek van kaft tot kaft las: het boek Theory of self-reproducing automata van John von Neumann. “In datzelfde jaar ’69 bracht ik mijn vakantie door op het Spaanse eilandje Formentera, naast Ibiza. Daar zaten toen veel feestende hippies. Ik lag daar een keer op het naaktstrand in dat boek te lezen, toen er een meisje langsliep en keek wat ik aan het lezen was. Ze schudde met haar hoofd en liep door. Nee, niet het boek dat ze daar verwachtte te zien.”
Zonder voorkennis
Het geheim van de clusterprogramma’s zit in een door Vitányi samen met Ming Li bedachte ‘universele maat van gelijkenis’. Deze berekent hoezeer digitale bestanden op elkaar lijken. Een computerprogramma comprimeert eerst alle bestanden. Vervolgens vergelijkt het paarsgewijs de gecomprimeerde bestanden met elkaar. Hoe meer twee bestanden op elkaar lijken, hoe kleiner het compressieprogramma de combinatie van beide kan opslaan. Tenslotte drukt het programma in een getal tussen 0 en 1 uit hoezeer het ene op het andere bestand lijkt. Aan de hand van die getallen wordt een boomstructuur gemaakt waarin bestanden die meer op elkaar lijken dichter bij elkaar in de boomstructuur zitten.
Hoe goed de methode werkt, wordt recentelijk systematisch onderzocht door haar resultaten te vergelijken met die van de best beschikbare dataminingtechnieken, die wél a-priori kennis op een vakgebied gebruiken. Vitányi: “En dan blijkt dat onze methode in het algemeen minstens even goed werkt, en dat ze zelfs veel beter presteert als er ineens gekke afwijkingen in de gegevens zitten. Andere programma’s zijn slecht in het herkennen daarvan, omdat ze van te voren gedefinieerde eigenschappen gebruiken. Onze methode gebruikt geen kennis vooraf. Dat is het cruciale. Of het nu gaat om talen, muziek, DNA of wat dan ook. Het maakt niet uit. En dat is vooral handig in gevallen waarbij je niet precies weet naar welke regelmaat je zoekt.”
Een Portugese medicus had vier jaar het hartritme van menselijke foetussen geanalyseerd. Toen zij lucht kreeg van Vitányi’s werk, bleek dat het programma in een mum van tijd met dezelfde conclusies kwam. En ten tijde van de SARS-uitbraak concludeerde het clusterprogramma dat SARS sterk verwant is aan het Corona-229-virus, een conclusie die de biologen met de jarenlang opgebouwde kennis van virussen ook stelden.
“Maar”, aldus Vitányi, “het is altijd maar afwachten hoe snel andere vakgebieden zulk theoretisch werk oppikken. Dat is de makke van abstracte wiskunde: hoe eenvoudig je zelf ook denkt dat het is, hoe helder je ook denkt het te hebben opgeschreven, voor niet-vakgenoten is het vaak heel moeilijk te geloven waarom het zou moeten werken. Tijdens de vogelgriepepidemie stuurden we enkele van onze resultaten over mutaties in het virus naar de groep van viroloog Ab Osterhaus in Rotterdam. ‘Hoe komen jullie daar aan?’ vroegen ze. ‘Tja, dat doet ons programma’, zeiden we. ‘Ja hallo, hoe weten we dat we daar op kunnen vertrouwen?’ was toen het antwoord.”
Een van de meest recente clustertoepassingen is het gebruik van zoekmachine Google als woordenboek om computers automatisch woorden te laten begrijpen. Samen met zijn promovendus Rudi Cilibrasi ontwikkelde Vitányi een afstandsmaat voor de betekenis van woorden. Zo levert het woord ‘horse’ 155 miljoen Google-hits op; het woord ‘rider’ 60 miljoen. Zoeken op pagina’s waarin beide woorden tegelijk voorkomen, levert 2,8 miljoen treffers. Uit die getallen kan worden berekend hoezeer ‘horse’ en ‘rider’ qua betekenis met elkaar in verband staan. Door een web van meer en minder verwante woorden te creëren, kunnen computers zo automatisch woorden begrijpen.
Typisch een methode voor Google zelf, zou je zeggen. “Ik weet niet of Google het al gebruikt”, zegt Vitányi. “Wel weet ik dat ze vijftien van mijn boeken over Kolmogorovcomplexiteit hebben besteld.”
Turingmachine
Wat betreft de toepassingen spreekt zijn werk over clustering het meest tot de verbeelding. Maar Vitányi’s interesse – zowel binnen als buiten de theoretische informatica – is breed. Ongeveer elke zeven jaar begon hij wel aan een nieuw terrein. Parallel rekenen, netwerkalgoritmen, de fysica van computing, machineleren, informatietheorie en quantumrekenen – hij heeft zich er allemaal in verdiept.
Zelf bewaart hij de dierbaarste herinneringen aan werk op meer esoterisch informaticaterrein. Zo bewees hij samen met collega Tao Jiang dat een Turingmachine die met twee leeskoppen een datatape afleest minstens zoveel kan berekenen als een Turingmachine die twee leeskoppen langs twee verschillende datatapes laat gaan – een per tape. Vitányi: “Die vraag stond al veertig jaar open. Het bewijs is het meest ingewikkelde bewijs met Kolmogorovcomplexiteit dat ik ooit heb gezien.”
Een goede neus voor baanbrekende nieuwe ontwikkelingen heeft hij ook. Toen de Amerikaan Peter Shor in 1994 op een congres zijn Shor-algoritme presenteerde als een mogelijke toepassing van de nog volstrekt hypothetische quantumcomputer, realiseerde Vitányi zich meteen dat dit de geboorte was van een nieuwe tak van wetenschap: het quantumrekenen. Terug op het CWI in Amsterdam heeft hij zich meteen ingespannen om een onderzoeksgroep op dit nieuwe terrein op te richten. “Als je als een van de eersten een nieuw terrein betreedt, dan kun je de grootste vruchten plukken.”
Hoogleraar Harry Buhrman is de huidige leider van de onderzoeksgroep Quantum Computing bij het CWI, en hij wekte als postdoc met Vitányi samen. “Paul is een van de weinige wetenschappers die ook op latere leeftijd nog altijd volop publiceert. Iemand die nog steeds gaat voor het onderzoek en niet voor het management.”
Bonje
In zijn e-mail over Vitányi laat Ronald de Wolf ook nog weten: “Als wetenschapper is hij vooruitstrevend. Hij heeft een goede neus voor interessante nieuwe richtingen. Hij is echt gericht op onderzoek en niet op politiek. Daardoor heeft hij wel vaak bonje met de bureaucratie.” Vitányi, die naast onderzoeker aan het CWI ook hoogleraar aan de Universiteit van Amsterdam (UvA) is, is zelf de eerste om zijn problemen met de regels-om-de-regels te beamen.
Hij vertelt over zijn Amerikaanse promovendus Rudi Cilibrasi: “Toen Rudi nog student was aan het California Institute of Technology, schreef hij me vanuit de VS een e-mail over een artikel van mij. Hij geloofde het bewijs dat ik daarin gaf in eerste instantie niet. Hij had het geprogrammeerd om te checken of het klopte. En inderdaad, zijn programma liet zien dat het bewijs klopte. Hij schreef verder dat hij na een bachelor van vier jaar aan CalTech erover zat te denken om een master in de logica in Amsterdam te doen. Maar ik dacht: iemand die dat moeilijke artikel zo goed snapt dat hij het ook nog kan programmeren, moet wel heel goed zijn. En dus bood ik hem een promotieplaats aan, die hij gelukkig aannam.”
Hij wil alleen maar briljante promovendi, zegt hij. Ook iets waar de universiteit niet zo blij mee is. Hij vervolgt zijn verhaal: “Cilibrasi deed prachtig werk, maar vlak voor de officiële promotie bleek dat het college van promoties van de UvA moeilijk deed over het feit je eigenlijk zonder een masterdiploma niet kunt promoveren. Wat een onzin, zei ik. Een vierjarig bachelordiploma van CalTech is toch zeker meer waard dan een masterdiploma van de UvA?! CalTech heeft tot nu toe 32 Nobelprijswinnaars gehad, het dubbele van heel Nederland! Ik heb volgehouden en na veel gesteggel kon hij toch promoveren.”
Kick
Vitányi heeft nog twee jaar te gaan tot zijn pensioen. Maar van ophouden na zijn 65e wil hij niet weten, zelfs niet nadat hij in 2006 door een herseninfarct werd getroffen. “De schade is puur motorisch, aan de rechterkant van mijn lichaam. Het heeft gelukkig geen invloed op mijn denken. En dus wil ik doorwerken. Ik werk aan de derde druk van mijn boek, en er moet nog een aantal artikelen de deur uit.”
Hij kan de toepassingen zijn werk niet meer allemaal bijhouden. “Maar ik weet bijvoorbeeld dat MIT-onderzoekers het recent zijn gaan gebruiken voor onderzoek naar de voorspelling van orkanen, Stanford-onderzoekers voor het voorspellen van aardbevingen en bio-informatici gebruiken het voor het vergelijken van DNA-strengen.”
Behalve voor het vergelijken van bestanden, maakt ook het comprimeren van individuele bestanden meer en meer gebruik van Kolmogorovcomplexiteit. MPEG-4, de op stapel staande opvolger van het bekende MPEG-3-formaat, gaat expliciet de theorie van de Kolmogorovcomplexiteit gebruiken. Vitányi: “Voor een theoreticus is het een enorme kick om te zien dat al een paar jaar na de theorie de toepassingen zo’n enorme vlucht nemen.”
Dit artikel is gepubliceerd in NRC Handelsblad, 8 september 2007
“Ik ben in eerste instantie theoretisch informaticus, maar in tweede instantie vind ik het geweldig als je die theorie kunt toepassen.”
Daarover heeft hij geen klagen, want het aantal toepassingen van zijn complexiteitstheorie is sinds het jaar 2000 wereldwijd explosief toegenomen. Het begon met een computerprogramma dat soorten op grond van hun DNA classificeert in een evolutionaire stamboom. Daarna volgden talen gerangschikt in taalbomen, muziekstukken geclassificeerd naar componist en literatuur geclusterd naar de schrijver. En dat allemaal zonder dat het programma ook maar een flauw benul heeft van muziek, literatuur of biologie. Zo onderscheidt de computer fragiele Chopin-sonates niet alleen van jazzy Miles Davis-beats, maar ook van meer verwante Debussy-composities, zonder iets te weten van ritmes, toonhoogten of melodie. De crux zit in een wiskundige vergelijking van de complexiteit van digitale bestanden.
Prof. dr. ir. Paul Vitányi (63) verdiept zich aan het Amsterdamse Centrum voor Wiskunde en Informatica (CWI) al drie decennia in de vraag hoe je de complexiteit van informatie en berekeningen zo precies mogelijk wiskundig beschrijft. En vervolgens in de vraag hoe computers slim kunnen redeneren met die complexe informatie. Ter ere van zijn werk organiseerde het CWI gisteren [vrijdag 7 september] een middag waarin drie toonaangevende collega-informatici, waaronder de Amerikaanse Turingprijswinnaar (een soort Nobelprijs voor de informatica) Andrew Yao lezingen hielden. Tevens ontving Vitányi tijdens het symposium een koninklijke onderscheiding: hij werd benoemd tot Ridder in de Orde van de Nederlandse Leeuw.
Samen met de Canadees Ming Li schreef Vitányi in 1993 de informaticabestseller Introduction to Kolmogorov complexity and its applications, waarvan begin 2008 de derde druk verschijnt. Als je beeld, geluid of tekst codeert in enen en nullen, dan is de Kolmogorovcomplexiteit de lengte van het kortste programma dat dat stuk informatie beschrijft. Stel dat je een bestand hebt bestaande uit honderdduizend nullen. Dan is het kortste programma om dit te beschrijven een stuk korter dan het oorspronkelijke bestand. Het kortste programma hoeft alleen maar te zeggen: ‘print honderdduizend nullen’. Dit bestand heeft een lage Kolmogorovcomplexiteit.
Maar als je honderdduizend maal een muntstuk opgooit, en achter elkaar noteert of je ‘kop’ (1) of ‘munt’ (0) krijgt, dan kun je het resultaat vrijwel nooit comprimeren. Het resultaat is zuivere willekeur. De kortste beschrijving is precies de oorspronkelijke reeks van nullen en enen – geen bit korter. Dan is de Kolmogorovcomplexiteit exact de lengte van de oorspronkelijke rij. De Rus Andrei Kolmogorov (1903-1987) dacht dat zijn wiskundige definitie onbruikbaar zou zijn, maar Vitányi, Li en anderen hebben laten zien dat het aantal toepassingen legio is.
Vitányi: “De Kolmogorovcomplexiteit is in de praktijk onberekenbaar. Maar het bijzondere is dat we hebben laten zien dat er toepassingen zijn waarvoor goede compressieprogramma’s een resultaat leveren dat waarschijnlijk nauwelijks afwijkt van de theoretische Kolmogorovwaarde.”
Lui
Paul Vitányi werd in 1944 geboren in Hongarije – “en dus ben ik automatisch niet-links” – uit een Hongaarse vader en een Nederlandse moeder. Op zijn tweede verhuisde hij naar Nederland. In de jaren vijftig en zestig waren het boeken als Giant brains (1949) van Edmund Callis Berkeley, het vertaalde Menselijk en machinaal denken (1964) van de Duitse ingenieur Karl Steinbuch en Cybernetics – Or the control and communication in the animal and the machine (1948) van de Amerikaanse wiskundige Norbert Wiener die hem intrigeerden.
“Cybernetica – dat wou ik studeren. Het dichtste wat daar in die tijd bij in de buurt kwam, was een studie elektrotechniek in Delft, met als specialisatie computers. Dat ging ik studeren. Maar ik was lui. Ik lag liever in bed dan ’s ochtends naar collega te gaan. En verplichte practica lopen vond ik ook erg vermoeiend. Na een tijdje dacht ik: ik kan beter wiskunde gaan doen, dan hoef ik helemaal geen colleges en practica meer te lopen. Dan kan ik gewoon thuis nadenken.”
Hij zou cum laude als wiskundige afgestudeerd zijn, ware het niet dat Delft – op de golf van de universitaire democratiseringsbeweging van de jaren zestig – het cum laude net had afgeschaft. Te elitair.
Van bescheidenheid heeft de Amsterdamse informaticus weinig last. Collega Ming Li zei in 2004 over Vitányi: “Paul heeft overal een sterke mening over, en met goede redenen.” Ronald de Wolf promoveerde 2001 cum laude bij Vitányi. Per e-mail laat hij vanuit Japan weten over zijn promotor: “Als mens is hij kleurrijk, erudiet, overal op de wereld geweest, kent iedereen, zit vol anekdotes en goede adviezen, sterke meningen, en dus niet altijd politiek correct.”
Anekdotes vertelt de flamboyante Vitányi inderdaad graag. “In 1969 studeerde ik nog in Delft. In mei van dat jaar zat ik een keer in Amsterdam buiten bier te drinken bij café Hoppe aan het Spui, toen ik opeens een boel studenten het Maagdenhuis zag binnengaan. Het begin van de Maagdenhuisbezetting. Het leek me leuk daar bij te zijn, en dus ben ik achter ze aan gegaan. Ik heb er twee dagen en nachten doorgebracht, maar toen was de bezetting nog bezig. Het probleem was dat ik in Delft een computer had gereserveerd voor mijn afstudeerwerk. Mijn afstudeerhoogleraar Van der Poel had voor zijn studenten een eigen computer. Heel uitzonderlijk in die tijd. Maar die moest je wel een paar weken van te voren reserveren. En dan mocht je er een paar uur op werken. Ik trok in het Maagdenhuis op met een paar sociologen. Het was allemaal erg amusant, maar ik wilde toch mijn programmeerwerk gaan doen. Dus zei ik tegen ze: ‘sorry, ik moet gaan, want ik heb een afspraak met een computer’. Dat vonden ze heel vreemd. Via een soort sluiproute kon ik uit het Maagdenhuis ontsnappen.”
Hij studeerde af op het terrein van de cellulaire automaten. Het was in die tijd dat hij voor de eerste en voor de laatste keer – hij vertelt het met zichtbare trots – een studieboek van kaft tot kaft las: het boek Theory of self-reproducing automata van John von Neumann. “In datzelfde jaar ’69 bracht ik mijn vakantie door op het Spaanse eilandje Formentera, naast Ibiza. Daar zaten toen veel feestende hippies. Ik lag daar een keer op het naaktstrand in dat boek te lezen, toen er een meisje langsliep en keek wat ik aan het lezen was. Ze schudde met haar hoofd en liep door. Nee, niet het boek dat ze daar verwachtte te zien.”
Zonder voorkennis
Het geheim van de clusterprogramma’s zit in een door Vitányi samen met Ming Li bedachte ‘universele maat van gelijkenis’. Deze berekent hoezeer digitale bestanden op elkaar lijken. Een computerprogramma comprimeert eerst alle bestanden. Vervolgens vergelijkt het paarsgewijs de gecomprimeerde bestanden met elkaar. Hoe meer twee bestanden op elkaar lijken, hoe kleiner het compressieprogramma de combinatie van beide kan opslaan. Tenslotte drukt het programma in een getal tussen 0 en 1 uit hoezeer het ene op het andere bestand lijkt. Aan de hand van die getallen wordt een boomstructuur gemaakt waarin bestanden die meer op elkaar lijken dichter bij elkaar in de boomstructuur zitten.
Hoe goed de methode werkt, wordt recentelijk systematisch onderzocht door haar resultaten te vergelijken met die van de best beschikbare dataminingtechnieken, die wél a-priori kennis op een vakgebied gebruiken. Vitányi: “En dan blijkt dat onze methode in het algemeen minstens even goed werkt, en dat ze zelfs veel beter presteert als er ineens gekke afwijkingen in de gegevens zitten. Andere programma’s zijn slecht in het herkennen daarvan, omdat ze van te voren gedefinieerde eigenschappen gebruiken. Onze methode gebruikt geen kennis vooraf. Dat is het cruciale. Of het nu gaat om talen, muziek, DNA of wat dan ook. Het maakt niet uit. En dat is vooral handig in gevallen waarbij je niet precies weet naar welke regelmaat je zoekt.”
Een Portugese medicus had vier jaar het hartritme van menselijke foetussen geanalyseerd. Toen zij lucht kreeg van Vitányi’s werk, bleek dat het programma in een mum van tijd met dezelfde conclusies kwam. En ten tijde van de SARS-uitbraak concludeerde het clusterprogramma dat SARS sterk verwant is aan het Corona-229-virus, een conclusie die de biologen met de jarenlang opgebouwde kennis van virussen ook stelden.
“Maar”, aldus Vitányi, “het is altijd maar afwachten hoe snel andere vakgebieden zulk theoretisch werk oppikken. Dat is de makke van abstracte wiskunde: hoe eenvoudig je zelf ook denkt dat het is, hoe helder je ook denkt het te hebben opgeschreven, voor niet-vakgenoten is het vaak heel moeilijk te geloven waarom het zou moeten werken. Tijdens de vogelgriepepidemie stuurden we enkele van onze resultaten over mutaties in het virus naar de groep van viroloog Ab Osterhaus in Rotterdam. ‘Hoe komen jullie daar aan?’ vroegen ze. ‘Tja, dat doet ons programma’, zeiden we. ‘Ja hallo, hoe weten we dat we daar op kunnen vertrouwen?’ was toen het antwoord.”
Een van de meest recente clustertoepassingen is het gebruik van zoekmachine Google als woordenboek om computers automatisch woorden te laten begrijpen. Samen met zijn promovendus Rudi Cilibrasi ontwikkelde Vitányi een afstandsmaat voor de betekenis van woorden. Zo levert het woord ‘horse’ 155 miljoen Google-hits op; het woord ‘rider’ 60 miljoen. Zoeken op pagina’s waarin beide woorden tegelijk voorkomen, levert 2,8 miljoen treffers. Uit die getallen kan worden berekend hoezeer ‘horse’ en ‘rider’ qua betekenis met elkaar in verband staan. Door een web van meer en minder verwante woorden te creëren, kunnen computers zo automatisch woorden begrijpen.
Typisch een methode voor Google zelf, zou je zeggen. “Ik weet niet of Google het al gebruikt”, zegt Vitányi. “Wel weet ik dat ze vijftien van mijn boeken over Kolmogorovcomplexiteit hebben besteld.”
Turingmachine
Wat betreft de toepassingen spreekt zijn werk over clustering het meest tot de verbeelding. Maar Vitányi’s interesse – zowel binnen als buiten de theoretische informatica – is breed. Ongeveer elke zeven jaar begon hij wel aan een nieuw terrein. Parallel rekenen, netwerkalgoritmen, de fysica van computing, machineleren, informatietheorie en quantumrekenen – hij heeft zich er allemaal in verdiept.
Zelf bewaart hij de dierbaarste herinneringen aan werk op meer esoterisch informaticaterrein. Zo bewees hij samen met collega Tao Jiang dat een Turingmachine die met twee leeskoppen een datatape afleest minstens zoveel kan berekenen als een Turingmachine die twee leeskoppen langs twee verschillende datatapes laat gaan – een per tape. Vitányi: “Die vraag stond al veertig jaar open. Het bewijs is het meest ingewikkelde bewijs met Kolmogorovcomplexiteit dat ik ooit heb gezien.”
Een goede neus voor baanbrekende nieuwe ontwikkelingen heeft hij ook. Toen de Amerikaan Peter Shor in 1994 op een congres zijn Shor-algoritme presenteerde als een mogelijke toepassing van de nog volstrekt hypothetische quantumcomputer, realiseerde Vitányi zich meteen dat dit de geboorte was van een nieuwe tak van wetenschap: het quantumrekenen. Terug op het CWI in Amsterdam heeft hij zich meteen ingespannen om een onderzoeksgroep op dit nieuwe terrein op te richten. “Als je als een van de eersten een nieuw terrein betreedt, dan kun je de grootste vruchten plukken.”
Hoogleraar Harry Buhrman is de huidige leider van de onderzoeksgroep Quantum Computing bij het CWI, en hij wekte als postdoc met Vitányi samen. “Paul is een van de weinige wetenschappers die ook op latere leeftijd nog altijd volop publiceert. Iemand die nog steeds gaat voor het onderzoek en niet voor het management.”
Bonje
In zijn e-mail over Vitányi laat Ronald de Wolf ook nog weten: “Als wetenschapper is hij vooruitstrevend. Hij heeft een goede neus voor interessante nieuwe richtingen. Hij is echt gericht op onderzoek en niet op politiek. Daardoor heeft hij wel vaak bonje met de bureaucratie.” Vitányi, die naast onderzoeker aan het CWI ook hoogleraar aan de Universiteit van Amsterdam (UvA) is, is zelf de eerste om zijn problemen met de regels-om-de-regels te beamen.
Hij vertelt over zijn Amerikaanse promovendus Rudi Cilibrasi: “Toen Rudi nog student was aan het California Institute of Technology, schreef hij me vanuit de VS een e-mail over een artikel van mij. Hij geloofde het bewijs dat ik daarin gaf in eerste instantie niet. Hij had het geprogrammeerd om te checken of het klopte. En inderdaad, zijn programma liet zien dat het bewijs klopte. Hij schreef verder dat hij na een bachelor van vier jaar aan CalTech erover zat te denken om een master in de logica in Amsterdam te doen. Maar ik dacht: iemand die dat moeilijke artikel zo goed snapt dat hij het ook nog kan programmeren, moet wel heel goed zijn. En dus bood ik hem een promotieplaats aan, die hij gelukkig aannam.”
Hij wil alleen maar briljante promovendi, zegt hij. Ook iets waar de universiteit niet zo blij mee is. Hij vervolgt zijn verhaal: “Cilibrasi deed prachtig werk, maar vlak voor de officiële promotie bleek dat het college van promoties van de UvA moeilijk deed over het feit je eigenlijk zonder een masterdiploma niet kunt promoveren. Wat een onzin, zei ik. Een vierjarig bachelordiploma van CalTech is toch zeker meer waard dan een masterdiploma van de UvA?! CalTech heeft tot nu toe 32 Nobelprijswinnaars gehad, het dubbele van heel Nederland! Ik heb volgehouden en na veel gesteggel kon hij toch promoveren.”
Kick
Vitányi heeft nog twee jaar te gaan tot zijn pensioen. Maar van ophouden na zijn 65e wil hij niet weten, zelfs niet nadat hij in 2006 door een herseninfarct werd getroffen. “De schade is puur motorisch, aan de rechterkant van mijn lichaam. Het heeft gelukkig geen invloed op mijn denken. En dus wil ik doorwerken. Ik werk aan de derde druk van mijn boek, en er moet nog een aantal artikelen de deur uit.”
Hij kan de toepassingen zijn werk niet meer allemaal bijhouden. “Maar ik weet bijvoorbeeld dat MIT-onderzoekers het recent zijn gaan gebruiken voor onderzoek naar de voorspelling van orkanen, Stanford-onderzoekers voor het voorspellen van aardbevingen en bio-informatici gebruiken het voor het vergelijken van DNA-strengen.”
Behalve voor het vergelijken van bestanden, maakt ook het comprimeren van individuele bestanden meer en meer gebruik van Kolmogorovcomplexiteit. MPEG-4, de op stapel staande opvolger van het bekende MPEG-3-formaat, gaat expliciet de theorie van de Kolmogorovcomplexiteit gebruiken. Vitányi: “Voor een theoreticus is het een enorme kick om te zien dat al een paar jaar na de theorie de toepassingen zo’n enorme vlucht nemen.”
