🤖 machine learning

The Expressive Limits of Diagonal SSMs for State-Tracking

Cet article établit que l'expressivité des modèles d'espace d'états (SSM) complexes à valeurs diagonales à $k$ couches pour le suivi d'état est précisément limitée aux groupes résolubles possédant une série sous-normale de longueur $k$ , révélant ainsi une barrière théorique fondamentale pour les groupes non abéliens et un écart empirique entre l'expressivité et la capacité d'apprentissage.

Auteurs originaux : Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

Publié 2026-08-17

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mehran Shakerinava, Behnoush Khavari, Siamak Ravanbakhsh, Sarath Chandar

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 d'apprendre à un robot à suivre une série d'instructions qui modifient son humeur interne ou sa position. Dans le monde de l'intelligence artificielle, cela s'appelle la « modélisation de séquence ». Le robot lit une histoire mot par mot, et à chaque nouveau mot, il met à jour sa compréhension de la direction que prend l'histoire. Pendant longtemps, les robots les plus célèbres (appelés Transformers) étaient excellents pour cela, mais ils étaient aussi incroyablement gourmands en puissance informatique. Ainsi, des scientifiques ont inventé un nouveau type de robot plus svelte, un modèle d'espace d'états, ou SSM. Considérez un SSM comme un robot doté d'une petite banque de mémoire efficace qui se met à jour instantanément au fur et à mesure qu'il lit, plutôt que de relire toute l'histoire à chaque fois.

Mais voici la partie délicate : ce n'est pas parce qu'un robot est efficace qu'il est assez intelligent pour tout faire. Certaines tâches sont comme des mathématiques simples (ajouter des nombres), tandis que d'autres sont comme des puzzles complexes impliquant de permuter des objets dans un ordre spécifique. En mathématiques, ces puzzles sont souvent décrits à l'aide de « groupes », qui sont simplement des règles sophistiquées sur la façon dont les choses peuvent être combinées ou permutées. Si les règles sont simples et prévisibles (comme l'addition de nombres), le robot peut les gérer facilement. Mais si les règles sont désordonnées et dépendent de l'ordre des opérations (comme échanger trois balles de couleurs différentes où échanger le rouge puis le bleu est différent d'échanger le bleu puis le rouge), le robot peut être confus. Les scientifiques veulent savoir : quelle est la limite absolue de ce que ces robots efficaces peuvent réellement comprendre ? Peuvent-ils apprendre à résoudre les puzzles désordonnés, ou sont-ils coincés avec les plus simples ?

Ce document plonge profondément dans cette question en testant un type de robot très efficace : un « SSM diagonal ». Les chercheurs voulaient voir si ces robots pouvaient apprendre à suivre des changements d'état complexes, spécifiquement ceux impliquant des groupes non abéliens (les puzzles désordonnés dépendant de l'ordre). Ils ont découvert un mur mathématique rigide : un robot diagonal à une seule couche ne peut tout simplement pas résoudre ces puzzles désordonnés, peu importe vos efforts. Cependant, si vous empilez deux couches ou plus de ces robots les uns sur les autres, ils acquièrent théoriquement le pouvoir de les résoudre, mais seulement si le puzzle possède une structure spécifique et stratifiée (appelée « groupe résoluble »).

Voici le rebondissement qui rend l'histoire intéressante : même si les robots empilés devraient être capables de résoudre ces puzzles en théorie, les chercheurs ont découvert qu'en pratique, ils échouent souvent à le faire. C'est comme avoir une voiture avec un moteur assez puissant pour grimper une montagne, mais le conducteur (l'algorithme d'entraînement) continue de rester coincé dans un fossé et ne trouve pas le chemin pour monter. Le papier prouve que le pouvoir existe dans l'architecture, mais que les méthodes d'entraînement standard peinent à le débloquer, surtout pour les tâches non abéliennes plus complexes.

La banque de mémoire du robot

Pour comprendre ce que les auteurs ont trouvé, nous devons d'abord examiner comment ces « SSM diagonaux » fonctionnent. Imaginez un robot avec une rangée d'interrupteurs. Lorsqu'il lit un nouveau mot, il bascule ces interrupteurs selon une règle simple. Dans un SSM « Diagonal », la règle pour basculer un interrupteur ne dépend pas des autres interrupteurs ; chaque interrupteur agit de manière indépendante. Cela rend le robot incroyablement rapide et facile à entraîner, comme une équipe de travailleurs chacun faisant son propre travail sans avoir besoin de se parler.

