🤖 machine learning

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Questo articolo introduce l'Induzione Gerarchica di Solomonoff (HSI), un framework che estende l'Induzione di Solomonoff per consentire la previsione ottimale di sequenze da set di dati di addestramento applicando il teorema di de Finetti per creare un iper-prior sui prior di Solomonoff, dimostrando così che l'HSI è teoricamente equivalente all'Induzione di Solomonoff garantendo al contempo la convergenza alla previsione ottimale all'aumentare dei dati.

Autori originali: Nathan Young

Pubblicato 2026-08-04

📖 8 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Nathan Young

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di indovinare la parola successiva in una storia, o la nota successiva in una canzone. Nel mondo dell'informatica, questo è chiamato "predizione di sequenze". Per decenni, lo standard di riferimento per farlo perfettamente è stato un'idea teorica chiamata Induzione di Solomonoff. Pensala come un detective super-intelligente che esamina ogni possibile modo in cui una storia potrebbe essere stata scritta da un programma per computer. Pesa ogni singolo programma, dando un enorme vantaggio a quelli brevi e semplici e un peso minuscolo a quelli lunghi e complicati. Se il detective potesse controllare ogni singolo programma nell'universo contemporaneamente, farebbe predizioni con un errore strettamente limitato dalla complessità del programma che genera la storia.

Tuttovo, c'è un problema. Questo detective perfetto è bravissimo a indovinare il passo successivo in una singola storia, ma non sa come "imparare" da una biblioteca intera di storie diverse. Se gli mostri un dataset di mille libri differenti, non può davvero dire: "Ah, vedo il modello qui; il prossimo libro sarà probabilmente simile a questi". Tratta ogni nuova storia come un nuovo mistero, incapace di aggiornare la sua comprensione basandosi sui dati di addestramento. Questo è un problema perché l'Intelligenza Artificiale moderna, come i chatbot che usiamo oggi, lavora addestrandosi su enormi dataset per apprendere regole generali. Abbiamo bisogno di un modo per mantenere la logica perfetta del detective, ma dargli la capacità di imparare da un'intera biblioteca di esempi, non solo da uno.

È qui che entra in gioco il saggio "Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model" di Nathan Young. L'autore propone un nuovo, aggiornato detective chiamato Induzione di Solomonoff Gerarchica (HSI). Invece di guardare solo ai programmi, l'HSI guarda alle regole che generano quei programmi. Immagina un "meta-detective" che non si limita a indovinare la parola successiva, ma indovina quale tipo di generatore di storie viene utilizzato. Mantiene un "iperprior" (hyperprior): una gigantesca lista pesata di tutti i modi possibili di scrivere storie. Quando l'HSI vede un dataset di esempi di addestramento, aggiorna questa lista, aumentando il peso dei generatori che si adattano ai dati e diminuendo il peso di quelli che non lo fanno.

Il saggio dimostra due cose principali. Primo, mostra che questo nuovo HSI è matematicamente identico al detective perfetto originale (l'Induzione di Solomonoff) quando osserva una singola sequenza, il che significa che mantiene tutte le capacità predittive limitate dell'originale. Secondo, e più importante, dimostra che l'HSI può imparare da un dataset proprio come fa un modello di machine learning. Il saggio dimostra che man mano che alimenti l'HSI con sempre più dati, il suo errore eccessivo medio diminuisce e infine converge a zero, permettendogli di predire perfettamente il modello sottostante. L'autore sostiene che l'HSI sia la versione "ideale" del machine learning: un modello teorico che ci mostra esattamente quanto bene un sistema potrebbe performare se avesse una potenza di calcolo illimitata e potesse imparare da qualsiasi dataset senza perdere la sua capacità di fare predizioni ottimali.

Il Nuovo Superpotere del Detective

Per capire perché questo sia importante, guardiamo come funziona il detective originale, l'Induzione di Solomonoff (SolInd). Immagina di avere una scatola magica in grado di eseguire qualsiasi programma per computer. Vuoi indovinare la lettera successiva in una stringa di testo. SolInd dice: "Proviamo ogni possibile programma che potrebbe aver scritto il testo che abbiamo visto finora". Assegna un punteggio a ciascun programma in base alla sua lunghezza: un programma breve e semplice riceve un punteggio alto, mentre uno lungo e complesso ne riceve uno molto basso. Poi combina tutti questi punteggi per indovinare la lettera successiva. Questo è brillante perché garantisce che, se il testo è stato creato da qualsiasi programma per computer, SolInd riuscirà prima o poi a capirlo, con un errore limitato dalla complessità di quel programma.

Ma ecco il difetto: SolInd è un po' un talento specializzato in una sola cosa. È progettato per predire il passo successivo in una singola sequenza. Se gli dai un dataset di 100 storie diverse per "addestrarlo", non sa cosa fare. Potresti provare a schiacciare tutte le 100 storie in un'unica stringa gigante e darle in pasto a SolInd, ma è come cercare di imparare il francese, lo spagnolo e il mandarino leggendo un libro dove queste lingue sono state incollate insieme casualmente. Il detective si confonde per la "colla" e l'ordine delle storie, inventando potenzialmente regole complicate solo per spiegare l'ordine, piuttosto che imparare le lingue vere e proprie. Non può "addestrarsi" nel modo in cui fa l'IA moderna; può solo "testare" su una sequenza alla volta.

L'introduzione di Nathan Young all'Induzione di Solomonoff Gerarchica (HSI) serve a correggere questo. Pensa all'HSI come a un detective che ha un capo. Il capo (l'iperprior) non guarda solo i programmi; il capo guarda le distribuzioni — le regole che decidono quali programmi vengono scritti.

