完全解析：使用Faiss進(jìn)行海量特征的相似度匹配

背景

我們不妨想象下面的幾個(gè)例子：

1. 輸入一張商品的圖片，從商品庫中匹配出相似的商品，這是以圖搜圖的一個(gè)例子；
2. 輸入一小段音樂，從音樂庫中匹配出對(duì)應(yīng)的音樂出，這是MIR的一個(gè)例子；
3. 輸入一張人臉，從人臉底庫中匹配出對(duì)應(yīng)的人，這是1:N 人臉識(shí)別的一個(gè)例子；

像這樣的例子還有很多，事實(shí)上，以神經(jīng)網(wǎng)絡(luò)對(duì)樣本進(jìn)行特征的提取，然后在海量的特征庫里進(jìn)行特征相似度的搜索/比對(duì)/匹配，已經(jīng)是AI技術(shù)落地的一大領(lǐng)域。Faiss就是Facebook維護(hù)的一個(gè)高效的特征相似度匹配和聚類的庫。

本文將從最基本的特征比對(duì)說起，然后落腳到我們?yōu)槭裁葱枰狥aiss，以及Faiss上提供的在特征比對(duì)之外的功能。

一個(gè)簡(jiǎn)單的特征相似度比對(duì)的例子

設(shè)想我們使用一個(gè)在ImageNet上預(yù)訓(xùn)練的resnet50模型來提特征，因?yàn)橹恍枰詈蟮?strong style="font-weight: bold;color: black;">2048維特征，我們?cè)诶又邪裷esnet50網(wǎng)絡(luò)最后的fc層去掉。別著急，在deepvac項(xiàng)目的examples目錄下正好有一個(gè)完全一樣的例子：

https://github.com/DeepVAC/deepvac/blob/master/examples/a_resnet_project/test_emb.py

假設(shè)我們現(xiàn)在要在db里放入7030張圖片的特征來作為我們的特征庫，之后，待搜索的圖片就和該特征庫來做相似度匹配。為了實(shí)驗(yàn)這個(gè)想法，首先我們來制作特征庫。當(dāng)我們執(zhí)行程序test_emb.py后，在process函數(shù)中，該test_emb.py會(huì)將目錄下的7030張圖片提取為7030個(gè)2048維的特征：

2020-09-02 11:50:44,507 1073:master INFO     feature shape: torch.Size([1, 2048])
2020-09-02 11:50:44,508 1073:master INFO     feature db shape: torch.Size([1, 2048])
2020-09-02 11:50:44,527 1073:master INFO     feature shape: torch.Size([1, 2048])
2020-09-02 11:50:44,529 1073:master INFO     feature db shape: torch.Size([2, 2048])
2020-09-02 11:50:44,544 1073:master INFO     feature shape: torch.Size([1, 2048])
2020-09-02 11:50:44,544 1073:master INFO     feature db shape: torch.Size([3, 2048])
2020-09-02 11:50:44,571 1073:master INFO     feature shape: torch.Size([1, 2048])
2020-09-02 11:50:44,571 1073:master INFO     feature db shape: torch.Size([4, 2048])
2020-09-02 11:50:44,599 1073:master INFO     feature shape: torch.Size([1, 2048])
2020-09-02 11:50:44,600 1073:master INFO     feature db shape: torch.Size([5, 2048])
......

那么最后這個(gè)特征庫的shape就為7030 x 2048?，F(xiàn)在我們要檢索一張圖片該怎么做呢？對(duì)該圖片提特征、和db里的特征進(jìn)行L2距離的計(jì)算、找出距離最近的1個(gè)或k個(gè)。代碼如下所示：

#deepvac關(guān)于配置文件的標(biāo)準(zhǔn)
>>> from config import config

#需要使用test_emb.py中的DeepvacEmb類
>>> from test_emb import DeepvacEmb
>>> emb = DeepvacEmb(config)

#加載上文保存的特征庫
>>> emb.loadDB('resnet50_gemfield_test.emb')

#獲得測(cè)試圖片的2048維特征
>>> xq = emb.getPillowImgFeatureVector("/gemfield/hostpv/nsfw/test/porn/00002640.000000.jpg")
>>> xq.shape
torch.Size([1, 2048])

