e-means : k-means 10x plus rapide par Meta FAIR
Original : E-means: Outperforming k-means in one-tenth the epochs
Pourquoi c'est important
Le k-means reste omniprésent en ML ; un gain de 10x change les usages à grande échelle.
Des chercheurs de Meta FAIR publient e-means, un algorithme de clustering qui remplace Lloyd's k-means avec un gain de vitesse de 10x en epochs et en temps réel, tout en atteignant une perte inférieure.
Développé chez Meta FAIR, e-means est un nouvel algorithme de clustering open-source qui s'attaque à l'un des problèmes les plus classiques du machine learning : le k-means. Signé par Swann Bessa, Hugo Touvron, Matthijs Douze, Hervé Jégou et leurs collègues, le projet remet en cause l'algorithme de Lloyd, utilisé en full-batch depuis des décennies.
Là où Lloyd effectue une seule mise à jour par epoch, e-means en réalise jusqu'à 97 grâce à des mises à jour en mini-batch basées sur des moyennes mobiles exponentielles — une technique empruntée au deep learning moderne. Résultat : e-means atteint une perte inférieure à celle de Lloyd en seulement 1,2 à 3 epochs, contre 25 pour l'état de l'art. En temps réel, cela se traduit par une réduction de 10 à 45x sur GPU face à Flash-KMeans, et de 8 à 15x sur CPU face à Faiss.
Autre atout majeur : aucun réglage d'hyperparamètres. La taille des batchs et le pas d'apprentissage sont dérivés automatiquement via des lois d'échelle. L'algorithme intègre également une meilleure initialisation, une stratégie de relance des clusters morts, un taux de décroissance cosinus et une phase de finalisation à coût marginal.
e-means est disponible directement dans la bibliothèque Faiss (faiss/contrib/e_means) et le papier est accessible sur arXiv (arxiv.org/abs/2611.09501).