🤖 machine learning

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Cet article introduit l'Induction Hiérarchique de Solomonoff (HSI), un cadre qui étend l'Induction de Solomonoff pour permettre la prédiction de séquences optimales à partir de jeux de données d'entraînement en appliquant le théorème de de Finetti afin de créer un hyperprior sur les priors de Solomonoff, prouvant ainsi que l'HSI est théoriquement équivalente à l'Induction de Solomonoff tout en garantissant la convergence vers une prédiction optimale à mesure que les données augmentent.

Auteurs originaux : Nathan Young

Publié 2026-08-04

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nathan Young

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de deviner le mot suivant dans une histoire, ou la note suivante dans une chanson. Dans le monde de l'informatique, cela s'appelle la « prédiction de séquence ». Pendant des décennies, la référence absolue pour faire cela parfaitement a été une idée théorique appelée l'Induction de Solomonoff. Considérez cela comme un détective super-intelligent qui examine toutes les manières possibles dont une histoire aurait pu être écrite par un programme informatique. Il pondère chaque programme, accordant un avantage énorme aux programmes courts et simples, et un poids minuscule aux programmes longs et complexes. Si le détective pouvait vérifier chaque programme de l'univers en même temps, il ferait des prédictions avec une erreur strictement bornée par la complexité du programme générant l'histoire.

Cependant, il y a un piège. Ce détective parfait est excellent pour deviner la prochaine étape d'une seule histoire, mais il ne sait pas comment « apprendre » à partir d'une bibliothèque entière de différentes histoires. Si vous lui présentez un ensemble de données de mille livres différents, il ne peut pas vraiment dire : « Ah, je vois le modèle ici ; le prochain livre sera probablement comme ceux-ci. » Il traite chaque nouvelle histoire comme un nouveau mystère, incapable de mettre à jour sa compréhension basée sur les données d'entraînement. C'est un problème car l'intelligence artificielle moderne, comme les chatbots que nous utilisons aujourd'hui, fonctionne en s'entraînant sur des ensembles de données massifs pour apprendre des règles générales. Nous avons besoin d'un moyen de conserver la logique parfaite de ce détective tout en lui donnant la capacité d'apprendre à partir d'une bibliothèque entière d'exemples, et non d'un seul.

C'est là qu'intervient le papier « Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model » de Nathan Young. L'auteur propose un détective amélioré, l'Induction de Solomonoff Hiérarchique (HSI). Au lieu de simplement regarder les programmes, l'HSI regarde les règles qui génèrent ces programmes. Imaginez un « méta-détective » qui ne se contente pas de deviner le mot suivant, mais qui devine quel type de générateur d'histoires est utilisé. Il conserve un « hyperprior » — une liste géante et pondérée de toutes les manières possibles d'écrire des histoires. Lorsqu'il voit un ensemble de données d'exemples d'entraînement, il met à jour cette liste, augmentant le poids des générateurs qui correspondent aux données et diminuant celui de ceux qui ne correspondent pas.

L'auteur prouve deux choses majeures. Premièrement, il montre que ce nouvel HSI est mathématiquement identique au détective parfait original (l'Induction de Solomonoff) lorsqu'il observe une séquence unique, ce qui signifie qu'il conserve tous les pouvoirs de prédiction bornés de l'original. Deuxièmement, et plus important encore, il prouve que l'HSI peut apprendre à partir d'un ensemble de données comme le fait un modèle d'apprentissage automatique. L'article démontre qu'à mesure que vous alimentez l'HSI avec de plus en plus de données, son erreur excédentaire moyenne diminue et finit par converger vers zéro, lui permettant de prédire parfaitement le modèle sous-jacent. L'auteur soutient que l'HSI est la version « idéale » de l'apprentissage automatique : un modèle théorique qui montre exactement comment un système pourrait performer s'il disposait d'une puissance de calcul illimitée et pouvait apprendre de n'importe quel ensemble de données sans perdre sa capacité à faire des prédictions optimales.