#從特征庫中搜索最匹配的，D為距離，I為索引
>>> D,I = emb.search(xq)
>>> D
[0.0]
>>> I
[248]

#從特征庫中搜索最匹配的3個(gè)
>>> D,I = emb.search(xq,k=3)
>>> D
[0.0, 14.658945083618164, 15.17888069152832]
>>> I
[248, 225, 448]

上面的代碼演示了從特征庫中去搜索最相似的圖片。其中使用到的Deepvac的search API就是基于PyTorch的torch.norm() API進(jìn)行的L2距離的計(jì)算。

在多個(gè)CUDA設(shè)備上進(jìn)行特征的相似度搜索

有的時(shí)候，我們的特征庫太大，以至于一個(gè)CUDA卡已經(jīng)裝載不下（比如20G的特征庫，而一個(gè)RTX2080ti才11G顯存）。這個(gè)時(shí)候該怎么辦呢？一個(gè)直覺的想法就是將特征庫拆分成多份，分別放在多個(gè)CUDA設(shè)備上。然后我們的查詢向量xq在每個(gè)CUDA設(shè)備上和特征庫相比對(duì)，最后再匯總排序取出距離最小的那個(gè)。

deepvac的syszux_feature_vector模塊就是這么干的，你可以看下該模塊中的NamesPathsClsFeatureVector類的實(shí)現(xiàn)：

https://github.com/DeepVAC/deepvac/blob/master/deepvac/syszux_feature_vector.pygithub.com

這個(gè)類也是DeepVAC內(nèi)部常用的一個(gè)工具類?，F(xiàn)在問題來了，即使有Deepvac中的search()方法，即使還有syszux_feature_vector模塊中的searchAllDB()方法，但在以下方面還是有點(diǎn)不夠靈活和有力：

1. 如何一次搜索一批的特征，而不僅僅是一個(gè)特征？
2. 如何返回更相似度最近的一批特征，而不只是一個(gè)特征？（好吧，Deepvac類也支持）
3. 如何讓特征庫使用的內(nèi)存空間更??？（你看，上面都需要把特征庫拆分到多個(gè)cuda設(shè)備上了）
4. 搜索速度方面如何更快？

這就是Faiss庫存在的意義。Faiss：Facebook AI Similarity Search。

Faiss環(huán)境準(zhǔn)備

提前說明的福利：你可以使用如下的docker環(huán)境，從而省卻自己配置環(huán)境的煩惱：

#只使用cpu
docker run -it gemfield/faiss:1.6.3-devel bash

#使用GPU的話
docker run --gpus all -it gemfield/faiss:1.6.3-devel bash

如果你不想使用上述的Docker鏡像，那么需要自行安裝依賴、編譯、安裝，這些步驟至少有：

1，安裝依賴包

安裝libopenblas-dev：

apt install libopenblas-dev

否則報(bào)錯(cuò)：CMake Error at /usr/share/cmake-3.18/Modules/FindPackageHandleStandardArgs.cmake:165 (message):
Could NOT find BLAS (missing: BLAS_LIBRARIES)

安裝swig：

apt install swig

否則報(bào)錯(cuò)：Could NOT find SWIG (missing: SWIG_EXECUTABLE SWIG_DIR python)。

2，編譯

在Faiss目錄里，執(zhí)行如下操作：

make build
cmake ..
make VERBOSE=1
make install

整個(gè)編譯的最終產(chǎn)物有：

• libfaiss.a （C++庫，也用于鏈接_swigfaiss.so）
• libfaiss_python_callbacks.a （用于鏈接_swigfaiss.so）
• _swigfaiss.so（用于python）

最后一步的make install會(huì)將libfaiss.a安裝到/usr/local/lib/libfaiss.a，以及將頭文件安裝到/usr/local/include/faiss/目錄下。

3，安裝python

在build/faiss/python目錄下：

python setup.py install

會(huì)將把_swigfaiss.so安裝在/opt/conda/lib/python3.7/site-packages/faiss-1.6.3-py3.7.egg/faiss/

Faiss的簡(jiǎn)單使用：Flat

我們先定義兩個(gè)變量xb和xq。xb用來表示特征庫，xq用來表示待查詢的2048維向量。如果沿用上面的例子，則xb就是提前存儲(chǔ)了7030個(gè)樣本的特征的“數(shù)據(jù)庫”，它的shape就是7030x2048——這樣的“數(shù)據(jù)庫”在Faiss中稱作Index object。

