基于投影殘差量化哈希的近似最近鄰搜索

楊定中，陳心浩

（中南民族大學(xué)實(shí)驗(yàn)教學(xué)中心，武漢430074）

1 概述

大規(guī)模數(shù)據(jù)集的最近鄰搜索（相似度搜索）在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)中有著廣泛應(yīng)用。然而，因?yàn)閿?shù)據(jù)規(guī)模過(guò)大和維數(shù)災(zāi)難問(wèn)題，確切的最近鄰搜索對(duì)于實(shí)時(shí)性較強(qiáng)的應(yīng)用是一個(gè)亟需解決的課題。最近，舍棄有限精度的近似最近鄰搜索引起了研究人員的關(guān)注，解決這一問(wèn)題的經(jīng)典方法來(lái)自基于量化的近似最近鄰搜索方法，該類方法的關(guān)鍵在于利用子量化器的排列組合而構(gòu)建量化器。積量化［1－2］通過(guò)將原始空間拆分成多個(gè)正交子空間，利用子空間的低復(fù)雜度量化器構(gòu)建出原始空間中的高復(fù)雜度量化器，但是積量化方法需要各個(gè)子空間統(tǒng)計(jì)無(wú)關(guān)，否則其正確率會(huì)顯著下降，殘差量化［3－4］則直接在原始高維空間訓(xùn)練量化器，所得量化殘差繼續(xù)訓(xùn)練下一階段子量化器，殘差量化器則為多個(gè)子量化器的組合?；诮M合所表示數(shù)據(jù)的容量成指數(shù)增長(zhǎng)，并在原始數(shù)據(jù)空間中進(jìn)行搜索處理，即使基于倒排索引，其搜索過(guò)程也是費(fèi)時(shí)的。目前，基于哈希的方法因其能在常量時(shí)間能完成搜索已被廣泛應(yīng)用于相似度檢索［5－7］。 已 有 的 哈 希 方 法 一 般 分 為 兩 大 類［8－9］：數(shù)據(jù)無(wú)關(guān)的方法和數(shù)據(jù)相關(guān)的方法。數(shù)據(jù)無(wú)關(guān)方法的一個(gè)代表是隨機(jī)投影殘差量化哈希，如漢明嵌入［10］和局部敏感哈希（Local Sensitive Hashing，LSH）［11－12］。在這類方法中，哈希函數(shù)為獨(dú)立于數(shù)據(jù)集的隨機(jī)投影。理論上，隨機(jī)投影保證了隨著編碼長(zhǎng)度的增加，原始距離或相似性在海明空間漸近式保持。因此，LSH相關(guān)的方法通常需要較長(zhǎng)的編碼而得到較高的精度。然而，長(zhǎng)編碼會(huì)導(dǎo)致低召回率，因?yàn)椋S著編碼長(zhǎng)度的增加，相似數(shù)據(jù)沖突（相似數(shù)據(jù)映射為相近的二進(jìn)制編碼）的概率成指數(shù)下降。所以，與LSH相關(guān)的方法通常采用構(gòu)建多個(gè)哈希表來(lái)確保合理的沖突概率，這樣查詢會(huì)至少在一個(gè)哈希表中與相應(yīng)的近鄰相沖突，直接后果就是明顯增加查詢時(shí)的時(shí)間開銷和內(nèi)存占用。為了生成更緊湊的哈希編碼，研究人員提出了許多數(shù)據(jù)相關(guān)的哈希方法，這類方法從數(shù)據(jù)集中訓(xùn)練哈希函數(shù)。近年來(lái)，一種基于譜圖劃分的哈希函數(shù)引起了注意，如譜哈希（Spectral Hashing，SPH）［13］，其采用一維拉普拉斯算子的簡(jiǎn)單解析特征函數(shù)作為哈希函數(shù)。在譜哈希中，引入2個(gè)重要的約束用于訓(xùn)練二進(jìn)制編碼：（1）每個(gè)哈希位平衡劃分?jǐn)?shù)據(jù)集；（2）不同的哈希位互不相關(guān)。這2個(gè)約束也在其他許多研究中廣泛使用。在文獻(xiàn)［8］中，迭代量化哈希（Iterative Quantization Hashing，ITQ）通過(guò)訓(xùn)練正交旋轉(zhuǎn)矩陣以改進(jìn)初始主成分分析（Principal Component Analysis，PCA）投影矩陣，以最小化數(shù)據(jù)從原始空間映射到漢明空間的量化誤差為目標(biāo)訓(xùn)練哈希函數(shù)。在文獻(xiàn)［14］中，漢明距離被用作原始數(shù)據(jù)空間中的數(shù)據(jù)點(diǎn)之間距離的重建，旨在最小化重建誤差來(lái)訓(xùn)練哈希函數(shù)。PCA哈希［15］采用數(shù)據(jù)的協(xié)方差矩陣最大特征值的特征向量用于生成哈希的投影矩陣，PCA哈希將原始數(shù)據(jù)經(jīng)PCA矩陣投影到低維空間。但是，PCA哈希將二進(jìn)制編碼基于投影后的數(shù)據(jù)會(huì)產(chǎn)生大量投影誤差而導(dǎo)致搜索精度降低。而且，在基于量化的近似最近鄰搜索時(shí)，量化殘差會(huì)直接丟棄，當(dāng)量化碼書較小時(shí)，會(huì)生成較大的量化誤差，極大影響搜索精度?；诖耍疚奶岢鐾队皻埐盍炕?，并結(jié)合PCA哈希和向量量化的思想，將向量投影到低維主空間，并在主空間的各維標(biāo)量上訓(xùn)練碼書，量化后的殘差按維度順序組成新的低維主空間向量，并將其反投影回原始向量空間形成新的高維殘差，通過(guò)對(duì)高維殘差的重復(fù)利用，生成一種多維度哈希函數(shù)。

