Résumé Technique : L'Intéressance comme Heuristique Inductive pour le Progrès Futur de la Compression

1. Énoncé du Problème

L'article aborde un goulot d'étranglement critique dans le développement de systèmes intelligents, ouverts et s'améliorant récursivement : le défi de l'intéressance. Alors que les paradigmes actuels d'apprentissage automatique (par exemple, la descente de gradient, l'apprentissage par renforcement) ont obtenu des succès significatifs dans la phase d'apprentissage (extraction de motifs à partir de données), la phase de génération reste un problème ouvert. Plus précisément, comment un système autonome peut-il identifier prospectivement quels tâches, données ou artefacts ont le potentiel de progrès futur, sans dépendre d'un filtrage humain en boucle ou de curriculums conçus à la main ?

Les mesures existantes d'intéressance (par exemple, l'erreur de prédiction, le gain d'information, le progrès d'apprentissage) sont largement a posteriori : elles quantifient ce qui a déjà été appris après que des ressources computationnelles ont été dépensées. Un système s'améliorant lui-même nécessite une heuristique prospective pour prédire la future apprenabilité avant d'engager des ressources significatives, distinguant ainsi l'inapprenable, l'already appris et l'inconnu-mais-apprenable.

2. Méthodologie

Les auteurs formalisent l'« intéressement » comme une heuristique inductive pour le progrès futur de la compression. Ils utilisent des outils issus de la Théorie de l'Information Algorithmique (AIT) et de la Statistique Algorithmique pour analyser la relation entre le progrès passé et la découverte future.

Concepts Clés

• Progrès de Compression : L'intéressance est définie comme la réduction attendue de la longueur totale de description (complexité du modèle + résidu des données) lorsqu'un nouvel objet est incorporé. Cela s'aligne sur le principe de la Longueur Minimale de Description (MDL).
• Profils Complexité vs Temps d'Exécution ($D_x$) : Les auteurs analysent la trajectoire de la longueur du programme le plus court $K_r(x)$ nécessaire pour calculer une chaîne $x$ dans un budget de temps d'exécution $r$. Une « chute » dans ce profil représente une percée en matière de compression.
• Profils Taille-Log vs Complexité ($P_x$) : Pour exploiter la statistique algorithmique, ils utilisent le profil décrivant la taille-logarithmique du plus petit ensemble contenant $x$ pour une complexité de modèle donnée.
• La Correspondance $P_x \leftrightarrow D_x$ : En utilisant la fonction de Busy Beaver ($BB$), les auteurs établissent une transformation affine entre le profil taille-log/complexité et le profil complexité/temps d'exécution. Cela permet de mapper les résultats théoriques dérivés de $P_x$ vers le domaine computationnellement pertinent $D_x$.
• Propriété Inductive : La question centrale est de savoir si la forme d'un profil observé jusqu'à un seuil $t$ (la « longueur de stagnation » $t - \hat{m}$, où $\hat{m}$ est la dernière chute observée) peut prédire statistiquement l'existence et l'ampleur des chutes futures (compression supplémentaire).

Priors Investigés

L'étude évalue les propriétés inductives sous trois priors distincts sur les chaînes calculables :

1. Prior de Longueur ($L$) : Probabilité uniforme sur les longueurs de chaînes.
2. Prior Algorithmique ($M$) : Le prior de Solomonoff, favorisant les chaînes avec de courtes descriptions (programmes).
3. Prior de Vitesse ($S$) : Pénalise à la fois la longueur du programme et le temps d'exécution, favorisant les chaînes calculables rapidement.

3. Contributions Clés

L'article apporte les contributions théoriques et empiriques suivantes :

