近似最近鄰檢索

  隨着數據科學和人工智能的應用普及，我們對高維向量數據的管理與使用需求越來越大。尤其是更多 ML 算法的提出，everything to embedding 的思想也被人熟知，大量的結構化或非結構化數據的湧入就意味着大量的高維度向量的生成。在這樣的背景下，一個優雅的 ANNS(近似最近鄰搜索) 算法就是很多 AI 應用產品落地過程中所必需的。下面我們將會從幾個問題入手，逐漸地瞭解 ANNS 算法。

1 什麼是近似最近鄰搜索

  顧名思義，ANNS 算法的輸入是目標節點，返回與目標節點最近的 k 個近鄰節點。如下圖所示，把藍色小球作爲目標節點，而我們期望做一次 top 2 近鄰的檢索，那麼算法應當爲我們返回兩個紅色小球。值得一提的是，目前距離度量函數通常選擇 L2 或 Inner-Product。

2 爲什麼需要近似最近鄰搜索

  我們將任何格式的數據映射到向量空間後，近鄰檢索可以用來快速比對每個向量節點。對於用戶來說，這意味着給定一個查詢後，ANNS 算法會快速返回相關結果。下面舉兩個例子，描述一下我們身邊常見的近鄰搜索場景。

 當我們在購物網站瀏覽某款籃球時，根據近鄰檢索算法返回的其他幾類近似產品可能會出現在相關商品推薦板塊。

 當節點之間的關係代表一定的語義特徵時，我們可以通過相似搜索的方法學習到相對於 woman 來說，具有類似 man-king 關係的詞是 queen。

  總結來說，在搜索、推薦等場景下，我們並不需要絕對準確的結果。而是可以選擇犧牲一定的精度，更爲快速的從海量節點中獲取到返回結果。

3 ANNS 算法分類

摘自杭州電子科技大學王夢召同學的分享

        目前，所有的 ANNS 算法可以分爲基於樹、基於哈希、基於量化、基於圖四種方法。基於樹和基於哈希的方法思路比較類似，都是通過查詢一個子集去降低比較計算的次數。基於量化的方法與之不同，通過壓縮編碼的方式，降低距離計算的複雜度，以此來增加查找的效率。以上三種方法均存在一些瓶頸問題。例如，基於樹的算法在標量和低維度的向量數據中表現較好。在百位或者千位維度的向量中，效率會急劇退化，甚至退化成暴力搜索。基於量化和基於哈希的方法均會在一些情況下存在精度天花板。

  而在過去的十年間，基於圖的 ANNS 算法一直是該領域的領先算法。此類算法的提出就是針對近鄰檢索提供有效、高效的解決方案。基於圖做近鄰搜索的主要思路是，通過一個 entry point，不斷訪問鄰居節點進行迭代，逐漸向目標節點進行收斂。這個過程既保證了減少比較的次數，又沒有過多的精度損失。

4 基於圖的 ANNS 算法

  在瞭解了基於圖的 ANNS 算法的優勢和搜索過程後，我們比較關心的是圖是如何形成的？那麼，下面簡單介紹下四種基圖結構，大多數的圖索引算法都是基於這四種基圖演化而來。

Delaunay Graph: 德勞內圖是由德勞內三角剖分算法而來，該算法通過最大化最小角保證了三角形結構的唯一性。每個三角形三個節點的外接圓上和圓內不允許出現其他節點。

Relative Neighborhood Graph:RNG 圖是德勞內圖的子圖結構，相比於德勞內圖，不同的是它需要保證每兩個點形成的 lune 區域內不出現其他節點。

K-Nearest Neighbor Graph:K 近鄰圖是有向圖結構，每個節點與其 K 個距離最近的節點相連。

Minimum Spanning Graph: 最小生成樹保證了圖連通的最小邊個數。

  每種基圖都有其代表性的算法，基於不同的圖結構，每種算法在近鄰召回這一任務上的表現也各不相同。在後面的文章中，我們會更詳細地爲大家介紹每種基圖的特點和一些有代表性的算法。

5 總結與展望

  本篇是 ANNS 算法系列的第一篇文章，主要與大家分享算法中基本的概念。後續的文章將會分爲以下幾個方向:

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UWCWiDBud01CRB9P20Zbvw

猜你喜歡