Een computer kan niet álles leren

Wiskunde Er zitten grenzen aan de voorspellingskracht van kunstmatige intelligentie. Dat schrijven wiskundigen op theoretische gronden.

Illustratie Rik van Schagen

Harry Mulisch wentelde zich graag in de bètawetenschappen. In zijn roman De ontdekking van de hemel komt het werk van de Duitse wiskundige Georg Cantor naar voren: hoofdpersoon Max Delius had zich „als student een tijdje beziggehouden met diens schokkende theorie van de transfiniete kardinaalgetallen, het oneindige aantal voltooid oneindige getallen”. Vervolgens laat Mulisch zijn lezers die de betekenis van deze geleerde woorden willen weten echter in de steek. Dat geeft niet, want een roman is geen leerboek wiskunde.

Ook een krantenstuk is dat niet, maar wie iets wil begrijpen van het werk van vijf wetenschappers dat begin dit jaar verscheen in Nature Machine Intelligence, over ‘onbeslisbaarheid in machine learning’, moet beginnen bij de oneindigheden van Cantor. Kunstmatige intelligentie kan niet voor alle problemen een passende oplossing bieden, schrijven de wetenschappers, en dat is precies het probleem waar Cantor in de negentiende eeuw op stuitte.

Punten op een lijn

In 1873 stuurde Georg Cantor zijn collega Richard Dedekind een brief waarin hij vroeg hoeveel punten er op een lijn liggen. Oneindig veel, dat was duidelijk, maar dit antwoord was voor Cantor niet precies genoeg. Hij wilde weten of de verzameling punten op een lijn ‘even groot’ of ‘groter’ is dan de verzameling natuurlijke getallen (1, 2, 3 enzovoorts). In het licht van de oneindigheid lijkt het vreemd om onderscheid te maken tussen ‘even groot’ en ‘groter’, maar Cantor definieerde ‘even groot’ ondubbelzinnig: twee verzamelingen zijn ‘even groot’ als de elementen ervan een-op-een aan elkaar gekoppeld kunnen worden.

Cantor hoefde niet op Dedekinds antwoord te wachten. Hij zag zelf in dat een lijn meer punten bevat dan dat er natuurlijke getallen zijn. Na deze ontdekking was de vraag: hoevéél groter dan de verzameling natuurlijke getallen is de verzameling punten op een lijn? Volgt een continuüm van punten wat betreft grootte direct op de verzameling natuurlijke getallen? Of zit er nog een verzameling tussen, een oneindige verzameling die groter is dan die van de natuurlijke getallen, maar kleiner dan een continuüm?

Cantor dacht dat verzamelingen die er qua grootte tussenin zitten, niet bestaan. Het lukte hem echter niet te bewijzen dat de oneindigheidsorde van een continuüm onmiddellijk volgt op de oneindigheidsorde van de verzameling natuurlijke getallen. Cantors vermoeden kwam bekend te staan als de continuümhypothese.

Wegwijzer voor wiskundigen

In 1900 legde de Duitse wiskundige David Hilbert bij een lezing tijdens het Internationaal Congres van Wiskundigen in Parijs zijn publiek 23 onopgeloste problemen voor – een soort wegwijzer voor wiskundigen in de nieuwe eeuw. Hilberts eerste vraag was: bewijs (of weerleg) de continuümhypothese. Het probleem was alleen: op basis van wat?

De verzamelingenleer van Cantor en Dedekind stond nog in de kinderschoenen en was nog niet van een degelijk wiskundig fundament voorzien. Zoals Euclides ruim tweeduizend jaar eerder axioma’s voor de meetkunde had opgesteld, deden Ernst Zermelo en Abraham Fraenkel dat voor de verzamelingenleer. Die axioma’s bevatten niets schokkends. Voorbeelden zijn: ‘twee verzamelingen zijn gelijk indien ze dezelfde elementen bevatten’ en ‘er bestaat een verzameling zonder elementen’.

Kon iemand er nu in slagen de continuümhypothese op basis van dit axiomasysteem te bewijzen? Het antwoord bleek nee te zijn: voortbouwend op werk van de beroemde logicus Kurt Gödel toonde de Amerikaan Paul Cohen in 1963 aan dat de hypothese onafhankelijk is van de axioma’s. Dat betekende dat zowel de acceptatie als de ontkenning van de continuümhypothese op een consistente wijze als nieuw axioma kon worden toegevoegd aan de bestaande axioma’s.

Advertenties als punten op een lijn

De axioma’s van Zermelo en Fraenkel vormen het fundament van de gehele moderne wiskunde, inclusief al haar toepassingen. Daaronder valt ook de machine learning, het onderzoeksveld dat draait om ‘zelflerende’ algoritmen. Begin dit jaar schreven vijf wetenschappers in de eerste aflevering van het nieuwe online magazine Nature Machine Learning dat ‘leerbaarheid’, net als de continuümhypothese, onbeslisbaar kán zijn.

In hun artikel lichten Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka en Amir Yehudayoff hun werk toe aan de hand van advertenties op een website. De eigenaar van een site wil graag advertenties op zijn site plaatsen en wel die, waar de meeste websitebezoekers in geïnteresseerd zijn. De eigenaar heeft een verzameling advertenties tot zijn beschikking – van auto’s, camera’s, schoenen of wat dan ook. Het punt is dat vooraf niet bekend is welk type bezoeker de site voornamelijk zal bezoeken.

