Facebookは類似検索ライブラリFaissをオープンソース化、これは最速の既知のアルゴリズムより8.5倍高速

[[210003]]

Facebook のオープンソース Faiss (Facebook AI Similarity Search) プロジェクトは、マルチメディア ドキュメントから類似項目をすばやく検索できる類似検索ライブラリを提供します。 Facebook AI Labs (FAIR) は、10億規模のデータセット上で最近傍検索アルゴリズムの実装を構築しました。これは、既知の最速アルゴリズムよりも約8.5倍高速で、10億の高次元ベクトル上に構築された初のk近傍グラフを含む新しい記録を樹立しました。

Facebook は今年 3 月に Facebook AI 類似検索 (Faiss) プロジェクトをリリースしました。このプロジェクトが提供するライブラリを使用すると、マルチメディア ドキュメント内の類似アイテムをすばやく検索できます。このシナリオの課題は、従来のクエリベースの検索エンジンでは解決できません。 Facebook AI Lab (FAIR) は、10 億レベルのデータセットに基づいて最近傍検索アルゴリズムの実装を構築しました。これは、既知の文献で GPU に実装されている最も高度で最速の k 選択アルゴリズムよりも約 8.5 倍高速であり、10 億の高次元ベクトルに基づいて構築された最初の k 近傍グラフを含む新しい記録を樹立しました。

類似検索について

従来のデータベースは、記号情報を含む構造化されたデータ テーブルで構成されています。たとえば、画像コレクションはデータ テーブルとして表すことができます。各行はインデックス付きの画像を表し、画像識別子や説明テキストなどの情報が含まれます。また、各行は他のデータ テーブル内のエンティティに関連付けることもできます。たとえば、ユーザーの画像はユーザー名のテーブルに関連付けることができます。

テキスト埋め込み (word2vec) や畳み込みニューラル ネットワーク (CNN) 記述子などのディープラーニングを通じてトレーニングされた AI ツールは、高次元ベクトルを生成できます。この表現は、後で説明するように、固定された記号表現よりもはるかに強力で柔軟性があります。ただし、SQL を使用してクエリを実行する従来のデータベースは、これらの新しい表現にはあまり適していません。まず、大量のマルチメディア情報の流入によって数十億のベクトルが生成されています。次に、より重要な点として、類似のエンティティを見つけるということは、類似の高次元ベクトルを見つけることを意味しますが、これは標準のクエリ言語のみを使用する場合、非常に非効率的で困難になります。

ベクトル表現の使い方は？

ある建物の画像（たとえば、名前が思い出せない中規模都市の市庁舎）があり、画像のコレクションからその建物のすべての画像を見つけたいとします。都市の名前を覚えていないので、従来の SQL でよく使用されるキー/値クエリは役に立ちません。

ここで類似性検索が役立ちます。画像のベクトル化された表現は、類似した画像に対して類似したベクトルを生成することを目的としています。類似したベクトルは、最短のユークリッド距離を持つベクトルとして定義されます。

ベクトル化された表現のもう 1 つの用途は分類です。アルバム内のどの写真が菊であるかを判断する分類器が必要だとします。分類器のトレーニング プロセスはよく知られています。アルゴリズムには、菊の写真と菊以外の写真 (車、羊、バラ、ヤグルマギクなど) が入力されます。分類器が線形の場合、属性値が写真ベクトルとのドット積である分類ベクトルが出力され、写真に菊が含まれている可能性が反映されます。分類器は、アルバム内のすべての写真とのドット積を計算し、ドット積が最大の写真を返します。このタイプのクエリは「最大内積」検索です。

したがって、類似性の検索と分類を行うには、次の操作を行う必要があります。

• クエリ ベクトルが指定されると、そのベクトルに最も近いユークリッド距離を持つデータベース オブジェクトのリストを返します。
• クエリ ベクトルが指定されると、ベクトルとのドット積が最大となるデータベース オブジェクトのリストを返します。

さらなる課題は、数十億のベクトルなど、非常に大規模な規模でこれらの操作を実行することです。

ソフトウェアパッケージ

既存のソフトウェア ツールでは、上記のデータベース検索操作を完了するには不十分です。従来の SQL データベース システムも、ハッシュ ベースの検索や 1 次元の区間検索に最適化されているため、あまり適していません。OpenCV などのソフトウェア パッケージの類似性検索機能は、スケーラビリティが著しく制限されています。同時に、他の類似性検索ライブラリは主に小規模なデータ セット (たとえば、100 万のベクトル) に適しています。他のソフトウェア パッケージは基本的に、特定の設定での効果を実証することを目的として、論文を発表するために出力される学術研究製品です。

