Meta FAIR発「e-means」k-meansを10倍高速化
原題: E-means: Outperforming k-means in one-tenth the epochs
なぜ重要か
k-meansは大規模なベクトル検索・量子化・クラスタリング全般の基盤技術であり、高速化の恩恵はRAGやVQ-VAEなど広範な実用システムに波及する。
Meta FAIRの研究チームが2026年、従来のk-meansアルゴリズム（Lloyd法）をエポック数・実時間ともに約10倍高速化した新アルゴリズム「e-means」を発表した。GPU環境では最大45倍の実時間短縮を達成しつつ、損失値も改善。コードはFaissライブラリにオープンソースとして公開されている。
Meta FAIRの研究者Swann Bessaらが開発した「e-means」は、1967年から使われてきたMacQueen更新則や、現在も主流のLloyd法（フルバッチ最適化）に代わる、現代的なk-meansアルゴリズムだ。
従来のk-meansは機械学習の問題としては珍しくフルバッチ最適化が標準だった。ミニバッチk-meansの先行研究は存在するが、いずれも半世紀以上前の更新則に依存していた。e-meansはここに深層学習の知見を持ち込み、指数移動平均（EMA）によるミニバッチ更新を採用した。
最大の特徴は「ハイパーパラメータのチューニングが不要」な点だ。バッチサイズとステップサイズをスケーリング則から自動算出するため、ユーザーが手動で調整する必要がない。さらに、コサインスケジュールの減衰率、改善された初期化とデッドクラスター再生戦略、そしてわずかな追加コストで学習損失を削減する「ファイナライゼーションステージ」も備える。
性能面では、様々なスケールとデータセットにおいて、Lloyd法が25エポックで達する損失をe-meansは1.2〜3エポックで下回る。GPU上でのFlash-KMeans（現時点の最速実装）比で10〜45倍、CPU上のFaiss比で8〜15倍の実時間短縮を計測している。速度と品質はトレードオフになりがちなk-meansにおいて、両者を同時に改善した点が技術的な肝となる。
コードはFaissの`faiss/contrib/e_means`として公開済み。論文はarXiv（arxiv.org/abs/2611.09501）で参照できる。共著者にはHugo TouvronやHervé Jégouら著名な研究者が名を連ねる。