導讀：本文是“資料拾光者”專欄的第三十八篇文章，這個系列將介紹在廣告行業中自然語言處理和推薦系統實踐。本篇主要介紹實際廣告搜尋業務中經常使用的大規模檢索利器faiss，希望對在海量高維向量空間進行大規模檢索任務感興趣的小夥伴有所幫助。

歡迎轉載，轉載請註明出處以及連結，更多關於自然語言處理、推薦系統優質內容請關注如下頻道。

知乎專欄：資料拾光者

公眾號：資料拾光者

摘要：本篇主要介紹實際廣告搜尋業務中經常使用的大規模檢索利器faiss。首先是背景介紹，主要講了相似度匹配任務和大規模檢索演算法以及如何應用到我們的實際業務場景；然後重點介紹了faiss，包括什麼是faiss、大規模檢索任務流程、faiss索引型別介紹、各種索引優缺點對比以及線上構建索引經驗分享；最後專案實踐了faiss。希望對在海量高維向量空間進行大規模檢索任務感興趣的小夥伴有所幫助。

下面主要按照如下思維導圖進行學習分享：

1.1 相似度匹配任務和大規模檢索演算法

機器學習領域中有很多相似度匹配任務。比如NLP場景中我們會根據一段文字，從海量文字資料集中去匹配相似文字。一個實際的業務就是根據使用者搜尋詞來展示語義相似的廣告，比如使用者在瀏覽器搜尋了”傳奇XX”，終端會展示傳奇遊戲相關的廣告；同樣的CV場景中根據一張圖片，從海量圖片庫去匹配相似圖片。比如要獲取某個人的資訊，可以根據一張採集到的圖片資訊去影象庫中匹配。按照這個邏輯下去，根據一條語音去匹配相似語音，根據一條影片去匹配相似影片等等。

這類任務就是相似度匹配任務，從表面上看是從文字資料集中去找相似的文字，但是對於計算機來說並不能理解文字，需要先將文字資料轉化成計算機可以理解的特徵向量embedding。這裡針對不同模態的資料會使用不同的模型對映成特徵向量，最後實際上去匹配相似的embedding向量。

從海量的高維向量庫進行向量匹配就需要用到大規模檢索演算法。

1.2 如何應用到我們的實際業務場景

我主要從事廣告相關的NLP工作，對應到我們線上業務場景中，可以根據使用者搜尋詞來匹配廣告，渠道可以是瀏覽器、軟體商店等等，廣告可以是app、H5廣告等；另一種業務場景是會根據語義相似度來匹配相似文字，擴充套件語料用於文字分類任務中。這是我們目前線上使用大規模檢索演算法的兩種應用場景。

上一節主要介紹了相似度匹配任務和我們實際業務場景中的應用，本節主要介紹實際專案中完成相似度匹配任務用到的技術，由Facebook維護開源的高效特徵相似度匹配庫faiss。

2.1 什麼是faiss

Faiss全稱是Facebook AISimilarity Search，是

Facebook維護的一個針對海量高維向量庫進行高效可靠檢索的開源庫

。當我們需要從海量文字資料集中進行相似文字檢索時，如果進行暴力檢索，也就是去和向量庫中的每一條樣本進行相似度匹配，那麼檢索的時間非常長，很難滿足線上實時性要求。針對這類問題，faiss提供了一整套大規模資料集檢索解決方案，總的來說主要從兩方面改善暴力檢索存在的問題，

第一方面是提升檢索速度，第二方面是降低記憶體使用

。

2.2 大規模檢索任務流程

基於Faiss構建大規模檢索任務主要包括以下幾個流程：

（1） 獲取候選集庫和待檢索資料

候選集庫就是需要去檢索的資料庫，比如海量的文字資料集、圖片庫等。待檢索資料就是需要去匹配的樣本，比如使用者搜尋query或者圖片等，這裡可以是一條或者多條。通常情況下這裡候選資料集庫和待檢索資料已經編碼成了embedding特徵向量。

（2） 構建並訓練索引

這個流程就是根據候選資料集庫去構建和訓練索引index，通俗的理解就是如何把海量資料集組織起來用於後續檢索。

不同的索引方式會影響檢索效率和記憶體使用

。Faiss支援多種索引，比如最簡單的暴力檢索Flat，還有多種近似查詢方式ANN（Approximate Nearest Neighbor）等等，下面是Faiss支援的部分索引型別：

圖1 faiss支援的部分索引型別

這裡需要說明的是很多索引在被檢索之前需要進行一個“訓練”操作，這個操作就是

根據特徵的分佈進行聚類訓練，從而提升檢索速度

。

