基于量化的近似最近鄰搜索技術研究.pdf

1、最近鄰搜索是機器學習、計算機視覺和信息檢索里一個重要的基礎性問題。然而，在大規(guī)模高維數據環(huán)境下，給定查詢點，找到其精確的最近鄰需要大量的計算及存儲空間。近似最近鄰搜索算法由于其存儲空間少、查找效率高等優(yōu)點引起了人們的廣泛關注。而如何快速、高效、準確地進行近似最近鄰搜索是目前學術研究的一個熱點和難點。
　　一般來說，近似最近鄰搜索的算法在盡可能保證其準確性的情況下主要從兩個方面提高搜索速度。第一個是利用特殊的數據結構來減少查詢點與數

2、據點的比較次數;第二個是利用緊湊碼來加速計算查詢點與數據點之間的距離，比如通過哈希算法或量化算法將數據點映射為緊湊碼。本文主要從第二個方面—基于量化的近似最近鄰搜索算法—研究如何獲得更優(yōu)質的緊湊碼來提高查找準確率和查找效率。
　　本文主要研究內容和創(chuàng)新成果如下:
　　1.針對無監(jiān)督的近似最近鄰搜索，本文提出一種組合量化方法。其主要思想是用若干個子中心點之和作為重構點來近似數據點，其中每個子中心點來自不同的子字典，數據點用這些

3、子中心點在各自子字典中的索引值來表示。同時，我們引入近似正交約束條件，使得計算查詢點與重構點的距離可以用查詢點和這幾個子中心點的距離之和來代替進而加速距離計算。與已有的量化方法的對比實驗結果表明，近似正交的組合量化可以獲得更高的查找準確率。
　　2.本文提出一種稀疏組合量化算法，用以減少組合量化中創(chuàng)建查閱表所需的時間。大規(guī)模數據的近似最近鄰搜索通常結合倒排表進一步加速搜索。而組合量化在對倒排表返回的數據點進行排序的時候，創(chuàng)建查閱表

4、所需的時間變得不可忽視。針對這一問題，本文提出的稀疏組合量化方法，引入了一個稀疏條件，使得重構字典里的每一個子中心點是一個稀疏向量。其好處是，當創(chuàng)建查閱表需要計算查詢點與子中心點的歐氏距離的時候，由于子中心點是一個稀疏向量，可以加速距離計算。在大規(guī)模數據集上的近似最近鄰搜索表明，稀疏組合量化相比較于組合量化，可以獲得更快的查找速度。
　　3.本文提出基于量化的近似最近鄰搜索算法用于跨模態(tài)最近鄰搜索領域中。所謂跨模態(tài)最近鄰搜索，指的

5、是查詢點和數據點來自不同的數據模態(tài)，例如用圖像查詢點去搜索相似的文本數據點，或用文本查詢點去搜索相似的圖像數據點。本文提出的算法只假設一幅圖像和一段文本是一對應的，而不需要已知圖像和文本的類別。該算法首先將來自不同模態(tài)的一對數據映射到同一空間中，之后在這個映射后的空間對不同模態(tài)的數據通過組合量化進行近似，同時使來自不同模態(tài)的一對數據的近似表示盡可能相同。大量的實驗比較表明，本文提出的算法在跨模近似態(tài)最近鄰搜索中可以獲得更高的查找準確率。

6、
　　4.針對有監(jiān)督近似最近鄰搜索，本文提出了一種新的量化方法。不同于無監(jiān)督近似最近鄰搜索，量化算法直接在數據庫上進行量化，本文提出的算法是使數據點首先通過一個線性變換，之后在線性變換后的數據點上進行組合量化。其優(yōu)化的目的不僅要使得量化后的近似表達能準確地代表線性變換后的數據點，同時也使得數據點在線性變換后具有類別可分離性，即相同類別的數據點在線性變換后距離很近，不同類別的數據點在線性變換后的空間內相距很遠。與現有的有監(jiān)督近似最近