最近研究ANN 檢索召回的內容，於是把對於 ANN 的內容整理總結下。由於現在深度學習和神經網絡的火爆，大家一聽到ANN，首先想到的是Artificial Neural Network人工神經網絡，不過這裡的ANN並不是Artificial Neural Network，而是Approximate Nearest Neighbor搜索。
1、概述
2、Ann簡介
3、Ann典型算法
3.1 樹方法： Kd-tree
3.2 樹方法：annoy
3.3 哈希算法
3.4 量化方法
3.5 近鄰圖方法
4、常見的開源檢索
5、Ann算法比較
6、Ann 現狀及未來
1、概述
新聞推薦系統從海量新聞中推薦出你感興趣的新聞，百度從海量的搜索結果中找到最優的結果，短視頻推薦出你每天都停不下來的視頻流，這些裡面都包含有今天要介紹的ANN方法。當然，在現在的檢索系統中，往往是多分支並行觸發的效果，雖然DNN 大行其道，但是 ANN 一直不可或缺。
通用理解上，ANN（Approximate Nearest Neighbor）是在向量空間中搜索向量最近鄰的優化問題。目前業界常用nmslib、Annoy算法作為實現。在實際的工程應用中，ANN是作為一種向量檢索技術應用，用於解決長尾Query召回問題。將一個資訊的ANN 召回系統抽象出來大概是下面的樣子。
2、Ann簡介
Ann（approximate nearest neighbor）是指一系列用於解決最近鄰查找問題的近似算法。最近鄰查找問題，即在給定的向量集合中查找出與目標向量距離最近的N個向量。
比較平凡的方法就是線性查找方法，也就是說每次檢索都會遍歷整個檢索庫，雖然準確率是100%，但是其效率是隨著檢索庫的增加而線性增加的，當檢索庫的大小超過一定閾值之後，每次檢索的時間開銷將會變得巨大，不能忍受。在搜索集小的時候，還可以接受，但是實際中向量集合往往很大，線性查找方法的計算資源消耗較大且耗時較長，在工程上一般都不會採用這種方法。
在 NN 的搜索上，提出了一些樹的方法，比如說 KD-tree，以及進化的 ball-tree，像kd-tree等一些優化方法並沒有提高高維空間裡的搜索效率，效率甚至比線性掃描還要低，導致準確最近鄰搜索難以直接用於實際問題。顧名思義，近似最近鄰搜索找到的向量不要求一定是準確的最近鄰，只要求距離準確的最近鄰很近就可以了，可以看到近似近鄰實際上是效果與性能的折衷。
3、Ann典型算法
最近鄰檢索作為數據檢索中使用最為廣泛的技術一直以來都是研究熱點，由於維度高、數據規模大，直接應用最近鄰方法並不可行，因此，最佳實踐是使用逼近方法搜索最近鄰。目前，近似最近鄰縮短搜索時間有兩類基本方案：第一類是縮短距離計算的時間，例如降維，第二類是減少距離計算的次數。
在工業上，常用的索引方法主要以倒排、PQ及其變種、基於樹的方法（比如KD樹）和哈希（典型代表LSH和ITQ）為主流。如果需要更高的召回率的話，則可能需要基於圖方法的ANN，比如HNSW。
主要分為：
- 樹方法，如 KD-tree，Ball-tree，Annoy
- 哈希方法，如 Local Sensitive Hashing (LSH)
- 矢量量化方法，如 Product Quantization (PQ)
- 近鄰圖方法，如 Hierarchical Navigable Small World (HNSW)
3.1 樹方法： Kd-tree
基於樹的經典實現為kd-tree，通過將空間按維度進行劃分，縮小檢索範圍來加速的方法。適用於空間維度較小的情況。Kd-tree 的方法是：找出數據集中方差最高的維度，利用這個維度的數值將數據劃分為兩個部分，對每個子集重複相同的過程。
Kd-tree 有一些變種，比如隨機 k-d 樹算法建立多棵隨機k-d樹，從具有最高方差的N_d維中隨機選取若干維度，用來做劃分。在對隨機k-d森林進行搜索時候，所有的隨機k-d樹將共享一個優先隊列。
3.2 樹方法：annoy
Annoy是Erik Bernhardsson寫的一個以樹為數據結構的近似最近鄰搜索庫，並用在Spotify的推薦系統中。annoy 算法在工程上應用較廣，annoy 算法的目標是建立一個數據結構能夠在較短的時間內找到任何查詢點的最近點，在精度允許的條件下通過犧牲準確率來換取比暴力搜索要快的多的搜索速度。
Annoy通過建立一個二叉樹來使得每個點查找時間複雜度是O(logn)。隨機選擇兩個點，以這兩個節點為初始中心節點，執行聚類數為2的kmeans過程，最終產生收斂後兩個聚類中心點。這兩個聚類中心點之間連一條線段（灰色短線），建立一條垂直於這條灰線，並且通過灰線中心點的線（黑色粗線）。這條黑色粗線把數據空間分成兩部分。在多維空間的話，這條黑色粗線可以看成等距垂直超平面。
在劃分的子空間內進行不停的遞歸迭代繼續劃分，直到每個子空間最多隻剩下K個數據節點。
通過多次遞歸迭代劃分的話，最終原始數據會形成二叉樹結構。二叉樹底層是葉子節點記錄原始數據節點，其他中間節點記錄的是分割超平面的信息。Annoy建立這樣的二叉樹結構是希望滿足這樣的一個假設:相似的數據節點應該在二叉樹上位置更接近，一個分割超平面不應該把相似的數據節點分在二叉樹的不同分支上。
查找的過程就是不斷看查詢數據節點在分割超平面的哪一邊。從二叉樹索引結構來看，就是從根節點不停的往葉子節點遍歷的過程。通過對二叉樹每個中間節點（分割超平面相關信息）和查詢數據節點進行相關計算來確定二叉樹遍歷過程是往這個中間節點左子節點走還是右子節點走。
3.3 哈希算法
哈希的方法是通過哈希函數把向量變換成0、1二值碼，hash 算法的的主要工作在於 hash 算法的設計上，要求相似的樣本經編碼後距離儘可能的近，不相似的樣本編碼後則儘可能的遠。工程中在要使用到哈希方法的場景下一般都會選用的局部敏感哈希（LSH）。
LSH的工作原理是通過hash函數首先將所有的樣本點映射到不同的桶中，在查詢樣本的最近鄰時，將其做相同的變換，查詢樣本的最近鄰很大概率會在查詢樣本落入相同的桶中，只需要在桶中進行搜索即可，不用在所有數據集中遍歷，進而加速了查找。
使用LSH對海量數據進行最近鄰查找的過程如下：
離線建立索引
<1>選取LSH哈希函數；
<2>根據對查找結果的準確率（即相鄰的數據被查找到的概率）確定hash table的個數L，每個table內的hash functions的個數K，以及跟LSH hash function自身有關的參數；
<3>將所有數據經過LSH hash function哈希到相應的桶內，構成了一個或多個hash table；
在線查找
<1>將查詢數據經過LSH hash function哈希得到相應的桶號；
<2>將桶號中對應的數據取出；（為了保證查找速度，通常只需要取出前2L個數據即可）；
<3>計算查詢數據與這2L個數據之間的相似度或距離，返回最近鄰的數據；
3.4 量化方法
向量量化是通過聚類把向量集聚成若干類，每類裡面的向量用對應的類中心來近似。這樣子，每個向量只需要用其對應的聚類中心的索引ID來表示，其與查詢向量間的距離用其對應的聚類中心與查詢向量間的距離來近似。向量量化帶來了兩項優勢：
（1）向量需要的存儲空間變少了，只需保存對應的聚類中心的ID；
（2）計算時間減少了，只需要通過聚類中心的索引ID來查詢預先計算好的聚類中心與查詢向量的距離表格。
3.5 近鄰圖方法
最近的方法是建立一個圖結構來解決最近鄰問題。點是頂點，將每個點與其他點相連，邊的權重為兩點之間的距離。各種各樣的啟發式策略來找出他們最近的鄰居。這裡介紹使用最廣泛的HNSW（Hierarchical Navigable Small World）。
HNSW是一種基於圖的數據結構。使用貪婪搜索算法的變體進行ANN搜索，每次選擇最接近查詢的未訪問的相鄰元素時，它都會從元素到另一個元素地遍歷整個圖，直到達到停止條件。
要理解 Hierarchical NSW，要先理解 NSW。NSW算法，對於每個新的傳入元素，我們從結構中找到其最近鄰居的集合（近似的 Delaunay 圖）。該集合連接到元素。隨著越來越多的元素被插入到結構中，以前用作短距離邊現在變成長距離邊，形成可導航的小世界。
圓（頂點）是度量空間中的數據，黑邊是近似的 Delaunay 圖，紅邊是用於對數縮放的長距離邊。 箭頭顯示從入口點到查詢的貪心算法的示例路徑（顯示為綠色）
圖中的邊有兩個不同的目的：
- Short-range edges，用作貪婪搜索算法所需的近似 Delaunay 圖。
- Long-range edges，用於貪婪搜索的對數縮放。負責構造圖形的可導航小世界（NSW）屬性。
NSW 中的貪婪搜索
- 算法計算從查詢q到當前頂點的朋友列表的每個頂點的距離，然後選擇具有最小距離的頂點。
- 如果查詢與所選頂點之間的距離小於查詢與當前元素之間的距離，則算法移動到所選頂點，並且它變為新的當前頂點。
- 算法在達到局部最小值時停止：一個頂點，其朋友列表不包含比頂點本身更接近查詢的頂點
Hierarchical Navigable Small World (HNSW)
- 該算法貪婪地遍歷來自上層的元素，直到達到局部最小值。
- 之後，搜索切換到較低層（具有較短 link），從元素重新開始，該元素是前一層中的局部最小值，並且該過程重複。
- 通過採用層狀結構，將邊按特徵半徑進行分層，從而將 NSW 的計算複雜度由多重對數（Polylogarithmic）複雜度降到了對數（logarithmic）複雜度。
4、常見的開源檢索
- AnnoySpotify自家的C++庫（提供Python綁定）。Annoy最突出的特性是支持使用靜態索引文件，這意味著不同進程可以共享索引。code：https://github.com/spotify/annoy
- FLANN加拿大英屬哥倫比亞大學出品的C++庫，提供C、MATLAB、Python、Ruby綁定。flann庫包含基於樹的實現（KD-tree）及哈希方法的實現（LSH）。code：https://github.com/mariusmuja/flann
- scikit-learn知名的Python機器學習庫scikit-learn提供了LSHForest、KDTree、BallTree實現。
- PANNS純Python實現。已“退休”，作者建議使用MRPT。
- NearPy純Python實現。基於局部敏感哈希（Locality-sensitive hashing，簡稱LSH，一種降維方法）。
- KGraphC++庫，提供Python綁定。基於圖（graph）算法。 *NMSLIB (Non-Metric Space Library) C++庫，提供Python綁定，並且支持通過Java或其他任何支持Apache Thrift協議的語言查詢。提供了SWGraph、HNSW、BallTree、MPLSH實現。
- hnswlib（NMSLIB項目的一部分） 相比當前NMSLIB版本，hnswlib內存佔用更少。主要支持HNSW（級聯式圖搜索）。HNSW索引會複製大量內存，不支持範圍檢索。code：https://github.com/searchivarius/nmslib
- RPForest純Python實現。主要特性是不需要在模型中儲存所有索引的向量。
- FALCONN是經過了極致優化的LSH。code：https://github.com/FALCONN-LIB/FALCONN
- FAISSFacebook出品的C++庫，提供可選的GPU支持（基於CUDA）和Python綁定。包含支持搜尋任意大小向量的算法（甚至包括可能無法在RAM中容納的向量）。faiss庫包含線性檢索方法（BLAS庫優化）、哈希方法的實現（LSH）及矢量量化方法的實現（PQ、IVFPQ）。faiss庫的一大優勢是支持索引的動態增刪。 faiss 庫的線性檢索方法利用 blas 庫加速，個人測試在 E5-2620 處理器上 128 維向量可以達到每秒約 1500 萬的檢索速度。 LSH 算法及 IVFPQ 算法在隨機生成（均勻分佈）的數據集上除 top1 外的召回效果不好。 ScalarQuantizer 算法在速度較慢的 cpu 上表現比 FlatL2 好，在較快的 cpu （ E5 2620 2.1GHz ）上不如 FlatL2 ，平均每秒可以檢索 1000 萬數據，準確率可以達到 95% 以上。 IndexPQ 索引性能數據（ E5-2680 v4 2.4GHz 28 核）運行時程序併發會利用滿 cpu 資源。 code ：https://github.com/facebookresearch/faiss/tree/master/demos
- DolphinnPy純Python實現。基於超平面局部敏感哈希算法。
- Datasketch純Python實現。基於MinHash局部敏感哈希算法。
- PyNNDescent純Python實現。基於k-近鄰圖構造（k-neighbor-graph construction）。
- MRPTC++庫，提供Python綁定。基於稀疏隨機投影（sparse random projection）和投票（voting）。
- NGT: C++庫，提供了Python、Go綁定。提供了PANNG實現。
5、Ann算法比較
ann算法 benchmark
https://github.com/erikbern/ann-benchmarks
作者在AWS EC2（c5.4xlarge）上的測試結果，比較算法的性能
glove-100-angular：
sift-128-euclidean
fashion-mnist-784-euclidean
gist-960-euclidean
nytimes-256-angular
glove-25-angular
從以上評測可以看出（越靠上、靠右，成績越好），幾乎在所有數據集上，排名前五的實現為：
- HNSW，比Annoy快10倍。
- KGraph位於第二，和HNSW的差距不算很大。和HNSW一樣，KGraph也是基於圖（graph）的算法。
- SW-graph，源自NWSLIB的另一個基於圖的算法。
- FAISS-IVF，源自Facebook的FAISS。
- Annoy 我們看到，有不少使用局部敏感哈希（LSH）的庫。這些庫的表現都不是很好。
6、Ann 現狀及未來
近些年，詞向量技術（尤其是基於DeepLearning的詞向量訓練技術）取得了長足的進步，業界在檢索、推薦等系統中都大量使用了詞向量技術，詞向量的思路，實質上是將文本映射到較高維度向量空間的向量上，通過向量間的關係來反映文本間的關係。這樣做的一個很大的好處就是我們能夠藉此發現一些隱匿的、深藏在文本背後的某種語義關係，因為我們認為距離相近的向量具有相似的語義。比如，衡量兩段文本的語義相似性，單純從文本層面上想辦法，我們可能通過兩者重疊的term來衡量，但是如果兩段文本分別用了不同的同義詞，則這種方法效果不好（可能要引入同義詞），但是詞向量的方法天然不存在這個問題，如果兩段文本語義相似，則兩者的向量距離就會比較小。
所以，詞向量特別適合解決字面上不相似但語義上相似的問題，舉例：
（1）語義檢索中，解決傳統term倒排命中非0即1的問題，召回語義上相似但看起來命中不好的結果，對傳統倒排召回結果進行補充；
（2）某些推薦應用中，需要將某些長尾的query轉化為語義相近的熱門表達，然後以熱門表達query進行後續的處理。
對於詞向量的匹配、查找類需求，最近鄰查找問題是一個始終繞不過去的問題。
閱讀更多 sandag 的文章
