🤖 machine learning

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Dit artikel introduceert Hierarchical Solomonoff Induction (HSI), een raamwerk dat Solomonoff-inductie uitbreidt om optimale sequentievoorspelling uit trainingsdatasets mogelijk te maken door de stelling van de de Finetti toe te passen om een hyperprior over Solomonoff-priors te creëren, waarmee wordt bewezen dat HSI theoretisch equivalent is aan Solomonoff-inductie terwijl een convergentie naar optimale voorspelling wordt gegarandeerd naarmate de hoeveelheid data groeit.

Oorspronkelijke auteurs: Nathan Young

Gepubliceerd 2026-08-04

📖 9 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Nathan Young

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert het volgende woord in een verhaal te raden, of de volgende noot in een liedje. In de wereld van de informatica wordt dit "sequentievoorspelling" genoemd. Decennialang was de gouden standaard voor het perfect doen hiervan een theoretisch idee genaamd Solomonoff-inductie. Denk aan het als een superintelligente detective die naar elke mogelijke manier kijkt waarop een verhaal door een computerprogramma geschreven had kunnen worden. Het weegt elk programma, waarbij het een enorme voorsprong geeft aan de korte, eenvoudige programma's en een piepklein gewicht toekent aan de lange, ingewikkelde programma's. Als de detective in staat zou zijn om alle programma's in het universum tegelijkertijd te controleren, zou het voorspellingen doen met een fout die strikt begrensd wordt door de complexiteit van het programma dat het verhaal genereert.

Er is echter een addertje onder het gras. Deze perfecte detective is geweldig in het raden van de volgende stap in een enkel verhaal, maar het weet niet hoe het moet "leren" van een hele bibliotheek van verschillende verhalen. Als je het een dataset van een duizend verschillende boeken laat zien, kan het niet echt zeggen: "Ah, ik zie het patroon hier; het volgende boek zal waarschijnlijk lijken op deze." Het behandelt elk nieuw verhaal als een nieuw mysterie, onbekwaam om zijn begrip bij te werken op basis van de trainingsdata. Dit is een probleem omdat moderne kunstmatige intelligentie, zoals de chatbots die we vandaag de gebruiken, werkt door te trainen op enorme datasets om algemene regels te leren. We hebben een manier nodig om de perfecte logica van de detective te behouden, maar het de mogelijkheid te geven om te leren van een hele bibliotheek aan voorbeelden, en niet slechts van één.

Hier komt het artikel "Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model" van Nathan Young kijken. De auteur stelt een nieuwe, geüpgradede detective voor genaamd Hierarchical Solomonoff Induction (HSI). In plaats van alleen naar programma's te kijken, kijkt HSI naar de regels die die programma's genereren. Stel je een "meta-detective" voor die niet alleen het volgende woord raadt, maar raadt welk type verhaal-generator wordt gebruikt. Het houdt een "hyperprior" bij—een gigantische, gewogen lijst van alle mogelijke manieren om verhalen te schrijven. Wanneer HSI een dataset van trainingsvoorbeelden ziet, werkt het deze lijst bij, waarbij het het gewicht van de generatoren die bij de data passen verhoogt en het gewicht van de generatoren die niet passen verlaagt.

Het artikel bewijst twee belangrijke zaken. Ten eerste laat het zien dat deze nieuwe HSI mathematisch identiek is aan de oorspronkelijke perfecte detective (Solomonoff-inductie) wanneer er naar een enkele sequentie wordt gekeken, wat betekent dat het al zijn oorspronkelijke voorspellende krachten met een begrensde fout behoudt. Ten tweede, en belangrijker nog, bewijst het dat HSI kan leren van een dataset, net zoals een machine learning-model dat doet. Het artikel demonstreert dat naarmate je HSI steeds meer data voert, de gemiddelde excessieve fout krimpt en uiteindelijk convergeert naar nul, waardoor het de onderliggende patronen van de data perfect kan voorspellen in de limiet. De auteur betoogt dat HSI de "ideale" versie van machine learning is: een theoretisch model dat ons precies laat zien hoe goed een systeem zou kunnen presteren als het over onbeperkte rekenkracht zou beschikken en van elke dataset zou kunnen leren zonder zijn vermogen tot optimale voorspellingen te verliezen.