就像數(shù)據(jù)庫的種類有很多一樣，Index的種類也有很多，我們先從最簡(jiǎn)單的IndexFlatL2開始。IndexFlatL2是什么類型的“數(shù)據(jù)庫”呢？就是使用暴力L2搜索的數(shù)據(jù)庫——也就是和特征庫中的每個(gè)特征進(jìn)行L2距離計(jì)算然后取出距離最近的那個(gè)。是不是看著很熟悉？沒錯(cuò)，這和上文中提到的DeepVAC的search() API的原理是一模一樣的。

好多種Index在被真正檢索前，是需要一個(gè)“訓(xùn)練”操作的，類似給數(shù)據(jù)庫的字段建立索引，Index object的“訓(xùn)練”其實(shí)就是提前根據(jù)特征的分布進(jìn)行聚類訓(xùn)練。而我們的IndexFlatL2并不在列，前面說了，它是最簡(jiǎn)單的“數(shù)據(jù)庫”：

import numpy as np
import faiss

d = 2048                          # dimension
nb = 7030                     # database size
nq = 10                       # nb of queries

np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.

xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

index = faiss.IndexFlatL2(d)
print(index.is_trained)

index.add(xb)
print(index.ntotal)

k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print("I: ",I)
print("D: ",D)

上面是使用IndexFlatL2的一個(gè)簡(jiǎn)單例子，Gemfield初始化了一個(gè)7030x2048的特征庫，然后一次檢索5個(gè)特征，也就是xq是5x2048。代碼輸出：

True
7030
I:  [[   0  998 1309 1134]
 [   1  252 2013 2790]
 [   2 1046 1342 1204]
 [   3   56 1846  910]
 [   4  714  324   50]]
D:  [[  0.      323.07217 325.1012  325.8144 ]
 [  0.      308.83826 313.52512 317.5051 ]
 [  0.      313.24506 313.52145 316.1954 ]
 [  0.      311.7074  313.01157 313.31152]
 [  0.      316.34128 316.5642  317.65128]]

I是5個(gè)待檢索特征各自前4個(gè)特征庫中最相似的index，D是對(duì)應(yīng)的距離。既然前文說過，IndexFlatL2只是最簡(jiǎn)單的一種“數(shù)據(jù)庫”，那么其它復(fù)雜的數(shù)據(jù)庫都有什么呢？你可以使用如下的方法簡(jiǎn)單list下就可以管中窺豹了：

>>> import faiss
>>> for s in dir(faiss):
...   if s.startswith('Index'):
...     print(s)
... 
IndexBinary
IndexBinaryFlat
IndexFlat
IndexFlat1D
IndexFlat1D_swigregister
IndexFlatIP
IndexFlatIP_swigregister
IndexFlatL2
IndexFlatL2BaseShift
IndexFlatL2BaseShift_swigregister
IndexFlatL2_swigregister
IndexFlat_swigregister
IndexHNSW
IndexHNSW2Level
IndexHNSW2Level_swigregister
IndexHNSWFlat
IndexHNSWFlat_swigregister
IndexHNSWPQ
IndexHNSWPQ_swigregister
IndexHNSWSQ
IndexHNSWSQ_swigregister
IndexHNSW_swigregister
IndexIDMap
IndexIDMap2
IndexIDMap2_swigregister
IndexIDMap_swigregister
IndexIVF
IndexIVFFlat
IndexIVFFlatDedup
IndexIVFFlatDedup_swigregister
IndexIVFFlat_swigregister
IndexIVFPQ
IndexIVFPQR
IndexIVFPQR_swigregister
IndexIVFPQStats
IndexIVFPQStats_swigregister
IndexIVFPQ_swigregister
IndexIVFScalarQuantizer
IndexIVFScalarQuantizer_swigregister
IndexIVFSpectralHash
IndexIVFSpectralHash_swigregister
IndexIVFStats
IndexIVFStats_swigregister
IndexIVF_swigregister
IndexLSH
IndexLSH_swigregister
IndexLattice
IndexLattice_swigregister
IndexPQ
IndexPQStats
IndexPQStats_swigregister
IndexPQ_swigregister
......

