Why Code, Why Now: Learnability, Computability, and the Real Limits of Machine Learning

Ce papier propose une hiérarchie à cinq niveaux de la capacité d'apprentissage fondée sur la structure de l'information pour expliquer pourquoi la génération de code progresse plus fiablement que l'apprentissage par renforcement, en démontrant que les limites du progrès en ML dépendent davantage de la nature apprenable d'une tâche que de la simple augmentation de la taille des modèles.

L'essentiel

Pourquoi le code est facile à apprendre pour les IA, mais pas le reste ?

Imaginez que vous essayez d'enseigner à un enfant deux choses très différentes :

1. Comment écrire un poème (c'est comme le langage naturel ou la créativité).
2. Comment construire une tour de Lego (c'est comme écrire du code informatique).

L'article de Zhimin Zhao pose une question fascinante : Pourquoi les intelligences artificielles (IA) actuelles deviennent-elles des génies pour écrire du code, alors qu'elles peinent encore à maîtriser des tâches comme la prise de décision complexe ou l'apprentissage par essai-erreur (ce qu'on appelle l'Apprentissage par Renforcement) ?

La réponse n'est pas que les IA sont "plus intelligentes" pour le code. La réponse est que le code est "plus facile à apprendre" en raison de sa structure, pas à cause de la taille du cerveau de l'IA.

Voici les concepts clés expliqués avec des métaphores.

---

1. Le problème du "Signal de Feedback" (La leçon de l'enseignant)

Pour apprendre, un élève a besoin de savoir s'il a raison ou tort.

• Le Code (Le Lego) : C'est comme un jeu de Lego avec des instructions strictes. Si vous mettez une pièce au mauvais endroit, la tour s'effondre immédiatement. L'erreur est claire, locale et immédiate.
  • Métaphore : Si vous écrivez une phrase de code avec une virgule manquante, l'ordinateur vous dit : "Erreur ligne 42". C'est un signal dense et précis. L'IA sait exactement où elle a fait une erreur.
• L'Apprentissage par Renforcement (Le Poème ou la Stratégie) : C'est comme essayer de deviner les règles d'un jeu en jouant, sans voir les autres joueurs. Vous faites un mouvement, et à la fin du jeu, on vous dit "Gagné" ou "Perdu".
  • Métaphore : Imaginez que vous jouez aux échecs, mais on ne vous dit pas si vous avez gagné qu'après 50 coups, et sans vous dire quel coup précis a été fatal. C'est le signal de feedback qui est faible, rare et flou.

Leçon : Le code fournit des "indices" à chaque étape. Les autres tâches n'en donnent pas.

---

2. La Pyramide de la "Apprenabilité" (Les 5 niveaux)

L'auteur propose une échelle de 5 niveaux pour classer les tâches selon la qualité des informations qu'elles donnent à l'IA.

• Niveau 0 : L'Invisible (Le Mur Noir)
  • Analogie : Essayer de deviner la couleur d'un objet dans une pièce totalement noire, sans toucher.
  • Résultat : Impossible. Aucune quantité de données ne peut aider. C'est le cas de certains problèmes mathématiques fondamentaux (comme le "problème de l'arrêt").
• Niveau 1 : Le Jeu du Chat et de la Souris (Adversaire)
  • Analogie : Vous essayez de deviner le code d'un coffre-fort, mais le propriétaire change le code chaque fois que vous essayez une combinaison.
  • Résultat : Instable. C'est souvent le cas dans les jeux vidéo où l'IA essaie de tricher, ou dans les systèmes de recommandation où les utilisateurs changent de comportement.
• Niveau 2 : Le Brouillard (Bruit)
  • Analogie : Vous essayez de distinguer deux pièces de monnaie, l'une donne "Face" 49% du temps, l'autre 51%. Il faut beaucoup d'essais pour être sûr, mais c'est possible.
  • Résultat : C'est là que fonctionne la plupart de l'IA actuelle (reconnaissance d'images, classification de spam). C'est difficile mais gérable avec beaucoup de données.
• Niveau 3 : La Validation Indirecte (Le Testeur)
  • Analogie : Vous écrivez un livre. Personne ne vous dit si c'est "parfait", mais si vous écrivez une phrase qui n'a pas de sens, le lecteur la siffle. Vous ne savez pas exactement comment écrire le chef-d'œuvre, mais vous savez ce qui est faux.
  • Résultat : C'est le niveau du code. On ne connaît pas toutes les règles de la grammaire, mais on sait quand un programme ne compile pas. L'IA apprend à éviter les erreurs.
• Niveau 4 : La Vérification Directe (Le Maître Absolu)
  • Analogie : Un professeur de maths qui vérifie chaque ligne de votre calcul instantanément.
  • Résultat : C'est le niveau idéal. Le code est souvent à ce niveau grâce aux compilateurs et aux tests.

Le secret du code : Le code est un mélange magique. Il est appris au Niveau 3 (on apprend par les erreurs), mais il est soutenu par des outils de Niveau 4 (les compilateurs qui vérifient tout). C'est cette combinaison qui rend le code "apprenable".

---

3. Le Piège de la "Taille du Modèle" (Pourquoi plus grand n'est pas toujours mieux)

Il y a une croyance populaire : "Si on fait juste des IA plus grosses avec plus de données, elles réussiront tout."

L'auteur dit : Non.

• Métaphore : Imaginez que vous essayez d'apprendre à un élève à résoudre un problème qui n'a pas de solution logique (Niveau 0). Peu importe si vous lui donnez une bibliothèque entière de livres (plus de données) ou un cerveau plus grand (plus de puissance), il ne pourra pas résoudre le problème. Le problème n'est pas l'élève, c'est la nature du problème.
• Le Code : Le problème a une structure claire. Donc, donner plus de puissance à l'IA aide vraiment.
• L'Apprentissage par Renforcement (RL) : Souvent, le problème est mal structuré (Niveau 1 ou 0). Augmenter la puissance de l'IA ne fait qu'accélérer l'échec ou la confusion.

---

4. La Distinction Importante : "Exprimable" vs "Apprenable"

C'est le cœur théorique de l'article.

• Exprimable : Est-ce qu'une machine pourrait théoriquement faire la tâche ? (Oui, un ordinateur peut calculer n'importe quoi).
• Apprenable : Est-ce qu'une machine peut apprendre à le faire en regardant des exemples ?

L'analogie du coffre-fort :

• Un coffre-fort est exprimable : il existe une combinaison qui l'ouvre.
• Mais il n'est pas apprenable si vous ne pouvez pas voir la serrure. Vous pouvez essayer des milliards de combinaisons (puissance de calcul), mais sans indice (structure de l'information), vous ne progresserez jamais.

Le code est spécial car il est à la fois exprimable (les règles sont claires) et apprenable (les erreurs sont visibles).

---

Conclusion : Ce que cela signifie pour l'avenir

L'article nous dit d'arrêter de penser que "plus de puissance de calcul" résoudra tous les problèmes.

• Le vrai défi : Identifier quels problèmes ont une "structure d'information" qui permet l'apprentissage.
• La stratégie gagnante : Au lieu de demander à l'IA de résoudre un problème géant d'un coup, il faut le décomposer en petits problèmes où l'IA reçoit des feedbacks clairs (comme vérifier chaque ligne de code).
• L'avenir : Les prochaines percées viendront de ceux qui sauront transformer des tâches "impossibles à apprendre" en tâches "possibles à apprendre" en changeant la façon dont on présente l'information à la machine.

En résumé : Le code n'est pas magique. C'est juste un domaine où les règles sont si claires et les erreurs si visibles que les IA peuvent apprendre à les maîtriser comme un enfant apprend à marcher. Pour le reste, nous devons d'abord construire le "terrain d'apprentissage" avant de lancer l'IA.

Résumé technique

1. Problématique

L'article aborde une disparité fondamentale dans le domaine de l'intelligence artificielle : alors que la génération de code progresse de manière fiable et prévisible grâce aux grands modèles, les approches par apprentissage par renforcement (RL) peinent à accumuler des compétences générales, même avec des budgets d'interaction massifs.

Les explications courantes (manque de puissance de calcul, signal de récompense trop rare) sont jugées insuffisantes car elles ne tiennent pas compte de la persistance de ce phénomène malgré les améliorations matérielles et algorithmiques. L'auteur postule que l'obstacle principal n'est pas architectural, mais structurel. La question centrale est de déterminer pourquoi certaines tâches sont « apprenables » à grande échelle alors que d'autres ne le sont pas, indépendamment de la taille du modèle.

2. Méthodologie et Cadre Théorique

L'auteur propose une analyse fondée sur la structure de l'information plutôt que sur la capacité des modèles. La méthodologie repose sur trois piliers :

1. Distinction formelle de trois propriétés :

   • Expressibilité : La capacité d'une classe de fonctions à représenter une solution exacte (existence mathématique).
   • Calculabilité : L'existence d'un algorithme qui termine et résout le problème (exécutabilité).
   • Apprenabilité (Learnability) : La capacité d'un système à converger vers une solution via l'observation de données, sous des contraintes de ressources et d'adversité.

2. Analyse de la structure de l'information du code :
   L'article identifie trois propriétés du code qui le rendent exceptionnellement apprenable :

   • Contraintes syntaxiques rigides : Une erreur rend le programme invalide immédiatement (binaire).
   • Erreurs localement identifiables : Les compilateurs et type-checkers fournissent des signaux d'erreur denses et localisés (contrairement au langage naturel où le sens est diffus).
   • Forte compositionnalité : Les motifs appris dans un contexte sont transférables à un autre.

3. Modélisation formelle :
   L'auteur utilise la théorie de l'apprentissage (PAC, identification à la limite) et la théorie de la complexité (hiérarchie arithmétique) pour formaliser les relations entre ces propriétés, en analysant la profondeur des alternances de quantificateurs ($\exists, \forall$) nécessaires pour définir chaque propriété.

3. Contributions Clés

A. Une hiérarchie à cinq niveaux d'apprenabilité

L'auteur propose une hiérarchie basée sur la qualité du feedback disponible pour l'apprenant, allant de l'inobservabilité totale à la vérification déterministe :

• Niveau 0 (Aucun feedback) : Indistinguabilité informationnelle (ex: problème de l'arrêt). Le scaling est inutile.
• Niveau 1 (Feedback Adversarial) : L'environnement s'adapte ou le cible se déplace (ex: jeux de classement, Goodhart's law). Convergence instable.
• Niveau 2 (Feedback Bruité) : Distinction statistique possible mais avec du bruit (ex: classification d'images). Correspond à l'apprenabilité PAC.
• Niveau 3 (Feedback Indirect) : Preuve unilatérale. On peut falsifier les hypothèses fausses, mais jamais confirmer la vérité absolue (ex: génération de langage à partir de données positives).
• Niveau 4 (Feedback Direct) : Vérification déterministe et immédiate de chaque sortie (ex: compilation, vérification de types).

B. Analyse des relations formelles

L'article établit que ces propriétés ne sont pas équivalentes :

• L'expressibilité ne garantit pas la calculabilité (ex: fonction de l'arrêt).
• La calculabilité ne garantit pas l'apprenabilité (ex: fonctions cryptographiques comme AES sont calculables mais non apprenables en temps polynomial).
• L'apprenabilité (PAC) implique que l'évaluation de l'hypothèse est calculable, mais l'inverse est faux.
• La génération à la limite est strictement plus facile que l'identification à la limite (on peut générer des programmes valides sans connaître la grammaire complète).

C. Explication de la divergence Code vs RL

L'article démontre que la génération de code réussit car elle combine une structure de niveau 3 (apprentissage sur des programmes valides) avec un échafaudage de niveau 4 (compilateurs, tests) qui fournit des signaux denses et locaux.
En revanche, le RL échoue souvent car il réduit ces signaux riches à une récompense scalaire binaire (passer/échouer), perdant la densité de l'information et la localité des erreurs. De plus, le RL souffre de non-stationnarité (la distribution des données change avec la politique de l'agent) et de problèmes d'attribution de crédit.

4. Résultats et Observations

• Le paradoxe de l'expressivité : Une plus grande expressivité (ex: classes de fonctions avec dimension VC infinie) peut nuire à l'apprenabilité. Plus l'espace d'hypothèses est riche, plus il est difficile de le contraindre avec des données finies sans surapprentissage.
• La limite du scaling : Le plafond de performance d'un modèle est souvent dicté par la structure de l'apprenabilité de la tâche, et non par la taille du modèle. Si une tâche est de niveau 0 ou 1, augmenter la puissance de calcul n'apporte pas de gains prévisibles.
• Manifold Hypothesis : Les modèles réussissent sur des tâches complexes car les données réelles (code, texte) occupent une sous-variété structurée de l'espace théorique, riche en « épiplexité » (information structurelle extractible), contrairement aux données aléatoires ou aux tâches purement logiques non structurées.
• Réingénierie des tâches : Le succès du ML repose souvent sur la transformation d'un problème non apprenable en un proxy apprenable (ex: prédire le prochain token au lieu de « comprendre » le code).

5. Signification et Implications

Ce travail remet en cause le paradigme dominant selon lequel « plus de données et de calcul » résoudront tous les problèmes d'IA. Il suggère un changement de perspective :

1. Diagnostic avant Architecture : Avant de concevoir un nouveau modèle, il faut diagnostiquer le niveau d'apprenabilité de la tâche.
2. Limites du RL : Le RL pur est structurellement limité pour les tâches nécessitant une vérification logique stricte ou souffrant de récompenses mal spécifiées (Goodhart's law).
3. Stratégies futures : Pour progresser, la communauté doit :
   • Décomposer les tâches monolithiques en sous-tâches avec des feedbacks attribuables.
   • Concevoir des structures de feedback intermédiaires (échafaudage).
   • Accepter des objectifs faibles (approximations locales) plutôt que des optimalités globales.
   • Se concentrer sur la ré-encodage des problèmes en proxies statistiques exploitables.

Conclusion : L'article conclut que les échecs de l'IA ne sont pas dus à un manque de capacité des modèles, mais à une méconnaissance de la structure informationnelle des problèmes. Les prochaines avancées viendront de l'identification des tâches dont la structure rend l'apprentissage possible, plutôt que de la simple augmentation de la puissance des modèles.