Functorial Neural Architectures from Higher Inductive Types

Cet article démontre que la généralisation compositionnelle des réseaux de neurones équivaut à la fonctorialité du décodeur, proposant une architecture basée sur les types inductifs supérieurs qui garantit cette propriété par construction et surpasse significativement les modèles non fonctoriels comme l'attention sur des espaces topologiques variés.

L'essentiel

🧩 Le Problème : Pourquoi les IA sont de mauvaises cuisinières

Imaginez que vous apprenez à cuisiner. Vous savez faire une omelette (œufs + feu) et vous savez faire une salade (légumes + vinaigre).
Un humain intelligent peut facilement combiner ces deux connaissances pour inventer une omelette aux légumes, même s'il n'a jamais vu cette recette spécifique dans un livre de cuisine.

Les réseaux de neurones actuels (les "cerveaux" de l'IA) échouent lamentablement sur ce genre de tâche. Si on leur apprend à additionner deux chiffres, ils paniquent souvent quand on leur demande d'en additionner cinq. Ils ne comprennent pas la logique de la recette ; ils mémorisent simplement les plats qu'ils ont déjà vus.

Les auteurs de ce papier disent : "Ce n'est pas un manque de mémoire ou de puissance. C'est un défaut de conception architecturale."

🏗️ La Solution : Construire avec des "Lego" mathématiques

Pour régler ce problème, les chercheurs ont proposé une nouvelle façon de construire les IA, basée sur des mathématiques très abstraites appelées Types Inductifs Supérieurs (HIT).

Pour faire simple, imaginez que vous ne construisez pas une IA en la laissant "apprendre" par essais et erreurs, mais en lui donnant des plans de construction rigoureux basés sur la forme de l'espace qu'elle doit naviguer.

Voici les trois piliers de leur méthode, expliqués avec des métaphores :

1. Les "Moteurs" indépendants (Les Foncteurs)

Dans une IA classique (comme les Transformers qui utilisent l'attention), tout le monde se regarde tout le temps. Si vous dites "Aller à gauche", le modèle regarde aussi ce qui se passe à droite, ce qui crée du bruit.

Dans la nouvelle architecture (appelée Type-B), l'IA fonctionne comme un train de wagons Lego.

• Chaque mot de votre phrase est un wagon.
• Chaque wagon est construit indépendamment par un petit moteur spécialisé.
• Ensuite, on les clipse les uns aux autres (concaténation).
• Le résultat ? Si vous savez faire un wagon "gauche" et un wagon "droite", vous savez faire "gauche + droite" sans jamais avoir besoin de réapprendre. C'est la compositionnalité.

2. La "Preuve" mathématique (Les 2-cellules)

Parfois, les règles sont plus complexes. Imaginez un espace où faire un tour complet dans un sens (A) puis un tour dans l'autre (B) ne revient pas au même point que de faire B puis A (comme sur un tore ou une bouteille de Klein).

Les auteurs ajoutent une pièce magique appelée 2-cellule. C'est comme un tutoriel vidéo intégré dans l'architecture.

• Si l'IA doit faire une séquence complexe (A puis B), elle utilise ce tutoriel pour savoir comment déformer son chemin pour respecter les règles de l'espace.
• C'est comme si l'IA avait un "guide de voyage" qui lui dit : "Attention, si tu fais ce chemin, tu dois faire une pirouette ici pour ne pas tomber dans le trou."

3. Pourquoi l'Attention (la méthode actuelle) échoue

L'attention, utilisée par ChatGPT et autres, est comme une réunion de bureau bruyante. Tout le monde parle à tout le monde en même temps.

• Le papier prouve mathématiquement que cette méthode ne peut jamais être parfaitement compositionnelle.
• Même si vous changez les paramètres, l'attention mélange toujours les informations de manière désordonnée. C'est comme essayer de construire un mur de Lego en jetant les briques au hasard et en espérant qu'elles s'assemblent : ça peut marcher sur de petits murs, mais ça s'effondre sur les grands.

🌍 Les Expériences : Trois Terrains de Jeu

Pour tester leur théorie, ils ont fait jouer leurs nouvelles IA sur trois terrains mathématiques différents :

1. Le Tore (La forme de donut) : C'est simple et symétrique.
   • Résultat : La nouvelle IA est 2 à 3 fois meilleure que les anciennes. Elle ne se perd pas.
2. Le "Wedge" (Deux cercles qui se touchent) : Ici, l'ordre compte beaucoup (A puis B n'est pas pareil que B puis A).
   • Résultat : C'est là que l'ancienne IA s'effondre totalement (elle confond les chemins). La nouvelle IA est 5 à 10 fois meilleure. Elle comprend parfaitement la logique.
3. La Bouteille de Klein (Un espace tordu) : C'est le niveau expert. Il faut une "pièce de preuve" (la 2-cellule) pour réussir.
   • Résultat : Sans la pièce de preuve, l'IA fait des erreurs. Avec elle, elle corrige ses erreurs de 46 %. C'est la première fois qu'une IA utilise une "preuve mathématique" apprise pour corriger sa géométrie.

💡 La Conclusion en une phrase

Au lieu d'essayer d'enseigner à une IA à "comprendre" la composition par la force brute (ce qui échoue), il faut construire l'IA avec la composition déjà intégrée dans ses fondations, comme un architecte qui dessine un pont capable de supporter le poids, plutôt que d'espérer que le béton durcisse assez fort.

En résumé :

• Ancienne méthode : "Apprends par cœur toutes les phrases." (Échoue sur le long terme).
• Nouvelle méthode : "Apprends la règle de construction, et assemble les pièces." (Réussit toujours, même sur des phrases jamais vues).

C'est une avancée majeure pour rendre les robots et les intelligences artificielles plus fiables, surtout lorsqu'ils doivent planifier des tâches complexes ou naviguer dans des environnements nouveaux.

Résumé technique

1. Problématique : L'échec de la généralisation compositionnelle

Les réseaux de neurones actuels échouent systématiquement à la généralisation compositionnelle, c'est-à-dire la capacité à produire des sorties correctes pour de nouvelles combinaisons de parties connues (ex: additionner des nombres à 5 chiffres après avoir appris l'addition à 2 chiffres, ou naviguer autour de deux obstacles après en avoir appris un seul).