以及GPU上的Index類型：

>>> import faiss
>>> for s in dir(faiss):
...   if s.startswith('GpuIndex'):
...     print(s)
... 
GpuIndexFlat
GpuIndexFlatConfig
GpuIndexFlatConfig_swigregister
GpuIndexFlatIP
GpuIndexFlatIP_swigregister
GpuIndexFlatL2
GpuIndexFlatL2_swigregister
GpuIndexFlat_swigregister
GpuIndexIVF
GpuIndexIVFConfig
GpuIndexIVFConfig_swigregister
GpuIndexIVFFlat
GpuIndexIVFFlatConfig
GpuIndexIVFFlatConfig_swigregister
GpuIndexIVFFlat_swigregister
GpuIndexIVFPQ
GpuIndexIVFPQConfig
GpuIndexIVFPQConfig_swigregister
GpuIndexIVFPQ_swigregister
GpuIndexIVFScalarQuantizer
GpuIndexIVFScalarQuantizerConfig
GpuIndexIVFScalarQuantizerConfig_swigregister
GpuIndexIVFScalarQuantizer_swigregister
GpuIndexIVF_swigregister
GpuIndex_swigregister

這里已經(jīng)看到了各種CPU的Index和GPU的Index，那么實(shí)踐中這兩者誰更快呢？

• xq的batch很小，Index很?。篊PU通常更快；
• xq的batch很小，Index很大：GPU通常更快；
• xq的batch很大，Index很小：隨便；
• xq的batch很大，Index很大：GPU通常更快；
• GPU通常比CPU快5到10倍；

讓Faiss使用更少的內(nèi)存：PQ

IndexFlatL2的暴力L2距離匹配是最基本的用法。很快你就會(huì)遇到一個(gè)問題，當(dāng)特征庫很大的時(shí)候，一個(gè)顯存就很快裝載不下特征庫了；即使是換成使用內(nèi)存來裝載特征庫，也裝載不下了。有沒有一種壓縮算法能減小特征庫的大小呢？這就是PQ（Product Quantizer）。

不管是IndexFlatL2、IndexIVFFlat、或者名字中包含有Flat的Index，都會(huì)在加載到內(nèi)存中的特征庫中保存全量的特征，以2048維的float類型為例，一個(gè)樣本就需要8192個(gè)字節(jié)。如果類似天貓京東這樣有1億件商品，每件商品就按照一個(gè)樣本圖片來算，也需要...763G的特征庫。如果我們能將特征庫進(jìn)行有效壓縮，那可以節(jié)省相當(dāng)可觀的資源。PQ就是帶著這樣的目的而來的，這是一種有損壓縮，所以這種Index進(jìn)行檢索的返回值只是近似的準(zhǔn)確，而不是像IndexFlatL2那樣可以返回絕對(duì)準(zhǔn)確的值。那么PQ是如何將一個(gè)樣本的8192字節(jié)壓縮的更小的呢？假設(shè)我們有100萬個(gè)樣本，每個(gè)樣本有2048維特征（100萬 x 2048）：

1. 我們將每個(gè)樣本的2048維vector拆分為8個(gè)sub-vector，每個(gè)sub-vector就是256維了。這樣就會(huì)有8個(gè)100萬x256維的矩陣；
2. 我們?cè)谶@8個(gè)矩陣上使用k = 256的k-means 聚類算法（Gemfield：這里的256和上面的256沒啥關(guān)系），這樣每個(gè)矩陣上會(huì)得到256個(gè)centroid（質(zhì)心），一共有8組256個(gè)centroid；聚類算法的使用，使得每個(gè)256維的centroid成為最能代表那3906個(gè)256維特征的一個(gè)向量（100w/256 = 3906）；為啥選擇k=256呢？因?yàn)?56個(gè)centroid的索引可以使用一個(gè)字節(jié)裝下；
3. 我們?cè)倩氐侥?億個(gè)商品的特征庫，我們將每個(gè)商品的2048維特征拆分成8個(gè)sub-vector，每一個(gè)sub-vector都被替換為距離最近的那個(gè)centroid，并使用該centroid的id來表示（1個(gè)字節(jié)?。?。如此以來，2048維特征就被替換成了8個(gè)centroid ID，也就是8個(gè)字節(jié)！如此以來，商品特征庫就從763G下降到了0.745G！

