ANNOY & HNSW

發布時間：2023-06-15 11:47:25

ANNOY我們之前已經介紹了IVF的ANN檢索算法，核心思路就是對全局的向量做聚類，然后在搜索的過程中只對特定的聚類簇中包含的特征向量

ANNOY

我們之前已經介紹了IVF的ANN檢索算法，核心思路就是對全局的向量做聚類，然后在搜索的過程中只對特定的聚類簇中包含的特征向量做檢索，ANNOY，全名Approximate Nearest Neighbors Oh Yeah，也是使用類似的思路，不過和IVF相比，采用類似二叉樹的方式進行檢索，整個算法表達上更加樸素清晰，具體可以參考以下這篇鏈接，實在是筆者看到過的對ANNOY解釋的最為清晰的一篇文章，筆者在此僅做以上介紹和對比，就不造重復的輪子了。

Annoy搜索算法(Approximate Nearest Neighbors Oh Yeah)

SW

HNSW（Hierarchical Navigable Small Worlds）是一種基于圖的ANN搜索算法，談到HNSW，我們就不得不從從SW說起，一種通俗的分類方式，將圖分為三種：

正則圖（Regular Graph）：指各頂點的度均相同的無向簡單圖
隨機圖（Random Graph）：指各頂點隨機進行連接的無向簡單圖
小世界（Small World）

這里我們先忽略小世界的定義，關注正則圖與隨機圖之間的區別，我們使用以下代碼來模擬正則圖和隨機圖

# Consider the scenario of 99 verticesnnum_vertex = 99nn# predefined reg_degree as 4nreg_degree = 4nn# generate a regular graphndef Gen_Reg_Graph(num_vertex, reg_degree):n tmp_dict_reg = {}n inf_big = 999nn for i in range(num_vertex):n tmp = []n for j in range(reg_degree // 2):n tmp.append((i + j + 1)% num_vertex)n tmp.append((i - j - 1)% num_vertex)n tmp_dict_reg[i] = tmpn n reg_graph = np.ones((num_vertex, num_vertex)) * inf_bign for i in range(num_vertex):n for j in tmp_dict_reg[i]:n reg_graph[i][j] = 1n # keep diaganol as 0n reg_graph[i][i] = 0n return reg_graphnnreg_graph = Gen_Reg_Graph(num_vertex, reg_degree)nprint(reg_graph)nn# generate a random graphndef Gen_Rnd_Graph(num_vertex):n tmp_dict_reg = {}n inf_big = 999n rnd_graph = np.ones((num_vertex, num_vertex)) * inf_bign # randomly set two vertices connectedn for i in range(num_vertex):n for j in range(num_vertex):n if random.randint(1,20) % 17 == 0:n rnd_graph[i][j] = 1n rnd_graph[j][i] = 1n # keep diaganol as 0n rnd_graph[i][i] = 0n return rnd_graphnnrnd_graph = Gen_Rnd_Graph(num_vertex)nprint(rnd_graph)nn# Dijkstrandef dijkstra(start, graph):n passed = [start]n nopass = [x for x in range(graph.shape[0]) if x != start]n dis = graph[start]n n while len(nopass):n idx = nopass[0]n for i in nopass:n if dis[i] < dis[idx]: idx = inn nopass.remove(idx)n passed.append(idx)nn for i in nopass:n if dis[idx] + graph[idx][i] < dis[i]: dis[i] = dis[idx] + graph[idx][i]n return disnndis_reg = dijkstra(0, reg_graph)nprint("Distance in regular graph {}".format(dis_reg))ndis_rnd = dijkstra(0, rnd_graph)nprint("Distance in random graph {}".format(dis_rnd))

我們首先通過以上代碼生成了一個正則圖和一個隨機圖，并通過dijkstra（隨手扒了一個dijktra的python實現）來觀察其中一個點到其他點的距離，最終得到以下輸出（這里的distance值可以理解為從一個頂點到另一個頂點的“跳躍次數”）