（3） 根據索引檢索資料

索引構建和訓練完成之後就可以用於檢索資料了。

2.3 faiss索引型別介紹

faiss支援多種索引，不同型別的索引對於檢索速度和記憶體使用情況影響很大。下面會從簡單到複雜分別介紹幾種重要的索引型別。

2.3.1 最簡單粗暴的索引FLAT

Faiss中最簡單的索引就是暴力檢索Flat，根據計算相似度方法的不同可以分為indexFlatL2和indexFlatIP

。indexFlatL2是基於歐式距離計算相似度，indexFlatIP則是基於內積計算相似度。這兩種索引都屬於暴力檢索，比較簡單，也不需要訓練流程，因為不需要根據特徵的分佈進行聚類操作。

Flat索引的優點在於準確率最高，因為需要和候選資料集中的所有資料進行相似度計算，所以是真正的

精確檢索

。而Falt索引的缺點也很明顯，Flat索引會將全部的候選資料集載入到記憶體中進行儲存，所以當候選資料集很大的時候會佔用很大的記憶體，同時需要和候選資料集中所有的資料計算相似度，所以檢索速度是最慢的。

2.3.2 使用記憶體更少的索引PQ

因為Flat索引會將全部的候選資料集載入到記憶體中進行儲存，所以當候選資料集很大的時候會佔用很大的記憶體。如何降低記憶體使用？這裡就需要用到PQ（Product Quantizer）索引。下面我們透過NLP的一個實際業務來講解PQ索引是如何降低記憶體使用的。之前講過我們會根據使用者搜尋來匹配對應廣告，比如使用者搜尋“傳奇XX”，我們則會返回傳奇遊戲廣告，這裡就是基於語義相似度來完成。下面詳細說明如何透過PQ索引來減少記憶體：

首先我們會將文字透過BERT模型編碼成768維度的向量。假如有1億條廣告，向量是float型別，如果使用Flat索引那麼我們的候選資料集庫就變成了1億X768維的向量矩陣，需要佔用286G記憶體；

然後使用PQ索引則會將每個樣本拆分成6個子矩陣，也就是768=128X6。這裡子矩陣的個數可靈活設定，子矩陣個數越少，壓縮越大，記憶體降低越多，準確率也會越低；

接著在每個子矩陣上進行聚類演算法，設定k=256，則每個子矩陣上會得到256個質心。

設定k為256的原因是每個子矩陣可以透過256個質心代表，而256個質心可以透過一個位元組表示

，2的8次方等於256；

最後透過PQ索引操作之後記憶體使用則大大降低，相當於原來需要286G=（1億X768X4）/（1024X1024X1024），現在僅需要0。56G=（1億X6X1）/（1024X1024X1024），記憶體佔用僅為原來的1/512。從單條樣本佔用記憶體的角度來看就是原來一條樣本需要768X4位元組，現在把一條樣本拆分到6個子矩陣中，並且每個子矩陣透過1個位元組來表示，就變成了6X1位元組。

下面是透過PQ減少記憶體使用的說明圖：

圖2 PQ減少記憶體使用說明

和Flat索引相比，

PQ索引則屬於近似查詢方法

，因為每個樣本相當於被壓縮了，所以記憶體使用大大降低。但是也正因為樣本被壓縮了，所以計算相似度時準確率有一定下降。需要注意的是因為需要進行聚類操作，所以構建索引的時候需要進行訓練。

2.3.3 檢索速度更快的索引IVF

上面

PQ索引透過壓縮樣本使得記憶體佔用大大降低，主要用於降低記憶體佔用，雖然可以一定程度上提升檢索速度，但還是需要和候選資料集庫中的全部資料進行相似度計算

。一個可行的提升檢索速度的方法是縮小檢索範圍，只和候選資料集庫中的部分資料集進行相似度計算。就拿hive表來舉例，當有一張表資料量級非常大的時候，我們可以把它做成分割槽表，這樣檢索資料的時候可以根據一定的“線索”只查詢部分分割槽的資料就可以達到提升檢索速度的效果了。透過這種方式可以將檢索全量資料變成檢索部分資料了，可以大大提升檢索效率。這種方式就是倒排索引IVF（Inverted File System）的核心思路。不管是Flat還是PQ都需要和候選資料集庫中的所有樣本進行相似度計算，如果可以減少搜尋量，那麼檢索速度則會快速提升。IVF索引就是將候選資料集庫進行聚類操作劃分成多個分割槽，當需要檢索資料時只需要檢索部分分割槽資料就可以了。

IVF索引核心是透過減少搜尋資料量級從而提升檢索速度，和PQ一樣都只能返回近似準確的結果

