🤖 machine learning

Transformer Circuits Can Realize Clustering Algorithms

Cet article démontre qu'une architecture de type transformer, nommée le $k$ -means transformer, peut théoriquement et empiriquement implémenter l'algorithme de Lloyd pour le partitionnement en $k$ -moyennes en utilisant des mécanismes de circuits standards, tout en apprenant à surpasser les performances de l'algorithme traditionnel et à se généraliser naturellement à diverses variantes de partitionnement grâce à des modifications architecturales.

Auteurs originaux : Kenneth L. Clarkson, Lior Horesh, Takuya Ito, Charlotte Park, Parikshit Ram

Publié 2026-08-11

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kenneth L. Clarkson, Lior Horesh, Takuya Ito, Charlotte Park, Parikshit Ram

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 un monde où les ordinateurs ne se contentent pas de deviner des motifs, mais apprennent réellement à suivre des instructions précises, étape par étape, comme un mathématicien humain. C'est le domaine de l'apprentissage automatique, et plus précisément d'une branche appelée « transformers ». Vous connaissez peut-être les transformers comme les moteurs ultra-intelligents derrière les chatbots et les générateurs d'images, mais au fond, ce ne sont que de vastes réseaux de mathématiques qui observent des données et tentent d'en trouver les connexions. Habituellement, nous apprenons à ces réseaux à être doués pour deviner le mot suivant dans une phrase ou pour identifier un chat dans une photo. Mais une grande question que les scientifiques se posent est la suivante : ces machines flexibles et apprenantes peuvent-elles réellement effectuer des problèmes mathématiques exacts et rigides, comme trier un tas d'objぉ désordonnés en groupes nets ? Il ne s'agit pas seulement de créer un meilleur chatbot ; il s'agit de comprendre si ces cerveaux numériques peuvent véritablement « penser » comme un programme informatique ou s'ils sont simplement très doués pour en imiter un.

Le document que vous allez explorer plonge directement dans ce mystère en s'attaquant à un problème classique appelé clustering k-moyennes (k-means clustering). Voyez cela comme un jeu de tri de billes. Imaginez que vous avez un sac géant de billes de différentes couleurs et tailles, toutes mélangées. Votre objectif est de les trier en $k$ groupes (disons 5 groupes) de sorte que les billes d'un même groupe soient aussi similaires que possible entre elles. Depuis des décennies, la méthode standard pour faire cela est un algorithme appelé algorithme de Lloyd. C'est une recette très spécifique, rigide : choisissez 5 emplacements aléatoires comme « centres », déplacez chaque bille vers le centre le plus proche, puis déplacez les centres vers l'emplacement moyen de leurs nouvelles billes, et répétez l'opération jusqu'à ce que les groupes ne changent plus. C'est une danse mathématique parfaite, mais il est difficile d'apprendre à une machine apprenante à le faire exactement, car la machine préfère généralement « deviner » plutôt que de suivre des règles strictes.

Les chercheurs de ce document, travaillant chez IBM Research et au MIT, ont posé une question audacieuse : pouvons-nous construire un transformer qui ne se contente pas de deviner comment trier les billes, mais qui exécute réellement les étapes exactes de l'algorithme de Lloyd ? Et plus impressionnant encore : pouvons-nous lui apprendre à le faire mieux que la recette originale ?

Ils ont construit un type spécial de transformer qu'ils appellent le « k-means transformer ». Au lieu de laisser la machine apprendre à trier par essais et erreurs, ils ont conçu les rouages internes de la machine (ses mécanismes d'attention et ses connexions) pour imiter physiquement les mathématiques de l'algorithme de Lloyd. Ils ont prouvé mathématiquement que si vous réglez les poids de la machine de la bonne manière, une couche de ce transformer effectue exactement une étape de la danse du tri. Si vous empilez dix couches, elle effectue dix étapes, répliquant parfaitement l'algorithme classique. C'est comme construire un robot qui ne se contente pas d'apprendre à marcher ; vous le construisez avec des jambes mécaniquement verrouillées pour faire exactement le même pas qu'un humain.

Mais l'histoire ne s'arrête pas là. L'équipe a ensuite pris cette machine et l'a laissée apprendre à partir de zéro en lui montrant des milliers de puzzles de tri différents. Ils ont découvert quelque chose de surprenant : le transformer entraîné ne s'est pas contenté de copier l'algorithme de Lloyd ; il a appris une nouvelle façon de trier, plus intelligente. Testée sur de nouveaux ensembles de données inédits, cette machine apprise a créé des groupes plus serrés et plus précis que l'algorithme de Lloyd classique ne le pouvait. C'était comme si le robot avait appris à danser les pas si bien qu'il avait inventé une meilleure chorégraphie.

