e-meansがLloyd法を凌駕、同じ損失でk-meansを10倍高速化
E-means: 10x faster k-means at equal loss
e-meansは、指数移動平均によるミニバッチ更新を採用した新しいk-means最適化手法。Lloyd法が25エポックかけて到達するテスト損失をわずか1.2〜3エポックで下回り、GPUでは10〜45倍、CPUでは8〜15倍の実時間短縮を実現する。バッチサイズとステップ幅はスケーリング則から自動決定され、ハイパーパラメータ調整は不要。局所解からの脱出率も大幅に改善している。
Lloydはe-meansの極端な一例にすぎず、ハイパーパラメータ探索の結果、この極端な設定は著しく最適から外れていることが分かった。これがe-meansがLloydを大きく上回る理由である。
HNでの議論
20- jlhawn
これをLloyd法の代替としてどこかで使えないだろうか。球面上の等面積二十面体メッシュを「緩和」するのにLloyd法を使っている趣味プロジェクトがある[1]。これを適応させたものに差し替えて、ずっと良いのか、あるいはこの手法でもっと反復回数を稼げるのか試してみるつもりだ。
編集：試したが、このユースケースでは間違いなく良くない。e-meansは巨大なデータセットへのパス回数が少なくて済む点で勝っているが、球面上のメッシュ緩和にはデータセットが存在しない。各Voronoiセルの重心はその幾何形状から直接計算できる。ミニバッチはそれを同じもののノイズの多いサンプル推定に置き換えるだけだ。目的関数も最適解も同じなので、せいぜいLloyd法に匹敵する程度。実際にはずっと遅く、グリッドにノイズが残り、サンプル数が少ないとメッシュが絡まってしまった。
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
- Luke2642
これはp=npが時として間違った問いである良い例だ。このNP困難問題では近似解で十分であり、それが45倍速く得られるならなおさら良い！
- real_faxenoff
この手法を自分のIVFインデックス（code-daemonプロジェクト）に適応させ、GPU上で146倍の高速化を達成した。
これはすごい！