Exact Local Optimality Does Not Compose: The Complexity of Chronological Realization

In de studie van systemen die evolueren in de loop van de tijd, zoals weerpatronen, aandelenmarkten of zelfs de manier waarop een mens een nieuwe taal leert, proberen wetenschappers vaak een vereenvoudigd model te bouwen van de onderliggende werkelijkheid. Deze modellen rusten op het idee dat het toekomstige gedrag van een systeem afhankelijk is van de huidige staat. Als je de staat kent, kun je voorspellen wat er vervolgens gebeurt. Echter, in de echte wereld zien we de ware staat zelden direct; we zien alleen een stroom van inputs en de resulterende outputs. Om dit te begrijpen, gebruiken onderzoekers een methode genaamd predictive state representation (voorspellende staat-representatie). In plaats van te gissen naar de verborgen interne conditie, bouwen ze een model dat volledig gebaseerd is op wat het systeem in het verleden heeft gedaan en wat het in de toekomst waarschijnlijk zal doen. Het doel is om de kleinste, meest efficiënte beschrijving van het systeem te vinden die nog steeds perfecte voorspelling mogelijk maakt.

Decennialang suggereerde een heersende intuïtie dat als elk individueel onderdeel van een systeem eenvoudig beschreven kon worden, het hele systeem ook eenvoudig beschrijfbaar zou moeten zijn. Als je de uitkomst van een enkel experiment met een kleine hoeveelheid geheugen kunt voorspellen, leek het logisch dat je een sequentie van experimenten met ongeveer dezelfde hoeveelheid geheugen kon voorspellen. Deze aanname vormt de basis van veel moderne kunstmatige intelligentie en regeltheorie, waarbij efficiëntie essentieel is. Als een systeem complex is, komt dat meestal doordat de onderdelen complex zijn. Maar wat als de complexiteit niet voortkomt uit de onderdelen zelf, maar uit de manier waarop ze in de loop van de tijd gedwongen worden samen te werken?

Een recente studie door Yixin Zhao daagt deze intuïtie rechtstreeks uit. De onderzoeker onderzocht een specifiek type systeem waarbij een enkel, gedeeld geheugen moet worden gebruikt om een grote verscheidenheid aan verschillende toekomstige scenario's te voorspellen. De vraag was recht door zee: als elk individueel scenario met een kleine, vaste hoeveelheid geheugen voorspeld kan worden, past de gehele collectie scenario's dan nog steeds binnen datzelfde kleine geheugen wanneer zij allemaal dezelfde onderliggende dynamiek moeten delen? Het antwoord, bewezen met wiskundige zekerheid, is een definitief nee. De studie laat zien dat de vereiste voor een enkele, gedeelde tijdlijn de geheugengrootte kan laten exploderen, waardoor deze ver voorbij gaat aan wat de individuele delen suggereren.

Om de ontdekking te begrijpen, stel je een bibliotheek van instructies voor. Elke instructie vertelt het systeem hoe het moet reageren op een specifieke reeks gebeurtenissen. De onderzoeker construeerde een familie van deze instructies waarbij elke instructie, op zichzelf staand, perfect uitgevoerd kon worden met een klein, vast aantal interne toestanden. Echter, toen de onderzoeker probeerde één enkele machine te bouwen die al deze instructies in de juiste volgorde kon uitvoeren, waarbij de machine voor elke taak hetzelfde interne geheugen deelde, had de machine een veel groter aantal toestanden nodig. De grootte van het geheugen nam niet slechts licht toe; het vermenigvuldigde zich met een factor die willekeurig groot gemaakt kon worden. Dit fenomeen, dat de auteur een "state blow-up" (toestands-explosie) noemt, onthult dat de kosten voor het handhaven van een consistente historie een verborgen belasting zijn die niet zichtbaar is wanneer men naar de taken in isolatie kijkt.

Het onderzoek gaat verder dan alleen aantonen dat de geheugengrootte groeit. Het bewijst dat het bepalen of een systeem gebouwd kan worden met een specifieke, beperkte hoeveelheid geheugen een ongelooflijk moeilijk computationeel probleem is. In de wereld van de informatica worden problemen gecategoriseerd op basis van hoe moeilijk ze op te lossen zijn. Sommige zijn makkelijk, sommige zijn moeilijk, en sommige zijn zo moeilijk dat geen enkel bekend algoritme ze efficiënt kan oplossen. De studie toont aan dat voor deze gedeelde systemen het besluit of er een oplossing bestaat, tot de moeilijkste bekende problemen behoort. Het is niet louter een kwestie van een berekening uitvoeren en wachten; de structuur van het probleem zelf verzet zich tegen een efficiënte oplossing. Zelfs als de individuele taken eenvoudig zijn en de geheugenlimiet net iets boven het minimum dat voor elke taak nodig is is ingesteld, wordt het controleren of een gedeelde oplossing bestaat een taak die waarschijnlijk onmogelijke hoeveelheden rekenkracht vereist.