內(nèi)存的使用量確實(shí)降下來了，但是如果特征庫只包含centroid ID的話，怎么進(jìn)行向量的相似度計(jì)算呢？只有centroid ID的話，怎么計(jì)算L2距離呢？？？是不是需要把特征庫里的1億個(gè)特征（每個(gè)特征此刻為8個(gè)字節(jié)）中的centroid ID替換成centroid來進(jìn)行L2距離的計(jì)算呢？這固然是一個(gè)直截了當(dāng)?shù)南敕?，只不過，替換回去（也就是解壓縮）的話，每個(gè)特征本來用8個(gè)字節(jié)表示，如今又要變成8096個(gè)字節(jié)了，那我們這么折騰一回圖啥呀！相反，我們可以這么做：

1，一個(gè)2048維的xq來了，將該xq vector拆分為8個(gè)sub-vector；

2，xq vector的每個(gè)sub-vector就和8x256的centroid中對(duì)應(yīng)的那組1x256的centroid進(jìn)行L2距離計(jì)算，得到256個(gè)距離；那么8組下來，就會(huì)得到8組256個(gè)L2距離；這個(gè)計(jì)算量仿佛和一個(gè)只有256個(gè)樣本特征的特征庫差不多；

3，上述的8組256個(gè)L2的距離，可以看成是一個(gè)表：256行x8列（畢竟是一個(gè)樣本的特征被拆分了8個(gè)sub vector，所以不是8x256而是256x8）；這個(gè)表很重要啊，我暫且稱之為gemfield表；

4，特征庫現(xiàn)在是已經(jīng)壓縮的狀態(tài)，也就是說每個(gè)樣本特征用的是8個(gè)centroid ID來表示的。而每個(gè)特征庫的樣本（每個(gè)xb記錄）和xq的L2距離，就等于每個(gè)xb記錄的8個(gè)sub-vector和xq的8個(gè)sub-vector的L2距離之和，就約等于xb記錄的8個(gè)centroid（中的每個(gè)）和xq的8個(gè)sub-vector（中的每個(gè)）的L2距離之和！而xb記錄的8個(gè)centorid中的每個(gè)和xq的8個(gè)sub-vector中的每個(gè)之間的L2距離，直接通過上述的gemfield表查表獲得！

5，將距離排序，取得距離最近的k個(gè)xb記錄（的index和distance）。

上面的centroid（最類中心的那個(gè)2048維向量），在Faiss中我們稱之為code；上述的8組256個(gè)centroid，在Faiss中我們稱之為8個(gè)code book；這8個(gè)code book可以表達(dá)256^8個(gè)值，還是很大的。

讓Faiss進(jìn)行更快的檢索：IVF

IndexFlatL2的暴力L2距離匹配是最基本的用法。很快你又會(huì)遇到一個(gè)問題，當(dāng)檢索量很大的時(shí)候，每次檢索哪怕減少一點(diǎn)時(shí)間，對(duì)整體系統(tǒng)的性能提升也會(huì)有很大的幫助；換言之，可以提升邊際效益。那么如何讓檢索更快呢？事實(shí)上，更快的檢索來自于兩個(gè)方面：

1. 兩兩特征比對(duì)更少的計(jì)算量；PQ順帶著做了；
2. 只和特征庫的一部分進(jìn)行比對(duì)；和特征庫的每一個(gè)特征進(jìn)行比對(duì)，叫做窮舉；只和部分特征進(jìn)行比對(duì)，叫做IVF；

問題是，為什么和特征庫的一部分進(jìn)行比對(duì)就能找到想要的答案呢？呃，不能。只能找到近似正確的答案。為什么和特征庫的一部分進(jìn)行比對(duì)就能找到近似正確的答案呢？呃，倒排索引（IVF）。IVF用來提前過濾dataset從而避開對(duì)全部特征庫的窮舉搜索，比如gemfield使用k-means算法將數(shù)據(jù)庫進(jìn)行聚類（比如100個(gè)分區(qū)），當(dāng)查詢一個(gè)xq的時(shí)候，和能代表這100個(gè)分區(qū)的100個(gè)centroid進(jìn)行L2比較，拿到最接近的5個(gè)；然后在這5個(gè)分區(qū)里再進(jìn)行窮舉搜索。這樣，有95%的xb記錄就被忽略掉了。

