一.簡(jiǎn)介

1.1 什么是Faiss

Faiss的全稱是Facebook AI Similarity Search，是Facebook的AI團(tuán)隊(duì)針對(duì)大規(guī)模相似度檢索問(wèn)題開發(fā)的一個(gè)工具，使用C++編寫，有python接口，對(duì)10億量級(jí)的索引可以做到毫秒級(jí)檢索的性能。
簡(jiǎn)單來(lái)說(shuō)，Faiss的工作就是把我們自己的候選向量集封裝成一個(gè)index數(shù)據(jù)庫(kù)，它可以加速我們檢索相似向量top-K的過(guò)程，其中有些索引還支持GPU構(gòu)建。

1.2 Faiss的安裝

## cpu版
$ conda install -c pytorch faiss-cpu
## gpu版
$ conda install -c pytorch faiss-gpu

二.Faiss檢索流程

2.1 構(gòu)建向量庫(kù)

這一部分就是將我們已有的數(shù)據(jù)轉(zhuǎn)成向量庫(kù)。

import numpy as np
d = 64                                           # 向量維度
nb = 100000                                      # index向量庫(kù)的數(shù)據(jù)量
nq = 10000                                       # 待檢索query的數(shù)目
np.random.seed(1234)             
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.                # index向量庫(kù)的向量
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.                # 待檢索的query向量

2.2 構(gòu)建索引

用faiss 構(gòu)建index，并將向量添加到index中。這里我們選用暴力檢索的方法FlatL2，L2代表構(gòu)建的index采用的相似度度量方法為L(zhǎng)2范數(shù)，即歐氏距離。

import faiss          
index = faiss.IndexFlatL2(d)             
print(index.is_trained)         # 輸出為True，代表該類index不需要訓(xùn)練，只需要add向量進(jìn)去即可
index.add(xb)                   # 將向量庫(kù)中的向量加入到index中
print(index.ntotal)             # 輸出index中包含的向量總數(shù)，為100000 

2.3 top-k檢索

檢索與query最相似的top-k。

k = 4                     # topK的K值
D, I = index.search(xq, k)# xq為待檢索向量，返回的I為每個(gè)待檢索query最相似TopK的索引list，D為其對(duì)應(yīng)的距離
print(I[:5])
print(D[-5:])

三.Faiss構(gòu)建索引的多種方式

構(gòu)建index方法和傳參方法可以為：

dim, measure = 64, faiss.METRIC_L2
param = 'Flat'
index = faiss.index_factory(dim, param, measure)

• dim為向量維數(shù)
• 最重要的是param參數(shù)，它是傳入index的參數(shù)，代表需要構(gòu)建什么類型的索引；
• measure為度量方法，目前支持兩種，歐氏距離和inner product，即內(nèi)積。因此，要計(jì)算余弦相似度，只需要將vecs歸一化后，使用內(nèi)積度量即可。

此外，Faiss官方支持八種度量方式，分別是：
1）METRIC_INNER_PRODUCT（內(nèi)積）
2）METRIC_L1（曼哈頓距離）
3）METRIC_L2（歐氏距離）
4）METRIC_Linf（無(wú)窮范數(shù)）
5）METRIC_Lp（p范數(shù)）
6）METRIC_BrayCurtis（BC相異度）
7）METRIC_Canberra（蘭氏距離/堪培拉距離）
8）METRIC_JensenShannon（JS散度）

3.1 Flat ：暴力檢索

• 優(yōu)點(diǎn)：該方法是Faiss所有index中最準(zhǔn)確的，召回率最高的方法，沒(méi)有之一；
• 缺點(diǎn)：速度慢，占內(nèi)存大。
• 使用情況：向量候選集很少，在50萬(wàn)以內(nèi)，并且內(nèi)存不緊張。
• Ps：雖然都是暴力檢索，faiss的暴力檢索速度比一般程序猿自己寫的暴力檢索要快上不少，所以并不代表其無(wú)用武之地，建議有暴力檢索需求的同學(xué)還是用下faiss。
• 構(gòu)建方法：

dim, measure = 64, faiss.METRIC_L2
param = 'Flat'
index = faiss.index_factory(dim, param, measure)
index.is_trained                                   # 輸出為True
index.add(xb)                                      # 向index中添加向量

3.2 IVFx Flat ：倒排暴力檢索

