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

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

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

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

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

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

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