Le nouveau super-pouvoir du détective

Pour comprendre pourquoi c'est important, regardons comment le détective original, l'Induction de Solomonoff (SolInd), fonctionne. Imaginez que vous avez une boîte magique capable d'exécuter n'importe quel programme informatique. Vous voulez deviner la lettre suivante dans une chaîne de texte. SolInd dit : « Essayons tous les programmes possibles qui auraient pu écrire le texte que nous avons vu jusqu'à présent. » Il attribue un score à chaque programme en fonction de sa longueur : un programme court et simple reçoit un score élevé, tandis qu'un programme long et complexe en reçoit un très bas. Il combine ensuite tous ces scores pour deviner la lettre suivante. C'est brillant car cela garantit que si le texte a été créé par n'importe quel programme informatique, SolInd finira par le comprendre, avec une erreur bornée par la complexité de ce programme.

Mais voici la faille : SolInd est un peu limité. Il est conçu pour prédire la prochaine étape d'une seule séquence. Si vous lui donnez un ensemble de données de 100 histoires différentes pour l'« entraîner », il ne sait pas quoi faire. Vous pourriez essayer d'écraser ces 100 histoires en une seule immense chaîne et la donner à SolInd, mais c'est comme essayer d'apprendre le français, l'espagnol et le mandarin en lisant un livre où ces langues sont simplement collées ensemble de manière aléatoire. Le détective est confus par la « colle » et l'ordre des histoires, inventant potentiellement des règles complexes juste pour expliquer l'ordre, plutôt que d'apprendre les langues réelles. Il ne peut pas « s'entraîner » comme le fait l'IA moderne ; il ne peut que « tester » une séquence à la fois.

Le papier de Nathan Young introduit l'Induction de Solomonoff Hiérarchique (HSI) pour corriger cela. Voyez l'HSI comme un détective qui a un patron. Le patron (l'hyperprior) ne regarde pas seulement les programmes ; le patron regarde les distributions — les règles qui décident quels programmes seront écrits.

Imaginez une bibliothèque où chaque livre est écrit par un auteur différent.

SolInd est un lecteur qui regarde un livre, essaie de deviner la phrase suivante, puis ferme le livre. Lorsqu'un nouveau livre arrive, il repart de zéro, oubliant tout ce qu'il a appris du précédent.
L'HSI est un lecteur qui possède une liste de tous les auteurs possibles. Lorsqu'il lit quelques pages d'un nouveau livre, il consulte sa liste. « Oh, ce style ressemble beaucoup à l'Auteur A », pense-t-il. « Je vais donner une probabilité plus élevée à l'Auteur A pour être l'écrivain. » À mesure qu'il lit plus de livres, il devient meilleur pour repérer quel auteur écrit quel livre. Il ne se contente pas de deviner le mot suivant ; il devine le style de l'écrivain en se basant sur toute la collection de livres qu'il a vus.

La magie mathématique

Le papier utilise un concept mathématique très habile pour prouver que l'HSI n'est pas seulement une idée fantaisiste, mais une mise à niveau rigoureuse. L'auteur utilise un concept statistique appelé le théorème de De Finetti. En termes simples, ce théorème stipule que si vous avez un groupe de choses qui semblent suivre un modèle (comme un jeu de cartes où l'ordre n'a pas d'importance), il doit y avoir une règle cachée (une « variable latente ») qui les génère.

Le papier applique cela aux programmes informatiques. Il soutient que si nous avons un ensemble de données de séquences, il existe un « véritable générateur » (un programme informatique ou une règle spécifique) qui les a créés. L'HSI traite ce générateur comme une variable cachée. Il maintient une distribution de probabilité sur tous les générateurs possibles. Lorsqu'il voit un ensemble de données, il met à jour sa croyance quant au générateur qui est le vrai.

