一文尽览近似最近邻搜索中的哈希与量化方法

编者按：最近邻搜索算法能够帮助人们在海量数据中快速搜索到有效内容，但是想要将其应用于实际，则需要解决如何缩短搜索时间的问题。本文将为大家介绍两种减少搜索时间的方法。基于哈希的近似最近邻搜索的方法通过设计和优化哈希函数，减少计算的次数，从而缩短搜索时间。基于量化的近似最近邻搜索方法则通过聚类把向量集聚成若干类，每类里面的向量用对应的类中心来近似。

我们每个人每天都在享受各种在线服务（在线搜索、新闻推荐等）所带来的种种便利。这些服务的背后隐藏着庞大的、需要计算机实时处理的数据。例如，在图像搜索领域，面对给定的一幅查询图像，系统要从庞大的数据库里（比如包含百万、千万甚至上亿图像）快速找出相似的图像；而在新闻推荐中，计算机也需要根据用户画像，从大量的新闻中找到最相关的新闻推荐给用户。

想要从海量数据中快速找到有效数据离不开 最近邻搜索算法 。最近邻搜索是计算机视觉、机器学习、多媒体搜索、计算几何等领域里非常基础、也是非常重要的问题。

我们先看看最近邻搜索的定义。给定一个查询目标q，最近邻搜索的目的是从一个庞大的参考（搜索）集合X=\{x_1,x_2,…,x_N\}里面，找到距离q最近的目标：

这里面，集合元素x和查询目标q可以是向量、集合或者其它形式，dist(.,.)是相应的距离。在文本相关的应用里，距离的定义基于Jaccard相似度：sim(A,B)=(A∩B)/(A∪B)；在计算机视觉、多媒体、机器学习及计算几何等领域里，研究及使用最为广泛的是欧氏距离度量：dist(x,q)=\|x-q\|_2，这一类问题是本文关注的重点。除此以外，基于内积相似度sim(x,q)=q^⊤ v的最近邻搜索也有不少研究。

假设向量的维数是d，搜索集里含有N个向量，那么线性扫描整个搜索集的时间复杂度是O(dN)。在搜索集小的情况下，计算量还能接受。但是 在实际应用里面，搜索集通常非常大 ，搜索时间非常长，像kd-tree等一些优化方法并没有提高高维空间里的搜索效率，效率甚至比线性扫描还要低，导致 准确最近邻搜索难以直接用于实际问题 。所以，近似最近邻搜索在研究和应用领域都受到广泛的关注。顾名思义， 近似最近邻搜索找到的向量不要求一定是准确的最近邻，只要求距离准确的最近邻很近就可以了。