• Cause identifiée : L'article soutient que cet échec n'est pas dû à un manque de capacité (scaling) mais à une défaillance architecturale.
• Hypothèse centrale : La généralisation compositionnelle est équivalente à la fonctorialité du décodeur. Un décodeur doit respecter la structure algébrique de l'entrée (concaténation de mots) dans la structure de la sortie.
• Limitation des Transformers : L'article démontre que l'attention auto-similaire (softmax), mécanisme dominant des modèles modernes, est intrinsèquement non fonctorielle pour toute tâche compositionnelle non triviale, car elle mélange les informations entre segments de manière dépendante du contenu, violant ainsi la structure de composition.

2. Méthodologie : Compilation de Types Inductifs Supérieurs (HIT)

Les auteurs proposent un cadre théorique et pratique pour compiler des spécifications mathématiques (Topologie et Théorie des Types) directement en architectures neuronales.

A. Fondements Théoriques

• Types Inductifs Supérieurs (HIT) : Utilisés pour spécifier les espaces topologiques via leurs générateurs (points de base, boucles) et leurs relations (cellules de dimension 2, homotopies).
  • Exemples étudiés : Le tore ($T^2$, groupe abélien $\mathbb{Z}^2$), le bouquet de deux cercles ($S^1 \vee S^1$, groupe libre $F_2$), et la bouteille de Klein ($K$, produit semi-direct $\mathbb{Z} \rtimes \mathbb{Z}$).
• Categorical Deep Learning : Les réseaux de neurones sont modélisés comme des applications paramétrées dans une catégorie. La composition des entrées doit correspondre à la composition des applications (foncteur monoidal).

B. L'Architecture "Transport" (Type-B)

Les auteurs définissent une compilation functorielle $D : BG \to \text{ParLoop}(X)$ :

1. Générateurs : Chaque générateur du groupe fondamental $\pi_1(X)$ est mappé à un réseau neuronal indépendant (MLP) générant une boucle paramétrique.
2. Composition : La concaténation de mots est implémentée par une concaténation structurelle (liste) des segments générés indépendamment. Cela garantit que $D(w_1 \cdot w_2) = D(w_1) \oplus D(w_2)$ par construction, et non par apprentissage.
3. Cellules 2 (Preuves) : Pour les relations non triviales (ex: $bab^{-1} = a^{-1}$ sur la bouteille de Klein), un réseau neuronal supplémentaire (homotopie apprise) est ajouté pour déformer continûment la boucle résultante, assurant la cohérence topologique.