Immagina una biblioteca dove ogni libro è scritto da un autore diverso.

SolInd è un lettore che guarda un libro, cerca di indovinare la frase successiva e poi chiude il libro. Quando arriva un nuovo libro, ricomincia da capo, dimenticando tutto di quello precedente.
HSI è un lettore che ha una lista di tutti i possibili autori. Quando legge alcune pagine di un nuovo libro, controlla la sua lista. "Oh, questo stile assomiglia molto all'Autore A", pensa. "Darò all'Autore A una probabilità maggiore di essere l'autore". Mentre legge più libri, diventa più bravo a individuare chi sta scrivendo quale libro. Non sta solo indovinando la parola successiva; sta indovinando lo stile dello scrittore basandosi sull'intera collezione di libri che ha visto.

La Magia Matematica

Il saggio utilizza un procedimento matematico molto intelligente per dimostrare che l'HSI non è solo un'idea affascinante, ma un aggiornamento rigoroso. L'autore utilizza un concetto statistico chiamato Teorema di De Finetti. In termini semplici, questo teorema afferma che se hai un gruppo di cose che sembrano seguire un modello (come un mazzo di carte dove l'ordine non conta), deve esserci una regola nascosta (una "variabile latente") che le sta generando.

Il saggio applica questo ai programmi per computer. Sostiene che se abbiamo un dataset di sequenze, esiste un "generatore vero" (un programma o una regola specifica) che le ha create. L'HSI tratta questo generatore come una variabile nascosta. Mantiene una distribuzione di probabilità su tutti i possibili generatori. Quando l'HSI vede un dataset, aggiorna la sua convinzione su quale sia il generatore reale.

Il saggio dimostra un risultato sorprendente: l'HSI è matematicamente equivalente a SolInd. Ciò significa che se prendi l'HSI e gli chiedi di predire una singola sequenza, performa esattamente come il detective perfetto originale, con un errore limitato dalla complessità del generatore. Ma l'HSI ha un superpotere extra: può anche condizionare il suo "capo" (l'iperprior) su un intero dataset.

L'autore dimostra che l'errore commesso dall'HSI quando predice un dataset è limitato dalla "complessità" del vero generatore nell'iperprior. In parole povere: se la regola che ha creato i tuoi dati è semplice, l'HSI la imparerà velocemente e commeterà quasi nessun errore. Se la regola è complessa, ci vorrà più tempo, ma il saggio dimostra che man mano che il dataset diventa più grande, l'errore eccessivo medio dell'HSI scenderà a zero. Esso converge alla predizione perfetta nel limite.

Cosa Significa per l'IA

Il saggio suggerisce che l'HSI è il "modello non limitato ideale" per il machine learning. Gli attuali modelli di IA, come i Large Language Models (LLM), stanno essenzialmente cercando di fare ciò che fa l'HSI, ma con una potenza di calcolo limitata e architetture specifiche (come le reti neurali).

L'autore sottolinea che gli LLM vengono spesso confrontati con SolInd, ma tale confronto è incompleto perché gli LLM imparano dai dataset, mentre SolInd no. L'HSI colma questa lacuna. Fornisce un tetto teorico a ciò che il machine learning può raggiungere. Ci dice che, se avessimo una potenza di calcolo infinita e il modo giusto di organizzare il nostro apprendimento, potremmo costruire un sistema che impara da qualsiasi dataset e predice il futuro con un'accuratezza ottimale.

Il saggio tocca anche un'applicazione pratica: come addestriamo l'IA. Attualmente, a volte addestriamo l'IA fornendole una lunga stringa di testo (concatenando i documenti). Il saggio suggerisce che un modo migliore, che si allinea all'HSI, è trattare ogni documento come un pezzo di dato separato che aggiorna l'iperprior del modello. Questo corrisponde alle recenti scoperte secondo cui l'addestramento su documenti separati funziona meglio rispetto al semplice incollarli insieme.