In het model van de vijf onderzoekers worden de bezoekers met behulp van een (onbekende) kansverdeling getrokken. Het is de bedoeling dat de computer na heel veel trekkingen een goede voorspelling kan doen over het type websitebezoeker.

Advertenties op sites, bezoekers met bepaalde interesses, het klinkt allemaal vertrouwd. Maar zodra de vijf wetenschappers hun model formeel gaan beschrijven, schudden ze die context direct van zich af. De grote, maar eindige verzameling advertenties vervangen ze door de verzameling punten op een lijnstuk van lengte 1, het kiezen van passende advertenties door het kiezen van eindige verzamelingen punten van dat lijnstuk.

Altijd succesvol

Deze abstracte versie blijkt gerelateerd te zijn aan Cantors vermoeden uit de negentiende eeuw. Het vijftal wetenschappers heeft namelijk bewezen dat het bestaan van een manier om ‘geschikte’ eindige deelverzamelingen van het lijnstuk te kiezen gelijkwaardig is aan de continuümhypothese. Dat betekent dat voor hun leerprobleem een algoritme bestaat dat áltijd succesvol leert, ongeacht de kansverdeling waaruit de eindige verzamelingen punten worden gegenereerd, mits de continuümhypothese waar is. En omgekeerd: zo’n succesvol leeralgoritme bestaat níét als de continuümhypothese ónwaar is. De vraag of er voor het abstracte leerprobleem een succesvol leeralgoritme bestaat, kan dus niet op basis van enkel de axioma’s van Zermelo en Fraenkel – zonder de continuümhypothese – beantwoord worden.

De auteurs spreken overigens niet van een leeralgoritme, maar van een leerfunctie. Klaas Pieter Hart, wiskundige van de Technische Universiteit Delft die het werk heeft bestudeerd en erover schreef op zijn blog, legt uit: „Een algoritme heeft een expliciete beschrijving en de bijbehorende functie is dan al gauw heel ‘netjes’, wat betekent dat de functie zogeheten meetbaarheidseigenschappen heeft. De functies die de vijf wiskundigen in hun bewijs gebruiken, zijn juist níét netjes.”

Een functie die je niet kunt implementeren op een computer, is geen algoritme

In de praktijk betekent dit dat zo’n leerfunctie nooit in computercode kan worden uitgedrukt. Een functie die je niet op een computer kunt implementeren, is geen algoritme.

Kan het leerprobleem, beschreven in het jargon van de verzamelingenleer, worden terugvertaald naar de concrete toepassing van advertenties op een site? Hart: „In werkelijkheid zal een machine nooit een heel continuüm aan advertenties voorgeschoteld krijgen. Wiskundigen gebruiken het continuüm om zinnige dingen over de ‘echte’ wereld te zeggen. Dat is hier ook gebeurd: alle ‘realistische’ ballast weg en meteen het hele interval van 0 tot 1 als domein gebruiken.”

Met die stap moet je dus oppassen. Als je je beperkt tot de breuken – ook oneindig in aantal, maar minder dan een continuüm – treden er geen problemen op. Hart vat het resultaat van de vijf wetenschappers als volgt samen: „Het bestaan van ‘willekeurige’ leerfuncties is consistent met de gangbare wiskundige axioma’s en onafhankelijk daarvan; het bestaan van ‘algoritmische’ leerfuncties is ontkracht.”

Abstract stuk gereedschap

Het abstracte leerprobleem is ver verwijderd van bekende toepassingen zoals gezichtsherkenning of het herkennen van tumoren op röntgenfoto’s. Is de stelling dan wel ergens goed voor? Of gaat het hier puur om het wetenschappelijke belang? Peter Grünwald van het Centrum Wiskunde & Informatica in Amsterdam, tevens hoogleraar aan de Universiteit Leiden, is een Nederlandse expert op het gebied van machine learning. Hij zegt erover: „Wanneer we in de wiskundige tak van machine learning nieuwe algoritmen ontwerpen, gebruiken we vaak nogal abstracte ideeën.” Hij noemt de zogeheten classificatieproblemen, waarvoor niet altijd een succesvolle leerfunctie kan bestaan vanwege het feit dat de zogeheten Vapnik-Chervonenkis-dimensie voor classificatieproblemen oneindig kan zijn.

Een begrip als Vapnik-Chervonenkis-dimensie is een abstracte wiskundige eigenschap en refereert zelf helemaal niet naar algoritmen. „Toch is het heel handig om zo’n abstract stuk gereedschap te hebben,” zegt Grünwald. „Uit de Vapnik-Chervonenkis-theorie volgt dat je niet eens hoeft te probéren een algoritme te ontwerpen dat classificatieproblemen van een bepaalde soort kan oplossen. Je kunt het vergelijken met iemand die zegt: ‘ik ga een straalmotor bouwen waarmee een vliegtuig sneller kan dan het licht’. Dan kun je ook, zonder iets over straalmotortechnologie te weten, direct zeggen dat dit onmogelijk is. Er zijn immers veel abstractere natuurkundige wetten, die niets met kerosine of wind te maken hebben, die het al uitsluiten.”

Uit het werk van de vijf onderzoekers volgt dat voor een bepaalde, algemenere klasse leerproblemen een abstracte notie, vergelijkbaar met de Vapnik-Chervonenkis-dimensie, niet kan bestaan. Grünwald: „Het werk zou daarom ooit nog wel eens belangrijk kunnen zijn, omdat het ons kan behoeden om nieuwe, super-algemene versies van de Vapnik-Chervonenkis-dimensie te bedenken. We weten dankzij dit werk dat zoiets gedoemd is te mislukken.”