目前， 近似最近邻缩短搜索时间有两类基本方案：第一类是缩短距离计算的时间 ，时间复杂度变为O(d'N)，例如将维数d从1000降到10，搜索时间缩短到1/100； 第二类是减少距离计算的次数 ，时间复杂度变为O(dN’)，例如将计算次数从1,000,000到1000，搜索时间缩短到1/1000。本文主要介绍第一类方案。

缩短距离计算时间的方法主要分为两种：第一种是哈希或者二值编码的方法；第二种是量化的方法。

基于哈希的近似最近邻搜索的方法

哈希的方法是通过哈希函数把向量x变换成二值码（海明码）b(例如0101110101011100)，然后将距离dist(x_1,x_2)近似成二值码距离（海明距离）dist(b_1,b_2) 。二值码距离可以通过popcount快速计算。这个方向的研究主要集中在哈希函数的设计及其优化，下面介绍几种典型的哈希方法。

哈希方法起源于Piotr Indyk等人提出的Locality-Sensitive Hashing（LSH）方法，即用随机投影的方法，把向量变成二值码。如果要生成32位二值码，LSH随机产生32个投影向量，\{w_1,w_2,…,w_32\}，每个投影向量生成一个二值码，相应的哈希函数可以选为：b_k = δ[w_k^⊤ x ≥ 0]。 最初LSH用于倒排表的方法来快速搜索最近邻，后来更多地用来产生随机二值码来近似距离，被认为二值码方法的基线算法。

但是，由于随机二值码方法没有利用搜索集里的数据来建立哈希函数，所以搜索效果不够理想。后来有大量的研究集中在利用搜索集学习更好的哈希函数，其中，Yair Weiss等人在NIPS 2008上提出的谱哈希方法（Spectral Hashing）是较早的工作之一，这种方法的出发点是希望海明距离大的两个数据点在原空间里的相似度要小，目标函数为最小化海明距离和原空间相似度的乘积，最后转化为解特征值或特征函数的问题。Brian Kulis等人提出的二值化重建嵌入（Binary Reconstructive Embedding）方法的目标是最小化距离重建误差，就是希望海明距离与原空间里的欧氏距离尽量接近。后续的工作还包括Jun Wang等人提出的Semi-Supervised Hashing，以及Wei Liu等人提出的Hashing with Graphs等。

搜索问题可以看成排序问题：距离查询点近的向量排在前面，远的向量排在后面。从这个出发，有些工作设计了保序的目标函数，使得根据在二值空间的序跟原空间里的序尽量一致。Mohammad Norouzi等人提出的三元组损失函数是一种最简单的保序函数：如果一个点q与点p_1的距离比q到p_2点的距离小，那么在二值空间里，点q和点p_1相应的海明距离比q和p_2的海明距离也要小。也有些工作设计更高阶的保序目标函数，比如Jianfeng Wang等人提出的order-preserving hashing。

不同于保相似度、保距离或者保序，Yunchao Gong等人提出的迭代量化的方法（Iterative Quantization，ITQ）的出发点是把二值编码当成原向量的近似，利用欧氏距离旋转不变性的性质，建立了最小化二值编码重建旋转原向量误差的目标函数，寻找最优的旋转变换和二值编码。尽管直观看上去重建向量的方法比保相似、保距离或者保序的方法简单，近似得更强，但ITQ实际效果还是很不错，原因是保相似、保距离或者保序需要建立二元或者多元关系，计算复杂度很大，从而需要各种近似，使得最后的效果不如预期。

图1: 哈希和量化对比的二维案例。左：量化的距离更加丰富；右：量化需要的比特数目少

基于量化的近似最近邻搜索方法

图2: 比较乘积量化、优化的乘积量化以及合成量化的二维案例。左：乘积量化；中：优化的乘积量化；右：合成量化。

向量量化是通过聚类把向量集聚成若干类，每类里面的向量用对应的类中心来近似 。这样子，每个向量只需要用其对应的聚类中心的索引ID来表示，其与查询向量间的距离用其对应的聚类中心与查询向量间的距离来近似。向量量化带来了两项优势：

（1）向量需要的存储空间变少了，只需保存对应的聚类中心的ID；

（2）计算时间减少了，只需要通过聚类中心的索引ID来查询预先计算好的聚类中心与查询向量的距离表格。

然而，直接用k-means算法并不能带来明显的效果：如果聚类中心数目太少，向量近似效果不佳；而如果聚类中心数目太多，距离表格计算时间又太长。因此，研究人员利用Cartesian量化用来解决此问题。Cartesian量化的聚类中心C是建立在几个小的聚类中心集合\{C_1,C_2,…,C_P\}的基础上：C=C_1×C_2×…×C_P\\，其好处在于通过几个小的聚类中心集合，可以得到非常多的聚类中心，甚至多于搜索的向量集合大小，从而向量近似效果可以得到保证。进一步通过引进一些限制或者策略来保证距离计算可以通过快速查找距离表格来实现，以降低计算时间。下面介绍三种主要的方法。

乘积量化

乘积量化（Product Quantization）把向量分成若干个子向量，然后对每个子向量集合分别聚类。具体来讲，向量x分成子向量\{x_1,x_2,…,x_P\}: x=[x_1^⊤ x_2^⊤…x_P^⊤ ]^⊤。然后对每个子向量的集合\{x_p1,x_p2,…,x_pN\}进行聚类, 得到K（为了方便，每个集合都生成相同数量的聚类中心）个聚类中心：C_p =\{c_p1,c_p2,…,c_pK \}。最终，乘积量化得到K^P聚类中心\{[c_(1k_1)^⊤,c_(2k_2)^⊤,…,c_(Pk_P)^⊤ ]^⊤;k_1∈\{0,1,…,K\},k_2∈\{0,1,…,K\},…,k_P=\{0,1,…,K\}\}。在最近邻搜索中，乘积量化每个向量x由其P个子向量对应的聚类中心的ID来表达：(k_1,k_2,…,k_P)。查询向量q与参考向量x距离有对称和非对称两种近似方法。

对称的方法：线下计算P个大小K×K的距离表格，每个表格D_p存储对应的聚类中心两两之间的距离D_p (i,j)= dist(c_pi,c_pj)。查询向量分成P个子向量，每个子向量找到对应的聚类中心，查询向量由聚类中心的ID来表示：((k_1) ̃,(k_2) ̃,…,(k_P) ̃)。这样子，距离近似为dist(p,x)≈∑_(p=1)^P D_p ((k_p) ̃,k_p)。

非对称的方法：线上预先计算一个大小P×K距离表格，把查询向量q分成P个子向量，q_1,q_2,…,q_P，然后计算这P个子向量与P组聚类中心的距离，D(p,j)=dist(q_p,c_pj)。这样，距离近似为dist(p,x)≈∑_(p=1)^P D(p,k_p)。很显然，后者距离近似的更为准确，但是需要额外距离表格的计算，在搜索数据库非常大的情况下，额外距离表格计算的时间可以忽略不计。

乘积量化需要把向量分成P个子向量，由于各个子向量的分布的不一样，每个子向量的量化性能不平衡，会导致距离近似不够理想。由Mohammad Norouzi等人提出的Cartesian k-means方法以及由Tiezheng Ge等人提出的优化的乘积量化方法首先旋转向量，然后在旋转后的空间里进行乘积量化。这里面旋转的目的是旋转后的每个子向量的量化性能尽量平衡。旋转具有不改变欧氏距离的性质，这是可以把旋转引进来的原因。

合成量化

合成量化（Composite Quantization）的基本思想是用P个同样维度的向量\{c_(1k_1), c_(2k_2), …, c_(Pk_P)\}的和来近似向量x：x≈x ̅=∑_(p=1)^P c_(pk_p)，其中，c_(pk_p)来自于第p个字典\{c_p1,c_p2,…,c_pK\}。相应的，每个向量x由P个向量的ID来表达：(k_1,k_2,…,k_P)。其带来的好处是向量近似误差更小。但是，需要重建向量，然后算距离，因此距离计算复杂度很大。合成量化根据下面的距离计算展开形式来设计加快距离计算的方法：

上面的等式右边：第二项只决定于查询向量q，对某个具体的查询向量，这一项不影响距离排序；第一项，由查询向量和字典的元素的距离构成，接受到一个查询向量时，可以预先计算查询向量与每个字典里的每个元素之间的距离形成距离表格，然后查询向量与搜索数据库里的每个向量的距离，可以通过查表快速地找到P个距离，然后求和得到，这部分的距离计算复杂度为O(P)，通常P会远小于向量的维度d，所以这部分计算速度提高了；第三项，

也可以通过查表的方法做，但是计算复杂度依然很大，所以近正交合成量化在优化字典的时候引进一限制条件，让这一项变成常数ε，从而这一项可以不用计算了。所以近正交的合成量化的优化目标是最小化量化误差，同时加入常数项限制：

合成量化从理论的角度分析得出：加入这个限制条件，实际上是在最小化量化误差和距离计算时间之和的上界。同时也指出了，乘积量化及其变种是合成量化的特例，从而合成量化的结果更好些。

合成量化一文，提出了近正交的合成量化的一种变体：对第三项用一个字节进行编码，减少字典的数量，比如用P-1个字典（每个字典包含256个元素，可以一个字节编码每个元素），实验发现在字典数目较多的情况下，这个变体的性能跟近正交合成量化结果差不多，字节数目较少的情况下，性能差些。

了解合成量化的更多内容，请查阅：

• Ting Zhang, Chao Du, Jingdong Wang. Composite Quantization for Approximate Nearest Neighbor Search. ICML 2014: 838-846

  https://www.microsoft.com/en-us/research/publication/composite-quantization-approximate-nearest-neighbor-search/

• Composite Quantization. Jingdong Wang, Ting Zhang. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018

  https://arxiv.org/abs/1712.00955

加和量化

类似合成量化的方法，Artem Babenko等人提出的加和量化（Additive Quantization）从下面的距离展开形式来实现距离的快速计算：

等式右边第一项只跟查询向量有关，不用计算；第二项可以通过查表快速计算；第三项用1个字节来近似。但是实验显示，加和量化的结果比合成量化略差。

我们在合成量化一文中也考虑到下面的欧氏距离转化成内积的形式，

合成量化或者加和量化可以用来量化 ，然后计算复杂度可以降到O(P)。但是，直接这样做的效果并不理想，原因在于，向量x和其模的取值范围不一样，导致量化性能不是很理想。

为了更好地推动基于哈希与量化的近似最近邻搜索这一方面的工作，我们在A Survey on Learning to Hash一文中梳理了该领域在2017年以前的工作，并把tex源码放在了https://github.com/welleast/Learning2Hash，邀请大家一起进一步完善该综述，特别是添加基于深度学习的哈希和量化方面的工作，有感兴趣的研究人员也可以通过留言跟我联系。

Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, Heng Tao Shen. A Survey on Learning to Hash. IEEE Trans. Pattern Anal. Mach. Intell. 40(4): 769-790 (2018).

https://arxiv.org/pdf/1606.00185.pdf

另外， 我们在GitHub上开源了基于近邻图的最近邻搜索算法 ，希望可以共同推动相关领域的发展。

GitHub主页：https://github.com/Microsoft/SPTAG

了解更多基于近邻图的最近邻搜索算法，请查阅：

• Jingdong Wang, Shipeng Li. Query-driven iterated neighborhood graph search for large scale indexing. ACM Multimedia 2012: 179-188

  https://www.microsoft.com/en-us/research/publication/query-driven-iterated-neighborhood-graph-search-for-scalable-visual-indexing/

• Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, Shipeng Li. Scalable k-NN graph construction for visual descriptors. CVPR 2012: 1106-1113

  https://ieeexplore.ieee.org/document/6247790

• Jingdong Wang, Naiyan Wang, You Jia, Jian Li, Gang Zeng, Hongbin Zha, Xian-Sheng Hua. Trinary-Projection Trees for Approximate Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 36(2): 388-403 (2014)

  https://ieeexplore.ieee.org/iel7/34/4359286/06549106.pdf