每逢碰到這個ANN的簡稱，小白菜總是想到Artificial Neural Network人工神經網絡，不過這里要展開的ANN并不是Artificial Neural Network，而是已被小白菜之前寫過很多次的Approximate Nearest Neighbor搜索。雖然讀書的那會兒，這一塊的工作專注得比較多，比如哈希，也整理過一個像模像樣的工具包hashing-baseline-for-image-retrieval，以及包括KD樹、PQ乘積量化等近似最近鄰搜索，但這些東西放在今天小白菜的知識體系里來看，依然自以為還非常的散亂。所以借再次有專研的機會之際，再做一次整理，完善自己在索引這方面的知識體系。

在具體到不同類的索引方法分類前，小白菜以為，從宏觀上對ANN有下面的認知顯得很有必要：brute-force搜索的方式是在全空間進行搜索，為了加快查找的速度，幾乎所有的ANN方法都是通過對全空間分割，將其分割成很多小的子空間，在搜索的時候，通過某種方式，快速鎖定在某一（幾）子空間，然后在該（幾個）子空間里做遍歷。可以看到，正是因為縮減了遍歷的空間大小范圍，從而使得ANN能夠處理大規模數據的索引。

根據小白菜現有的對ANN的掌握，可以將ANN的方法分為三大類：基于樹的方法、哈希方法、矢量量化方法。這三種方法里面，著重總結典型方法，其中由以哈希方法、矢量量化方法為主。

基于樹的方法

幾乎所有的ANN方法都是對全空間的劃分，所以基于樹的方法也不例外?；跇涞姆椒ú捎?strong>樹這種數據結構的方法來表達對全空間的劃分，其中又以KD樹最為經典，下面分別對KD樹和Annoy進行簡單介紹。

KD樹

下面左圖是KD樹對全空間的劃分過程，以及用樹這種數據結構來表達的一個過程。

對KD樹選擇從哪一維度進行開始劃分的標準，采用的是求每一個維度的方差，然后選擇方差最大的那個維度開始劃分。這里有一個比較有意思的問題是：為何要選擇方差作為維度劃分選取的標準？我們都知道，方差的大小可以反映數據的波動性。方差大表示數據波動性越大，選擇方差最大的開始劃分空間，可以使得所需的劃分面數目最小，反映到樹數據結構上，可以使得我們構建的KD樹的樹深度盡可能的小。為了更進一步加深對這一點的認識，可以以一個簡單的示例圖說明：

假設不以方差最大的x軸為劃分面(x_var = 16.25)，而是以y軸(y_var = 0.0)軸為劃分面，如圖中虛線所示，可以看到，該劃分使得圖中的四個點都落入在同一個子空間中，從而使得該劃分成為一個無效的劃分，體現在以樹結構上，就是多了一層無用的樹深度。而以x軸為初始劃分則不同(圖像實線所示)，以x軸為初始劃分可以得到數據能夠比較均勻的散布在左右兩個子空間中，從而使得整體的查找時間能夠最短。注意，在實際的kd樹劃分的時候，并不是圖中虛線所示，而是選取中值最近的點。上面示意圖構建的具體kd樹如下所示：

In [9]: kdtree.visualize(tree)(9, 4)(2, 4) (10, 4)(1, 4)

一般而言，在空間維度比較低的時候，KD樹是比較高效的，當空間維度較高時，可以采用下面的哈希方法或者矢量量化方法。

kd-trees are not suitable for efficiently finding the nearest neighbour in high dimensional spaces.
In very high dimensional spaces, the curse of dimensionality causes the algorithm to need to visit many more branches than in lower dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points.

Annoy

Annoy是Erik Bernhardsson寫的一個以樹為數據結構的近似最近鄰搜索庫，并用在Spotify的推薦系統中。Annoy的核心是不斷用選取的兩個質心的法平面對空間進行分割，最終將每一個區分的子空間里面的樣本數據限制在K以內。對于待插入的樣本xixi，從根節點依次使用法向量跟xixi做內積運算，從而判斷使用法平面的哪一邊（左子樹or右子樹）。對于查詢向量qiqi，采用同樣的方式（在樹結構上體現為從根節點向葉子節點遞歸遍歷），即可定位到跟qiqi在同一個子空間或者鄰近的子空間的樣本，這些樣本即為qiqi近鄰。

