FAISS：数百万ドル規模のデータで顔とクローンをすばやく見つける

毎年、DANグループが毎年開催 するクライアントカンファレンスの前夜、パートナーやクライアントにイベントの感動や思い出を楽しんでもらえるように、どんなことが面白いか考えていました。私たちは、この会議と過去の数千枚の写真のアーカイブを作成することを決定しました（そして、そのときまでに全部で18枚ありました）。人が私たちに写真を送信し、数秒で私たちのアーカイブから数年間、彼と一緒に選択した写真を送信します。



私たちは自転車を発明したのではなく、よく知られたdlibライブラリを使用して、各人の埋め込み（ベクトル表現）を受け取りました。 



便宜上Telegramボットを追加しましたが、すべて問題ありませんでした。顔認識アルゴリズムの観点から見ると、すべてがうまくいきましたが、会議は終了しました。私は、実証済みのテスト済みの技術を手放したくありませんでした。数千人から数億人に行きたかったのですが、特定の業務はありませんでした。しばらくして、私たちの同僚は、そのような大量のデータを扱う必要がある仕事をしました。



問題は、Instagramネットワーク内にスマートボットモニタリングシステムを作成することでした。ここで私たちの考えはシンプルで複雑なアプローチを生み出しました：



シンプルな方法：サブスクライバーよりもはるかに多くのサブスクリプションがあり、アバターがない、フルネームが入力されていないなどのすべてのアカウントを考慮します。その結果、私たちは、半死んだアカウントの理解できない群衆を得ます。



難しい方法：最近のボットはより賢くなり、コンテンツを投稿、スリープ、さらには書き込みさえするようになったので、疑問が生じます。まず、友達もボットであることが多いため、友達に注意を払い、重複する写真を追跡します。次に、ボットが自分の写真を生成する方法を知っていることはほとんどありません（これは可能ですが））、つまり、Instagramの別のアカウントにいる人の写真の重複は、ボットのネットワークを見つける良いきっかけになります。

次は何ですか？

単純なパスが非常に予測可能であり、すぐに結果が出る場合、難しいパスは正確に困難です。それを実装するには、後続の類似性を比較するために信じられないほど大量の写真をベクトル化してインデックス付けする必要があるためです。それを実践する方法は？結局のところ、技術的な問題が発生します。

1. 検索速度と精度
2. データが占めるディスク容量
3. 使用されるRAMのサイズ。 

写真が少ない場合、少なくとも1万を超えない場合は、ベクタークラスタリングを使用した単純なソリューションに制限できますが、大量のベクターを処理し、ベクターに最も近い近傍を検索するには、複雑で最適化されたアルゴリズムが必要です。



Annoy、FAISS、HNSWなどの有名で実績のあるテクノロジーがあります。nmslibおよびhnswlibライブラリーで使用可能な高速HNSW近隣探索アルゴリズムは、同じベンチマークでわかるように、CPUに関する最新の結果を示しています。しかし、本当に大量のデータを処理するときに使用されるメモリの量に満足できないため、すぐにそれを切り捨てました。AnnoyとFAISSのどちらかを選択し始め、最終的にはFAISSを選択しました。これは、利便性、メモリ使用量の削減、GPUでの使用の可能性、およびパフォーマンスのベンチマークです（たとえば、こちらをご覧ください）。ちなみに、FAISSではHNSWアルゴリズムがオプションとして実装されています。

FAISSとは何ですか？

Facebook AIリサーチの類似検索 -Facebook AIリサーチチームが開発し、最も近い近傍とベクトル空間のクラスタリングをすばやく見つけます。高速の検索により、数十億ベクターまでの非常に大きなデータを扱うことができます。



FAISSの主な利点は、GPUでの最先端の結果ですが、CPUでの実装はhnsw（nmslib）よりもわずかに劣っています。CPUとGPUの両方で検索できるようにしたいと考えました。さらに、FAISSはメモリ使用量と大規模バッチでの検索に関して最適化されています。



ソース