De auteur ontwikkelde twee verschillende manieren om dit te bewijzen. De eerste omvat een specifiek geconstrueerde familie van taken die fungeert als een duidelijk tegenvoorbeeld. In dit scenario toonde de onderzoeker aan dat hoewel de lokale geheugenbehoeften klein zijn, de gedeelde geheugenbehoeften lineair groeien met het aantal taken, wat een gat creëert dat zo groot als gewenst kan zijn. De tweede benadering gebruikt een complexere, abstracte constructie om aan te tonen dat het probleem van het vinden van een oplossing computationeel onhandelbaar is. Dit betekent dat zelfs met de krachtigste computers geen efficiënte manier bestaat om te bepalen of een systeem in een klein gedeeld model kan worden gecomprimeerd. Het bewijs berust op het vertalen van het probleem naar een geometische puzzel met vormen en hun relaties, waarmee wordt aangetoond dat het oplossen van het geheugenprobleem gelijkstaat aan het oplossen van een bekend, extreem moeilijk geometrisch probleem.

Deze bevindingen hebben diepgaande implicaties voor hoe we denken over leren en controle. Ze suggereren dat de moeilijkheid van het beheren van een complex systeem niet alleen gaat over de complexiteit van de componenten, maar over de rigiditeit van de tijdlijn die zij moeten volgen. Wanneer een systeem een gedeelde historie moet onthouden om voorspellingen te doen, kan het gedwongen worden een veel zwaardere cognitieve last te dragen dan de som van de delen zou suggereren. Dit is geen falen van de huidige technologie of een tijdelijke beperking van algoritmen; het is een fundamentele structurele eigenschap van hoe tijd en geheugen met elkaar interageren in voorspellende systemen. De studie isoleert deze intrinsieke kosten, door aan te tonen dat de prijs van chronologische consistentie een toestandsdimensie is die onbegrensd kan zijn.

Het werk verheldert ook de grenzen van wat efficiënt geleerd kan worden. Als een systeem te complex is om te worden gecomprimeerd in een klein gedeeld model, dan vecht elke leeralgoritme die een dergelijk model probeert te vinden tegen een wiskundige barrière. De onderzoeker toonde aan dat zelfs wanneer de data perfect is en de regels duidelijk zijn, de vraag of een klein gedeeld model bestaat vaak onmogelijk snel te beantwoorden is. Dit onderscheidt het vermogen om individuele gebeurtenissen te voorspellen van het vermogen om een verenigd, efficiënt model van het gehele proces te onderhouden. De kloof tussen deze twee capaciteiten is geen bug die met betere software kan worden opgelost; het is een kenmerk van de wiskunde die de sequentiële systemen beheerst.

In de bredere context van kunstmatige intelligentie dient dit resultaat als een waarschuwing. Het waarschuwt tegen de aanname dat omdat een systeem in isolatie eenvoudig functioneert, het ook eenvoudig zal functioneren wanneer het wordt geïntegreerd in een groter, tijdsafhankelijk kader. De complexiteit van het geheel kan fundamenteel verschillend zijn van de complexiteit van de delen. De studie biedt een rigoureus kader voor het begrijpen van dit verschil, en biedt een nieuwe manier om de kosten van gedeeld geheugen in dynamische systemen te meten. Door te bewijzen dat lokale optimaliteit niet componeert, dwingt het onderzoek tot een herwaardering van hoe we systemen ontwerpen en analyseren die moeten leren van een stroom van ervaringen.

Het artikel concludeert door te wijzen naar toekomstige vragen. Hoewel de resultaten bewezen zijn voor klassieke systemen, merkt de auteur op dat soortgelijke uitdagingen waarschijnlijk ook bestaan in de kwantumwereld, waar de regels van waarschijnlijkheid en staat nog exotischer zijn. De studie opent een deur naar het begrijpen van hoe deze fundamentele limieten van toepassing zijn op meer geavanceerde vormen van computationele verwerking. Voor nu staat de kernbevinding vast: de eis voor een enkele, gedeelde historie kan een systeem dwingen zijn interne complexiteit uit te breiden op manieren die zowel wiskundig onvermijdelijk als computationeel ontmoedigend zijn. De efficiëntie die we hopen te vinden in onze modellen kan een illusie zijn wanneer de tijdlijn gedeeld wordt, wat een diepe en onvermijdelijke prijs onthult voor de coherentie van de tijd.