• 優(yōu)點(diǎn)：IVF主要利用倒排的思想，在文檔檢索場(chǎng)景下的倒排技術(shù)是指，一個(gè)kw后面掛上很多個(gè)包含該詞的doc，由于kw數(shù)量遠(yuǎn)遠(yuǎn)小于doc，因此會(huì)大大減少了檢索的時(shí)間。在向量中如何使用倒排呢？可以拿出每個(gè)聚類中心下的向量ID，每個(gè)中心ID后面掛上一堆非中心向量，每次查詢向量的時(shí)候找到最近的幾個(gè)中心ID，分別搜索這幾個(gè)中心下的非中心向量。通過(guò)減小搜索范圍，提升搜索效率。
• 缺點(diǎn)：速度也還不是很快。
• 使用情況：相比Flat會(huì)大大增加檢索的速度，建議百萬(wàn)級(jí)別向量可以使用。
• 參數(shù)：IVFx中的x是k-means聚類中心的個(gè)數(shù)
• 構(gòu)建方法：

dim, measure = 64, faiss.METRIC_L2 
param = 'IVF100,Flat'                           # 代表k-means聚類中心為100,   
index = faiss.index_factory(dim, param, measure)
print(index.is_trained)                          # 此時(shí)輸出為False，因?yàn)榈古潘饕枰?xùn)練k-means，
index.train(xb)                                  # 因此需要先訓(xùn)練index，再add向量
index.add(xb)

3.3 IVFxPQy 倒排乘積量化

• 優(yōu)點(diǎn)：工業(yè)界大量使用此方法，各項(xiàng)指標(biāo)都均可以接受，利用乘積量化的方法，改進(jìn)了IVF的k-means，將一個(gè)向量的維度切成x段，每段分別進(jìn)行k-means再檢索。
• 缺點(diǎn)：集百家之長(zhǎng)，自然也集百家之短
• 使用情況：一般來(lái)說(shuō)，各方面沒(méi)啥特殊的極端要求的話，最推薦使用該方法！
• 參數(shù)：IVFx，PQy，其中的x和y同上
• 構(gòu)建方法：

dim, measure = 64, faiss.METRIC_L2  
param =  'IVF100,PQ16'
index = faiss.index_factory(dim, param, measure) 
print(index.is_trained)                          # 此時(shí)輸出為False，因?yàn)榈古潘饕枰?xùn)練k-means， 
index.train(xb)                                  # 因此需要先訓(xùn)練index，再add向量 index.add(xb)
index.add(xb)

3.4 LSH 局部敏感哈希

• 原理：哈希對(duì)大家再熟悉不過(guò)，向量也可以采用哈希來(lái)加速查找，我們這里說(shuō)的哈希指的是局部敏感哈希（Locality Sensitive Hashing，LSH），不同于傳統(tǒng)哈希盡量不產(chǎn)生碰撞，局部敏感哈希依賴碰撞來(lái)查找近鄰。高維空間的兩點(diǎn)若距離很近，那么設(shè)計(jì)一種哈希函數(shù)對(duì)這兩點(diǎn)進(jìn)行哈希計(jì)算后分桶，使得他們哈希分桶值有很大的概率是一樣的，若兩點(diǎn)之間的距離較遠(yuǎn)，則他們哈希分桶值相同的概率會(huì)很小。
• 優(yōu)點(diǎn)：訓(xùn)練非常快，支持分批導(dǎo)入，index占內(nèi)存很小，檢索也比較快
• 缺點(diǎn)：召回率非常拉垮。
• 使用情況：候選向量庫(kù)非常大，離線檢索，內(nèi)存資源比較稀缺的情況
• 構(gòu)建方法：

dim, measure = 64, faiss.METRIC_L2  
param =  'LSH'
index = faiss.index_factory(dim, param, measure) 
print(index.is_trained)                          # 此時(shí)輸出為True
index.train(xb) 
index.add(xb)

3.5 HNSWx

• 優(yōu)點(diǎn)：該方法為基于圖檢索的改進(jìn)方法，檢索速度極快，10億級(jí)別秒出檢索結(jié)果，而且召回率幾乎可以媲美Flat，最高能達(dá)到驚人的97%。檢索的時(shí)間復(fù)雜度為loglogn，幾乎可以無(wú)視候選向量的量級(jí)了。并且支持分批導(dǎo)入，極其適合線上任務(wù)，毫秒級(jí)別體驗(yàn)。
• 缺點(diǎn)：構(gòu)建索引極慢，占用內(nèi)存極大（是Faiss中最大的，大于原向量占用的內(nèi)存大小）
• 參數(shù)：HNSWx中的x為構(gòu)建圖時(shí)每個(gè)點(diǎn)最多連接多少個(gè)節(jié)點(diǎn)，x越大，構(gòu)圖越復(fù)雜，查詢?cè)骄_，當(dāng)然構(gòu)建index時(shí)間也就越慢，x取4~64中的任何一個(gè)整數(shù)。
• 使用情況：不在乎內(nèi)存，并且有充裕的時(shí)間來(lái)構(gòu)建index
• 構(gòu)建方法：

dim, measure = 64, faiss.METRIC_L2   
param =  'HNSW64' 
index = faiss.index_factory(dim, param, measure)  
print(index.is_trained)                          # 此時(shí)輸出為True 
index.add(xb)