Le papier prouve un résultat stupéfiant : l'HSI est mathématiquement équivalent à SolInd. Cela signifie que si vous prenez l'HSI et que vous lui demandez de prédire une séquence unique, il performe exactement aussi bien que le détective parfait original, avec une erreur bornée par la complexité du générateur. Mais l'HSI possède un super-pouvoir supplémentaire : il peut aussi conditionner son « patron » (l'hyperprior) à un ensemble de données complet.

L'auteur démontre que l'erreur commise par l'HSI lors de la prédiction d'un ensemble de données est bornée par la « complexité » du véritable générateur dans l'hyperprior. En langage courant : si la règle qui a créé vos données est simple, l'HSI l'apprendra rapidement et fera presque aucune erreur. Si la règle est complexe, cela prendra plus de temps, mais le papier prouve qu'à mesure que l'ensemble de données s'agrandit, l'erreur excédentaire moyenne de l'HSI tombera à zéro. Il converge vers la prédiction parfaite dans la limite.

Ce que cela signifie pour l'IA

Le papier suggère que l'HSI est le « modèle non borné idéal » pour l'apprentissage automatique. Les modèles d'IA actuels, comme les Large Language Models (LLM), tentent essentiellement de faire ce que fait l'HSI, mais avec une puissance de calcul limitée et des architectures spécifiques (comme les réseaux de neurones).

L'auteur souligne que les LLM sont souvent comparés à SolInd, mais que cette comparaison est incomplète car les LLM apprennent à partir de jeux de données, alors que SolInd ne le fait pas. L'HSI comble cette lacune. Il fournit un plafond théorique à ce que l'apprentissage automatique peut accomplir. Il nous dit que si nous avions une puissance de calcul infinie et la bonne façon d'organiser notre apprentissage, nous pourrions construire un système qui apprend de n'importe quel ensemble de données et prédit l'avenir avec une précision optimale.

Le papier aborde également une application pratique : comment nous entraînons l'IA. Actuellement, nous entraînons parfois l'IA en lui fournissant une longue chaîne de texte (concaténation de documents). Le papier suggère qu'une meilleure méthode, qui s'aligne sur l'HSI, consiste à traiter chaque document comme une pièce de données distincte qui met à jour l'« hyperprior » du modèle. Cela correspond aux découvertes récentes selon lesquelles l'entraînement sur des documents séparés fonctionne mieux que de simplement les coller ensemble.

Le piège

Bien sûr, il y a un piège. Tout comme l'original SolInd, l'HSI est incalculable. Il nécessite de vérifier un nombre infini de programmes et une quantité infinie de mémoire. Nous ne pouvons pas construire un véritable HSI aujourd'hui. C'est une « expérience de pensée » qui nous montre la limite théorique de l'intelligence.

Cependant, l'auteur soutient que cela ne le rend pas inutile. Ce n'est pas parce que nous ne pouvons pas construire un moteur parfait que nous ne pouvons pas construire de meilleures voitures en comprenant comment un moteur parfait fonctionne. L'HSI nous donne une carte. Il nous montre que la façon dont l'IA moderne apprend (en mettant à jour ses croyances basées sur les données) est la bonne direction, et il nous donne un moyen mathématique de mesurer à quel point nous sommes proches de l'idéal.

En résumé, ce papier prend le « détective parfait » du passé et lui donne un « patron apprenant ». Il prouve que ce nouveau système, l'HSI, conserve tous les pouvoirs de prédiction optimaux de l'ancien détective tout en acquérant la capacité d'apprendre à partir d'une bibliothèque entière d'exemples. C'est une preuve théorique que l'algorithme d'apprentissage automatique le plus performable existe, et qu'il ressemble beaucoup à une hiérarchie de probabilités se mettant à jour au fil du temps. Bien que nous ne puissions pas encore le construire, cela nous indique exactement ce que nous devons viser.

Résumé technique : Induction de Solomonoff Hiérarchique : un modèle d'apprentissage automatique non borné

Énoncé du problème