IVF，全稱Inverted File Index，中文翻譯為倒排索引，指的是在文本搜索中（比如搜索引擎），將每個(gè)單詞到該單詞所屬的文檔之間的映射關(guān)系保存到數(shù)據(jù)庫中。Gemfield是非常不喜歡這個(gè)概念的，英文的Inverted File Index我都感覺詞不達(dá)意，而中文的“倒排索引”更是讓人摸不著頭腦。以一本書為例，書前面的目錄就是索引：

index，索引

書最后面的index就是倒排索引，如下所示：

IVF，倒排索引

因此，在Faiss中所有帶有IVF的index，指的都是提前將數(shù)據(jù)庫使用k-means聚類算法劃分為多個(gè)partition，每個(gè)partition中包含有對(duì)應(yīng)的feature vectors（這就是inverted file lists指向的），同時(shí)，每個(gè)partition還有對(duì)應(yīng)的centroid，用來決定該partition是應(yīng)該被窮舉搜索，還是被忽略。

IVF這個(gè)方法當(dāng)然加快了檢索的速度，但是也是有代價(jià)的。假如xq是落在partition的邊緣地帶，那這個(gè)xq最近的記錄大概率是距離它最近（這個(gè)最近指的是和centroid比較）的前面好多個(gè)partition里的一個(gè)，這樣即使我們指定很多個(gè)比較近的partition（比如5個(gè)），如果ground truth實(shí)際上是在第6個(gè)partition里，這樣返回的結(jié)果依然是不準(zhǔn)確的。

因此，帶有IVF的檢索只能返回近似正確的值，而不能像IndexFlatL2那樣返回絕對(duì)正確的值。但是像上面這種ground truth是在第6個(gè)partition里，而我們指定5個(gè)partition也是比指定1個(gè)partition要更準(zhǔn)確些的（代價(jià)就是檢索時(shí)間多了）。一旦找到最近的那個(gè)partition后，便就要開始窮舉檢索該partition里的每條記錄了，這就是IndexIVFFlat的由來。在某個(gè)partition中進(jìn)行搜索的過程還可以使用上一節(jié)的PQ壓縮的算法，因此，在Faiss中，我們還經(jīng)常會(huì)使用的一個(gè)Index叫作IndexIVFPQ。

這個(gè)partition的概念，在Faiss中稱之為Voronoi cells；選擇某個(gè)Voronoi cells然后進(jìn)行檢索的動(dòng)作，稱之為“probe”；而在最近的“多少個(gè)”Voronoi cells中進(jìn)行檢索，這個(gè)“多少個(gè)”的數(shù)量稱之為nprobe；在IVF Index object的屬性中，就有nprobe這個(gè)屬性：

import numpy as np
import faiss

d = 2048                          # dimension
nb = 7030                     # database size
nq = 10                       # nb of queries

np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.

xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.

index = faiss.IndexFlatL2(d)
print(index.is_trained)

index.add(xb)
print(index.ntotal)

######
nlist = 100
m = 8
k = 4
quantizer = faiss.IndexFlatL2(d)  # this remains the same
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
                                  # 8 specifies that each sub-vector is encoded as 8 bits
index.train(xb)
index.add(xb)
#nprobe
index.nprobe = 10
D, I = index.search(xb[:5], k)
print("I: ",I)

IndexIVFPQ的參數(shù)中，d代表特征的維度2048，nlist代表Voronoi cells的數(shù)量，m代表subquantizers的數(shù)量（給PQ用），8代表使用8bits表示一個(gè)特征的1個(gè)sub-vector。代碼輸出：

root@pytorch160-ai2:/home/gemfield# python test.py 
#當(dāng)index.nprobe = 10
I:  [[  14   68    0  599]
 [ 297    1  546  227]
 [ 246  311    2  137]
 [ 213    3  256  248]
 [   4  919  644 1351]]

可見確實(shí)只能返回近似準(zhǔn)確的值。

無論如何內(nèi)存都不夠用：Distributed index