Les chercheurs ont testé ces robots sur un jeu appelé « suivi d'état » (state-tracking). Dans ce jeu, le robot reçoit une séquence de commandes (comme « échanger la balle rouge », « faire pivoter la balle bleue ») et doit se souvenir de la disposition finale des balles. Si les commandes sont simples et commutent (ce qui signifie que l'ordre n'importe pas, comme 2 + 3 est la même chose que 3 + 2), le robot est un expert. Mais si les commandes ne commutent pas (comme mettre ses chaussettes avant ses chaussures plutôt que ses chaussures avant ses chausques), le robot fait face à un défi bien plus difficile.

Le mur théorique : Une couche vs plusieurs couches

Le document commence par une preuve mathématique solide sur ce qu'un robot à une seule couche peut faire. Les auteurs ont montré qu'un SSM diagonal à une seule couche est fondamentalement limité à la résolution de puzzles uniquement « abéliens » — ceux où l'ordre des opérations n'importe pas. Peu importe la façon dont vous réglez le robot, s'il n'a qu'une seule couche de ces interrupteurs indépendants, il ne peut pas suivre l'état d'un groupe complexe et non abélien (comme les permutations de trois objets, connu sous le nom de groupe $S_3$ ).

Cependant, l'histoire devient plus passionnante lorsque l'on empile les couches. Les auteurs ont prouvé que si vous empilez $k$ couches de ces robots diagonaux, l'équipe peut résoudre un puzzle si et seulement si le puzzle peut être décomposé en une chaîne de $k$ étapes abéliennes plus simples. Voyez cela comme une course de relais. Si le puzzle est trop complexe pour un seul coureur, vous pouvez passer le témoin à un deuxième coureur, qui le passe à un troisième. Tant que le puzzle peut être découpé en un nombre spécifique d'étapes simples et ordonnées, une équipe de ce nombre de robots peut théoriquement le résoudre. Cela signifie que la profondeur (ajouter plus de couches) est la clé pour débloquer une intelligence plus complexe, mais cela vient avec une règle stricte : vous avez besoin d'exactement autant de couches que le puzzle possède de « tranches » de complexité.

L'écart d'apprentissage : Théorie vs Réalité

C'est ici que l'intrigue s'épaissit. Les auteurs ne se sont pas contentés des mathématiques ; ils ont construit ces robots et ont essayé de les entraîner. Ils ont testé des modèles à une et deux couches sur diverses tâches, incluant l'addition simple (abélienne) et le puzzle de permutation $S_3$ plus complexe (non abélien).

Les résultats étaient un mélange de succès et de frustration. Pour les tâches simples, les robots apprenaient rapidement et pouvaient gérer de très longues séquences. Mais pour la tâche $S_3$ complexe, même si le robot à deux couches devrait être assez puissant pour la résoudre (selon leurs mathématiques), il échouait la plupart du temps. Le robot n'arrivait tout simplement pas à apprendre le bon schéma, même après des milliers d'essais.

Les chercheurs ont découvert que le problème n'était pas que le robot ne pouvait pas le faire ; la solution existait réellement dans la conception du robot. C'était plutôt comme si le robot cherchait une aiguille dans une botte de foin, et que la méthode d'entraînement standard (la descente de gradient) continuait de rater l'aiguille. Dans une expérience, ils ont essayé d'« aider » le robot en le faisant partir très près de la bonne réponse. Lorsqu'ils ont fait cela, le robot a soudainement appris la tâche et a pu gérer des séquences beaucoup plus longues que celles qu'il avait vues auparavant. Cela suggère que la solution est là, cachée dans l'« espace des poids » du robot, mais que le chemin pour la trouver est incroyablement étroit et difficile à naviguer avec un entraînement standard.

La conclusion

Le document conclut que, bien que les SSM diagonaux soient efficaces et théoriquement capables de résoudre des problèmes de suivi d'état complexes si l'on empile suffisamment de couches, il existe un écart massif entre ce qu'ils peuvent faire et ce qu'ils apprennent réellement. Les mathématiques disent qu'un robot à deux couches peut résoudre le puzzle $S_3$ , mais en pratique, il échoue généralement. Cela souligne une leçon cruciale pour la recherche en IA : le fait qu'un modèle ait le potentiel d'être intelligent ne signifie pas qu'il apprendra facilement à l'être. Les auteurs suggèrent que pour combler cet écart, nous devrons peut-être changer la façon dont nous entraînons ces modèles ou peut-être modifier légèrement leur architecture (comme permettre un peu plus d'interaction entre les interrupteurs) pour rendre le chemin vers la solution moins glissant.