L'induction de Solomonoff (SolInd) est établie comme le modèle idéal et non borné pour la prédiction de séquences a priori. Elle opère par induction bayésienne sur des entrées vers une machine de Turing universelle (MTU), attribuant des priors basés sur la longueur du programme ( $2^{-\ell(s)}$ ). Bien que SolInd possède de fortes propriétés d'optimalité — telles que la dominance universelle et les bornes d'erreur liées à la complexité de Kolmogorov — elle échoue à décrire naturellement l'extrapolation à partir d'un ensemble de données d'entraînement donné, une fonction centrale des modèles de langage de grande taille (LLM) et des systèmes d'apprentissage automatique (ML) modernes.

La limitation principale de SolInd est qu'elle est conçue pour des séquences individuelles, et non pour des ensembles de données. Bien que l'on puisse concaténer un ensemble de données en un seul préfixe pour un prédicteur SolInd, cette approche risque d'introduire des informations artificielles (par exemple, issues du tri ou des délimiteurs) et d'identifier des programmes plus complexes que le générateur réel. Par conséquent, SolInd ne peut pas être « entraînée » au sens de l'apprentissage automatique ; elle sert uniquement de modèle idéal pour la prédiction au moment du test sur des séquences individuelles et ne peut pas mettre à jour sa distribution en fonction d'un ensemble de données de manière indépendante de l'ordre.

Méthodologie

Le présent article propose l'Induction de Solomonoff Hiérarchique (HSI) comme une généralisation de SolInd aux distributions calculables. La méthodologie repose sur deux piliers théoriques :