2 投影殘差量化哈希

2．1 哈希函數(shù)構(gòu)造

投影殘差量化哈希的哈希函數(shù)形式上為一向量量化器，哈希編碼為量化索引。投影殘差量化哈希的量化器由多個(gè)標(biāo)量量化器組成，其生成過(guò)程包括如下多個(gè)階段：對(duì)于給定的訓(xùn)練集v＝｛xi∈RD，1≤i≤N｝，首先用PCA投影陣M1將v投影到低維空間生成低維向量集，如式（1）所示。

對(duì)于數(shù)據(jù)庫(kù)向量和查詢，均可以按式（5）生成相應(yīng)的哈希編碼并進(jìn)行基于漢明距離的快速最近鄰搜索。

投影殘差量化哈希基于各一維數(shù)據(jù)與標(biāo)量類心的最近鄰關(guān)系進(jìn)行哈希編碼，形式上2個(gè)標(biāo)量類心將一維空間劃分為3個(gè)子集，如圖1（a）所示。根據(jù)數(shù)據(jù)與tc之間的大小關(guān)系進(jìn)行哈希編碼，由于tc（tc＝（c0＋c1）／2）的取值來(lái)源于一維數(shù)據(jù)的2個(gè)類心，將tc作為邊界實(shí)現(xiàn)數(shù)據(jù)的有效二分更符合數(shù)據(jù)的實(shí)際分布。如圖1（b）所示，圓點(diǎn)表示數(shù)據(jù)分布，正方形c0，c1分別為聚類類心，正方形tc為類心均值。顯然，將tc而不是中值（第5個(gè)圓點(diǎn)所示數(shù)據(jù)）作為二分邊界更為合理。

圖1 哈希編碼示例

2．2 編碼權(quán)重

在基于哈希進(jìn)行近似最近鄰搜索時(shí)，對(duì)于給定的查詢，直接計(jì)算查詢的哈希編碼與數(shù)據(jù)庫(kù)向量的哈希編碼之間的漢明距離，然后根據(jù)漢明距離按由小到大的順序返回相應(yīng)的數(shù)據(jù)庫(kù)向量作為查詢的近鄰。但是由于哈希編碼和漢明距離的特殊性，通常會(huì)有多個(gè)數(shù)據(jù)庫(kù)向量與查詢具有相同的漢明距離，一般的處理就是將其視為與查詢擁有相同的近鄰關(guān)系，按向量在數(shù)據(jù)庫(kù)出現(xiàn)的先后順序返回給查詢。但實(shí)際情況并非如此，如圖2所示。

圖2 漢明距離排序歧義示例

在圖2中，p1，p2，p3與查詢q的漢明距離都為1，若根據(jù)漢明距離直接返回結(jié)果，則q的近鄰優(yōu)先關(guān)系為p1，p2，p3。但是，從圖2中可以看出，p3離查詢q更近，直接依據(jù)漢明距離返回結(jié)果會(huì)帶來(lái)一定的歧義。此類問(wèn)題一個(gè)有效的方法就是給編碼加上權(quán)重，即使2個(gè)二進(jìn)制編碼串之間的漢明距離相同，但由于各編碼位權(quán)重不同，最終帶權(quán)重的編碼產(chǎn)生的漢明距離大小也會(huì)不同，對(duì)搜索結(jié)果中漢明距離相同的數(shù)據(jù)庫(kù)向量生成新的排序結(jié)果。二進(jìn)制編碼位的權(quán)重取決于其對(duì)應(yīng)的哈希函數(shù)，而哈希函數(shù)的權(quán)重則取決于自身的可區(qū)分性，區(qū)分性強(qiáng)的哈希函數(shù)能以較大概率將相近的數(shù)據(jù)編碼為相同的二進(jìn)制位，如果數(shù)據(jù)分布均勻，方差較小，則相近的數(shù)據(jù)極有可能編碼為相同的0，1位，因此哈希函數(shù)的權(quán)重與數(shù)據(jù)分布的方差直接負(fù)相關(guān)。不僅如此，基于某個(gè)哈希函數(shù)對(duì)數(shù)據(jù)x進(jìn)行哈希編碼時(shí)，若x離哈希函數(shù)的邊界較近，則原本為0的哈希編碼可能由于誤差編碼為1，或者原本為1而編碼為0。由此可見，權(quán)重與數(shù)據(jù)離哈希函數(shù)的閾值所表示的邊界距離應(yīng)有正相關(guān)關(guān)系。