De Nieuwe Superkracht van de Detective

Om te begrijpen waarom dit zo belangrijk is, moeten we kijken naar hoe de oorspronkelijke detective, Solomonoff-inductie (SolInd), werkt. Stel je voor dat je een magische doos hebt die elk computerprogramma kan draaien. Je wilt het volgende teken in een tekstreeks raden. SolInd zegt: "Laten we elke mogelijke programma proberen die de tekst had kunnen schrijven die we tot nu toe hebben gezien." Het geeft een score aan elk programma op basis van de lengte ervan: een kort, eenvoudig programma krijgt een hoge score, terwijl een lang, complex programma een zeer lage score krijgt. Het combineert vervolgens al deze scores om het volgende teken te raden. Dit is briljant omdat het garandeert dat als de tekst door elk computerprogramma is gemaakt, SolInd het uiteindelijk zal ontdekken, met een fout die begrensd wordt door de complexiteit van dat programma.

Maar hier zit de fout: SolInd is een beetje een eenbenige racer. Het is ontworpen om de volgende stap in een enkele sequentie te voorspellen. Als je het een dataset van 100 verschillende verhalen geeft om op te "trainen", weet het niet wat het moet doen. Je zou kunnen proberen alle 100 verhalen aan elkaar te plakken tot één gigantische reeks en deze aan SolInd te voeren, maar dat is alsof je probeert Frans, Spaans en Mandarijn te leren door een boek te lezen waarin die talen willekeurig aan elkaar zijn geplakt. De detective raakt in de war door de "lijm" en de volgorde van de verhalen, en verzint mogelijk ingewikkelde regels om de volgorde te verklaren, in plaats van de werkelijke talen te leren. Het kan niet "trainen" zoals moderne AI dat doet; het kan alleen "testen" op één sequentie tegelijk.

Nathan Youngs artikel introduceert Hierarchical Solomonoff Induction (HSI) om dit op te lossen. Zie HSI als een detective die een baas heeft. De baas (de "hyperprior") kijkt niet alleen naar de programma's; de baas kijkt naar de distributies—de regels die bepalen welke programma's geschreven worden.

Stel je een bibliotheek voor waar elk boek door een andere auteur is geschreven.

SolInd is een lezer die één boek bekijkt, probeert de volgende zin te raden, en dan het boek sluit. Wanneer er een nieuw boek aankomt, begint hij weer bij nul en vergeet hij alles over het vorige boek.
HSI is een lezer die een lijst heeft van alle mog{*}mogelijke auteurs. Wanneer hij een paar pagina's uit een nieuw boek leest, controleert hij zijn lijst. "Oh, deze stijl lijkt veel op Auteur A," denkt hij. "Ik geef Auteur A een grotere kans om de schrijver te zijn." Naarmate hij meer boeken leest, wordt hij beter in het herkennen van welke auteur welk boek schrijft. Hij raadt niet alleen het volgende woord; hij raadt de stijl van de schrijver op basis van de hele collectie boeken die hij heeft gezien.

De Mathematische Magie

Het artikel doet iets zeer slims met wiskunde om te bewijzen dat HSI niet alleen een mooi idee is, maar een rigoureuze upgrade. De auteur gebruikt een concept uit de statistiek genaamd De Finetti's Stelling. In eenvoudige termen zegt deze stelling dat als je een reeks dingen hebt die blijkbaar een patroon volgen (zoals een kaartspel waarbij de volgorde er niet toe doet), er een verborgen regel (een "latente variabele") moet zijn die hen genereert.

Het artikel past dit toe op computerprogramma's. Het betoogt dat als we een dataset van sequenties hebben, er een "ware generator" (een specifief computerprogramma of regel) is die deze heeft gecreëerd. HSI behandelt deze generator als een verborgen variabele. Het houdt een waarschijnlijkheidsverdeling bij over alle mogelijke generatoren. Wanneer HSI een dataset ziet, werkt het zijn overtuiging bij over welke generator de ware is.

