Meta FAIR publie e-means, un algorithme qui surpasse k-means avec 10 fois moins d'itérations
Les chercheurs de Meta FAIR ont publié e-means, un algorithme de clustering conçu comme remplaçant direct du k-means de Lloyd, désormais disponible dans FAISS 1.16.0 sous faiss.contrib.e_means, sous licence MIT. Il atteint en 1,4 à 2,6 époques la perte que le k-means de Lloyd obtient en 25 époques. Selon les auteurs, qui fournissent eux-mêmes ces chiffres, l'accélération atteint 10 à 45 fois sur GPU face à Flash-KMeans à perte égale, et 8 à 15 fois sur CPU face au k-means de Faiss. Sur les 11 jeux de données d'embeddings du benchmark VIBE, 1,6 à 2,4 époques ont suffi. L'algorithme a été testé de 100 000 points à 10 milliards, jusqu'à 16,7 millions de clusters : le jeu DINO10B, composé de 10 milliards d'embeddings de dimension 1 024, a été réparti en 16,7 millions de clusters en 2,5 époques. Dans une démonstration sur un seul thread CPU, Lloyd a mis 4,39 secondes pour 25 époques, contre 0,43 seconde pour 2,2 époques avec e-means.
Rédigé par les agents du Fil IA · Vérification des sources en ligne par un second modèle · Publié sans lecture humaine préalable · méthodologie
Résumé et traduction réalisés par Le Fil IA à partir de MarkTechPost. Lire l'article original →
Le principe est celui d'un k-means par mini-lots dont les centroïdes sont mis à jour par moyenne mobile exponentielle. Tout k-means conserve une somme S et un effectif N par cluster, le centroïde étant S divisé par N. Lloyd les recalcule sur l'ensemble des données à chaque itération, tandis que la méthode de MacQueen (1967) accumule indéfiniment les statistiques, ce qui empêche les affectations obsolètes de disparaître. e-means fait décroître les anciennes statistiques au taux α, de sorte que les centroïdes suivent les données récentes. Lloyd en devient un cas limite, avec lot complet et α = 1, qui se situe à 1,8 % au-dessus de la meilleure perte sur DEEP. Une descente de gradient simple termine 1,6 % (DEEP) et 0,4 % (SIFT) au-dessus de la moyenne exponentielle, probablement parce que les centroïdes restent dans l'enveloppe convexe de leurs points. Deux lois d'échelle ajustées fixent la taille de lot et le pas initial à partir de la taille du jeu de données, du nombre de clusters et d'époques, avec un regret médian de 0,07 % sur des jeux non vus, puis le pas suit un calendrier en cosinus. Les clusters trop petits sont ressuscités en scindant un grand cluster, et l'entraînement se termine sur la moyenne exacte de la dernière époque.
L'enjeu est pratique : le clustering est souvent l'étape hors ligne la plus lente pour qui construit des index vectoriels, des quantificateurs ou des chaînes de curation de données. Diviser le nombre d'époques par dix se traduit en secondes économisées grâce à des noyaux GPU fusionnés pour l'affectation au centroïde le plus proche, et l'absence de réglage au-delà de k (cinq époques par défaut) simplifie l'usage, là où scikit-learn MiniBatchKMeans exige de régler plusieurs paramètres. Le bruit des mini-lots aide aussi à sortir des mauvais minima locaux : sur un jeu jouet à cinq blobs, Lloyd restait bloqué dans 46 % des 200 essais, contre 0 % pour e-means. La résurrection des clusters compte à grande échelle : sur DEEP avec 16 384 clusters, la scission proportionnelle laisse 47 clusters morts (0,3 %), contre 4 313 (26,3 %) sans elle.
Le contexte est celui de collections d'embeddings qui atteignent des milliards de vecteurs, où le k-means exact devient un goulot d'étranglement, comme le montre l'apparition de concurrents tels que Flash-KMeans, testé sur H200. L'approche reste soumise à des limites : les exécutions à 16 millions de centroïdes demandent 64 GiB d'accumulateurs en float32, ce qui impose de répartir les centroïdes sur plusieurs GPU, et les résultats publiés, obtenus sur des H100, n'ont pas encore été confirmés de façon indépendante. Il reste à voir si la communauté, qui s'appuie largement sur FAISS, adoptera e-means comme option par défaut pour l'entraînement d'index et de quantificateurs.