Le théorème de De Finetti : Appliqué aux distributions échangeables, ce théorème stipule que toute séquence infinie de variables échangeables peut être modélisée comme étant conditionnellement indépendante étant donné une variable latente. Cette variable latente définit une distribution qui est un mélange de toutes les distributions indépendantes et identiquement distribuées (i.i.d.). Dans le contexte du ML, cela implique qu'un ensemble de données non ordonné peut être vu comme le préfixe d'une séquence infinie générée par une distribution calculable, modélisée comme un mélange de toutes ces distributions.
Formulation bayésienne hiérarchique : L'HSI construit un hyperprior ( $H$ $H$ ) sur l'espace de tous les priors de Solomonoff (ou équivalemment, de toutes les MTU).
- Soit $\{U_i\}$ une énumération de machines de Turing contenant toutes les MTU.
- Soit $H(U_i)$ une semi-mesure énumérable (l'hyperprior) attribuant un poids à chaque machine.
- Le prédicteur HSI $P_H$ est défini comme un mélange pondéré des priors de Solomonoff $P_{U_i}$ :
  $P_H(x) = \sum_i H(U_i) P_{U_i}(x)$
- Conditionnement (Entraînement) : Lors de l'observation d'un ensemble de données $X$ , l'hyperprior est mis à jour (conditionné) par $H(U_i | X) \propto H(U_i) \prod_{x \in X} P_{U_i}(x)$ . Cet hyperprior conditionné est ensuite utilisé pour prédire de futures séquences, de manière analogue à la façon dont un modèle de ML met à jour ses poids après l'entraînement.

Contributions clés et résultats théoriques

1. Équivalence entre HSI et SolInd

L'article étend la preuve de Wood et al. [2013] concernant les mélanges universels pour démontrer que l'HSI est mathématiquement équivalente à SolInd en termes de la classe de prédicteurs qu'elle représente.

Théorème 3.1 : La classe des mélanges universels de mélanges universels ( $U_\Xi$ ) est identique à la classe des mélanges universels de semi-mesures ( $U_\xi$ ).
Corollaire 3.1.3 : La classe des priors HSI ( $U_H$ ), définie sur tout hyperprior incluant toutes les MTU, est exactement équivalente à la classe des priors de Solomonoff ( $U_M$ ).
Implication : L'HSI ne crée pas une « nouvelle » classe de prédicteurs dépassant la puissance de SolInd ; elle fournit plutôt un mécanisme pour conditionner SolInd sur des ensembles de données. Toute instance de l'HSI est une instance de SolInd, et toute instance de SolInd peut être représentée comme une instance de l'HSI avec un hyperprior spécifique.

2. Bornes d'erreur et convergence

L'article établit que l'HSI hérite des propriétés d'optimalité de SolInd mais les étend au contexte des ensembles de données :

Borne d'erreur excédentaire : L'erreur excédentaire de l'HSI sur n'importe quel ensemble de données $X$ , par rapport au générateur réel $U_\mu$ , est bornée par la complexité de ce générateur au sein de l'hyperprior $H$ . Plus précisément :
$-\log_2 \left( \frac{P_H(X)}{P_{U_\mu}(X)} \right) < -\log_2(H(U_\mu))$
Convergence : À mesure que la taille de l'ensemble de données $|X|$ augmente, l'erreur excédentaire moyenne converge vers zéro :
$\lim_{|X| \to \infty} \frac{-\log_2(P_H(X)/P_{U_\mu}(X))}{|X|} = 0$
Ceci prouve que l'HSI atteint une prédiction optimale dans la limite, tout comme SolInd pour les séquences individuelles, mais avec désormais la capacité d'apprendre à partir d'un ensemble de données.

3. Raffinement des définitions de la Machine de Turing Universelle

L'article affine la définition d'une MTU en assouplissant l'exigence selon laquelle une machine ne doit produire aucune sortie sur des entrées non standard (une contrainte présente dans Wood et al., 2013).

Corollaire 3.1.5 : Une machine est universelle par adjonction si elle peut émuler toute autre machine via un encodage sans préfixe, même si elle produit une sortie sur d'autres entrées. Cela élargit la classe de machines considérées comme « universelles » sans altérer la classe résultante des priors de Solomonoff.

Résultats et affirmations de portée significative

L'article affirme que l'HSI représente le modèle non borné idéal de prédiction de séquence donné un ensemble de données, comblant ainsi le fossé théorique entre SolInd (idéal pour les séquences individuelles) et le ML moderne (qui apprend à partir d'ensembles de données).

Entraînement idéal : Contrairement à SolInd, qui ne peut pas être entraînée, l'HSI décrit la performance idéale d'un système qui conditionne son prior sur un ensemble de données. Elle sert de borne supérieure de ce que les systèmes de ML (y compris les LLM) peuvent accomplir en matière de prédiction de séquence.
Indépendance de l'ordre : L'HSI fournit un cadre pour l'extrapolation à partir d'ensembles de données qui est indépendant de l'ordre sous l'hypothèse d'ensembles de données échangeables. Cela répond à une limitation de la simple concaténation de chaînes pour SolInd, où l'ordre des données peut introduire des informations ou des biais artificiels.
Formalisation des limites de documents : L'article suggère que l'HSI offre un modèle formel pour comprendre l'entraînement sur des documents séparés par rapport à des documents concaténés. Le conditionnement d'un hyperprior sur un ensemble de données (HSI) est théoriquement supérieur à l'utilisation d'un ensemble de données comme un préfixe concaténé (SolInd), ce qui s'aligne sur les observations empiriques selon lesquelles le masquage intra-document est plus performant que la concaténation inter-document.

Limites et portée

L'auteur reconnaît explicitement que l'HSI, comme SolInd, est incalculable. Elle nécessite l'exécution d'un nombre illimité de programmes pendant un temps et une mémoire illimités.

L'article ne propose pas d'approximation calculable ou d'algorithme spécifique pour une mise en œuvre.
Il note que bien que l'HSI soit monolithique (traitant les hypothèses et les machines séparément par la sortie), des approximations bornées pourraient bénéficier de la modularisation des calculs ou de la reconnaissance de similitudes structurelles entre les programmes — des caractéristiques que l'HSI elle-même ne possède pas, mais que de futurs algorithmes non bornés pourraient modéliser.
La signification de ce travail est théorique : elle fournit un benchmark non borné rigoureux pour comprendre les capacités et les limites des modèles actuels de prédiction de séquence comme les LLM.