Faiss ライブラリは上記の制限を解決し、次のような利点があります。

• 複数の類似性検索方法が提供されており、さまざまな用途と機能セットがサポートされています。
• メモリ使用量と速度に特別に最適化されています。
• 最も関連性の高いインデックス作成方法には、最先端の GPU 実装が提供されます。

類似検索評価

学習システム（画像、ビデオ、テキスト ファイルなど）からベクトルが抽出されると、類似性検索ライブラリで使用できるようになります。

参照比較としてブルート フォース アルゴリズムがあり、これはすべての類似性を非常に正確かつ完全に計算し、最も類似した要素のリストを返します。これにより、参照結果のゴールド スタンダード リストが提供されます。ブルートフォース アルゴリズムの効率的な実装は単純ではなく、通常は他のコンポーネントのパフォーマンスに依存することに注意してください。

参照結果からの小さな偏差を許容するなど、ある程度の精度を犠牲にすると、類似性検索は数桁高速化されます。たとえば、ある画像に対する最初の類似検索結果と 2 番目の類似検索結果が入れ替わった場合、どちらも特定のクエリに対して正しい結果である可能性があるため、大きな問題にはならない可能性があります。検索を高速化するには、通常インデックス作成と呼ばれるデータ セットの前処理も必要です。

このように、私たちは次の 3 つの指標に焦点を当てています。

スピード。クエリに最も類似する 10 個以上のベクトルを見つけるのにどれくらいの時間がかかりますか? うまくいけば、ブルート フォース アルゴリズムよりも時間がかからないでしょう。そうでなければ、インデックスの意味は何でしょうか?

メモリ消費量。この方法はどのくらいの RAM を消費しますか? 元のベクトルより多いですか、少ないですか? Faiss は RAM での検索のみをサポートしていますが、ディスク データベースは SSD でも桁違いに遅くなります。

正確さ。返された結果リストは、ブルート フォース検索結果とどの程度一致していますか? 精度は、クエリ結果セットの最初に返された真に最も近い結果の数を数えることによって評価できます (このメトリックは、1-recall@1 と呼ばれることがよくあります)。または、返された最初の 10 件の結果のうち 10 件の最も近い近傍を含む平均パーセンテージを測定することによって評価できます (つまり、メトリック 10-intersection)。

通常、特定のメモリ リソース内で速度と精度の間でトレードオフを行う必要があります。 Faiss 氏は、生のベクトルを圧縮する方法に焦点を当てました。これは、10 億のベクトル データセットに拡張するための唯一のオプションだからです。10 億のベクトルをインデックス化する必要がある場合、32 バイトごとに大量のメモリが消費されます。

多くのインデックス ライブラリは、約 100 万のベクトルの小規模データ セットに適しています。たとえば、nmslib には、このサイズのデータ​​に適した非常に効率的なアルゴリズムがいくつか含まれています。このアルゴリズムは Faiss よりもはるかに高速ですが、より多くのストレージを必要とします。

10億のベクトルに基づく評価

この規模のデータセットについてはエンジニアリング コミュニティで認められたベンチマークがないため、私たちは研究結果に基づいて評価を行います。

評価精度は、10億枚の画像を含むデータセットであるDeep1Bに基づいています。各画像は CNN によって処理されており、CNN アクティベーション マップの 1 つが画像の説明に使用されます。これらのベクトル間のユークリッド距離を比較することで、画像の類似性を定量化できます。

Deep1B には、クエリ画像のより小さなセットと、ブルートフォース アルゴリズムによって生成された真の類似性検索結果も付属しています。したがって、検索アルゴリズムを実行すると、結果で 1-recall@1 を評価できます。

インデックスを選択

評価目的のため、メモリを 30G に制限します。このメモリ制約は、インデックス作成方法とパラメータの選択の基礎となります。 Faiss のインデックス メソッドは文字列として表され、この場合は OPQ20_80、IMI2x14、PQ20 と呼ばれます。