Les chercheurs ont également montré que cette idée de « la machine comme algorithme » est incroyablement flexible. En modifiant les composants internes de leur transformer — comme la façon dont il prête attention aux données ou comment il normalise les nombres — ils pouvaient instantanément transformer leur machine en différents types d'algorithmes de tri. Ils pouvaient le faire gérer un tri « souple » (où une bille peut appartenir partiellement à deux groupes), un tri « sphérique » (pour des données qui vivent sur une forme de sphère), ou même un tri « élagué » (qui ignore les billes aberrantes ou atypiques qui ne s'intègrent nulle part).

En résumé, ce document prou parfaitement que les transformers ne sont pas seulement des devineurs flous ; ils sont assez puissants pour être construits comme des calculateurs exacts, étape par étape, pour des problèmes mathématiques complexes. Plus important encore, il montre que lorsque nous laissons ces calculateurs apprendre, ils peuvent découvrir de nouvelles façons améliorées de résoudre ces mêmes problèmes, comblant ainsi le fossé entre l'informatique rigide et l'intelligence artificielle flexible.

Résumé technique : Les circuits de Transformers peuvent réaliser des algorithmes de partitionnement

Énoncé du problème

Le partitionnement (clustering), et particulièrement le partitionnement $k$ -moyennes ( $k$ -means), est un problème d'optimisation combinatoire fondamental en informatique, pourtant il est connu pour être NP-difficile. Bien que les architectures de deep learning, spécifiquement les transformers, excellent dans l'apprentissage de caractéristiques hiérarchiques à partir de données brutes, la mesure dans laquelle elles peuvent implémenter des calculs algorithmiques discrets et exacts reste incertaine. Cet article comble le fossé entre les algorithmes de partitionnement discrets classiques et les architectures neuronales modernes en étudiant si les mécanismes de circuits de transformers peuvent instancier exactement les étapes itératives de l'algorithme de Lloyd pour le partitionnement $k$ -moyennes.

Méthodologie

L'architecture Transformer $k$ -moyennes

Les auteurs proposent une architecture transformer encodeur-décodeur spécifique conçue pour exécuter l'algorithme de Lloyd de manière in-context. L'architecture utilise des composants de transformer standards : auto-attention, attention croisée, connexions résiduelles et réseaux de neurones à propagation avant (FFN), mais avec des paramétrages et des définitions de scores d'attention spécifiques.

Plongements d'entrée (Input Embeddings) :
- Encodeur : Traite l'ensemble de $n$ points de données $X \in \mathbb{R}^{d \times n}$ . Chaque point $x_i$ est plongé dans un vecteur de dimension $(d+k)$ $[x_i^\top, y_i^\top]^\top$ , où $y_i \in \{0,1\}^k$ représente l'assignation de cluster un-hot (initialement nulle).
- Décodeur : Traite les $k$ centres de clusters $C \in \mathbb{R}^{d \times k}$ . Chaque centre $c_j$ est plongé dans un vecteur de dimension $(d+k)$ $[c_j^\top, e_j^\top]^\top$ , où $e_j$ est le vecteur caractéristique $j$ -ième (indice un-hot).
Mécanismes d'attention :
- Attention Euclidienne : Pour les mises à jour d'assignation de points par l'encodeur, l'article utilise une version limite de l'attention soft-max basée sur les distances euclidiennes au carré négatives : $A_{ji} = -\|Kz_j - Qx_i\|^2$ . Lorsque le paramètre de température $\gamma \to \infty$ , cela approxime une opération arg-max, assignant les points au centre le plus proche.
- Attention Produit Scalaire (Dot-Product) : Pour les étapes de mise à jour des centres par le décodeur, une attention produit scalaire standard est utilisée pour calculer la moyenne des points assignés.
- Connexions Résiduelles : Utilisées pour réinitialiser les assignations ou les centres actuels à zéro avant la mise à jour par attention croisée, implémentant ainsi efficacement les étapes d'« assignation » et de « mise à jour » de l'algorithme de Lloyd en une seule passe directe (forward pass).
Construction Théorique :
- Théorème 2.1 : Prouve qu'un transformer à $T$ couches avec des poids fixes spécifiques (définis dans l'Équation 5) et une attention soft-max limite ( $\gamma \to \infty$ ) exécute exactement $T$ itérations de l'algorithme de Lloyd. La taille du modèle est $O(d+k)$ , ce qui est plus petit que la taille de l'entrée $O(d(n+k))$ .
- Théorème 2.2 : Démontre qu'un transformer à attention produit scalaire standard peut également exécuter exactement l'algorithme de Lloyd si les plongements de tokens sont augmentés de normes au carré et qu'un réseau de neurones à propagation avant (FFN) avec une activation quadratique rectifiée est utilisé pour mettre à jour les centres.

Expériences d'Apprentissage

Les auteurs entraînent un transformer à une seule couche sur une distribution de tâches de partitionnement (échantillons de mélanges gaussiens) en minimisant une borne supérieure lissée de l'objectif $k$ -moyennes. L'entraînement utilise un soft-max standard ( $\gamma=1$ ) plutôt que le cas limite théorique. Le modèle entraîné est ensuite évalué sur des tâches inconnues, en faisant varier la taille de l'échantillon, la dimensionnalité et les stratégies d'initialisation (aléatoire vs $k$ -means++).

