Faiss: 効率的な類似性検索のためのライブラリ

ベクトルデータベースとして有名なFaissですが、どのようなものなのか知りたくて次のURL先をChatGPTに日本語で要約してもらいました。

https://engineering.fb.com/2017/03/29/data-infrastructure/faiss-a-library-for-efficient-similarity-search/

FacebookはFaissというライブラリをリリースしました。これはマルチメディアドキュメントを迅速に検索するためのもので、GPU上で最速のk選択アルゴリズムとともに、10億規模のデータセット用の最近傍検索実装を構築しました。これにより、いくつかの記録を破ることができました。

類似検索について

従来のデータベースはテーブル形式で、画像やテキスト情報がシンボリック情報として保存されます。しかし、AIのツールが生成する高次元ベクトルはより柔軟で強力。これらの新しい表現には対応していないため、効率的な類似検索が困難です。

ベクトル表現はどのように使用できますか?

ベクトル表現の使い方は、画像検索や分類に役立ちます。例えば、名前を忘れた建物の画像を似た画像から見つけることができます。類似性検索では、画像のベクトルが類似したものを生成し、ユークリッド空間で近いものを見つけます。分類では、例えばデイジーの画像を他の画像と区別する分類子が使われます。ベクトルとの内積を計算し、最も高い値を持つ画像が結果として返されます。これらの操作は大規模なデータベースでも使えるように工夫されます。

ソフトウェアパッケージ

ソフトウェアパッケージ「Faiss」は、データ検索に特化し、幅広い方法で高速に動作します。メモリ効率も高く、GPUを使用した高度なインデックス作成も可能です。

類似検索の評価

「類似検索の評価では、学習機械が抽出したベクトルを使って、類似性検索ライブラリに入力します。参照総当たりアルゴリズムは、類似点を計算し、最も類似した要素のリストを返します。高速化のためにはデータセットの前処理やインデックス作成が重要で、スピード、メモリ使用量、正確さが評価されます。Faissは圧縮方法に焦点を当て、数十億のベクトルのデータセットに対応できる特長があります。

10億個のベクトルの評価

10億個のベクトルの評価は、大規模なデータセットを使って類似性検索を行うことです。画像の特徴をベクトルとして表現し、それらのベクトルを比較して画像の類似度を計算します。評価にはDeep1Bというデータセットが用いられ、検索アルゴリズムの性能を測るために使われます。

インデックスの選択

メモリ制約を考慮して、Faissのインデックス選択方法について説明されています。インデックスは文字列で表現され、前処理ステップ、分割方法、エンコードコンポーネントが示されます。最適なインデックスの選択方法はドキュメントに記載されています。インデックス作成後は、大量のベクトルを処理し、ディスクに保存したり検索/追加/削除ができます。

インデックスで検索する

Faissは、インデックスを使用して効率的にデータを検索することができる。検索時にはパラメータを調整する必要があり、精度と検索時間のトレードオフを最適化する。Faissには自動チューニング機能があり、一定の精度で最速の検索時間を提供できる。例えば、40%の1-recall@1を得るには、ベクトルあたり2ミリ秒未満のクエリ時間か、0.5ミリ秒の時間バジェットで30%に到達できる。これは500クエリ/秒(QPS)に相当する。比較的に先進的な研究結果では、同じ精度を得るには20ミリ秒かかる。

GPU を使用した数十億規模のデータセット

GPUを使用した大規模なデータセット処理は効率的で、ネイティブ マルチ GPU サポートにより単一マシンで驚異的なパフォーマンスを発揮します。GPU FaissはNvidia GPU（Kepler、コンピューティング機能3.5+）をサポートし、CPUに比べて5〜10倍高速です。近似インデックス作成では、4つのMaxwell Titan X GPUで9,500万枚の画像の128D CNN記述子上のk近傍グラフを35分で構築できます。また、10億ベクトルのk最近傍グラフも短時間で作成可能です。他のコンポーネントも優れたパフォーマンスを発揮します。

フードの下

Facebook AI Researchチームは、2015年にFaissを開発しました。このライブラリは、CPU側でマルチスレッドを活用し、複数のGPUで並列検索を行うことに焦点を当てました。BLASライブラリを使用して効率的な距離計算を行い、マシンSIMDベクトル化とポップカウントを使って分離ベクトルの距離計算を高速化します。

GPU側

GPU側の類似性検索において、以前のGPU実装ではパフォーマンスの問題がありました。Faiss GPUでは小さなk選択アルゴリズムを設計し、高速化を実現しました。この状態は他のカーネルと組み合わせ可能であり、正確な検索に役立ちます。さらに、効率的なタイリング戦略と近似検索の実装にも注意が払われました。マルチGPUサポートや半精度浮動小数点サポートも提供されています。エンジニアリングの詳細な作業が行われました。

やってみて

FaissはC++で作られ、Pythonで使えるようになっています。GitHubから取得してコンパイルし、Pythonでimportします。Faissはnumpyと統合されており、すべての関数がnumpyの配列を受け取ります（データ型はfloat32）。

インデックスオブジェクト

Faissは、ベクトルを追加して検索できるインデックスを提供するライブラリです。例えば、IndexFlatL2は距離を使用する総当たりインデックスです。インデックス付きベクトルの数は`index.ntotal`でわかります。検索は`index.search(xq, k)`で行い、類似したベクトルのインデックスがIに格納されます。行列Dは二乗距離を示します。Faissには12種類のインデックスがあり、PythonとC++のインターフェースがあります。