文字列には、ベクトルに適用された前処理手順 (OPQ20_80)、データベースのパーティション分割方法を示す選択メカニズム (IMI2x14)、およびベクトルが積量子化器 (PQ) を使用してエンコードされ、20 バイトのコードが生成されることを示すコーディング コンポーネント (PQ20) に関する情報が含まれています。したがって、その他のオーバーヘッドを含めた合計メモリ使用量は 30G 未満になります。

これは技術的な話なので、Faiss のドキュメントでは、ニーズに最適なインデックスを選択する方法についてのガイダンスが提供されています。

インデックスの種類を選択したら、インデックス作成プロセスを開始できます。 Faiss のアルゴリズム実装では、10 億のベクトルを処理し、それらをインデックス ライブラリに配置します。インデックスはディスクに保存されるか、すぐに使用され、インデックスの取得と追加/削除が交互に実行される可能性があります。

クエリインデックス

インデックスが準備されると、一連の検索時間パラメータが設定され、アルゴリズムが調整されます。評価の便宜上、ここではシングルスレッド検索が使用されます。メモリ消費量は制限され固定されているため、精度と検索時間の間のトレードオフを最適化する必要があります。つまり、たとえば 40% の 1-recall@1 を達成するには、可能な限り短い検索時間で済むようにパラメータを設定できます。

幸いなことに、Faiss には、パラメータ空間をスキャンして、最適な動作ポイント、つまり特定の精度で可能な限り最適な検索時間、またはその逆に特定の検索時間で最適な精度を提供するパラメータを収集する自動チューニング メカニズムが付属しています。 Deep1B の動作ポイントは次のように視覚化されます。

この図から、1 回あたりの再現率 40% を達成するには、各クエリに 2 ミリ秒未満かかる必要があることがわかります。0.5 ミリ秒に最適化できれば、1 回あたりの再現率 30% を達成できます。クエリ時間が 2 ミリ秒の場合、シングルコアの処理能力は 500 QPS です。

この結果は、基本的に業界の最新の研究結果、つまりCVPR 2016でBabenkoとLempitskyが発表した論文「ディープディスクリプタの10億規模のデータセットの効率的なインデックス作成」に匹敵します。この論文ではDeep1Bデータセットが紹介されました。1回の再現率45%を達成するのに20ミリ秒かかりました。

数十億規模のデータセット向け GPU

また、ネイティブのマルチ GPU サポートにより驚異的な単一マシン パフォーマンスを実現できるコンピューティング GPU 実装にも多大な投資を行ってきました。 GPU 実装はすでに対応する CPU デバイスの代替として機能しており、CUDA API を理解しなくても GPU のパフォーマンスを活用できます。 Faiss は、2012 年以降にリリースされたすべての Nvidia GPU (Kepler、コンピューティング機能 3.5 以上) をサポートしています。

私たちは、メモリ帯域幅または浮動小数点ユニットを最大限に活用するように努めるべきであることを示すルーフライン モデルをガイドラインとして使用します。 Faiss の GPU 実装は、単一の GPU 上の対応する CPU 実装よりも 5 ～ 10 倍高速に実行され、NVIDIA の P100 などの新しい Pascal アーキテクチャ ハードウェアでは 20 倍以上高速になります。

主なパフォーマンス数値:

• おおよそのインデックスについては、YFCC100M データセットの 9,500 万枚の画像を使用して、128D CNN 記述子に基づくブルートフォース k 近傍グラフ (k=10) を、インデックス構築時間を含めてわずか 4 つの Maxwell Titan X GPU で 35 分で構築できます。
• 数十億のベクトルに対する k 最近傍グラフが実現可能になりました。 Deep1B データセットに基づいて、4 つの Maxwell Titan X GPU を使用して 12 時間以内に 10 交差 0.65 を達成するブルート フォース k-NN グラフ (k=10) を構築できます。また、8 つの Pascal P100-PCIe GPU を使用して 12 時間以内に 0.8 を達成するブルート フォース k-NN グラフを構築できます。 Titan X 構成では、5 時間以内に低品質の画像を生成できます。
• 他のコンポーネントも印象的なパフォーマンスを示しました。たとえば、上記の Deep1B インデックスを構築するには、k-means を使用して 6,701 万個の 120 次元ベクトルを 262,144 個のクラスターにクラスタリングする必要がありますが、25 回の EM 反復で 4 つの Titan X GPU (12.6 tflow/s) では 139 分、8 つの P100 GPU (40 tflow/s) では 43.8 分かかります。クラスタリング トレーニング データセットは、パフォーマンスに追加の影響を与えることなく、必要に応じてデータを GPU にストリーミングできるため、GPU メモリに収まる必要がないことに注意してください。