在某些情況下，內(nèi)存或者顯存無論如何都不夠使用。比如要加載20多個(gè)GB的特征庫，但是顯卡只有11GB，又不想妥協(xié)任何的準(zhǔn)確度。那怎么辦呢？方法之一就是將特征庫分散加載到多個(gè)服務(wù)器的CUDA設(shè)備上。

在項(xiàng)目倉庫的faiss/contrib/目錄下，F(xiàn)aiss提供了rpc.py，一個(gè)小型的RPC庫?；谠揜PC庫，F(xiàn)aiss在faiss/contrib/client_server.py中實(shí)現(xiàn)了run_index_server() API和ClientIndex類。在不同的服務(wù)器上，使用run_index_server() API運(yùn)行服務(wù)：

#比如四個(gè)服務(wù)器: ai{1..4}.gemfield.org
#index就是所有特征庫的四分之一
run_index_server(index, port, v6=v6)

在客戶端，使用client_index=ClientIndex(host_port_array)來訪問：

syszux_ports = [
    ('ai1.gemfield.org', 12010),
    ('ai2.gemfield.org', 12011),
    ('ai3.gemfield.org', 12012),
    ('ai4.gemfield.org', 12013),
]

client_index = ClientIndex(syszux_ports)
#xq是query vector
D, I = client_index.search(xq, 5)

其實(shí)client_index獲得分段的結(jié)果，最后歸并取最好結(jié)果的這個(gè)過程，和文章開頭提到的syszux_feature_vector.py里的邏輯是一樣的。

無論如何內(nèi)存都不夠用：On-disk storage

參考項(xiàng)目中的faiss/contrib/ondisk.py。

當(dāng)xq是pytorch的tensor時(shí)

在前文的各種例子中，你都發(fā)現(xiàn)，無論是xb還是xq，它們都是轉(zhuǎn)換為numpy數(shù)組才開始調(diào)用Faiss的API的。沒錯(cuò)，在Faiss中，numpy就是一等公民。既然Faiss是Facebook的項(xiàng)目，既然Facebook還有PyTorch這么流行的項(xiàng)目，那么在Faiss中為什么不原生支持PyTorch的Tensor呢？更何況numpy只能存活在CPU上，Tensor可是CPU和GPU通吃??！實(shí)在是令人莫名其妙、瞠目結(jié)舌、匪夷所思！

在前文的例子中：

https://github.com/DeepVAC/deepvac/blob/master/examples/a_resnet_project/test_emb.pygithub.com

我們的特征庫可都是使用PyTorch的Tensor來存儲(chǔ)和序列化的，查詢特征xq也是tensor，總不能每次都從Tensor轉(zhuǎn)換成numpy吧。目前，F(xiàn)aiss提供了一種臨時(shí)的措施，可以直接讀取Tensor底層的內(nèi)存（Tensor必須是is_contiguous的），然后使用index的search_c() API來檢索。關(guān)于在index中檢索PyTorch Tensor的詳細(xì)用法，你可以參考syszux_feature_vector.py中的NamesPathsClsFeatureVectorByFaissPytorch類：

https://github.com/DeepVAC/deepvac/blob/master/deepvac/syszux_feature_vector.pygithub.com

最后，如何選擇一種Index呢？

我們已經(jīng)見識(shí)過的關(guān)鍵字有Flat、IVF、PQ，那么如何選擇一種Index來匹配我們的場(chǎng)景呢？

1. 當(dāng)需要絕對(duì)準(zhǔn)確的結(jié)果時(shí)，使用Flat；比如IndexFlatL2 或者 IndexFlatIP；
2. 如果內(nèi)存完全夠用富裕的不行，使用HNSW；如果一般夠用，使用Flat；如果有點(diǎn)吃緊，使用PCARx,...,SQ8；如果非常吃緊，使用OPQx_y,...,PQx；
3. 如果特征庫小于1M個(gè)記錄，使用"...,IVFx,..."；如果在1M到10M之間，使用"...,IVF65536_HNSW32,..."；如果在10M - 100M之間，使用"...,IVF262144_HNSW32,..."；如果在100M - 1B之間，使用"...,IVF1048576_HNSW32,..."。

用于訓(xùn)練的xb記錄越多，聚類算法的訓(xùn)練效果越好，但訓(xùn)練需要花的時(shí)間也就越多，別忘了這一點(diǎn)。