C. Preuve Formelle

• Les résultats clés (fonctorialité stricte des décodeurs de transport et impossibilité pour l'attention) sont formalisés et vérifiés dans Cubical Agda, un assistant de preuve basé sur la théorie des types homotopique.
• Cela garantit que les propriétés de compositionnalité tiennent pour toutes les valeurs de paramètres et toutes les longueurs de mots, et non seulement sur un jeu de données d'entraînement.

3. Contributions Clés

1. Foncteur de Compilation : Une méthode automatique pour transformer des spécifications HIT en architectures neuronales, garantissant la correction compositionnelle par construction.
2. Théorèmes d'Impossibilité : Preuve formelle que l'attention softmax ne peut jamais être un foncteur monoidal pour des groupes non triviaux, quelle que soit la configuration des poids.
3. Distinction Type-A / Type-B :
   • Type-A (Non-fonctoriel) : Dépendances croisées entre segments (ex: Transformers, GRU).
   • Type-B (Fonctoriel) : Segments générés indépendamment et concaténés structurellement (ex: Décodeur de transport).
4. Validation Expérimentale : Une hiérarchie d'expériences sur trois espaces topologiques validant chaque niveau de la théorie (contraintes d'enroulement, composition monoidale, et preuves d'homotopie).

4. Résultats Expérimentaux

Les expériences comparent les architectures Type-A (Transformers, Cover, Transport-Attention) et Type-B (Transport, Homotopy) sur la génération de courbes géométriques continues.

• Tore ($T^2$, Abélien) :
  • Les architectures Type-B surpassent les Type-A d'un facteur 2 à 2,7x sur des mots longs (extrapolation).
  • L'erreur par segment reste constante pour les Type-B, tandis qu'elle se dégrade pour les Type-A.
• Bouquet de cercles ($S^1 \vee S^1$, Groupe Libre $F_2$) :
  • L'écart s'élargit considérablement (5,5 à 10x).
  • Les modèles Type-A échouent catastrophiquement à distinguer l'ordre des générateurs (ex: $ab \neq ba$), tombant à 14% de précision sur la circularité à $L=10$, tandis que les Type-B maintiennent 100% de précision.
  • Les GRU (séquentiels) font mieux que les Transformers mais restent inférieurs aux Type-B car ils manquent de composition structurelle stricte.
• Bouteille de Klein ($K$, Relation non triviale) :
  • C'est le test critique pour la cellule 2 (l'homotopie apprise).
  • Pour les mots non canoniques (ex: $abab$) qui activent la relation $bab^{-1} = a^{-1}$, l'ajout du terme de preuve $H$ (décodeur Homotopy) réduit l'erreur de 46% par rapport au décodeur de transport simple.
  • Cela démontre que l'apprentissage d'une transformation naturelle (2-cellule) est nécessaire et mesurable empiriquement.

5. Signification et Implications

• Changement de Paradigme : L'article déplace la question de "Le réseau peut-il apprendre à composer ?" vers "L'architecture garantit-elle la fonctorialité ?".
• Généralisation Garantie : Contrairement aux méthodes empiriques, cette approche offre des garanties théoriques de généralisation hors distribution (ODD) pour n'importe quelle longueur de séquence, basées sur la structure topologique du problème.
• Limites des Transformers : Il fournit une preuve structurelle (et non seulement empirique) expliquant pourquoi les Transformers échouent sur des tâches comme SCAN ou COGS : l'attention brise la factorisation monoidale nécessaire à la composition.
• Pipeline Vérifié : La proposition d'un pipeline "Spécifier (HIT) → Vérifier (Agda) → Compiler → Entraîner" ouvre la voie à des architectures neuronales certifiées pour des domaines à structure compositionnelle forte (planification robotique, programmes modulaires, chimie moléculaire).

En résumé, cet article établit un lien fondamental entre la topologie algébrique et l'apprentissage automatique, démontrant que la généralisation compositionnelle robuste nécessite une architecture qui respecte la structure catégorielle du problème, une propriété que les architectures basées sur l'attention ne peuvent posséder.