低レベルの実装

FacebookのAI研究チームは、多くの研究成果と膨大なエンジニアリング実践に基づいたFaissの開発を2015年に開始しました。 Faiss ライブラリでは、特に CPU に関して、いくつかの基本テクノロジの最適化に重点を置くことにしました。次のテクノロジを多用しました。

• マルチスレッドは、マルチコア リソースを活用し、複数の GPU で並列検索を実行するために使用されます。
• BLAS ライブラリを使用して、行列と行列の乗算を通じて距離計算を効率的かつ正確に実行します。 BLAS を使用しないブルート フォース実装は最適ではない可能性があります。 BLAS/LAPACK は Faiss の唯一の必須依存関係です。
• マシン SIMD ベクトル化とポップカウントは、独立したベクトルの距離計算を高速化するために使用されます。

GPUについて

前述の類似性検索の GPU 実装では、従来の CPU アルゴリズム (ヒープ検索アルゴリズムなど) が GPU に適していないため、k 選択 (k 個の最小または最大の要素の検索) ではパフォーマンス上の問題が発生します。 Faiss GPU 向けに、文献で知られている中で最も高速な軽量 k 選択アルゴリズム (k<=1024) を設計しました。すべての中間状態は、高速な読み取りと書き込みのためにレジスタに保存されます。 k 選択は入力データに対して 1 回のパスで実行でき、出力のピーク GPU メモリ帯域幅として理論上のピーク パフォーマンスの最大 55% で実行されます。状態はレジスタ ファイルにのみ保存されるため、他のカーネルと簡単に統合でき、非常に高速な正確かつ近似的な検索アルゴリズムになります。

効率的な戦略と近似検索のカーネル実装の基礎を築くために、多大な努力が払われてきました。マルチコア GPU のサポートは、単一の GPU で使用可能なビデオ メモリのサイズに制限されることなく、データ シャーディングまたはデータ レプリケーションを通じて提供できます。また、半精度浮動小数点数 (float16) のサポートも提供されており、サポートされている GPU で完全な float16 演算を実行できるほか、以前のアーキテクチャで提供されていた中間 float16 ストレージも実行できます。 float16 エンコーディング ベクトル テクノロジによりロスレス アクセラレーションを実現できることがわかりました。

つまり、重要な要素における継続的なブレークスルーは実際には非常に重要であり、Faiss は確かにエンジニアリングの詳細に多大な労力を費やしてきました。

Faissを使い始める

Faiss は C++ で実装されており、Python をサポートしています。 Github からソース コードをダウンロードしてコンパイルし、Python で Faiss モジュールをインポートするだけで使用を開始できます。 Faiss は Numpy も完全に統合し、numpy (float32 を使用) 配列を構築するためのすべての関数をサポートします。

Faiss を入手:

https://github.com/facebookresearch/faiss

インデックス オブジェクト Faiss (C++ と Python の両方) は、インデックス Index のインスタンスを提供します。各 Index サブクラスは、どのベクトルを追加および検索できるかを記述するインデックス構造を実装します。たとえば、IndexFlatL2 は、L2 距離検索を使用できるブルート フォース インデックスです。

これにより、インデックス ベクトルの数が表示されます。 IndexFlat に追加するということは、その後ベクトルに対して他の操作が実行されないため、単にインデックスの内部ストレージにコピーすることを意味します。

検索を実行するには:

I は整数行列であり、出力は次のようになります。

xq の最初のベクトルの場合、xb 内で最も類似するベクトルのインデックスは 0 (0 から開始) で、2 番目に類似するのは #393、3 番目は #363 です。 xq の 2 番目のベクトルの場合、類似ベクトルのリストは #1、#555 などになります。この場合、xq の最初の 3 つのベクトルは、xb の最初の 3 つのベクトルと同じように見えます。

行列 D は、I と同じサイズの平方距離行列であり、各結果ベクトルに対するクエリの平方ユークリッド距離を表します。

Faiss は、他のインデックスで構成される 12 種類を超えるインデックス タイプを実装します。オプションの GPU バージョンには、CPU と CPU インデックスの間にチャネルを備えたまったく同じインターフェイスがあります。 Python インターフェイスは主に C++ 参照を強調表示するために C++ から生成されるため、Python 検証コードを統合された C++ コードに変換するのは簡単です。