e-meansプロジェクトは、最先端のk-means実装と比較して、GPUで10〜45倍、CPUで8〜15倍のウォールクロック時間の短縮を達成する現代的な最適化ルールを導入します。従来のフルバッチLloydアルゴリズムを、指数移動平均（EMA）を用いたミニバッチアプローチに置き換えることで、この手法はクラスタリングの品質とトレーニング速度の両方を同時に向上させます。
このグラフは、従来のLloydアルゴリズムと同じテスト損失に到達するためにe-meansが必要とするエポック数の大幅な削減を例示しています。
フルバッチから指数移動平均への移行
従来のk-meansは通常、各イテレーションでセントロイドを更新するためにデータセット全体をフルパスで走査する必要があるLloydアルゴリズムに依存しています。このアプローチは正確ではありますが、大規模なデータセットでは低速であり、損失が常に単調に減少するため、容易に局所解に陥ることがあります。
e-meansはこれを、指数移動平均（EMA）を使用したミニバッチ更新ルールに置き換えます。統計量をゼロから再計算する代わりに、各クラスターの点の合計とカウントをアルファの割合で更新し、セントロイドが全履歴ではなく最近の割り当てを追跡できるようにします。このアプローチは、EMAの更新によってセントロイドが割り当てられた点の凸包内に留まることが保証されるため、勾配降下法よりも安定しています。
この図は、指数移動平均（EMA）更新ルールが、従来の手法に対する安定した効果的な代替手段を提供していることを示しています。
「e-meansは速度と損失の両方において優れた成果を達成しています。」
— e-means: 10x faster k-means at equal loss - Blog
自動スケーリング則と堅牢性
ミニバッチk-meansにおける大きな障害の一つは、バッチサイズやステップサイズなどのハイパーパラメータを調整する必要があることです。e-meansは、問題の特性（点の数、クラスター数、目標エポック）からこれらの値を自動的に導き出すスケーリング則を使用することで、この問題を解決します。これにより、手動の介入なしにアルゴリズムが最適に動作することを保証します。
このプロジェクトでは、ミニバッチk-meansにおける手動のハイパーパラメータ調整の必要性を排除するために、これらのスケーリング則を利用しています。
このプロジェクトはまた、「デッドクラスター復活」戦略を実装することでクラスタリングの信頼性を向上させています。クラスターに割り当てられた点がなくなった場合、e-meansは単にランダムな点を再サンプリングするのではなく、大きなアクティブなクラスターを分割することでそれを復活させます。これにより、コードブックの容量を維持し、トレーニング中に有効なクラスター数が減少するのを防ぎます。
パフォーマンスの向上とトレードオフ
24の異なるデータセットにわたる実験的検証により、e-meansはLloydアルゴリズムよりも一貫して低いテスト損失に到達することが示されました。例えば、VIBE埋め込みベンチマークでは、e-meansは1.6〜2.4エポックで目標エラーに到達し、標準的な実装で必要とされる25エポックから大幅に削減されました。
アルゴリズムの変更がこれらの利点の基礎を提供していますが、このプロジェクトは、これらの改善がウォールクロックの高速化として現れることを確実にするために、特化したカーネルも活用しています。主なトレードオフは、この手法の効率性が、必要とされるエポックの削減をGPUなどのハードウェア上での実用的な時間短縮へと変換するために、これらの最適化されたカーネルに依存しているという点です。
この視覚資料は、アルゴリズムの改善と特化したGPUカーネルを組み合わせることで達成される実用的なウォールクロックの高速化を実証しています。
HN Digestによる図。e-means.github.ioの報告数値に基づく。値はソースの表記通り。