Distance in regular graph [ 0. 1. 1. 2. 2. 3. 3. 4. 4. 5. 5. 6. 6. 7. 7.n 8. 8. 9. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 14. 15.n 15. 16. 16. 17. 17. 18. 18. 19. 19. 20. 20. 21. 21. 22. 22.n 23. 23. 24. 24. 25. 25. 24. 24. 23. 23. 22. 22. 21. 21. 20.n 20. 19. 19. 18. 18. 17. 17. 16. 16. 15. 15. 14. 14. 13. 13.n 12. 12. 11. 11. 10. 10. 9. 9. 8. 8. 7. 7. 6. 6. 5.n 5. 4. 4. 3. 3. 2. 2. 1. 1.]nDistance in random graph [ 0. 3. 1. 2. 3. 2. 2. 3. 3. 2. 1. 1. 2. 1. 1. 2. 3. 3.n 3. 3. 2. 2. 3. 3. 1. 2. 2. 2. 2. 2. 3. 2. 2. 2. 2. 1.n 2. 2. 2. 2. 2. 3. 2. 2. 3. 2. 3. 1. 2. 2. 3. 2. 2. 2.n 3. 3. 3. 2. 2. 2. 2. 2. 3. 2. 2. 2. 3. 2. 2. 3. 2. 2.n 3. 3. 2. 3. 2. 2. 2. 3. 2. 3. 2. 3. 2. 2. 2. 2. 2. 3.n 1. 2. 3. 3. 3. 2. 3. 3. 3.]

不難看出，在正則圖中，從一個點到另一個點的搜索次數在特定情況下要遠遠高于隨機圖（當然這和我們在隨機圖中設計的連通的概率也有關系），通常情況下，正則圖中的頂點的路徑更長，但是同時更聚合，也就是空間中距離相近的兩個點是互相連接的。而隨機圖中的頂點盡管路徑更短，但是幾乎是完全不聚合的，也就是很難保證在空間中相鄰的兩個點在圖中是相連接的，故而很難在實際的向量檢索、ANN等場景中使用隨機圖。

而Small World則基于兩者之間，在原本的正則圖中類似“擊鼓傳花”的這個搜索的過程中，偶然的可以在兩個相去甚遠的點中來個“長傳”，這可以極大的加速了整個檢索的步驟。

# predefined reg_degree as 4nreg_degree = 4nndef Gen_Reg_Graph(num_vertex, reg_degree):n tmp_dict_reg = {}n inf_big = 999nn for i in range(num_vertex):n tmp = []n for j in range(reg_degree // 2):n tmp.append((i + j + 1)% num_vertex)n tmp.append((i - j - 1)% num_vertex)n tmp_dict_reg[i] = tmpn n sw_graph = np.ones((num_vertex, num_vertex)) * inf_bign for i in range(num_vertex):n for j in tmp_dict_reg[i]:n sw_graph[i][j] = 1n # keep diaganol as 0n sw_graph[i][i] = 0n n # randomly set 2 express wayn for i in range(2):n x = random.randint(0,99)n y = random.randint(0,99)n sw_graph[x][y] = 1n sw_graph[y][x] = 1n return sw_graphnnsw_graph = Gen_Reg_Graph(num_vertex, reg_degree)nprint(sw_graph)ndis_sw = dijkstra(0, sw_graph)nprint("Distance in random graph {}".format(dis_sw))

輸出為

Distance in small world graph [ 0. 1. 1. 2. 2. 3. 3. 4. 4. 5. 5. 6. 6. 7. 7.n 8. 8. 9. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 14. 15.n 15. 16. 16. 17. 17. 16. 16. 15. 15. 14. 14. 13. 14. 14. 15.n 15. 16. 16. 17. 16. 16. 15. 15. 14. 14. 13. 13. 12. 12. 11.n 11. 10. 10. 9. 10. 10. 11. 11. 12. 12. 13. 13. 14. 13. 13.n 12. 12. 11. 11. 10. 10. 9. 9. 8. 8. 7. 7. 6. 6. 5.n 5. 4. 4. 3. 3. 2. 2. 1. 1.]