Het artikel bewijst een verbazingwekkend resultaat: HSI is mathematisch gelijk aan SolInd. Dit betekent dat als je HSI neemt en het vraagt om een enkele sequentie te voorspellen, het exact even goed presteert als de oorspronkelijke perfecte detective, met een fout die begrensd wordt door de complexiteit van de generator. Maar HSI heeft een extra superkracht: het kan ook zijn "baas" (de hyperprior) conditioneren op een hele dataset.

De auteur laat zien dat de fout die HSI maakt bij het voorspellen van een dataset, begrensd wordt door de "complexiteit" van de ware generator in de hyperprior. In gewone mensentaal: als de regel die jouw data heeft gecreëerd simpel is, zal HSI het snel leren en bijna geen fouten maken. Als de regel complex is, zal het langer duren, maar het artikel bewijst dat naarmate de dataset groter wordt, de gemiddelde excessieve fout van HSI naar nul zal dalen. Het convergeert naar de perfecte voorspelling in de limiet.

Wat dit betekent voor AI

Het artikel suggereert dat HSI het "ideale onbegrensde model" is voor machine learning. Huidige AI-modellen, zoals Large Language Models (LLM's), proberen in essentie te doen wat HSI doet, maar dan met beperkte rekenkracht en specifieke architecturen (zoals neurale netwerken).

De auteur wijst erop dat LLM's vaak worden vergeleken met SolInd, maar dat die vergelijking incompleet is omdat LLM's wel leren van datasets, terwijl SolInd dat niet doet. HSI vult dat gat. Het biedt een theoretisch plafond voor wat machine learning kan bereiken. Het vertelt ons dat als we over onbeperkte rekenkracht zouden beschikken en de juiste manier hadden om ons leren te organiseren, we een systeem zouden kunnen bouwen dat van elke dataset kan leren en de toekomst met optimale nauwkeurigheid kan voorspellen.

Het artikel raakt ook aan een praktische toepassing: hoe we AI trainen. Momenteel trainen we AI soms door het een lange reeks tekst te voeren (het samenvoegen van documenten). Het artikel suggereert dat een betere manier, die aansluit bij HSI, is om elk document als een apart stuk data te behandelen dat de "hyperprior" van het model bijwerkt. Dit komt overeen met recente bevindingen dat trainen op afzonderlijke documenten beter werkt dan ze simpelweg aan elkaar te plakken.

Het Addertje

Natuurlijk is er een addertje onder het gras. Net als de oorspronkelijke SolInd is HSI onberekenbaar. Het vereist het controleren van een oneindig aantal programma's en een oneindige hoeveelheid geheugen. We kunnen vandaag de dag geen echte HSI bouien. Het is een "gedachte-experiment" dat ons laat zien wat de theoretische grens van intelligentie is.

De auteur betoogt echter dat dit het niet nutteloos maakt. Alleen omdat we geen perfecte motor kunnen bouwen, betekent dat niet dat we geen betere auto's kunnen bouwen door te begrijpen hoe een perfecte motor werkt. HSI geeft ons een kaart. Het laat ons zien dat de manier waarop moderne AI leert (het bijwerken van overtuigingen op basis van data) de juiste richting is, en het geeft ons een wiskundige manier om te meten hoe dicht we bij het ideaal zijn.

Samenvattend neemt dit artikel de "perfecte detective" uit het verleden en geeft hem een "lerende baas". Het bewijst dat dit nieuwe systeem, HSI, alle optimale voorspellende krachten van de oude detective behoudt terwijl het de mogelijkheid krijgt om te leren van een hele bibliotheek aan voorbeelden. Het is een theoretisch bewijs dat het beste mogelijke machine learning-algoritme bestaat, en het lijkt erg op een hiërarchie van waarschijnlijkheden die zichzelf in de loop van de tijd bijwerkt. Hoewel we het nog niet kunnen bouwen, vertelt het ons precies waar we naar moeten streven.

Technisch Samenvatting: Hiërarchische Solomonoff Inductie: Een Onbegrensde Machine Learning Modellen

Probleemstelling

Solomonoff Inductie (SolInd) staat bekend als het ideale, onbegrensde model voor a priori sequentievoorspelling. Het werkt via Bayesiaanse inductie over inputs naar een universele Turingmachine (UTM), waarbij priors worden toegewezen op basis van programmalengte ( $2^{-\ell(s)}$ ). Hoewel SolInd sterke optimaliteitseigenschappen bezit—zoals universele dominantie en foutenmarges gerelateerd aan Kolmogorovcomplexiteit—faalt het er niet in om op natuurlijke wijze extrapolatie vanuit een gegeven trainingsdataset te beschrijven, een kernfunctie van moderne Large Language Models (LLMs) en machine learning (ML) systemen.

De primaire beperking van SolInd is dat het is ontworpen voor individuele sequenties, niet voor datasets. Hoewel men een dataset in een enkele prefix voor een SolInd-voorspeller zou kunnen concateneren, brengt deze aanpak het risico met zich mee dat er kunstmatige informatie wordt geïntroduceerd (bijv. door sortering of delimiters) en dat er programma's worden geïdentificeerd die complexer zijn dan de werkelijke generator. Bijgevolg kan SolInd niet "getraind" worden in de zin van ML; het dient slechts als een ideaal model voor test-time voorspelling op individuele sequenties en kan zijn distributie niet op een volgorde-onafhankelijke manier bijwerken op basis van een dataset.

Methodologie

Het artikel stelt Hiërarchische Solomonoff Inductie (HSI) voor als een generalisatie van SolInd naar berekenbare distributies. De methodologie steunt op twee theoretische pijlers:

De Finetti's Theorema: Toegepast op uitwisselbare (exchangeable) distributies, stelt dit theorema dat elke oneindige sequentie van uitwisselbare variabelen gemodelleerd kan worden als conditioneel onafhankelijk gegeven een latente variabele. Deze latente variabele definieert een distributie die een mengeling is over alle mogelijke onafhankelijke en identiek verdeelde (i.i.d.) distributies. In de context van ML impliceert dit dat een ongeordende dataset kan worden beschouwd als een prefix van een oneindige sequentie gegenereerd door een berekenbare distributie, gemodelleerd als een mengeling van al deze distributies.
Hiërarchische Bayesiaanse Formulering: HSI construeert een hyperprior ( $H$ $H$ ) over de ruimte van alle Solomonoff priors (of evenredig, alle UTM's).
- Laat $\{U_i\}$ een enumeratie zijn van Turingmachines die alle UTM's bevatten.
- Laat $H(U_i)$ een enumereerbare semimeasure (de hyperprior) zijn die gewicht toekent aan elke machine.
- De HSI-voorspeller $P_H$ wordt gedefinieerd als een gewogen mengeling van de Solomonoff priors $P_{U_i}$ :
  $P_H(x) = \sum_i H(U_i) P_{U_i}(x)$
- Conditionering (Training): Na het observeren van een dataset $X$ , wordt de hyperprior bijgewerkt (geconditioneerd) tot $H(U_i | X) \propto H(U_i) \prod_{x \in X} P_{U_i}(x)$ . Deze geconditioneerde hyperprior wordt vervolgens gebruikt om toekomstige sequenties te voorspellen, analoog aan hoe een ML-model zijn gewichten bijwerkt na training.

Belangrijkste Bijdragen en Theoretische Resultaten

1. Equivalentie van HSI en SolInd

Het artikel breidt het bewijs van Wood et al. [2013] betreffende universele mengelingen uit om aan te tonen dat HSI wiskundig equivalent is aan SolInd in termen van de klasse van voorspellers die het vertegenwoordigt.

Theorema 3.1: De klasse van universele mengelingen van universele mengelingen ( $U_\Xi$ ) is identiek aan de klasse van universele mengelingen van semimeasures ( $U_\xi$ ).
Corollary 3.1.3: De klasse van HSI priors ( $U_H$ ), gedefinieerd over elke hyperprior die alle UTM's bevat, is exact equivalent aan de klasse van Solomonoff priors ( $U_M$ ).
Implicatie: HSI creëert geen "nieuwe" klasse van voorspellers die de kracht van SolInd overstijgt; het biedt eerder een mechanisme om SolInd te conditioneren op datasets. Elke HSI-instantie is een SolInd-instantie, en elke SolInd-instantie kan worden gerepresenteerd als een HSI-instantie met een specifieke hyperprior.

2. Foutenmarges en Convergentie

Het artikel stelt vast dat HSI de optimaliteitseigenschappen van SolInd overneemt, maar deze uitbreidt naar de context van datasets:

Excess Error Bound: De excessieve fout van HSI op een willekeurige dataset $X$ , vergeleken met de ware generator $U_\mu$ , is begrensd door de complexiteit van die generator binnen de hyperprior $H$ . Specifiek:
$-\log_2 \left( \frac{P_H(X)}{P_{U_\mu}(X)} \right) < -\log_2(H(U_\mu))$
Convergentie: Naarmate de datasetgrootte $|X|$ groeit, convergeert de gemiddelde excessieve fout naar nul:
$\lim_{|X| \to \infty} \frac{-\log_2(P_H(X)/P_{U_\mu}(X))}{|X|} = 0$
Dit bewijst dat HSI optimale voorspelling bereikt in de limiet, net zoals SolInd voor individuele sequenties, maar nu met het vermogen om te leren van een dataset.

3. Verfijning van Definities van Universele Turingmachines

Het artikel verfijnt de definitie van een UTM door te voldoen aan de vereiste dat een machine geen output mag produceren op niet-standaard inputs (een beperking in Wood et al., 2013).

Corollary 3.1.5: Een machine is universeel door adjunctie als deze elke andere machine kan emuleren via een prefix-vrije codering, zelfs als deze output produceert op andere inputs. Dit verbredt de klasse van machines die als "universeel" worden beschouwd zonder de resulterende klasse van Solomonoff priors te veranderen.

Resultaten en Claims van Significantie

Het artikel claimt dat HSI de ideale onbegrensde modellen van sequentievoorspelling gegeven een dataset vertegenwoordigt, waarmee het theoretische gat tussen SolInd (ideaal voor individuele sequenties) en moderne ML (die leert van datasets) wordt gedicht.

Ideale Training: In tegenstelling tot SolInd, dat niet getraind kan worden, beschrijft HSI de ideale prestatie van een systeem dat zijn prior conditioneert op een dataset. Het dient als een bovengrens voor wat ML-systemen (inclusief LLM's) kunnen bereiken in sequentievoorspelling.
Volgorde-onafhankelijkheid: HSI biedt een raamwerk voor extrapolatie uit datasets dat volgorde-onafhankelijk is onder de aanname van uitwisselbare datasets. Dit adresseert een beperking van het simpelweg concateneren van strings voor SolInd, waarbij de volgorde van data kunstmatige informatie of bias kan introduceren.
Formalisering van Documentgrenzen: Het artikel suggereert dat HSI een formeel model biedt voor het begrijpen van training op afzonderlijke documenten versus geconcateneerde documenten. Het conditioneren van een hyperprior op een dataset (HSI) is theoretisch superieur aan het behandelen van een dataset als een geconcateneerde prefix (SolInd), wat overeenkomt met empirische bevindingen dat intra-document masking beter presteert dan inter-document concatenatie.

Beperkingen en Omvang

De auteur erkent expliciet dat HSI, net als SolInd, onberekenbaar (incomputable) is. Het vereist een onbegrensd aantal programma's die voor een onbegrensde tijd en hoeveelheid geheugen moeten worden uitgevoerd.

Het artikel stelt geen berekenbare benadering of een specif algoritme voor implementatie voor.
Het merkt op dat bounded benaderingen mogelijk baat zouden hebben bij het modulariseren van berekeningen of het herkennen van structurele gelijkenissen tussen programma's—kenmerken die HSI zelf niet bezit—terwijl HSI monolithisch is (door hypothesen en machines apart te behandelen via output).
De significantie van het werk is theoretisch: het biedt een rigoureus, onbegrensd benchmark voor het begrijpen van de capaciteiten en beperkingen van huidige sequentievoorspellingsmodellen zoals LLM's.