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)
レポジトリ
実装されているメソッドの探し方
- IFがpython側でそんなに定義されていないので、
IndexHogeHoge.h
などをGitHubのリンクから探す
トラブルシューティング
Faiss assertion ‘err == CUBLAS_STATUS_SUCCESS’…と出てクラッシュする
- 原因
- 特定のnvidiaのハードウェア(A100など)と相性が悪い
- 対応
- 別のnvidiaのハードウェアでしばらくお茶を濁す
- github issueを参照し、faissのアップデートを待つなどのヒューリスティック
- 参考