FAISSを使用すると、特定のベクトルxに対してk個の最も近いベクトルをすばやく見つけることができます。しかし、この検索は内部ではどのように機能しますか？

インデックス

FAISSの主な概念はindexであり、本質的にはパラメーターとベクトルのコレクションにすぎません。パラメータのセットは完全に異なり、ユーザーのニーズに依存します。ベクトルは変更されないままにすることができますが、再構築することができます。一部のインデックスは、ベクターを追加するとすぐに使用でき、一部は事前のトレーニングが必要です。ベクトル名はインデックスに格納されます。0からnまでの番号、またはInt64型に適合する数値として格納されます。



最初のインデックスであり、カンファレンスで使用した最も単純なものはFlatです。すべてのベクトルのみが格納され、特定のベクトルの検索は徹底的な検索によって実行されるため、トレーニングする必要はありません（ただし、以下の学習について）。少量のデータでは、このような単純なインデックスで検索のニーズを完全にカバーできます。



例：

import numpy as np
dim = 512  #     512
nb = 10000  #    
nq = 5 #      
np.random.seed(228)
vectors = np.random.random((nb, dim)).astype('float32')
query = np.random.random((nq, dim)).astype('float32')

フラットインデックスを作成し、トレーニングなしでベクトルを追加します。

import faiss
index = faiss.IndexFlatL2(dim)
print(index.ntotal)  #   
index.add(vectors)
print(index.ntotal)  #    10 000 

次に、ベクトルから最初の5つのベクトルの7つの最近傍を見つけます。

topn = 7
D, I = index.search(vectors[:5], topn)  #  : Distances, Indices
print(I)
print(D)

距離が0の最も近い近傍はベクトル自体であり、残りは距離を増やすことで範囲が決まります。クエリからベクターを検索してみましょう：

D, I = index.search(query, topn) 
print(I)
print(D)

クエリからのベクトルがインデックスにないため、結果の最初の列の距離はゼロではなくなりました。



インデックスをディスクに保存してから、ディスクからロードできます。

faiss.write_index(index, "flat.index")
index = faiss.read_index("flat.index")

すべてが初級のようです！数行のコード-そして、高次元のベクトルで検索するための構造がすでにあります。しかし、512次元の数千万のベクトルしかないこのようなインデックスは、約20 GBの重さとなり、使用時に同じ量のRAMを占有します。



カンファレンスのプロジェクトでは、フラットインデックスを使用したこのような基本的なアプローチのみを使用しました。比較的少量のデータのおかげですべてが素晴らしいものでしたが、今では数千万から数億の高次元ベクトルについて話しています。

反転リストで検索をスピードアップ

ソース



FAISSの主な最も優れた機能は、IVFインデックス、つまり反転ファイルインデックスです。転置ファイルのアイデアは簡潔で、美しく指に説明：



レッツは、最も雑多戦士、ナンバリング、たとえば、1,000,000人から成る巨大な軍隊を想像してみてください。軍全体を一度に指揮することは不可能です。軍事慣習のように、私たちは軍をサブユニットに分割する必要があります。分けましょう$$$\sqrt{1 000 000} = 1000$各部隊の代表を指揮官の役割として選択します。また、性格、出身地、物理的データなどを可能な限り送信するよう努めます。戦士を1つのユニットに配置し、司令官を選択して、彼ができるだけ正確にユニットを表すようにします。その結果、私たちの任務は、100万人の兵士を指揮することから、指揮官を介して1000ユニットを指揮することまで削減されました。



これがIVFインデックスの背後にある考え方です。k-meansアルゴリズムを使用して、ベクトルの大きなセットを少しずつグループ化しましょう、重心に従って各パーツを設定することは、特定のクラスターに対して選択された中心であるベクトルです。重心までの最小距離を検索してから、この重心に対応するクラスター内のベクトル間の最小距離を探します。kを等しくする$$$\sqrt{n}$どこ $$$n$ -インデックス内のベクトルの数。2つのレベルで最適な検索が行われます。 $$$\sqrt{n}$ 次に重心 $$$\sqrt{n}$各クラスターのベクトル。徹底的な検索と比較して、検索は数回高速化され、何百万ものベクトルを扱う際の問題の1つを解決します。





