一文縱覽向量檢索

注：本文部分索引結構示例圖源自https://yongyuan.name/blog/vector-ann-search.html

什么是向量檢索

首先我們了解下什么是向量，所謂向量就是由n個數字（二值向量由n個比特組成）組成的數組，我們稱之為n維向量。而向量檢索就是在一個給定向量數據集中，按照某種度量方式，檢索出與查詢向量相近的K個向量（K-Nearest Neighbor，KNN），但由于KNN計算量過大，我們通常只關注近似近鄰（Approximate Nearest Neighbor，ANN）問題。

向量度量

常見的向量度量有四種：歐式距離、余弦、內積、海明距離

不同的度量方式對應不同的場景，通常歐式距離用于圖片檢索，余弦用于人臉識別，內積多用于推薦，海明距離由于向量比較小，通常用于大規模視頻檢索場景。

有了度量以后，我們通常會用召回率（也通常叫精度）來評估向量檢索的效果，對于給定的向量q，其在數據集上的K近鄰為N，通過檢索召回的K個近鄰集合為M，則

召回越接近100%代表索引效果越好。

向量檢索解決的問題

向量檢索從本質上講，其思維框架和傳統的檢索方法沒有什么區別，后面在講解向量檢索的索引結構部時，體會能更深刻一些。

1.????? 減少候選向量集

和傳統的文本檢索類似，向量檢索也需要某種索引結構來避免在全量的數據上做匹配，傳統文本檢索是通過倒排索引來過濾掉無關文檔，而向量檢索是通過對向量建立索引結構來繞過不相關的向量，本文重點討論相關的向量索引結構。

2.????? 降低單個向量計算的復雜度

傳統文本檢索在排序時通常會采用漏斗模型，上層計算比較輕量，越往下計算越精細，但隨著過濾的進行，需要計算的文檔數也逐級下降，對高維向量而言，單個向量的計算量還是比較重，通常會對向量進行量化，對向量做近似計算，最后在一個很小的數據集上做原始向量的排序。

下面我們圍繞這兩個問題來展開向量檢索的相關討論。

向量檢索索引結構

為向量建立高效的索引結構是向量檢索面對的頭號問題，在開始展開前我們看一個Benchmark項目，這個項目在多個公開的向量數據集對比了相關索引結構的召回性能指標，使我們能夠快速對各種索引結構的性能表現有個直觀的認識。

暴力計算

暴力計算是最簡單但復雜度最高的一種方式，在計算召回的時候，暴力計算的結果是作為答案的基準數據，在人臉識別的場景中經常要求100%的召回率，這種情況下一般直接暴力計算。

基于樹的方法

基于樹的方法有很多種，比較典型的有KDTree、BallTree、VPTree，類比傳統的二叉樹，樹結構無非是在建樹的時候是決定往左還是往右擴展，不同的向量樹索引在于按照什么標準去決策，KDTree（如下圖所示）會選取向量中某個方差最大的維度取中值作為判定標準，也就是以超平面去劃分空間，而BallTree則以球面去劃分空間，VPTree會先選取一個制高點，然后計算每個點和制高點的距離，取距離中值作為判定標準。通常這些方法在檢索的時候都會利用三角形不等式來去除不必要的探索。

基于樹的方法還有很多其他類型，但萬變不離其宗，無非就是按照某個判定標準，對向量空間進行劃分，但不管怎么劃分，由于需要回溯的，都決定了基于樹的方法在性能上要稍遜一籌。

哈希方法

哈希對大家再熟悉不過，向量也可以采用哈希來加速查找，我們這里說的哈希指的是局部敏感哈希（Locality Sensitive Hashing，LSH），不同于傳統哈希盡量不產生碰撞，局部敏感哈希依賴碰撞來查找近鄰。

滿足如下兩個條件的哈希函數稱為（d1,d2,p1,p2）-sensitive：

1.????? 如果d(x,y) <= d1，則h(x) = h(y)的概率至少為p1；

2.????? 如果d(x,y) >= d2，則h(x) = h(y)的概率至少為p2；

上面的表達式用人話來說就是：高維空間的兩點若距離很近，那么設計一種哈希函數對這兩點進行哈希值計算，使得他們哈希值有很大的概率是一樣的，若兩點之間的距離較遠，他們哈希值相同的概率會很小。不同距離度量的哈希函數不同，不是所有距離度量（如內積）都能找到對應局部敏感哈希

基于倒排方法

