基于投影残差量化哈希的近似最近邻搜索

杨定中，陈心浩

（中南民族大学实验教学中心，武汉430074）

1 概述

大规模数据集的最近邻搜索（相似度搜索）在机器学习和计算机视觉中有着广泛应用。然而，因为数据规模过大和维数灾难问题，确切的最近邻搜索对于实时性较强的应用是一个亟需解决的课题。最近，舍弃有限精度的近似最近邻搜索引起了研究人员的关注，解决这一问题的经典方法来自基于量化的近似最近邻搜索方法，该类方法的关键在于利用子量化器的排列组合而构建量化器。积量化［1－2］通过将原始空间拆分成多个正交子空间，利用子空间的低复杂度量化器构建出原始空间中的高复杂度量化器，但是积量化方法需要各个子空间统计无关，否则其正确率会显著下降，残差量化［3－4］则直接在原始高维空间训练量化器，所得量化残差继续训练下一阶段子量化器，残差量化器则为多个子量化器的组合。基于组合所表示数据的容量成指数增长，并在原始数据空间中进行搜索处理，即使基于倒排索引，其搜索过程也是费时的。目前，基于哈希的方法因其能在常量时间能完成搜索已被广泛应用于相似度检索［5－7］。 已 有 的 哈 希 方 法 一 般 分 为 两 大 类［8－9］：数据无关的方法和数据相关的方法。数据无关方法的一个代表是随机投影残差量化哈希，如汉明嵌入［10］和局部敏感哈希（Local Sensitive Hashing，LSH）［11－12］。在这类方法中，哈希函数为独立于数据集的随机投影。理论上，随机投影保证了随着编码长度的增加，原始距离或相似性在海明空间渐近式保持。因此，LSH相关的方法通常需要较长的编码而得到较高的精度。然而，长编码会导致低召回率，因为，随着编码长度的增加，相似数据冲突（相似数据映射为相近的二进制编码）的概率成指数下降。所以，与LSH相关的方法通常采用构建多个哈希表来确保合理的冲突概率，这样查询会至少在一个哈希表中与相应的近邻相冲突，直接后果就是明显增加查询时的时间开销和内存占用。为了生成更紧凑的哈希编码，研究人员提出了许多数据相关的哈希方法，这类方法从数据集中训练哈希函数。近年来，一种基于谱图划分的哈希函数引起了注意，如谱哈希（Spectral Hashing，SPH）［13］，其采用一维拉普拉斯算子的简单解析特征函数作为哈希函数。在谱哈希中，引入2个重要的约束用于训练二进制编码：（1）每个哈希位平衡划分数据集；（2）不同的哈希位互不相关。这2个约束也在其他许多研究中广泛使用。在文献［8］中，迭代量化哈希（Iterative Quantization Hashing，ITQ）通过训练正交旋转矩阵以改进初始主成分分析（Principal Component Analysis，PCA）投影矩阵，以最小化数据从原始空间映射到汉明空间的量化误差为目标训练哈希函数。在文献［14］中，汉明距离被用作原始数据空间中的数据点之间距离的重建，旨在最小化重建误差来训练哈希函数。PCA哈希［15］采用数据的协方差矩阵最大特征值的特征向量用于生成哈希的投影矩阵，PCA哈希将原始数据经PCA矩阵投影到低维空间。但是，PCA哈希将二进制编码基于投影后的数据会产生大量投影误差而导致搜索精度降低。而且，在基于量化的近似最近邻搜索时，量化残差会直接丢弃，当量化码书较小时，会生成较大的量化误差，极大影响搜索精度。基于此，本文提出投影残差量化哈希，并结合PCA哈希和向量量化的思想，将向量投影到低维主空间，并在主空间的各维标量上训练码书，量化后的残差按维度顺序组成新的低维主空间向量，并将其反投影回原始向量空间形成新的高维残差，通过对高维残差的重复利用，生成一种多维度哈希函数。

2 投影残差量化哈希

2．1 哈希函数构造

投影残差量化哈希的哈希函数形式上为一向量量化器，哈希编码为量化索引。投影残差量化哈希的量化器由多个标量量化器组成，其生成过程包括如下多个阶段：对于给定的训练集v＝｛xi∈RD，1≤i≤N｝，首先用PCA投影阵M1将v投影到低维空间生成低维向量集，如式（1）所示。

对于数据库向量和查询，均可以按式（5）生成相应的哈希编码并进行基于汉明距离的快速最近邻搜索。

投影残差量化哈希基于各一维数据与标量类心的最近邻关系进行哈希编码，形式上2个标量类心将一维空间划分为3个子集，如图1（a）所示。根据数据与tc之间的大小关系进行哈希编码，由于tc（tc＝（c0＋c1）／2）的取值来源于一维数据的2个类心，将tc作为边界实现数据的有效二分更符合数据的实际分布。如图1（b）所示，圆点表示数据分布，正方形c0，c1分别为聚类类心，正方形tc为类心均值。显然，将tc而不是中值（第5个圆点所示数据）作为二分边界更为合理。

图1 哈希编码示例

2．2 编码权重