綜上所述，某個(gè)哈希函數(shù)的權(quán)重可以用如下公式表示：

其中，f（x）為x的變化函數(shù)，如投影殘差量化哈希中投影運(yùn)算與取某一維度值的復(fù)合運(yùn)算；ti為類心均值。

3 實(shí)驗(yàn)結(jié)果與分析

3．1 實(shí)驗(yàn)環(huán)境

硬件環(huán)境為Intel Xeon E7520 1．87GHz CPU，32GB內(nèi)存，軟件環(huán)境為linux CentosOS。編程環(huán)境采用Matlab R2011a，用C＋＋加速。搜索性能采用2種方式評(píng)估：（1）Recall＠K，即長(zhǎng)度為K的結(jié)果列表中所含最近鄰占所有最近鄰的比率，K值相同，Recall越高，搜索性能越好；（2）Recall－Precision曲線，曲線下方面積越大，搜索性能越好。實(shí)驗(yàn)測(cè)試了投影殘差量化哈希性能并與主流方法進(jìn)行比較。實(shí)驗(yàn)所用數(shù)據(jù)集為公開發(fā)布的SIFT和GIST數(shù)據(jù)集，其詳細(xì)情況如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3．2 性能分析

投影殘差量化哈希的編碼長(zhǎng)度取決于投影維度d及階段數(shù)L，對(duì)于給定的編碼長(zhǎng)度d×L，d和L有不同組合，實(shí)驗(yàn)首先測(cè)試了不同組合對(duì)搜索性能的影響。

圖3所示為SIFT數(shù)據(jù)集用32 bit二進(jìn)制編碼后的搜索性能，圖例中xy：x為投影維度d，y為階段數(shù)L。從圖3可以看出，在｛132，216，48，84，162，321｝組合下，投影殘差量化哈希的搜索精度基本相同，僅當(dāng)d＝8，L＝4時(shí)，投影殘差量化哈希的搜索性能最優(yōu)，一個(gè)主要的原因是該組合提供了最多的空間劃分。在后續(xù)實(shí)驗(yàn)中，對(duì)不同編碼長(zhǎng)度，d，L均采用空間劃分最大組合。同時(shí)，實(shí)驗(yàn)還測(cè)試了二進(jìn)制編碼權(quán)重對(duì)搜索精度的影響。圖4所示為SIFT數(shù)據(jù)集上編碼長(zhǎng)度分別為32 bit，64 bit，96 bit時(shí)的搜索精度，右上角星號(hào)表示帶權(quán)重的哈希編碼后的搜索精度，當(dāng)編碼長(zhǎng)度為32 bit，K＝5 000時(shí)，帶權(quán)重的PRVQH的召回率由原始的0．625提高到0．665，搜索性能提高了6．4%。當(dāng)編碼長(zhǎng)度為64 bit，K＝5 000時(shí)，帶權(quán)重的PRVQH召回率由原始的0．73提高到0．77，搜索性能提高了5．48%，當(dāng)編碼長(zhǎng)度為96 bit，K＝5 000時(shí)，帶權(quán)重的PRVQH召回率由原始的0．85提高到0．89，搜索性能提高了4．71%。由此可見，帶權(quán)重的哈希編碼重排搜索結(jié)果后，搜索性能會(huì)有較大的提升。

3．3 與主流方法的性能比較

將 本 文 方 法 與 ITQ［8］，SPH［13］，BRE［14］和PCAH［15］主流哈希方法進(jìn)行性能比較，結(jié)果如圖5、圖6所示。圖5為SIFT數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，編碼長(zhǎng)度分別為32bit，64bit和96bit。從圖5（a）可以看出，在相同編碼長(zhǎng)度（32bit）下，本文所提出的PRVQH方法搜索性能明顯好于其他主流方法，在64bit（圖5（b）所示），96bit（圖5（c）所示）情形下，PRVQH的搜索性能同樣高于其他主流哈希方法。圖6為GIST數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，從中可以看出，PRVQH相比于其他主流哈希方法表現(xiàn)出同樣優(yōu)越的搜索性能。由此可見，在各種編碼長(zhǎng)度的情況下，本文所提出的投影殘差量化哈希搜索性能都優(yōu)于其他主流方法。