。假如把候選資料集劃分成100個“分割槽”，我們設定搜尋的區域為top10分割槽，當正確的結果在第11分割槽的時候就會導致我們無法檢索到正確的結果。這也是IVF只能返回近似準確結果的原因。

IVF是可以和PQ組合使用的，相當於壓縮了樣本，同時還減少了搜尋範圍，不僅減少了記憶體時候，還提升了檢索速度，這就是我們經常使用的IndexIVFPQ索引

。

2.3.4 基於圖索引HNSW

除了PQ索引和IVF索引，實際業務中比較常用的還有基於圖的HNSW（Hierarchcal Navigable Small World graphs）索引。這塊後續我會專門寫一篇文章詳細介紹HNSW圖檢索演算法。

2.4 各種索引優缺點對比

這裡分享一張組裡小夥伴總結的faiss實驗結論：

圖3 faiss實驗結果圖

實驗設定候選資料集為100W，檢索top50個詞。

下面分別從檢索的準確率、搜尋時間、索引是否需要訓練和是否支援GPU來對比不同索引

：

從檢索結果的準確率來看，FlatL2和FlatIP效果是最好的，因為是真正的精確檢索，相當於無損檢索了全量候選資料集。接下來是HNSW和PQ，PQ索引也會檢索全量候選資料集，但是對樣本有壓縮，所以準確率略微下降。然後是IVFPQ索引，因為使用了倒排索引，只會檢索部分候選資料集，所以準確率進一步下降。最後是LSH基於敏感雜湊對映的方式；

從搜尋時間來看，FlatL2、FlatIP和PQ應該是最慢的，因為需要檢索全部候選資料集。區別在於FlatL2和FlatIP中樣本沒有壓縮，PQ對樣本進行了壓縮。接下來是LSH索引，搜尋時間有一定提升。搜尋最快的是HNSW索引和IVFPQ索引。IVFPQ因為使用倒排索引，大大減少了搜尋的資料量級，所以搜尋速度有很大提升。HNSW是基於圖的檢索方式，檢索速度也很快；

從索引是否需要訓練來看，因為PQ和IVF需要進行聚類操作，所以這兩類索引需要進行訓練，其他索引則不需要；

從索引是否支援GPU來看，Flat、PQ和IVF均支援GPU訓練和檢索，可以大大提升索引構建和檢索速度。

有點遺憾的是HNSW不支援GPU

。

2.5 線上構建索引經驗分享

上面也介紹了各種索引的優缺點，其實主要是檢索準確率和檢索速度之間的博弈。如果你需要最好的搜尋準確率，候選資料集不是很大，並且實時性要求不高，那麼Flat索引搜尋結果是最好的；如果你需要很高的實時性，那麼最好使用近似檢索演算法，IVF、HNSW等都行；如果你的記憶體比較小，那麼PQ索引則可以大大減少記憶體使用。

整體來看檢索準確率和檢索速度都比較好的是HNSW和IVFPQ索引，如果有GPU加持那麼IVFPQ可能更好

。我們線上也主要使用這兩種索引。

實際業務中具體使用哪種索引取決於你的應用場景，分別從記憶體使用、檢索速度、檢索準確率、是否支援GPU、是否支援增量資料等各個方面來考慮選擇最合適的索引型別

。只要瞭解了各種索引的原理，那麼選擇哪種型別的索引則簡單了很多。

上面主要從理論的角度學習了faiss，這裡給出一個非常簡單faiss程式碼實踐，幫助小夥伴入門，下面是基於faiss構建大規模檢索任務的程式碼例項：

圖4 基於faiss構建大規模檢索任務的程式碼例項

針對實際業務場景，比如根據使用者搜尋召回對應廣告，主要是利用simbert模型將文字根據語義相似度編碼成768維度向量，然後就可以利用上述faiss程式碼構建索引並檢索資料了。

本篇主要介紹實際廣告搜尋業務中經常使用的大規模檢索利器Faiss。首先是背景介紹，主要講了相似度匹配任務和大規模檢索演算法以及如何應用到我們的實際業務場景；然後重點介紹了faiss，包括什麼是faiss、大規模檢索任務流程、faiss索引型別介紹、各種索引優缺點對比以及線上構建索引經驗分享；最後專案實踐了faiss。希望對在海量高維向量空間進行大規模檢索任務感興趣的小夥伴有所幫助。

［1］ FAISS專案：

https：//

github。com/facebookrese

arch/faiss/wiki

最新最全的文章請關注我的微信公眾號或者知乎專欄：資料拾光者。

碼字不易，歡迎小夥伴們點贊和分享。