En résumé, ces robots efficaces sont comme des étudiants brillants qui possèdent le savoir théorique pour résoudre un problème difficile, mais qui échouent sans cesse à l'examen parce qu'ils n'arrivent pas à comprendre comment appliquer ce savoir. Le document cartographie précisément ce dont ils sont capables, mais nous avertit également que les amener à performer réellement est un défi bien plus difficile que ce que les mathématiques suggèrent.

Résumé Technique : Les Limites Expressives des SSM Diagonaux pour le Suivi d'État

Énoncé du Problème

Les modèles d'espace d'état (SSM - State-Space Models) sont apparus comme des alternatives efficaces et parallélisables aux Transformers pour la modélisation de séquences à longue portée. Cependant, leur puissance expressive théorique reste mal comprise, particulièrement en ce qui concerne leur capacité à effectuer des tâches de suivi d'état (state-tracking). Ces tâches, qui impliquent de maintenir et de mettre à jour un état caché basé sur une séquence d'entrées (par exemple, des contrôles de parité, l'addition modulaire ou le suivi de permutations), sont étroitement liées aux langages réguliers et sont critiques pour des applications telles que l'exécution de code et l'analyse de programmes.

Alors que les Transformers sont connus pour éprouver des difficultés avec certaines tâches de suivi d'état (spécifiquement celles nécessitant des opérations de groupes non résolubles), les SSM ont été initialement supposés exceller grâce à leur nature récurrente. Des travaux récents ont montré que les SSM standards (y compris les variantes invariantes dans le temps et diagonales) échouent même sur des tâches simples et résolubles comme la parité. Cet article étudie les limites expressives précises des SSM Diagonaux à Valeurs Complexes Dépendants de l'Entrée (DCD) sur des tâches séquentielles de suivi d'état, en se concentrant spécifiquement sur la capacité à suivre des groupes finis. La question centrale est : Quelles classes de groupes un SSM DCD à $k$ couches peut-il théoriquement représenter, et les algorithmes d'apprentissage standards peuvent-ils trouver de manière fiable ces représentations ?

Méthodologie

Les auteurs emploient une combinaison d'analyse de la théorie des groupes et d'évaluation empirique.

Cadre Théorique

Définition du Modèle : L'étude se concentre sur les SSM DCD, où la matrice de transition $A(x_t)$ est diagonale et à valeurs complexes, et dépend de l'entrée $x_t$ . La mise à jour de l'état suit une récurrence affine : $h_t = A(x_t)h_{t-1} + b(x_t)$ .
Connexion avec la Théorie des Groupes : Les auteurs associent les tâches de suivi d'état à la simulation de groupes finis. Un modèle suit un groupe $G$ s'il peut calculer le produit cumulé d'une séquence d'éléments de groupe.
Analyse à Couche Unique : Les auteurs prouvent qu'un SSM DCD à une seule couche ne peut pas suivre un groupe non-Abélien avec une précision finie. Ils démontrent que même avec un terme de biais dépendant de l'entrée $b(x_t)$ et un décodeur, la nature commutative des matrices diagonales restreint le modèle aux groupes Abéliens.
Analyse Multi-couches : L'article étend cela aux SSM DCD à $k$ $k$ couches. Ils établissent une condition nécessaire et suffisante pour l'expressivité : un SSM DCD à $k$ $k$ couches peut suivre un groupe $G$ $G$ si et seulement si $G$ $G$ admet une série sous-normale de longueur $k$ avec des facteurs Abéliens.
- Mathématiquement, cela signifie que $G = G_k \trianglerighteq G_{k-1} \trianglerighteq \dots \trianglerighteq G_1 \trianglerighteq \{e\}$ , où chaque quotient $G_{i+1}/G_i$ est Abélien.
- Ce résultat identifie la plage d'expressivité précise des SSM DCD à $k$ couches comme étant la classe des groupes résolubles avec une profondeur structurelle spécifique.
Preuve Constructive : Les auteurs fournissent une construction concrète pour un SSM DCD à 2 couches suivant le groupe symétrique $S_3$ (le plus petit groupe non-Abélien résoluble) en le décomposant en une cascade de deux automates Abéliens ( $C_2$ et $C_3$ ).

Évaluation Empirique

Les auteurs évaluent les variantes à une et deux couches de plusieurs architectures SSM (Mamba, Negative Mamba, AUSSM, et AUSSM simplifié) aux côtés des RNN.

Tâches : Suivi d'état sur divers groupes, incluant des groupes Abéliens ( $C_2, C_6, C_{24}, C_{60}$ ), des produits de groupes cycliques ( $C_2 \times C_4, C_3 \times C_6$ ), et des groupes non-Abéliens résolubles ( $S_3, A_4$ ). Le groupe non-résoluble $A_5$ est inclus comme groupe de contrôle.
Protocole : Les modèles sont entraînés sur des séquences allant jusqu'à une longueur de 60 en utilisant l'apprentissage curriculaire et testés pour la généralisation sur des séquences allant jusqu'à 1000.

Contributions Clés

Caractérisation Théorique : L'article fournit la première caractérisation précise du pouvoir expressif des SSM diagonaux. Il prouve que :
- Les SSM DCD à une couche sont limités aux groupes Abéliens.
- Les SSM DCD à $k$ couches sont limités aux groupes résolubles possédant une série sous-normale de longueur $k$ .
- Cela établit un bénéfice théorique strict de la profondeur pour la modélisation de la dynamique non-Abélienne sous la contrainte diagonale.
Identification du Fossé d'Apprentabilité : Bien que la théorie prouve que les SSM DCD à 2 couches peuvent représenter des groupes non-Abéliens comme $S_3$ , les résultats empiriques montrent que l'optimisation standard basée sur le gradient échoue à apprendre ces solutions. Les modèles échouent systématiquement à se généraliser sur de longues séquences pour $S_3$ et $A_4$ , malgré la capacité théorique de le faire.
Aperçu de l'Initialisation : Les auteurs démontrent qu'initialiser un modèle à proximité de la solution analytique (dérivée de leur construction théorique) lui permet d'apprendre et de généraliser. Cela suggère que l'échec n'est pas dû à un manque de capacité dans l'espace des poids, mais plutôt à la difficulté du paysage d'optimisation pour trouver ces encodages spécifiques sans guidage.

Résultats

Groupes Abéliens : Les modèles à une couche (spécifiquement Negative Mamba et AUSSM) apprennent et généralisent avec succès sur les tâches Abéliennes (ex: parité, comptage modulaire).
Groupes Non-Abéliens Résolubles : Les modèles multi-couches (2 couches) théoriquement capables de suivre $S_3$ et $A_4$ échouent à se généraliser en pratique. Ils atteignent une grande précision sur les longueurs d'entraînement mais s'effondrent sur des séquences de test plus longues.
Groupes Non-Résolubles : Comme prévu, aucun modèle (y compris les SSM DCD multi-couches) n'apprend le groupe non-résoluble $A_5$ .
Comparaison avec les RNN : Les RNN, qui n'ont aucune barrière d'expressivité théorique pour ces tâches, réussissent généralement à apprendre et à généraliser, soulignant que l'échec des SSM est spécifique à leurs contraintes architecturales et à leur dynamique d'optimisation, et non simplement à la difficulté de la tâche.

Signification et Revendications

L'article affirme établir une distinction nette entre expressivité et apprenabilité dans les SSM diagonaux.

Expressivité : La profondeur fournit un chemin discipliné et théoriquement prouvable pour augmenter le pouvoir expressif des SSM diagonaux, passant des groupes Abéliens aux groupes résolubles. Les auteurs définissent la frontière exacte de cette capacité en utilisant la théorie des groupes.
Apprentabilité : Les auteurs soutiennent que bien que ces modèles possèdent la capacité théorique de résoudre des tâches de suivi d'état complexes, les algorithmes d'entraînement standard peinent à découvrir les configurations de poids requises. Cela suggère que le "biais inductif" de la diagonalité, bien qu'efficace, peut activement entraver la découverte de structures non-Abéliennes.
Implications : Ce travail suggère que le simple empilement de couches diagonales est insuffisant pour obtenir des performances fiables sur des tâches non-Abéliennes sans de meilleures stratégies d'optimisation ou des modifications architecturales (ex: structures bloc-diagonales). Il appelle à une séparation des préoccupations lors de l'évaluation de nouvelles architectures de séquences : la capacité théorique d'un modèle ne garantit pas son utilité pratique.

Les auteurs concluent que les progrès futurs nécessiteront non seulement d'élargir la frontière de l'expressivité (ex: via des transitions bloc-diagonales), mais aussi de développer des méthodes d'entraînement capables de naviguer de manière fiable dans le paysage de perte pour trouver des solutions qui existent, en principe, de manière garantie.