SuperEMeans: e-means を 3 倍高速化する
SuperEMeans: Making e-means 3× faster (lkuffo.com)
要約
SuperEMeans は、SuperKMeans と e-means を統合した新しいクラスタリングアルゴリズムです。高次元ベクトルデータのクラスタリングを、品質を犠牲にすることなく最大 3 倍高速化します。この技術は、大規模なベクトルインデックスの構築において、検索パフォーマンスのボトルネックを解消する上で重要な進歩となります。
全文翻訳
SuperEMeans: e-means を 3 倍高速化する
TL;DR: SuperKMeans と e-means を融合させた結果、品質のトレードオフなしに高次元ベクトルのクラスタリングが 3 倍高速化しました。現在 https://github.com/cwida/SuperKMeans で利用可能です。
最近、ベクトル埋め込みのクラスタリングに関する多くの話題があります:EVōC、SuperKMeans、QGKmeans、そして先週は e-means、o-means、s-means などです。これらのうち、e-means は非常に重要です。なぜなら、わずか 2 エポックで Lloyd のアルゴリズムと同等の品質を約束するからです。これはベクトル検索にとってなぜ重要なのでしょうか?
クラスタリングは、大規模ベクトルインデックス(例: IVF、ScANN)の重要な構成要素です。これは、ユーザーが類似性検索クエリを発行する前に待たされるボトルネックとなります。
1 年前、私たちは SuperKMeans をリリースしました。SuperKMeans は、クラスタリング中にベクトル次元をスキャンすることを回避することで、品質のトレードオフなしに Lloyd の k-means を 2〜10 倍高速化します。SuperKMeans は業界で急速に採用されています(ParadeDB、Zilliz、FAISS)。これは、高次元ベクトルのクラスタリングパフォーマンスを向上させることがいかにタイムリーであるかを示しています。しかし、e-means もエポック数を減らすことで労力を削減するという点でエキサイティングです。従来、ベクトル埋め込みのクラスタリングは 10 エポックに標準化されていました。e-means は わずか 2 エポックで 同等(またはそれ以上)のクラスタリング品質を約束します。e-means の作成者による素晴らしいウェブサイトをご覧ください:https://e-means.github.io/
興味深いことに、彼らの論文では、SuperKMeans の次元削減のアイデアは e-means と直交すると提案されています。私たちも同意します。これら 2 つのアイデアが互いに反対する要素は何もありません。当然、私たちはこの作業に取り掛かりました!
セットアップ
私たちはクラスタリングライブラリを拡張して、e-means と SuperEMeans(https://github.com/cwida/SuperKMeans でオープンソース化)を実装し、その利点を測定しました。
データセット: 2 つのデータセットを使用します。i) VectorDBBench ベンチマークからの 5M 個の 1536 次元 OpenAI 埋め込み:https://huggingface.co/datasets/makneeee/openai_large_5m。(27 GB)。ii) Cohere Embed V3 モデルで埋め込まれた最初の 10M 件の MS MARCO パッセージ(1024 次元ベクトル):https://huggingface.co/datasets/Cohere/msmarco-v2.1-embed-english-v3 (40 GB)。
インデックス: ポイント/クラスタ比 1:256 の IVF インデックスを構築します。これにより、OpenAI データセットで約 20,000、Cohere データセットで約 40,000 のセントロイドが得られます。
セットアップ: この実験では、16 コア、128 GB RAM を搭載した単一の Zen 5 マシン(r8a.4xlarge | $1.278/hr)を使用します。ただし、SuperKMeans ライブラリは任意の CPU(例: Intel、Graviton、Zen)で動作します。
結果
以下のプロットは、Lloyd のアルゴリズム(10 イテレーション)、SuperKMeans(10 イテレーション)、e-means(2 エポック)、および SuperEMeans(2 エポック)のエンドツーエンドクラスタリング実行時間を比較したものです。SuperEMeans は e-means を大幅に高速化し、最大 1.8 倍高速です。
[画像: 実行時間比較グラフ]
しかし…品質の高いインデックスなのでしょうか?
各アプローチで得られたセントロイドが、ベクトル検索タスクでどの程度うまく機能するかを比較してみましょう。この分析のために、IVF インデックスに 1000 件のクエリを発行します。次に、利用可能なクラスタの 1% をスキャンしたときのトップ 100 件の結果のうち、真のトップ 100 件に含まれる割合(recall@100)を測定します。また、これらのクラスタをスキャンした際に実行された距離計算の数を数えることで、クラスタのバランスも比較しました。OpenAI の結果を表にまとめます。
| アルゴリズム | 実行時間 (秒) | プローブされたセントロイドの 1% における平均 Recall@100 | プローブされたセントロイドの 1% における平均スキャンベクトル数 |
|---|---|---|---|
| Lloyd の k-means (10 イテレーション) | 985 | 0.962 | 52 053 |
| SuperKMeans (10 イテレーション) | 232 | 0.962 | 51 993 |
| e-means (2 エポック) | 203 | 0.967 | 58 184 |
| SuperEMeans (2 エポック) | 128 | 0.967 | 58 198 |
| e-means (2 エポック、作者の実装) | 333 | 0.967 | 58 111 |
Recall@100 は e-means の方がわずかに高いです。しかし、検索中にスキャンするベクトル数は約 10% 増加します。スキャンベクトル数を一致させるためには、e-means ではわずかに少ないクラスタ(全クラスタの約 0.90%)をプローブする必要があります。これにより、recall@100 = 0.964 となり、スキャンベクトル数は 51,962 となります。これは、従来の k-means よりも最終的に優れたトレードオフをもたらします。
Cohere の場合も同様です。
| アルゴリズム | 実行時間 (秒) | プローブされたセントロイドの 1% における平均 Recall@100 | プローブされたセントロイドの 1% における平均スキャンベクトル数 |
|---|---|---|---|
| Lloyds k-means (10 イテレーション) | 2504.4 | 0.919 | 112 714 |
| SuperKMeans (10 イテレーション) | 623.3 | 0.919 | 112 547 |
| e-means (2 エポック) | 525.8 | 0.923 | 135 380 |
| SuperEMeans (2 エポック) | 295.3 | 0.923 | 135 463 |
| e-means (2 エポック、作者の実装) | 927.1 | 0.925 | 136 185 |
ここでも、e-means ではわずかに少ないクラスタ(全クラスタの約 0.90%)をプローブする必要があります。これにより、recall@100 = 0.918 となり、スキャンベクトル数は 121,511 となります。ここでは、e-means が同じリコールで 8% 多いベクトルをスキャンするため、ギャップは e-means にとって有利ではありません。
なぜ e-means はより多くのベクトルをスキャンするのか?
e-means では、最も頻繁にクエリされるベクトル空間の領域において、クラスタは Lloyd の k-means よりも肥大化しています。しかし、e-means は WCSS (MSE) を低下させますが、これはクラスタのバランスを報酬としない目的関数です。一方、ベクトル検索はスキャンするすべてのポイントに対してコストが発生します。注意点として、コストは固定されたプローブクラスタ数におけるレイテンシであり、検索品質ではありません(スキャンベクトル数を一致させると、ほぼ同じリコールが得られるため)。
アルゴリズム的な理由としては、この不均衡は e-means のミニバッチ更新に起因します。初期バッチでわずか数個のポイントを獲得したクラスタは、残りのクラスタリング期間中も少数のポイントしか保持しません。
これを相殺するために、e-means はリバイバルステップを導入しています。これは 5 バッチごとに、バッチ内での使用量がクラスタ全体の平均使用量の 0.1 倍を下回ったクラスタを再シードします。これが起こると、そのクラスタは削除され、大きなクラスタは 2 つに分割されます。このしきい値は保守的すぎると判断され、多くの小さなクラスタがバッチ間で少数のポイントしか持たないまま固定されてしまいました。リバイバルしきい値を 0.1 から 0.3 に引き上げると、Cohere データセットではクラスタのバランスとスキャンコストが Lloyd のレベルに近づきます。
| アルゴリズム | プローブされたセントロイドの 1% における平均 Recall@100 | プローブされたセントロイドの 1% における平均スキャンベクトル数 |
|---|---|---|
| k-means (10 イテレーション) | 0.919 | 112 714 |
| e-means (2 エポック、リバイバル t=0.1) | 0.923 | 135 380 (1.20倍増加) |
| e-means (2 エポック、リバイバル t=0.3) | 0.918 | 119 548 (1.06倍増加) |
より多くのエポック
5 エポック(作者の 実装におけるデフォルト値)では、SuperEMeans による高速化は驚異的で、最大 3 倍高速です!
| Cohere | 実行時間 (秒) | プローブされたセントロイドの 1% における平均 Recall@100 | プローブされたセントロイドの 1% における平均スキャンベクトル数 |
|---|---|---|---|
| e-means (5 エポック) | 1283 | 0.927 | 136 212 |
| SuperEMeans (5 エポック) | 436 (3倍高速) | 0.927 | 136 191 |
| OpenAI | 実行時間 (秒) | プローブされたセントロイドの 1% における平均 Recall@100 | プローブされたセントロイドの 1% における平均スキャンベクトル数 |
|---|---|---|---|
| e-means (5 エポック) | 513 | 0.968 | 58 078 |
| SuperEMeans (5 エポック) | 162 (3.2倍高速) | 0.968 | 58 086 |
e-means はクラスタリングアルゴリズムにおける興味深い進歩です。クラスタのバランスに注意を払うさらなる進歩を期待したいです。これはベクトル検索パフォーマンスの重要な要素であり、k-means の WCSS / MSE 目標と必ずしも一致しません。
いずれにせよ、今後の展開が楽しみです!作者も論文で述べているように、近似割り当ては大規模クラスタリング(10億点以上)を加速できます。そこでは 1 エポックでも数時間かかることがあります。私たちのライブラリでは、階層的 k-means を実装しており、これもベクトル埋め込みデータセットで成功を収めています(NVIDIA の cuVS ライブラリに実装されています)。しかし、e-means とはあまりうまくいきませんでした。これもクラスタのリバイバル機能の働き方によるものかもしれません。
別の選択肢は、量子化されたベクトルをクラスタリングすることです。例えば、32 ビット浮動小数点数を 8 ビット整数に、またはクラスタリング前に 1 ビットの RaBitQ コードに量子化します。私たちはこれを 別の研究論文 で驚くべき結果とともに探求しました。
SuperKMeans および e-means の詳細な技術レポートは arXiv で入手可能です。
再現性
このブログ投稿の結果を再現するためのソースコードは、https://github.com/lkuffo/reproducibility-superemeans で入手できます。