圖5 SIFT數(shù)據(jù)集上各方法的性能比較

圖6 GIST數(shù)據(jù)集上各方法的性能比較

4 結(jié)束語(yǔ)

隨著互聯(lián)網(wǎng)及多媒體技術(shù)的發(fā)展，基于內(nèi)容的相似度搜索逐漸成為研究熱點(diǎn)。由于存儲(chǔ)空間小，搜索速度快，二進(jìn)制哈希不斷吸引研究人員的廣泛關(guān)注。本文提出的投影殘差量化哈希，采用多階段策略，結(jié)合反投影和殘差量化的思想，有效減少了量化過(guò)程中的殘差，在搜索時(shí)，采用基于帶權(quán)重的漢明距離進(jìn)一步提高了搜索性能，與其他主流哈希方法比較的實(shí)驗(yàn)結(jié)果也驗(yàn)證了本文方法的先進(jìn)性。在后續(xù)工作中，將結(jié)合實(shí)際數(shù)據(jù)分布，研究更為合理的編碼權(quán)重，進(jìn)一步提高基于二進(jìn)制哈希的搜索精度。

［1］Jegou H，Douze M，Schmid C．Product Quantization for Nearest Neighbor Search［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）：117－128．

［2］Kalantidis Y，Avrithis Y．Locally Optimized Product Quantization for Approximate Nearest Neighbor Search［C］／／Proceedings of IEEE Conference on Computer Vision and Pattern Recognition．Washington D．C．，USA：IEEE Press，2014：2329－2336．

［3］Chen Yongjian，Guan Tao，Wang Cheng．Approximate Nearest Neighbor Search by Residual Vector Quantization［J］．Sensors，2010，10（12）：11259－11273．

［4］Ai Liefu，Yu Junqing，Guan Tao，et al．Efficient Approximate Nearest Neighbor Search by Optimized Residual Vector Quantization［C］／／Proceedings of IEEE Conference on Content－based Multimedia Indexing．Washington D．C．，USA：IEEE Press，2014：1－4．

［5］Zhou Wengang，Lu Yijuan，Li Houqiang，et al．Spatial Coding for Large Scale Partial－duplicate Web Image Search［C］／／Proceedings of International Conference on Multimedia．New York，USA：ACM Press，2010：511－520．

［6］Song Jingkuan，Yang Yi，Huang Zi，et al．Multiple Feature Hashing for Real－time Large Scale Nearduplicate Video Retrieval［C］／／Proceedings of the 19th ACM International Conference on Multimedia．New York，USA：ACM Press，2011：423－432．

［7］Zhou Wenqang，Lu Yijuan，Li Houqiang，et al．Scalar Quantization for Large Scale Image Search［C］／／Proceedings of the 20th ACM International Conference on Multimedia．New York，USA：ACM Press，2012：169－178．

［8］Gong Yunchao，Lazebnik S，Gordo A，et al．Iterative Quantization：A Procrustean Approach to Learning Binary Codes for Large－scale Image Retrieval［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（12）：2916－2929．

［9］Liu Wei，Wang Jun，Kumar S，et al．Hashing with Graphs［C］／／Proceedings of the 28th International Con－ference on Machine Learning，Bellevue，USA：［s．n．］，2011：522－529．

［10］Jain M，Jégou H，Gros P．Asymmetric Hamming Embedding：Taking the Best of Our Bits for Large Scale Image Search［C］／／Proceedings of the 19th ACM International Conference on Multimedia．New York，USA：ACM Press，2011：1441－1444．

［11］Ji Jianqiu，Li，Jianmi，Yan Shui－Cheng，et al．Superbitlocality－sensitive Hashing［EB／OL］．（2012－09－15）．http：／／papers．nips．cc／paper／4847－super－bit－locality－sensitivehashing．pdf．

［12］高毫林，徐 旭，李弼程．近似最近鄰搜索算法——位置敏感哈希［J］．信息工程大學(xué)學(xué)報(bào)，2013，14（3）：332－340．

［13］Li Peng，Wang Meng，Cheng Jian，et al．Spectral Hashing with Semantically Consistent Graph for Image Index－ing［J］． IEEE Transactions on Multimedia，2013，15（1）：141－152．

［14］Kulis B，Darrell T．Learning to Hash with Binary Reconstructive Embeddings［EB／OL］．（2009－07－16）．http：／／www．eecs．berkeley．edu／Pubs／TechRpts／2009／EECS－2009－101．pdf．

［15］Yu Xiang，Zhang Shaoting，Liu Bo，et al．Large Scale Medical Image Search via Unsupervised PCA Hashing［C］／／Proceedings of IEEE Conference on Computer Vision and Pattern Recognition．Washington D．C．，USA：IEEE Press，2013：393－398．