ベクトル空間は、k平均法によってk個のクラスターに分割されます。各クラスターには、重心の



サンプルコードが割り当てられています。

dim = 512
k = 1000  #  “”
quantiser = faiss.IndexFlatL2(dim) 
index = faiss.IndexIVFFlat(quantiser, dim, k)
vectors = np.random.random((1000000, dim)).astype('float32')  # 1 000 000 “”

または、インデックスを作成するための便利なFAISSを使用して、はるかにエレガントにそれを書き留めることができます。

index = faiss.index_factory(dim, “IVF1000,Flat”)
 :
print(index.is_trained)   # False.
index.train(vectors)  # Train    
 
#  ,      ,      :
print(index.is_trained)  # True
print(index.ntotal)   # 0
index.add(vectors)
print(index.ntotal)   # 1000000

このタイプのインデックスをフラットの後に検討した結果、潜在的な問題の1つである検索速度を解決しました。これは、徹底的な検索に比べて数倍遅くなります。

D, I = index.search(query, topn) 
print(I)
print(D)

ただし、「しかし」が1つあります。検索精度と速度は、訪問したクラスターの数に依存します。これは、nprobeパラメーターを使用して設定できます。

print(index.nprobe)  # 1 –           
index.nprobe = 16  #   -16    top-n  
D, I = index.search(query, topn) 
print(I)
print(D)

ご覧のように、nprobeを増やした後、完全に異なる結果が得られました。Dの最短距離の頂点が良くなっています。



インデックス内の重心の数に等しいnprobeを取得できます。これは、徹底的な検索による検索と同等になり、精度は最大になりますが、検索速度は著しく低下します。

ディスクの検索-On Disk Inverted Lists

すばらしい、最初の問題を解決しました。これで数千万のベクトルで許容可能な検索速度が得られました。ただし、巨大なインデックスがRAMに収まらない限り、これはすべて役に立ちません。



特に私たちのタスクでは、FAISSの主な利点は、IVFインデックスの反転リストをディスクに格納し、メタデータのみをRAMにロードできることです。



そのようなインデックスの作成方法：メモリに収まる最大量のデータに必要なパラメーターを使用してindexIVFをトレーニングし、トレーニングされたインデックスだけでなくベクターもトレーニングされたインデックスにパーツで追加し、各パーツのインデックスをディスクに書き込みます。

index = faiss.index_factory(512, “,IVF65536, Flat”, faiss.METRIC_L2)

GPUインデックスのトレーニングは次のように行われます。

res = faiss.StandardGpuResources()
index_ivf = faiss.extract_index_ivf(index)
index_flat = faiss.IndexFlatL2(512)
clustering_index = faiss.index_cpu_to_gpu(res, 0, index_flat)  #  0 –  GPU
index_ivf.clustering_index = clustering_index

faiss.index_cpu_to_gpu（res、0、index_flat）をfaiss.index_cpu_to_all_gpus（index_flat）に置き換えて、すべてのGPUを一緒に使用できます。



トレーニングサンプルはできる限り代表的で均一な分布を持つことが非常に望ましいため、必要な数のベクトルから事前にトレーニングデータセットを作成し、データセット全体からランダムに選択します。

train_vectors = ...  #     
index.train(train_vectors)

#    ,   :
faiss.write_index(index, "trained_block.index") 

#       
#      :
for bno in range(first_block, last_block+ 1):
    block_vectors = vectors_parts[bno]
    block_vectors_ids = vectors_parts_ids[bno]  # id ,  
    index = faiss.read_index("trained_block.index")
    index.add_with_ids(block_vectors, block_vectors_ids)
    faiss.write_index(index, "block_{}.index".format(bno))

その後、すべての反転リストを結合します。これは、各ブロックが本質的に同じトレーニング済みインデックスであり、内部に異なるベクトルがあるだけなので可能です。

