• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

faiss

date: 2020-05-15 excerpt: faiss

tag: faiss近傍探索GPULSHHNSW


faiss

概要

  • faissは高速なL2, L1, etcのベクトルの距離を見てランキングをするライブラリで、高速に検索する仕組みがたくさんある
  • alternativeな同様に使えるライブラリとして、cumlの近傍探索がある

インストール

$ python3 -m pip install faiss-cpu

全探索の例

  • FlatL2は全探索
import faiss 

V = V.astype(np.float32)      # 入力として許可される型は`np.float32`
index = faiss.IndexFlatL2(40) # 40は説明変数の次元数
print(index.is_trained)
index.add(V)                  # add vectors to the index, インデックスに追加しないと検索できない
print(index.ntotal)

k = 10000                     # we want to see 10000 nearest neighbors
D, I = index.search(V[:5], k) # sanity check(検索対象のベクトルをクエリとして切り出して検索)
print(I)                      # 検索の結果、近い要素のインデックスが得られる
print(D)                      # 距離

GPUで全探索する

  • 全探索などをGPUで計算できる
  • CPUより10倍以上早い(手元の環境では15倍早かった)

シングルGPUの場合

import faiss

X = X.astype(np.float32)
d = len(X[0])
res = faiss.StandardGpuResources()
indexCPU = faiss.IndexFlatL2(d)
indexGPU = faiss.index_cpu_to_gpu(res, 0, indexCPU)
print(indexGPU.is_trained)
indexGPU.add(X)
print(indexGPU.ntotal)

マルチGPUの場合

import faiss

X = X.astype(np.float32)
d = len(X[0])
indexCPU = faiss.IndexFlatL2(d)
indexGPU = faiss.index_cpu_to_all_gpus(indexCPU)
print(indexGPU.is_trained)
indexGPU.add(X)
print(indexGPU.ntotal)

LSHを使用する

  • かなり早いが精度は低い
  • 速度が必要な際の選択肢
import faiss

X = X.astype(np.float32)
d = len(X[0])
nbits = 5120
indexLSH = faiss.IndexLSH(d, nbits)
indexLSH.add(X)
# LSH 32 -> 精度: 0.099
# LSH 64 -> 精度: 0.150
# LSH 1024 -> Wall time: 36.7 s, 精度: 0.34
# LSH 5120 -> Wall time: 189 s, 精度: 0.375

HNSWを使用する

  • NSW(Navigable Small World Graphs)とは、データを点とするノードのグラフを作っておく
  • これを階層化したバージョンがHierarchical NSW: HNSWである
  • indexの追加時にグラフに追加するので、検索時には早くなるが、追加時に計算リソースを使用する
    • かなり重いので、リアルタイム検索が必要の場合に限定したほうがいい
import faiss

X = X.astype(np.float32)
d = len(X[0])
indexHNSW = faiss.IndexHNSWFlat(d, 32) 
print(indexHNSW.is_trained)
indexHNSW.add(X)    
print(indexHNSW.ntotal)

レポジトリ

  • faiss/github.com
  • Getting Started/wiki

実装されているメソッドの探し方

  • IFがpython側でそんなに定義されていないので、IndexHogeHoge.hなどをGitHubのリンクから探す

トラブルシューティング

Faiss assertion ‘err == CUBLAS_STATUS_SUCCESS’…と出てクラッシュする

  • 原因
    • 特定のnvidiaのハードウェア(A100など)と相性が悪い
  • 対応
    • 別のnvidiaのハードウェアでしばらくお茶を濁す
    • github issueを参照し、faissのアップデートを待つなどのヒューリスティック
  • 参考
    • faiss::gpu::runMatrixMult … cublas failed (13):…

参考

  • 近似最近傍探索の最前線
  • billion-scaleの近似最近傍探索
  • Nearest Neighbor Indexes for Similarity Search
  • Python · xlm-roberta, rapidfuzz-2.0.11-cp37, Private Datasource +14


faiss近傍探索GPULSHHNSW Share Tweet