在基于哈希进行近似最近邻搜索时，对于给定的查询，直接计算查询的哈希编码与数据库向量的哈希编码之间的汉明距离，然后根据汉明距离按由小到大的顺序返回相应的数据库向量作为查询的近邻。但是由于哈希编码和汉明距离的特殊性，通常会有多个数据库向量与查询具有相同的汉明距离，一般的处理就是将其视为与查询拥有相同的近邻关系，按向量在数据库出现的先后顺序返回给查询。但实际情况并非如此，如图2所示。

图2 汉明距离排序歧义示例

在图2中，p1，p2，p3与查询q的汉明距离都为1，若根据汉明距离直接返回结果，则q的近邻优先关系为p1，p2，p3。但是，从图2中可以看出，p3离查询q更近，直接依据汉明距离返回结果会带来一定的歧义。此类问题一个有效的方法就是给编码加上权重，即使2个二进制编码串之间的汉明距离相同，但由于各编码位权重不同，最终带权重的编码产生的汉明距离大小也会不同，对搜索结果中汉明距离相同的数据库向量生成新的排序结果。二进制编码位的权重取决于其对应的哈希函数，而哈希函数的权重则取决于自身的可区分性，区分性强的哈希函数能以较大概率将相近的数据编码为相同的二进制位，如果数据分布均匀，方差较小，则相近的数据极有可能编码为相同的0，1位，因此哈希函数的权重与数据分布的方差直接负相关。不仅如此，基于某个哈希函数对数据x进行哈希编码时，若x离哈希函数的边界较近，则原本为0的哈希编码可能由于误差编码为1，或者原本为1而编码为0。由此可见，权重与数据离哈希函数的阈值所表示的边界距离应有正相关关系。

综上所述，某个哈希函数的权重可以用如下公式表示：

其中，f（x）为x的变化函数，如投影残差量化哈希中投影运算与取某一维度值的复合运算；ti为类心均值。

3 实验结果与分析

3．1 实验环境

硬件环境为Intel Xeon E7520 1．87GHz CPU，32GB内存，软件环境为linux CentosOS。编程环境采用Matlab R2011a，用C＋＋加速。搜索性能采用2种方式评估：（1）Recall＠K，即长度为K的结果列表中所含最近邻占所有最近邻的比率，K值相同，Recall越高，搜索性能越好；（2）Recall－Precision曲线，曲线下方面积越大，搜索性能越好。实验测试了投影残差量化哈希性能并与主流方法进行比较。实验所用数据集为公开发布的SIFT和GIST数据集，其详细情况如表1所示。

表1 实验数据集

3．2 性能分析

投影残差量化哈希的编码长度取决于投影维度d及阶段数L，对于给定的编码长度d×L，d和L有不同组合，实验首先测试了不同组合对搜索性能的影响。

图3所示为SIFT数据集用32 bit二进制编码后的搜索性能，图例中xy：x为投影维度d，y为阶段数L。从图3可以看出，在｛132，216，48，84，162，321｝组合下，投影残差量化哈希的搜索精度基本相同，仅当d＝8，L＝4时，投影残差量化哈希的搜索性能最优，一个主要的原因是该组合提供了最多的空间划分。在后续实验中，对不同编码长度，d，L均采用空间划分最大组合。同时，实验还测试了二进制编码权重对搜索精度的影响。图4所示为SIFT数据集上编码长度分别为32 bit，64 bit，96 bit时的搜索精度，右上角星号表示带权重的哈希编码后的搜索精度，当编码长度为32 bit，K＝5 000时，带权重的PRVQH的召回率由原始的0．625提高到0．665，搜索性能提高了6．4%。当编码长度为64 bit，K＝5 000时，带权重的PRVQH召回率由原始的0．73提高到0．77，搜索性能提高了5．48%，当编码长度为96 bit，K＝5 000时，带权重的PRVQH召回率由原始的0．85提高到0．89，搜索性能提高了4．71%。由此可见，带权重的哈希编码重排搜索结果后，搜索性能会有较大的提升。

3．3 与主流方法的性能比较

将 本 文 方 法 与 ITQ［8］，SPH［13］，BRE［14］和PCAH［15］主流哈希方法进行性能比较，结果如图5、图6所示。图5为SIFT数据集上的实验结果，编码长度分别为32bit，64bit和96bit。从图5（a）可以看出，在相同编码长度（32bit）下，本文所提出的PRVQH方法搜索性能明显好于其他主流方法，在64bit（图5（b）所示），96bit（图5（c）所示）情形下，PRVQH的搜索性能同样高于其他主流哈希方法。图6为GIST数据集上的实验结果，从中可以看出，PRVQH相比于其他主流哈希方法表现出同样优越的搜索性能。由此可见，在各种编码长度的情况下，本文所提出的投影残差量化哈希搜索性能都优于其他主流方法。

图5 SIFT数据集上各方法的性能比较

图6 GIST数据集上各方法的性能比较

4 结束语

随着互联网及多媒体技术的发展，基于内容的相似度搜索逐渐成为研究热点。由于存储空间小，搜索速度快，二进制哈希不断吸引研究人员的广泛关注。本文提出的投影残差量化哈希，采用多阶段策略，结合反投影和残差量化的思想，有效减少了量化过程中的残差，在搜索时，采用基于带权重的汉明距离进一步提高了搜索性能，与其他主流哈希方法比较的实验结果也验证了本文方法的先进性。在后续工作中，将结合实际数据分布，研究更为合理的编码权重，进一步提高基于二进制哈希的搜索精度。

［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］．信息工程大学学报，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．