王井东作者

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

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

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

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

我们先看看最近邻搜索的定义。给定一个查询目标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个元素,可以一个字节编码每个元素),实验发现在字典数目较多的情况下,这个变体的性能跟近正交合成量化结果差不多,字节数目较少的情况下,性能差些。

了解合成量化的更多内容,请查阅:

加和量化

类似合成量化的方法,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

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

专注科研19年,盛产黑科技

理论搜索哈希推荐算法
2
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

二值化技术

二值化是将像素图像转换为二进制图像的过程。

最近邻搜索技术

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q ∈ M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。

图像搜索技术

图像搜索是通过搜索图像文本或者视觉特征,为用户提供互联网上相关图像资料检索服务的专业搜索引擎系统,是搜索引擎的一种细分。图像搜索方法一般有两种:通过输入与图片名称或内容相似的关键字来进行检索;或者通过上传与搜索结果相似的图片或图片URL进行搜索。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

线搜索技术

最优化问题中,线搜索是一种寻找目标函数 的局部最小值 的近似方法。 它是最基础的迭代近似方法之一,另一种是置信域方法。 线搜索近似首先找到一个使目标函数 下降的方向,然后计算 应该沿着这个方向移动的步长。 下降方向可以通过多种方法计算,比如梯度下降法,牛顿法和拟牛顿法。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

哈希函数技术

散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

暂无评论
暂无评论~