傳統倒排索引是根據文檔包含某個詞，然后將當前文檔放入改詞的倒排索引中來建立索引結構，那向量是如何建立起倒排索引呢？通過聚類把整個向量空間劃分為K個區域，每個區域用一個中心點C代替，這樣每個向量和所有中心點對比，將自身歸入到距離自己最近的中心點對應的倒排，整個索引結構就建立起來了

另一種基于倒排的索引是BOW，原理大體相同，例如一張圖片會抽取出幾百個局部特征，先對所有的特征聚類，形成中心點，這些中心點作為倒排的基礎，建立索引時，把圖片的每個局部特征歸類到其最近的中心點，建立倒排，檢索時會根據命中的次數來過濾結果。

基于圖的方法

前面介紹的索引結構都可以歸類為基于空間劃分的方法，每個向量只會屬于某個劃分好的一個區域，這些方法最大的的問題是為了提高召回需要考察很大一塊區域的向量，導致計算量激增，那有沒有更好的方法來解決這個問題呢？基于圖的方法就可以比較好的實現這一目標，圖方法最樸素的想法是鄰居的鄰居也可能是鄰居，這樣把最近鄰的查找轉化為圖的遍歷，由于其連通性，可以針對性的考察部分向量而不是按區域來考察，因此可以大幅降低向量的考察范圍。

最近幾年圖方法是向量檢索研究的一個熱點，出現了如KGraph、NSG、HNSW、NGT等一批圖索引方法，但實際上這些圖方法的主要區別在構建過程，不同圖方法采用不同的手段來提升圖的質量，但圖檢索的步驟基本是一致的：a.選好入口點；b.遍歷圖；c.收斂。在不斷實踐中我們觀察到一些特性來評判圖索引質量，指引我們在圖方法改進的方向：

1.????? 鄰居點接近K近鄰

2.????? 鄰居點數量盡可能少，即減少出度

3.????? 盡可能保證圖的連通性，增加入度

下面我們以HNSW為例介紹一下圖方法的原理，之所以選取HNSW在于該方法易于理解，比較容易實現流式索引構建和更新，屬于傳統方法在向量上的完美體現。

HNSW背后其實是跳表在圖上的應用，跳表作為一種簡單高效的索引結構在Redis、LevelDB等系統中獲得廣泛應用，如下圖所示：

第一層上有全量的數據，在上層根據隨機投幣決定，越往上投到的概率越小，投到高層的節點往下都有一條記錄，作為檢索的高速公路快速前進。

HNSW的原理也類似，不同于傳統跳表在每層用鏈表來串聯節點，HNSW在每層都是一個NSW（Navigable Small World Graph），通過圖數據結構組織，上層節點也是通過投幣決定在哪一層，并且它們在下層圖中都有記錄，上層圖可以看做下層圖的一個縮影，檢索時，從上到下，不斷指引檢索過程逐步靠近想要探尋的向量空間。另外在構圖過程中HNSW通過邊的裁剪來保證圖的連通性，這里順便提一下，縱觀多篇圖方法的論文，都從自己的視角表述了邊裁剪方法， 但不管各種方法對裁邊描述的有多酷炫，其方法本質都是一模一樣的，只是視角不一樣而已。

向量量化

前面把主流的向量檢索的索引技術基本都概述了一遍，經過索引結構對考察的向量做了裁剪以后，對高維向量而言，單個的計算量還是很大，有沒有方法來減少計算量呢？量化正是基于這個目的技術，所謂量化是指把一個很大的值空間量化到一個較小的值范圍，舉個簡單的例子，全世界有60多億人口，也就是地球人的表征有60多億種，我們可以把人量化為男人和女人兩種類型，這樣就把一個60多億的空間量化成只有兩個值的范圍。

常用的量化一般包括PQ（及其優化OPQ、LOPQ）和二值兩種。

PQ原理如圖，PQ中的P是乘積的意思，那怎么就冒出個乘積呢？在下圖中一個128維的向量空間在經過PQ處理后，向量空間切分成了4段，每段內由256個中心點來量化表達，因此原始的128維空間現在可以用每段里的中心點組合，也即256 * 256 * 256 * 256種組合來表達，這就是所謂的乘積。

對于二值向量，由于現代CPU都提供了專門的指令，計算海明距離非常快速，在海量的向量檢索中通常會直接生成二值向量，生成二值向量方法常見的有ITQ（Iterative Quantization）、DeepHash等方法。