為了提高查詢的召回，Annoy采用建立多棵樹的方式，這種做法是一種非常常見的做法，比如NV-tree也采用這種方式，哈希方法采用多表的哈希方法。

值得注意的是，Annoy如果不保存原始特征，則Annoy只能返回查詢的k個近鄰，至于這k個里面的排序順序是怎么樣的，它是不知道的，如果需要知道，需要對這k個返回的結果，獲取原始特征，再計算各自的相似度，排序一下即可得到這k個結果的排序。

根據Annoy的定義的節點數據結構，如下：

struct ANNOY_NODE_ATTRIBUTE Node { S n_descendants; union {S children[2]; // Will possibly store more than 2T norm; }; T dot_factor; T v[1]; // We let this one overflow intentionally. Need to allocate at least 1 to make GCC happy };

其中T v[1]保存原始特征，保存原始的特征的壞處是造成占用內存過大，索引文件過大。

哈希方法

哈希，顧名思義，就是將連續的實值散列化為0、1的離散值。在散列化的過程中，對散列化函數(也就是哈希函數)有一定的要求。根據學習的策略，可以將哈希方法分為無監督、有監督和半監督三種類型。在評估某種哈希方法用于圖像檢索的檢索精度時，可以使用knn得到的近鄰作為ground truth，也可以使用樣本自身的類別作為ground truth。所以在實際評估準確度的時候，根據ground truth的定義，這里面是有一點小的trick的。通常對于無監督的哈希圖像檢索方法，由于我們使用的都是未標記的數據樣本，所以我們會很自然的采用knn得到的近鄰作為ground truth，但是對于圖像檢索的這一任務時，在對哈希函數的構造過程中，通常會有“相似的樣本經編碼后距離盡可能的近，不相似的樣本編碼后則盡可能的遠”這一基本要求，這里講到的相似，指語義的相似，因而你會發現，編碼的基本要求放在無監督哈希方法里，似乎與采用knn得到的近鄰作為ground truth的評價方式有些南轅北轍。對無監督哈希方法的ground truth一點小的疑惑在小白菜讀書的時候就心存這樣的困惑，一直懸而未解。當然，在做無監督的圖像哈希方法，采用樣本自身的類別作為ground truth是毋庸置疑的。

小白菜讀書那會兒，研究了很多的哈希圖像檢索方法（見hashing-baseline-for-image-retrieval），有時候總會給一些工程實踐上的錯覺（在今天看來是這樣的），即新論文里的方法遠遠碾壓經典的方法，那是不是在實際中這些方法就很work很好使。實踐的經歷告訴小白菜，還是經典的東西更靠譜，不是因為新的方法不好，而是新的事物需要經過時間的沉淀與優化。

所以，這里不會對近兩年的哈希方法做鋪陳，而是聊一聊工程中在要使用到哈希方法的場景下一般都會選用的局部敏感哈希（Local Sensitive Hashing, LSH）。

Local Sensitive Hashing

關于LSH的介紹，小白菜以為，Locality-Sensitive Hashing: a Primer這個講解得極好，推薦一讀。下面是小白菜結合自己的理解，提煉的一些在小白菜看來需要重點理解的知識（附上LSH劃分空間示意圖，在進行理解的時候可以參照改圖）。

局部敏感是啥？

當一個函數（或者更準確的說，哈希函數家族）具有如下屬性的時候，我們說該哈希函數是局部敏感的：相近的樣本點對比相遠的樣本點對更容易發生碰撞。

用哈希為什么可以加速查找？

對于brute force搜索，需要遍歷數據集中的所有點，而使用哈希，我們首先找到查詢樣本落入在哪個cell(即所謂的桶)中，如果空間的劃分是在我們想要的相似性度量下進行分割的，則查詢樣本的最近鄰將極有可能落在查詢樣本的cell中，如此我們只需要在當前的cell中遍歷比較，而不用在所有的數據集中進行遍歷。

為什么要用多表哈希？

對于單表哈希，當我們的哈希函數數目K取得太大，查詢樣本與其對應的最近鄰落入同一個桶中的可能性會變得很微弱，針對這個問題，我們可以重復這個過程L次，從而增加最近鄰的召回率。這個重復L次的過程，可以轉化為構建L個哈希表，這樣在給定查詢樣本時，我們可以找到L個哈希桶（每個表找到一個哈希桶），然后我們在這L個哈希表中進行遍歷。這個過程相當于構建了K*L個哈希函數(注意是“相當”，不要做“等價”理解)。

多表哈希中哈希函數數目K和哈希表數目L如何選取？

哈希函數數目K如果設置得過小，會導致每一個哈希桶中容納了太多的數據點，從而增加了查詢響應的時間；而當K設置得過大時，會使得落入每個哈希桶中的數據點變小，而為了增加召回率，我們需要增加L以便構建更多的哈希表，但是哈希表數目的增加會導致更多的內存消耗，并且也使得我們需要計算更多的哈希函數，同樣會增加查詢相應時間。這聽起來非常的不妙，但是在K過大或過小之間仍然可以找到一個比較合理的折中位置。通過選取合理的K和L，我們可以獲得比線性掃描極大的性能提升。

Multiprobe LSH是為了解決什么問題？

多probe LSH主要是為了提高查找準確率而引入的一種策略。首先解釋一下什么是Multiprobe。對于構建的L個哈希表，我們在每一個哈希表中找到查詢樣本落入的哈希桶，然后再在這個哈希桶中做遍歷，而Multiprobe指的是我們不止在查詢樣本所在的哈希桶中遍歷，還會找到其他的一些哈希桶，然后這些找到的T個哈希桶中進行遍歷。這些其他哈希桶的選取準則是：跟查詢樣本所在的哈希桶鄰近的哈希桶，“鄰近”指的是漢明距離度量下的鄰近。

通常，如果不使用Multiprobe，我們需要的哈希表數目L在100到1000之間，在處理大數據集的時候，其空間的消耗會非常的高，幸運地是，因為有了上面的Multiprobe的策略，LSH在任意一個哈希表中查找到最近鄰的概率變得更高，從而使得我們能到減少哈希表的構建數目。

綜上，對于LSH，涉及到的主要的參數有三個：

• K，每一個哈希表的哈希函數（空間劃分）數目
• L，哈希表（每一個哈希表有K個哈希函數）的數目
• T，近鄰哈希桶的數目，即the number of probes

這三個設置參數可以按照如下順序進行：首先，根據可使用的內存大小選取L，然后在K和T之間做出折中：哈希函數數目K越大，相應地，近鄰哈希桶的數目的數目T也應該設置得比較大，反之K越小，L也可以相應的減小。獲取K和L最優值的方式可以按照如下方式進行：對于每個固定的K，如果在查詢樣本集上獲得了我們想要的精度，則此時T的值即為合理的值。在對T進行調參的時候，我們不需要重新構建哈希表，甚至我們還可以采用二分搜索的方式來加快T參數的選取過程。

LSH開源工具包

關于LSH開源工具庫，有很多，這里推薦兩個LSH開源工具包：LSHash和FALCONN, 分別對應于學習和應用場景。

LSHash

LSHash非常適合用來學習，里面實現的是最經典的LSH方法，并且還是單表哈希。哈希函數的系數采用隨機的方式生成，具體代碼如下：

def _generate_uniform_planes(self):""" Generate uniformly distributed hyperplanes and return it as a 2Dnumpy array."""return np.random.randn(self.hash_size, self.input_dim)

hash_size為哈希函數的數目，即前面介紹的K。整個框架，不論是LSH的哈希函數的生成方式，還是LSH做查詢，都極其的中規中矩，所以用來作為了解LSH的過程，再適合不過。如果要在實用中使用LSH，可以使用FALCONN。

FALCONN

FALCONN是經過了極致優化的LSH，其對應的論文為NIPS 2015?Practical and Optimal LSH for Angular Distance，Piotr Indyk系作者之一（Piotr Indyk不知道是誰？E2LSH這個頁面對于看過LSH的應該非常眼熟吧），論文有些晦澀難懂，不過FALCONN工具包卻是極其容易使用的，提供有C++使用的例子random_benchmark.cc以及Python的例子random_benchmark.py，另外文檔非常的詳實，具體可參閱falconn Namespace Reference和falconn module。下面將其Python例子和C++例子中初始化索引以及構建哈希表的部分提取出來，對其中的參數做一下簡要的分析。

Python初始化與構建索引L127：

# Hyperplane hashing params_hp = falconn.LSHConstructionParameters() params_hp.dimension = d params_hp.lsh_family = 'hyperplane' params_hp.distance_function = 'negative_inner_product' params_hp.storage_hash_table = 'flat_hash_table' params_hp.k = 19 params_hp.l = 10 params_hp.num_setup_threads = 0 params_hp.seed = seed ^ 833840234print('Hyperplane hash\n')start = timeit.default_timer() hp_table = falconn.LSHIndex(params_hp) hp_table.setup(data) hp_table.set_num_probes(2464)

C++初始化與構建索引L194:

// Hyperplane hashing LSHConstructionParameters params_hp; params_hp.dimension = d; params_hp.lsh_family = LSHFamily::Hyperplane; params_hp.distance_function = distance_function; params_hp.storage_hash_table = storage_hash_table; params_hp.k = 19; params_hp.l = num_tables; params_hp.num_setup_threads = num_setup_threads; params_hp.seed = seed ^ 833840234;cout << "Hyperplane hash" << endl << endl;Timer hp_construction;unique_ptr<LSHNearestNeighborTable<Vec>> hptable(std::move(construct_table<Vec>(data, params_hp))); hptable->set_num_probes(2464);

可以看到，有3個很重要的參數，分別是k、l和set_num_probes，對應的具體意義前面已經解釋，這里不再贅述。

FALCONN的索引構建過程非?？?#xff0c;百萬量級的數據，維度如果是128維，其構建索引時間大概2-3min的樣子，實時搜索可以做到幾毫秒的響應時間?？傊?#xff0c;這是小白菜見過的構建索引時間最短查詢響應時間也極快的ANN工具庫。

另外談一下數據規模問題。對于小數據集和中型規模的數據集(幾個million-幾十個million)， FALCONN和NMSLIB是一個非常不錯的選擇，如果對于大型規模數據集(幾百個million以上)，基于矢量量化的Faiss是一個明智的選擇。關于這方面的討論，可以參閱小白菜參閱的討論benchmark。

當然，FALCONN還不是很完善，比如對于數據的動態增刪目前還不支持，具體的討論可以參見Add a dynamic LSH table。其實這不是FALCONN獨有的問題，NMSLIB目前也不支持。一般而言，動態的增刪在實際應用場合是一個基本的要求，但是我們應注意到，增刪并不是毫無限制的，在增刪頻繁且持續了一段時間后，這是的數據分布已經不是我們原來建索引的數據分布形式了，我們應該重新構建索引。在這一點上，Faiss支持數據的動態增刪。

對于哈希方法及其典型代表局部敏感哈希，暫時就整理到這里了。下面小白菜對基于矢量量化的方法談一談自己理解。

矢量量化方法

矢量量化方法，即vector quantization，其具體定義為：將一個向量空間中的點用其中的一個有限子集來進行編碼的過程。在矢量量化編碼中，關鍵是碼本的建立和碼字搜索算法。比如常見的聚類算法，就是一種矢量量化方法。而在ANN近似最近鄰搜索中，向量量化方法又以乘積量化(PQ, Product Quantization)最為典型。在之前的博文基于內容的圖像檢索技術的最后，對PQ乘積量化的方法做過簡單的概要。在這一小節里，小白菜結合自己閱讀的論文和代碼對PQ乘積量化、倒排乘積量化(IVFPQ)做一種更加直觀的解釋。

PQ乘積量化

PQ乘積量化的核心思想還是聚類，或者說具體應用到ANN近似最近鄰搜索上，K-Means是PQ乘積量化子空間數目為1的特例。PQ乘積量化生成碼本和量化的過程可以用如下圖示來說明：

在訓練階段，針對N個訓練樣本，假設樣本維度為128維，我們將其切分為4個子空間，則每一個子空間的維度為32維，然后我們在每一個子空間中，對子向量采用K-Means對其進行聚類(圖中示意聚成256類)，這樣每一個子空間都能得到一個碼本。這樣訓練樣本的每個子段，都可以用子空間的聚類中心來近似，對應的編碼即為類中心的ID。如圖所示，通過這樣一種編碼方式，訓練樣本僅使用的很短的一個編碼得以表示，從而達到量化的目的。對于待編碼的樣本，將它進行相同的切分，然后在各個子空間里逐一找到距離它們最近的類中心，然后用類中心的id來表示它們，即完成了待編碼樣本的編碼。

正如前面所說的，在矢量量化編碼中，關鍵是碼本的建立和碼字的搜索算法，在上面，我們得到了建立的碼本以及量化編碼的方式。剩下的重點就是查詢樣本與dataset中的樣本距離如何計算的問題了。

在查詢階段，PQ同樣在計算查詢樣本與dataset中各個樣本的距離，只不過這種距離的計算轉化為間接近似的方法而獲得。PQ乘積量化方法在計算距離的時候，有兩種距離計算方式，一種是對稱距離，另外一種是非對稱距離。非對稱距離的損失小(也就是更接近真實距離)，實際中也經常采用這種距離計算方式。下面過程示意的是查詢樣本來到時，以非對稱距離的方式(紅框標識出來的部分)計算到dataset樣本間的計算示意：

具體地，查詢向量來到時，按訓練樣本生成碼本的過程，將其同樣分成相同的子段，然后在每個子空間中，計算子段到該子空間中所有聚類中心得距離，如圖中所示，可以得到4*256個距離，這里為便于后面的理解說明，小白菜就把這些算好的距離稱作距離池。在計算庫中某個樣本到查詢向量的距離時，比如編碼為(124, 56, 132, 222)這個樣本到查詢向量的距離時，我們分別到距離池中取各個子段對應的距離即可，比如編碼為124這個子段，在第1個算出的256個距離里面把編號為124的那個距離取出來就可，所有子段對應的距離取出來后，將這些子段的距離求和相加，即得到該樣本到查詢樣本間的非對稱距離。所有距離算好后，排序后即得到我們最終想要的結果。

從上面這個過程可以很清楚地看出PQ乘積量化能夠加速索引的原理：即將全樣本的距離計算，轉化為到子空間類中心的距離計算。比如上面所舉的例子，原本brute-force search的方式計算距離的次數隨樣本數目N成線性增長，但是經過PQ編碼后，對于耗時的距離計算，只要計算4*256次，幾乎可以忽略此時間的消耗。另外，從上圖也可以看出，對特征進行編碼后，可以用一個相對比較短的編碼來表示樣本，自然對于內存的消耗要大大小于brute-force search的方式。

在某些特殊的場合，我們總是希望獲得精確的距離，而不是近似的距離，并且我們總是喜歡獲取向量間的余弦相似度（余弦相似度距離范圍在[-1,1]之間，便于設置固定的閾值），針對這種場景，可以針對PQ乘積量化得到的前top@K做一個brute-force search的排序。

倒排乘積量化

倒排PQ乘積量化(IVFPQ)是PQ乘積量化的更進一步加速版。其加速的本質逃不開小白菜在最前面強調的是加速原理：brute-force搜索的方式是在全空間進行搜索，為了加快查找的速度，幾乎所有的ANN方法都是通過對全空間分割，將其分割成很多小的子空間，在搜索的時候，通過某種方式，快速鎖定在某一（幾）子空間，然后在該（幾個）子空間里做遍歷。在上一小節可以看出，PQ乘積量化計算距離的時候，距離雖然已經預先算好了，但是對于每個樣本到查詢樣本的距離，還是得老老實實挨個去求和相加計算距離。但是，實際上我們感興趣的是那些跟查詢樣本相近的樣本（小白菜稱這樣的區域為感興趣區域），也就是說老老實實挨個相加其實做了很多的無用功，如果能夠通過某種手段快速將全局遍歷鎖定為感興趣區域，則可以舍去不必要的全局計算以及排序。倒排PQ乘積量化的”倒排“，正是這樣一種思想的體現，在具體實施手段上，采用的是通過聚類的方式實現感興趣區域的快速定位，在倒排PQ乘積量化中，聚類可以說應用得淋漓盡致。

倒排PQ乘積量化整個過程如下圖所示：

在PQ乘積量化之前，增加了一個粗量化過程。具體地，先對N個訓練樣本采用K-Means進行聚類，這里聚類的數目一般設置得不應過大，一般設置為1024差不多，這種可以以比較快的速度完成聚類過程。得到了聚類中心后，針對每一個樣本x_i，找到其距離最近的類中心c_i后，兩者相減得到樣本x_i的殘差向量(x_i-c_i)，后面剩下的過程，就是針對(x_i-c_i)的PQ乘積量化過程，此過程不再贅述。

在查詢的時候，通過相同的粗量化，可以快速定位到查詢向量屬于哪個c_i（即在哪一個感興趣區域），然后在該感興趣區域按上面所述的PQ乘積量化距離計算方式計算距離。

from:?http://yongyuan.name/blog/ann-search.html?

總結

以上是生活随笔為你收集整理的图像检索：再叙ANN Search的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。