ivfs = []
for bno in range(first_block, last_block+ 1):
    index = faiss.read_index("block_{}.index".format(bno), faiss.IO_FLAG_MMAP)
    ivfs.append(index.invlists)
    #  index   inv_lists 
    #        :
    index.own_invlists = False

#   :
index = faiss.read_index("trained_block.index")

#   invlists
#  invlists       merged_index.ivfdata
invlists = faiss.OnDiskInvertedLists(index.nlist, index.code_size, "merged_index.ivfdata")
ivf_vector = faiss.InvertedListsPtrVector() 

for ivf in ivfs: 
    ivf_vector.push_back(ivf)

ntotal = invlists.merge_from(ivf_vector.data(), ivf_vector.size())
index.ntotal = ntotal  #     
index.replace_invlists(invlists)  
faiss.write_index(index, data_path + "populated.index")  #    

結論 ：これで、インデックスがpopulated.indexとmerged_blocks.ivfdataファイルになりました。



でpopulated.index、インバーテッドリストを使用したファイルに、元の完全なパスを記録しそうであれば、インデックスの読み取りの変化がフラグを使用する必要があります何らかの理由でファイルパスivfdata faiss.IO_FLAG_ONDISK_SAME_DIRあなたはと同じディレクトリにivfdataファイルを検索することができ、 populated.index：

index = faiss.read_index('populated.index', faiss.IO_FLAG_ONDISK_SAME_DIR)

FAISSプロジェクトのGithub のデモ例がベースとして使用されました。



インデックスを選択するためのミニガイドはFAISS Wikiにあります。たとえば、1200万のベクトルのトレーニングデータセットをRAMに収めることができたため、262144の重心にIVFFlatインデックスを選択し、数億に拡大しました。ガイドのインデックスIVF262144_HNSW32を使用することも提案されています。クラスターへのベクトルの所属は、32個の最近傍点をもつHNSWアルゴリズムによって（つまり、量子化器IndexHNSWFlatを使用して）決定されますが、以降のテストでは、このようなインデックスによる検索は精度が低くなります。さらに、そのような量子化器は、GPUでの使用の可能性を排除することを覚えておく必要があります。

製品の量子化によりディスク使用量を劇的に削減

ディスク検索方法のおかげで、RAMから負荷を取り除くことは可能でしたが、100万のベクターを含むインデックスは、依然として約2 GBのディスク容量を必要としました。もちろん、目標を設定して追加のディスク領域を割り当てると、ボリュームはそれほど大きくありませんが、少し気になりました。



そしてここでベクトルコーディングが救いに来ます、すなわちスカラー量子化（SQ）と製品量子化（PQ）。 SQは、nビット（通常は8、6、または4ビット）の各ベクトルコンポーネントのエンコーディングです。 1つのfloat32コンポーネントを8ビットでエンコードするという考えは、精度の低下という観点からはあまりにも憂鬱に見えるため、PQオプションを検討します。ただし、場合によっては、SQfp16をfloat16に圧縮しても精度はほとんど失われません。



製品の量子化の本質は次のとおりです。次元512のベクトルはn個の部分に分割され、それぞれが256個の可能なクラスター（1バイト）にクラスター化されます。nバイトを使用してベクトルを表します。FAISS実装では、nは通常64を超えません。しかし、そのような量子化は、データセットからのベクトル自体には適用されませんが、これらのベクトルの差と、反転リストを生成する段階で取得された対応する重心に適用されます！反転リストは、ベクトルとその重心間の距離のエンコードされたセットになることがわかります。

index = faiss.index_factory(dim, "IVF262144,PQ64", faiss.METRIC_L2)

すべてのベクトルを保存する必要はないことがわかりました。ベクトルごとにnバイト、重心ベクトルごとに2048バイトを割り当てるだけで十分です。私たちの場合、私たちは$$$n = 64$、つまり $$$\frac{512}{64} = 8$-256クラスターの1つで定義される1つのサブベクトルの長さ。







ベクトルxで検索する場合、最も近い重心は通常のフラット量子化器で最初に決定され、次にxもサブベクトルに分割されます。各サブベクトルは、対応する256の重心の1つの数によってエンコードされます。そして、ベクトルまでの距離は、サブベクトル間の64の距離の合計として定義されます。