NSW

我們回到上面正則圖的概念，根據給定的頂點（在實際的檢索場景中，常常表現為多個特征向量），我們總是可以通過德勞內三角形的分割方式，將不同的頂點進行聯通，然后在圖中隨機創建Expressway mechanism（上面說的“長傳”的學名），也就是建立比較遙遠的兩個點間的連接。但是這種方法在實際場景中是行不通的，德勞內三角形分割的時間復雜度為，其中d是頂點的維度，在高維的場景中時間復雜度迅速膨脹到極高的規模（鑒于是非多項式時間的，所以大概也可以算是NP問題？）。

而論文中解決這個問題的方式卻實打實的簡單到令人發指，整個NSW圖構建的算法步驟可以用偽代碼描述如下

V: set of verticesnG: inital state of NSW graphnnfor v_i in V:n V.pop(v_i) # 這一步建議隨機在V中選擇v_i特征向量n for v_j in G.find_topk_NN(v_i):n G.connect(v_i, v_j)

對，隨機選擇V中的一個頂點，找到已建立的NSW圖中的topk最近鄰（NN），將其連接，重復這個過程直到V中的所有的點都已經被便利。

為什么按照上面這個過程就可以得到一個很好的NSW圖呢？回想下上面提到的SW具有兩個特征，SW具有正則圖中的局部聚合的特性，但是同時也有隨機圖中的Expressway mechanism，而我們隨機添加頂點的過程中，在算法的早期，因為圖中的點數量較少，所以很容易建立兩個遙遠的點之間的Expressway，而在算法的后期，因為圖中的點數量已經多起來，對于全局的數據空間具有一定的代表性，那么添加的新的點在選取topk的時候，基本上都會選擇到其具備相鄰的點，那么就保證了SW圖中的局部聚合的特性。

跳表

想要更好的理解HNSW，就首先需要理解跳表的原理，跳表是可以理解為一種特殊的鏈表(下圖from百度百科)

可以看到，跳表其實也使用了我們上文中所說的這種Express Mechanism機制，只不過跳表上的Express Mechanism建立在一維空間之中（類似于數軸），同時由多層鏈表進一步加速鏈表上特定元素的搜索過程。

對于一個元素的檢索過程，比如檢索數字3，首先在頂層的鏈表中執行比對，在第一層中發現3比head要大，但是比4要小，那么我們就向下進入第二層鏈表中檢索，以此類推。

HNSW

而HNSW就是在普通的NSW之上，結合跳表的思路來進一步優化檢索的性能（在高層中進行搜索比在底部局部執行搜索的速度要快得多得多）

我們在檢索的過程中，分為兩個不同的階段，分別是建立HNSW圖以及在HNSW圖中進行檢索

建立HNSW圖：INSERT

HNSW圖的建立可以粗略的被偽代碼描述如下（詳細描述請移步論文）

vi: vectex to be insertednep: enter point at first layernhighest_layer: fewest verticesnlowest_layer: all verticesnn# specify a layer to insert vininserted_layer = random_ln_gen(vi)nn# go down to the layer vi is inserted, without building new connections (search process)nfor layer in [highest_layaer:inserted_layer]:n NN = Search_Layer(ep, layer, vi)n ep = Select_New_Ep_From_NN(vi, NN)nn# going down to layer0, building new connections at each layernfor layer in [inserted_layer:lowest_layer]:n NN = Search_Layer(ep, layer, vi)n NiceNN = Select_Neighbors(NN) #對于理解HNSW的過程而言，事實上不需要理解Select_Neighbors也可以n Update_Connections(NiceNN, vi)

執行HNSW中的檢索：SEARCH

執行HNSW中的檢索可以粗略的被偽代碼描述如下（詳細描述請移步論文）

vi: vertex to be searchednep: enter point at first layernn# go down to the layer vi is inserted, without building new connectionsnfor layer in [highest_layaer:lowest_layer]:n NN = Search_Layer(ep, layer, vi)n ep = Select_New_Ep_From_NN(vi, NN)nnFinal_Search(NN)