其他技術

聚類

向量聚類主要指的是K-means系列方法，如經典的K-means、K-means++、K-means#、One pass K-means、YinYang k-means等，在實踐中我們也使用過分層的方法來獲得海量中心點。

內積轉換

前面在哈希章節我們已經看到對內積是沒有辦法找到對應的局部敏感哈希函數，內積也不滿足三角形不等式，因此導致很多索引結構無法直接使用內積作為度量，大多數做法是先對向量做歸一化再檢索，但歸一化會轉換向量空間分布。研究人員通過一個數學觀察發現了一個方法，通過一定規則變換，可以使得內積和歐式能夠實現負相關，如下圖所示：

對向量轉換后，可直接用歐式距離度量方式檢索。

向量檢索發展趨勢

本文開頭我們提到向量檢索的思維框架和傳統檢索沒有什么區別，到目前為止傳統方法應用到向量檢索的紅利也基本吃完。這兩年的一個發展趨勢是各種方法的組合，通過吸收各種方法的長處，來獲得更好的性能、承載更大規模的向量。

量化圖

從Benchmark上我們可以清晰的看到，處在優勢地位的方法基本被圖方法霸屏，同時我們知道量化可以降低單個向量的計算量，因此很自然的一種想法是讓兩者強強聯手，在圖遍歷過程中使用量化計算來加速，這種方法對于在高維度方法上優勢明顯，加速比能達到三倍以上。

圖+倒排

圖的性能雖然卓越，但缺點也非常明顯，為了保證檢索效果，圖上邊的保存消耗大量的存儲

尤其在向量本身很小的二值向量上，這是不能承受之重，另外圖的鄰居本身具有隨機性，對硬件處理向量也非常不利。倒排方式則恰恰相反，索引結構基本不消耗太多空間，但缺點是空間劃分方法容易導致召回率不高，但我們從暴力計算的觀察獲得一些啟發，暴力計算從空間劃分角度有兩種視角：可以將暴力計算看做成把所有向量聚類為一個；也可以將暴力計算看做聚類為N（N為向量數據集的大小）個中心，每個中心點是向量本身。這兩種方法都能100%召回，但他們一個是因為中心點下面的向量太多，另一個因為聚類的中心點太多，而導致計算量不可接受，那我們是否可以找到一個平衡點？適當的中心點數目使得召回和性能取得一個比較好的平衡？圖+倒排方式應運而生，用海量中心點去分割向量空間，圖方法來組織海量中心點。

華為云向量檢索實踐

向量檢索的應用出現了空前的繁榮，華為云搜索服務（Cloud Search Service,CSS）目前已經對外開放向量檢索的能力，我們針對高性能和海量數據兩種典型的場景都提供了解決方案。

實現上我們主要基于圖方法，在裁邊優化，連通性增強，指令加速，多線程處理等方面做了大量增強。對比測試中，我們召回率遠高于Faiss，在高維度數據上差距更為明顯，在同樣召回下，我們性能在SIFT，GIST等公開數據集上是Faiss 2.3倍以上。對比測試采用的是相同的機器，相同的算法。

總結：

本文針對向量檢索要解決的問題，梳理了主流向量檢索相關的技術，分析了向量檢索目前的一個趨勢。在向量檢索的發展歷程中，還有很多相關的方法沒有囊括進來，但萬變不離其宗，這些方法要么還是傳統方法的擴展或者應用三角不等式的優化或者應用層次方法等等。期盼本文能幫助梳理向量檢索的脈絡。

參考文獻：

1.? J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18:509–517,1975

2.? P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proc. of the 4th annual ACM-SIAM Symposium on Discrete Algorithms, pages 311–321, 1993

3.? Liu, T.; Moore, A. & Gray, A. (2006). New Algorithms for Efficient High-Dimensional Nonparametric Classification. Journal of Machine Learning Research.?7: 1135–1158.

4.? P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pages 604–613, Dallas, TX, 1998.

5.? W. Dong, C. Moses, and K. Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pages 577–586. ACM, 2011.

6.? Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR,abs/1603.09320, 2016.

7.? https://arxiv.org/abs/1707.00143

8.? https://yongyuan.name/blog/vector-ann-search.html

9.? A. Shrivastava and P. Li. An improved scheme for asymmetric lsh. Technical report, arXiv:1410.5410, 2014.

10. H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117{128, 2011.

11.https://arxiv.org/abs/1810.07355

搜索引擎 全文檢索

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。