結果はどうですか？

“ IVF262144、PQ64”インデックスは、検索の速度と精度に関するすべてのニーズを完全に満たし、さらにインデックスをさらに拡大してディスク領域を適切に使用できるようになったため、実験を中止しました。より具体的には、現時点では3億1500万のベクトルで、インデックスは22 GBのディスク領域と約3 GBのRAMを使用しています。



前に触れなかったもう1つの興味深い詳細は、インデックスで使用されるメトリックです。デフォルトでは、任意の2つのベクトル間の距離はユークリッドL2メトリックで計算されます。または、より理解しやすい言語では、距離は座標ごとの差の平方和の平方根として計算されます。ただし、別のメトリックを設定できます。特に、METRIC_INNER_PRODUCTメトリックをテストしました、またはベクトル間のコサイン距離のメトリック。ユークリッド座標系の2つのベクトル間の角度の余弦は、ベクトルの長さの積に対するベクトルのスカラー（座標方向）積の比として表されるため、余弦です。空間内のすべてのベクトルが1の場合、角度の余弦は、座標方向の積と正確に等しくなります。この場合、ベクトルが空間に近づくほど、それらの内積は1に近くなります。



メトリックL2は、スカラー積のメトリックに直接数学的に移行します。ただし、2つの指標を実験的に比較すると、内積指標は画像の類似度の係数をより適切に分析するのに役立つという印象がありました。さらに、私たちの写真の埋め込みは、InsightFaceは、コサイン距離を使用してArcFaceアーキテクチャを実装します。ここで読むことができるFAISSインデックスには他のメトリックもあります。

結論と奇妙な例

それで、すべてが始まったところに戻ります。そしてそれは思い出して、Instagramネットワークでボットを見つける問題を解決するという動機で、より具体的には、特定のユーザーセットの人々またはアバターとの重複した投稿を探すことでした。資料を作成する過程で、ボット検索の方法論の詳細な説明が別の記事に引き出されることが明らかになりました。これについては今後の出版物で説明しますが、ここでは、FAISSでの実験の例に限定します。



写真や顔をさまざまな方法でベクトル化できます。InsightFaceテクノロジーを選択しました（画像のベクトル化とそれらからのn次元の特徴の選択は別の長い話です）。私たちが受け取ったインフラストラクチャを使った実験の過程で、非常に興味深く、面白い特性が発見されました。



たとえば、同僚や知人の許可を得て、検索で彼らの顔をアップロードし、彼らがいる写真をすぐに見つけました





。出典





友人の大規模なグループでのピクニック、友人のアカウントから写真。ソース





渡されたばかり。未知の写真家が彼の主題のプロフィールのために彼らを捕らえました。彼らは自分の写真がどこに行くのかを知りませんでした、そして、5年後に彼らは彼らがどのように写真を撮られたかを完全に忘れました。出典





この場合、写真家は不明であり、密かに撮影されています。

すぐに:)の前の瞬間に座って、SLRで不審な女の子を思い出しソース



したがって、簡単なアクションで、FAISSは有名なFindFaceの類似物を膝の上に集めることができます。



もう1つの興味深い機能：FAISSインデックスでは、顔が互いに類似しているほど、対応するベクトルが空間に配置されます。私は自分の顔の検索結果の精度がやや劣っていることを詳しく調べることにし、ひどく似たクローンを見つけました:)





著者のクローンの一部。

写真出典：1、2、  3は、



一般的に言えば、FAISSは、任意の創造的なアイデアの実現のための巨大なフィールドを開きます。たとえば、似た顔のベクトル近接という同じ原理を使用して、人から人への経路を構築できます。または、最後の手段として、FAISSをそのようなミームを作成するための工場にします。





出典



ご清聴ありがとうございました。この資料がHabrの読者に役立つことを願っています。



この記事は、同僚のArtyom Korolev（コロールヴァート）、ティムール・カディロフとアリーナ・レシェトニコワ。



R＆D電通イージスネットワークロシア。