Il Problema

Naturalmente, c'è un ostacolo. Proprio come l'originale SolInd, l'HSI è non computabile. Richiede il controllo di un numero infinito di programmi e una quantità infinita di memoria. Non possiamo costruire un vero HSI oggi. È un "esperimento mentale" che ci mostra il limite teorico dell'intelligenza.

Tuttavia, l'autore sostiene che questo non lo renda inutile. Proprio come non possiamo costruire un motore perfetto, non è detto che non possiamo costruire auto migliori comprendendo come funziona un motore perfetto. L'HSI ci fornisce una mappa. Ci mostra che il modo in cui l'IA moderna impara (aggiornando le convinzioni basandosi sui dati) è la direzione giusta, e ci dà un modo matematico per misurare quanto siamo vicini all'ideale.

In sintesi, questo saggio prende il "detective perfetto" del passato e gli dà un "capo che impara". Dimostra che questo nuovo sistema, l'HSI, mantiene tutti i poteri predittivi ottimali del vecchio detective, acquisendo al contempo la capacità di imparare da un'intera biblioteca di esempi. È una prova teorica che esiste il miglior algoritmo di machine learning possibile, e che esso assomiglia molto a una gerarchia di probabilità che si aggiorna nel tempo. Anche se non possiamo costruirlo ancora, ci dice esattamente verso cosa dovremmo puntare.

Sintesi Tecnica: Induzione di Solomonoff Gerarchica: Un Modello di Apprendimento Automatico Illimitato

Definizione del Problema

L'Induzione di Solomonoff (SolInd) è stabilita come il modello ideale e illimitato per la predizione a priori di sequenze. Essa opera tramite induzione bayesiana su input per una macchina di Turing universale (UTM), assegnando prior basati sulla lunghezza del programma ( $2^{-\ell(s)}$ ). Sebbene SolInd possieda forti proprietà di ottimalità — come la dominanza universale e i limiti di errore legati alla complessità di Kolmogorov — essa non riesce a descrivere naturalmente l'estrapolazione da un dato dataset di addestramento, una funzione centrale dei moderni Large Language Models (LLM) e dei sistemi di machine learning (ML).

Il limite primario di SolInd è che è progettata per singole sequenze, non per dataset. Sebbene si possa concatenare un dataset in un unico prefisso per un predittore SolInd, questo approccio rischia di introdurre informazioni artificiali (ad esempio, dalla ordinazione o dai delimitatori) e di identificare programmi più complessi del vero generatore. Di conseguenza, SolInd non può essere "addestrata" nel senso del ML; essa funge solo da modello ideale per la predizione di sequenze individuali al tempo di test e non può aggiornare la sua distribuzione basandosi su un dataset in modo indipendente dall'ordine.

Metodologia

Il documento propone l'Induzione di Solomonoff Gerarchica (HSI) come una generalizzazione di SolInd alle distribuzioni computabili. La metodologia si basa su due pilastri teorici:

Teorema di De Finetti: Applicato alle distribuzioni scambiabili, questo teorema afferma che qualsiasi sequenza infinita di variabili scambiabili può essere modellata come condizionalmente indipendente data una variabile latente. Questa variabile latente definisce una distribuzione che è una miscela di tutte le distribuzioni indipendenti e identicamente distribuite (i.i.d.). Nel contesto del ML, ciò implica che un dataset non ordinato può essere visto come il prefisso di una sequenza infinita generata da una distribuzione computabile, modellata come una miscela di tutte tali distribuzioni.
Formulazione Bayesiana Gerarchica: L'HSI costruisce un iperprior ( $H$ $H$ ) sullo spazio di tutti i prior di Solomonoff (o equivalentemente, di tutte le UTM).
- Sia $\{U_i\}$ un'enumerazione di macchine di Turing che contiene tutte le UTM.
- Sia $H(U_i)$ una semimisura enumerabile (l'iperprior) che assegna un peso a ciascuna macchina.
- Il predittore HSI $P_H$ è definito come una miscela pesata dei prior di Solomonoff $P_{U_i}$ :
  $P_H(x) = \sum_i H(U_i) P_{U_i}(x)$
- Condizionamento (Addestramento): Osservando un dataset $X$ , l'iperprior viene aggiornato (condizionato) a $H(U_i | X) \propto H(U_i) \prod_{x \in X} P_{U_i}(x)$ . Questo iperprior condizionato viene poi utilizzato per predire sequenze future, analogamente a come un modello di ML aggiorna i suoi pesi dopo l'addestramento.

Contributi Chiave e Risultati Teorici

1. Equivalenza tra HSI e SolInd

Il documento estende la dimostrazione di Wood et al. [2013] riguardante le miscele universali per dimostrare che l'HSI è matematicamente equivalente a SolInd in termini della classe di predittori che rappresenta.

Teorema 3.1: La classe delle miscele universali di miscele universali ( $U_\Xi$ ) è identica alla classe delle misture universali di semimisure ( $U_\xi$ ).
Corollario 3.1.3: La classe dei prior HSI ( $U_H$ ), definita su qualsiasi iperprior che includa tutte le UTM, è esattamente equivalente alla classe dei prior di Solomonoff ( $U_M$ ).
Implicazione: L'HSI non crea una "nuova" classe di predittori che superi il potere di SolInd; piuttosto, fornisce un meccanismo per condizionare SolInd su dataset. Qualsiasi istanza di HSI è un'istanza di SolInd, e ogni istanza di SolInd può essere rappresentata come un'istanza di HSI con un iperprior specifico.

2. Limiti di Errore e Convergenza

Il documento stabilisce che l'HSI eredita le proprietà di ottimalità di SolInd ma le estende al contesto dei dataset:

Limite dell'Errore in Eccesso: L'errore in eccesso di HSI su qualsiasi dataset $X$ , rispetto al vero generatore $U_\mu$ , è limitato dalla complessità di tale generatore all'interno dell'iperprior $H$ . Specificamente:
$-\log_2 \left( \frac{P_H(X)}{P_{U_\mu}(X)} \right) < -\log_2(H(U_\mu))$
Convergenza: Al crescere della dimensione del dataset $|X|$ , l'errore medio in eccesso converge a zero:
$\lim_{|X| \to \infty} \frac{-\log_2(P_H(X)/P_{U_\mu}(X))}{|X|} = 0$
Ciò dimostra che l'HSI raggiunge la predizione ottimale nel limite, proprio come SolInd per le singole sequenze, ma ora con la capacità di apprendere da un dataset.

3. Raffinamento delle Definizioni di Macchina di Turing Universale

Il documento raffina la definizione di UTM rilassando il requisito che una macchina debba produrre nessun output su input non standard (un vincolo in Wood et al., 2013).

Corollario 3.1.5: Una macchina è universale per aggiunzione se può emulare qualsiasi altra macchina tramite una codifica prefix-free, anche se produce output su altri input. Questo amplia la classe di macchine considerate "universali" senza alterare la classe risultante di prior di Solomonoff.

Risultati e Rivendicazioni di Significatività

Il documento sostiene che l'HSI rappresenti il modello ideale illimitato di predizione di sequenze dato un dataset, colmando il vuoto teorico tra SolInd (ideale per singole sequenze) e il ML moderno (che apprende da dataset).

Addestramento Ideale: A differenza di SolInd, che non può essere addestrato, l'HSI descrive la prestazione ideale di un sistema che condiziona il suo prior su un dataset. Serve come limite superiore per ciò che i sistemi di ML (inclusi gli LLM) possono raggiungere nella predizione di sequenze.
Indipendenza dall'Ordine: L'HSI fornisce un quadro per l'estrapolazione da dataset che è indipendente dall'ordine sotto l'assunto di dataset scambiabili. Ciò affronta un limite della semplice concatenazione di stringhe per SolInd, dove l'ordine dei dati può introdurre informazioni o bias artificiali.
Formalizzazione dei Confini dei Documenti: Il documento suggerisce che l'HSI offre un modello formale per comprendere l'addestramento su documenti separati rispetto a documenti concatenati. Condizionare un iperprior su un dataset (HSI) è teoricamente superiore al trattare un dataset come un prefisso concatenato (SolInd), allineandosi con i risultati empirici secondo cui il masking intra-documento supera la concatenazione inter-documento.

Limitazioni e Ambito

L'autore riconosce esplicitamente che l'HSI, come SolInd, è incomputabile. Richiede un numero illimitato di programmi da eseguire per un tempo e una memoria illimitati.

Il documento non propone un'approssimazione computabile o un algoritmo specifico per l'implementazione.
Si nota che, mentre l'HSI è monolitica (trattando ipotesi e macchine separatamente tramite l'output), le approssimazioni limitate potrebbero beneficiare della modularizzazione dei calcoli o del riconoscimento di somiglianze strutturali tra i programmi — caratteristiche che l'HSI stessa non possiede, ma che futuri algoritmi illimitati potrebbero modellare.
La significatività del lavoro è teorica: fornisce un benchmark rigoroso e illimitato per comprendere le capacità e i limiti degli attuali modelli di predizione di sequenze come gli LLM.