Contributions Clés

Implémentation Exacte de l'Algorithme de Lloyd : L'article fournit une preuve théorique et une validation empirique qu'une architecture de transformer avec des choix de paramètres spécifiques implémente exactement l'algorithme de Lloyd pour le partitionnement $k$ -moyennes. Cela comble le fossé entre les étapes algorithmiques discrètes et les mécanismes de circuits neuronaux continus.
Algorithme de Partitionnement Apprenable : Lorsqu'il est entraîné sur une distribution de tâches de partitionnement, l'architecture de transformer apprend un algorithme de partitionnement généralisable qui surpasse l'algorithme de Lloyd standard en termes de qualité de partitionnement (objectif $k$ -moyennes plus faible), même en utilisant une attention soft-max standard ( $\gamma=1$ ).
Variantes Architecturales pour Divers Algorithmes : En modifiant des mécanismes de circuits de transformer spécifiques (par exemple, types d'attention, normalisation, fonctions d'activation), les auteurs montrent comment instancier divers algorithmes de partitionnement existants et nouveaux :
- Soft $k$ -means : Obtenu en remplaçant le soft-max limite par un soft-max standard et une attention linéaire.
- Spherical $k$ -means : Obtenu en utilisant l'attention produit scalaire et une normalisation par token (ex: RMSNorm).
- Trimmed $k$ -means : Obtenu en remplaçant le soft-max par une attention norm-max (arg-max régularisé).
- Robust $k$ -means : Obtenu en utilisant une attention sparse soft-max.
- Randomized $k$ -medoids : Obtenu en utilisant une attention Gumbel-softmax pour sélectionner les points de données réels comme centres.

Résultats

Équivalence Théorique : La validation numérique confirme qu'avec une température grande mais finie ( $\gamma = 10^4$ ), la trajectoire des centres de clusters et des assignations finales du transformer correspond exactement à l'algorithme de Lloyd sur 10 itérations.
Supériorité de Performance : Dans les expériences d'apprentissage, le transformer entraîné converge vers un objectif log- $k$ -moyennes moyen de $\sim 5,0$ , surpassant l'algorithme de Lloyd ( $\sim 5,25$ ) sur les mêmes tâches. Cette amélioration se maintient lorsque le transformer est testé sur des tâches avec différentes tailles d'échantillons (généralisation) et différents schémas d'initialisation (ex: $k$ -means++), malgré un entraînement uniquement sur des initialisations aléatoires.
Dimensionnalité des Plongements : Les études d'ablation montrent que les $k$ dimensions supplémentaires dans les plongements de tokens (total $d+k$ ) sont cruciales. Un modèle avec seulement $d$ dimensions échoue à égaler la performance de Lloyd, convergeant vers un objectif plus élevé ( $\sim 5,35$ ).
Analyse des Poids : Les poids appris présentent des similitudes structurelles avec les constructions théoriques (par exemple, des formes diagonales dominantes dans les matrices $Q^\top K$ ) mais montrent également des différences distinctes, suggérant que l'algorithme appris dévie de l'algorithme de Lloyd standard de manières spécifiques (par exemple, dans la façon dont les centres sont mis à jour).

Signification et Revendications

L'article affirme que les mécanismes de circuits de transformers peuvent instancier des routines algorithmiques exactes pour le partitionnement, fournissant une « approche générale pour développer des algorithmes de partitionnement alternatifs et nouveaux grâce à des modifications architecturales interprétables ».

Transparence Algorithmique : Ce travail démontre que les transformers ne sont pas seulement des approximateurs de fonctions boîtes noires, mais peuvent être explicitement conçus pour exécuter des algorithmes discrets et bien définis comme celui de Lloyd.
Apprentabilité : Crucialement, l'article montre que cette architecture spécifiée à la main est non seulement théoriquement capable, mais aussi apprenable à partir de données pour produire des algorithmes qui surpassent la référence classique.
Cadre pour l'Innovation : En considérant le partitionnement comme un « squelette de transformer », les auteurs fournissent un cadre où la modification des composants standards (attention, normalisation) produit diverses variantes de partitionnement, incluant des versions robustes et randomisées.

Les auteurs notent des limites, spécifiquement que leurs résultats théoriques reposent sur une attention soft-max limite difficile à rétropropager, bien qu'ils montrent que le modèle fonctionne avec un soft-max standard. Ils précisent également que si le modèle généralise à un $n$ plus grand (nombre de points), il ne supporte pas actuellement la généralisation à un $k$ plus grand (nombre de clusters) s'il est entraîné sur un $k$ fixe. Ce travail se positionne comme un fondement pour l'exploration ultérieure des implémentations neuronales de méthodes classiques.