1. Formalisation de l'Intéressance Inductive : Les auteurs prouvent que la propriété inductive de l'intéressance est théoriquement viable. Ils démontrent que la longueur de stagnation (l'écart depuis la dernière percée de compression observée) est le principal prédicteur du progrès futur.
2. Décroissance Exponentielle de la Probabilité de Découverte : Ils prouvent que la probabilité d'une nouvelle « chute » de compression s'annule exponentiellement à mesure que la longueur de stagnation augmente. Cela implique que les objets les plus prometteurs pour un engagement ultérieur sont ceux présentant le progrès le plus récent.
3. Comparaison des Priors :
   • Le Prior Algorithmique s'avère significativement plus « optimiste » que le Prior de Longueur. Pour le même profil observé, le Prior Algorithmique produit une augmentation quadratique du progrès futur de compression attendu par rapport au Prior de Longueur.
   • Le Prior de Vitesse est le plus « conservateur », supposant que si une méthode de compression plus rapide existait, elle aurait déjà été découverte, conduisant à un progrès futur attendu proche de zéro dans de nombreux cas.
4. Validation Empirique : Les tendances théoriques sont confirmées à travers trois paradigmes universels computationnels : les systèmes 2-Tag, les automates cellulaires Règle 110 et Brainfuck (BF). Dans tous les cas, les données soutiennent la conclusion que le progrès récent est un indicateur fort de la future compressibilité, en particulier sous le Prior Algorithmique.

4. Résultats

• Bornes Théoriques : Sous les Priors de Longueur et Algorithmique, la probabilité d'une chute future $p(m_x \ge t | \hat{P})$ est approximativement $2^{-(t-\hat{m})}$. Le progrès futur de compression attendu décroît également de manière exponentielle avec la longueur de stagnation.
• Sensibilité au Prior : Bien que la décroissance exponentielle s'applique à tous les priors, l'ampleur du progrès attendu diffère. Le Prior Algorithmique prédit un potentiel de découverte significativement plus élevé que le Prior de Longueur, tandis que le Prior de Vitesse prédit un progrès additionnel minimal.
• Confirmation Empirique : Les expériences sur les systèmes 2-Tag, Règle 110 et Brainfuck reflètent les courbes théoriques. À mesure que le nombre d'étapes depuis le dernier progrès observé augmente, le progrès de compression restant moyen s'annule. Les résultats pour le Prior de Vitesse dans les contextes empiriques sont moins prononcés que dans la limite théorique (en raison de l'absence de temps d'exécution extrêmement courts dans les configurations expérimentales spécifiques), mais la tendance générale selon laquelle la stagnation réduit le progrès attendu reste valable.

5. Signification et Revendications

L'article soutient que l'intéressance ne doit pas être considérée comme une propriété intrinsèque d'un objet, mais comme une heuristique relationnelle et prospective basée sur la trajectoire du progrès de compression.

• Autonomie : En formalisant l'intéressance comme une évaluation prospective, l'article fournit une base rationnelle pour que les systèmes autonomes sélectionnent des tâches sans intervention humaine. Il suggère que les systèmes devraient privilégier les objets où la « longueur de stagnation » est courte.
• Fondement Théorique : Ce travail ancre le concept intuitif de « curiosité » ou d'« intéressement » dans le cadre rigoureux de la Théorie de l'Information Algorithmique, dépassant les définitions heuristiques pour atteindre des propriétés inductives prouvables.
• Limites et Orientations Futures : Les auteurs notent modestement que leurs résultats théoriques reposent sur la fonction de Busy Beaver, qui implique des temps d'exécution physiquement irréalisables. Cependant, ils soutiennent que le caractère indépendant de la machine de ces résultats reflète les propriétés algorithmiques intrinsèques des objets. Ils reconnaissent que dans des domaines structurés (par exemple, les systèmes biologiques, les fractales), l'histoire du progrès pourrait importer davantage que la simple récence de la dernière chute (émergence sans échelle), une propriété non entièrement capturée par les priors actuels. Ils concluent que les travaux futurs doivent se concentrer sur le développement de modèles introspectifs capables de modéliser explicitement leurs propres « frontières de compression » pour atteindre une véritable ouverture.