Faiss PQ索引簡介

• 1.向量檢索問題

• 2.faiss索引型別

• 3.乘積量化

• 3.1 向量量化

• 3.2 乘積量化

• 3.3 空間佔用對比

• 3.4 faiss中乘積量化的應用

• 3.5 超參

• 4.參考資料

1.向量檢索問題

隨著神經網路的發展，embedding的思想被廣泛的應用在搜推廣、影象、自然語言處理等領域，在實際的工業場景中，我們常常會遇到基於embedding進行文字、影象、視訊等物料的相關內容檢索問題，這類問題通常要求在幾毫秒的時間內完成百萬甚至億級別候選物料上的檢索。在這類問題中，主要需要考慮的三個問題是速度、記憶體以及準確性，其中速度是必須要解決的問題，同時我們希望能在保證速度的基礎上，儘可能的提升準確率，降低記憶體佔用。因此可以想到，我們是不是可以通過一定的方法，利用記憶體和準確率來換取查詢速度的提升。Faiss是由FacebookAI團隊開發的向量檢索庫，提供了多種向量查詢方案，可以實現在億級別候選物料上的毫秒級查詢，是目前最主流的向量檢索庫。在Faiss中，把具體的查詢演算法實現稱為索引，由於faiss中提供了多種型別的索引，因此瞭解其中不同索引索引的實現方式對於我們的應用就尤為關鍵。

2.faiss索引型別

)

faiss索引型別主要可以分為暴力檢索、乘積量化、區域性敏感雜湊、基於圖的方法。向量檢索問題通常需要考慮召回率、耗時以及記憶體佔用三個問題，而實際的工業場景中，一般存在候選物料量級較大，耗時要求高的情況。對比faiss的索引型別，暴力檢索類索引雖然召回率百分百，但耗時無法接受。而常用的索引型別主要是乘積量化和圖兩類標籤。其中，基於圖的方法召回率可以逼近暴力檢索且耗時也略優於乘積量化類索引，但是在構建索引過程中需要佔用的記憶體很大，如果能保證足夠的資源，圖方法可以在耗時和召回率上做到最優。乘積量化召回率低於圖方法，但是能保證較好的耗時和空間佔用，是在候選物料集較大時的最優選擇。

索引	召回率	耗時
暴力檢索	最優	最差
基於圖的索引	優	優
乘積量化	次優	優

3.乘積量化

3.1 向量量化

在介紹乘積量化前，首先需要介紹向量量化的基本概念。向量量化和訊號編碼的概念基本類似，就是將由連續值構成的向量從歐式空間對映到一個由有限離散值構成的集合中,定義該對映為,則,這裡也成為codebook。 如上圖所示，定義對映函式為kmeans，向量量化流程如下:

1.訓練kmeans聚類，得到每個點所屬的聚類編號 2.將每個向量所屬的聚類編號作為量化結果

faiss中對應該類方法的索引型別為IndexIVFFlat。

3.2 乘積量化

乘積量化的思路就是將向量分割成多段後，對每一段分別進行向量量化。假設將向量維度為,切分成段，則每段的維度大小為，對於第個分段，向量表示為,對應的codebook為。在索引訓練完成後，全域性的codebook表示為各個分段量化結果的乘積，這也是乘積量化的命名原因。

3.3 空間佔用對比

假設向量維度為D,向量量化的codebook大小為,儲存codebook需要的空間;乘積量化每個分段只需要的codebook大小,儲存codebook需要的空間。可以發現，分段量化後可以在空間佔用更小的情況下達到一樣大的codebook規模。

3.4 faiss中乘積量化的應用

在faiss的乘積量化的實現中，還引入了層次化量化的思想，在乘積量化前引入了一層粗糙量化，形成粗糙量化+細粒度量化的兩層結構。引入粗糙量化的主要目的在於優化查詢速度，由於候選向量的數量級一般較大，如果直接遍歷所有候選，效率還是很難達到要求。加入粗糙量化後，通過計算查詢向量到粗糙量化類簇中心的聚類就可以選出幾個最有可能包含正確結果的類簇，然後再在這些類簇上進行第二級的查詢，就可以大大縮減查詢時間，同時保證查詢效率 索引構建 : 1. 構建第一層的量化器,codebook,得到每個向量X的向量量化結果2. 計算每個向量粗糙量化後的殘差,對進行乘積量化

粗糙量化+細粒度量化的形式可以進一步加快查詢速度，但是也會造成一定的召回率損失，實際應用時需要通過調參較低這一影響。在粗糙聚類後，各個類簇內的向量分佈可能差異較大，如果直接用原始向量進行細粒度量化，可能在檢索時會放大誤差，使用殘差進行細粒度量化能緩解這個問題。

向量查詢 在兩層量化構建索引後，查詢可以改寫為如下形式

其中,和y無關，可以預先計算快取，部分需要計算查詢向量到粗糙聚類中心的距離，這部分的計算量取決於訓練時設定的粗糙聚類中心個數，部分需要計算查詢向量和簇內殘差向量，這部分計算量和設定的查詢類簇數量相關，最壞情況下需要遍歷所有類簇。

3.5 超參

構建PQ索引時，超引數的選擇會在很大程度上影響線上效果，需要多調參找到召回率和耗時之間的trader-off。主要影響效果的引數包括粗糙量化類簇個數、分塊數量、分塊位元組等影響索引訓練的引數，查詢的類簇數量這種影響查詢階段的引數，除此之外PQ索引型別對查詢效果也有很大影響，可以嘗試PQ，OPQ，PQ with PCA等不同索引。

4.參考資料

1. Huang J T ,  Sharma A ,  Sun S , et al. Embedding-based Retrieval in Facebook Search[C]// 2020.

2. faiss wiki:http://github.com/facebookresearch/faiss/wiki

3. 語義向量召回之ANN檢索:http://mp.weixin.qq.com/s/YOnzPcQiaoNf1aSImNOA5g

4. Faiss基於PQ的倒排索引實現:http://zhuanlan.zhihu.com/p/34363377

轉轉研發中心及業界小夥伴們的技術學習交流平臺，定期分享一線的實戰經驗及業界前沿的技術話題。關注公眾號「轉轉技術」（綜合性）、「大轉轉FE」（專注於FE）、「轉轉QA」（專注於QA），更多幹貨實踐，歡迎交流分享~