频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Shortlist Selection with Residual-Aware Distance Estimator for K-Nearest Neighbor Search
2016-09-27 10:04:00         来源:南有乔木ICT的博客  
收藏   我要投稿

简介

CVPR2016的一篇关于KNN搜索的paper。论文的主要贡献就是提出了关于shortlist计算的算法。在倒排索引的检索过程中,主要经过两步。第一:返回候选集。第二,采用更精确的距离度量风方式进行Rerank。可以这样说,候选集合决定了返回结果的下限,第二步的rerank过程中,才决定了检索的上限。所以,关于倒排索引的改进主要有两个策略。Iverted multi-index就是改进了返回候选集,采用了product quantization的方法,将原始的数据集进行更细的划分,通过和聚类中心的比较,然后返回一个shortlist的候选集,然后从候选集中计算距离,返回最小的K的data。但是如果采用原始的高维向量进行计算,将会占据大量内存和CPU时间。例如测试数据Gist960,960维的数据计算距离将是很耗时耗内存。Rerank又是必要的操作,所以采用hash技术或者是量化的方法改进第二步。其中hash技术包括LSH,spectral hash,ITQ等等。量化的方法包括,PQ, OPQ等等。 在本篇论文中,作者提出了一种新的量化方法对shortlist进行rerank,并通过实验结果证明效果更好。

算法过程

倒排索引进行改进

在传统的倒排索引中,原始的数据集X=x1,x2,x3,......xn会经过K-means聚类,生成M个聚类。对于每一个原始的数据,找出离它最近的聚类中心,形成M个Inverted list-L1,L2,L3,.....LM。在这里计算距离的时候采用欧式距离。
在本篇论文中,作者提出了一种新的距离计算方法。首先计算原始的数据xi 到距离中心q(x)的residual distance。首先定义residual distance 为rx:
rx=d(x,q(x))
同理,我们定义查询query y与量化距离中心q(x)的距离为hy,x:
hy,x=d(y,q(x))
查询query y与原始的数据x的距离可以写成余弦定理的形式:
d(y,x)2=h2y,x+r2x?2hy,xrxcosθ=h2y,x+r2(1?2hy,xrxcosθ),(1)
θ是两个向量y?q(x)x?q(x)之间的角度。
我们观察上述公式,(1?2hy,xrxcosθ)取决于特定的x和特定的y。我们把(1?2hy,xrxcosθ)估算为常量αK。现在我们只需要计算h2y,xr2x。其中r2x是和查询无关的。h2y,x是和查询y有关的。所以上面的公式可以写成下面这种形式:
d^(y,x)2=h2y,x+αKr2x,(2)
我们观察αK的值。当αK为0时,就是传统的距离度量方式。当两个向量正交的时候,αK为1,上面的公式就是勾股定理的形式。
但是在实际中,对于任意的向量,并不是所有的向量都会正交。所以,作者提出了一种训练的方法,得到一个和近邻K有关的αK。首先从原始的数据集X中随机选出Nsdata{s1,s2,s3,......sNs},然后计算每一个样本si的K个最近邻。把样本si的第jth个邻居记为nji。我们通过随机选取的数据来进行评估αK的值。但是这样做会出现overfitting。所以需要从每一个si中随机选取另外K的data point,记为{mi1,mi2,mi3,.......miK}。我们通过下面的公式来计算整个数据集的αK的值:
αK=12KNs∑i=1Ns(∑j=1Kf(si,nij)+∑j=1Kf(si,mij)),(3)
这里:
f(y,x)=1?2hy,xrxcosθ=d(y,x)2?h2y,xr2x
在训练αK的值的时候,需要排除掉数据和聚类中心重合的点,这样做为了避免分母r2x为0的情况。这里训练的αK是和K相关的,当出现新的K值时候,我们可以简单的使用αK=1来提前计算。实验表明,当使用训练过的αK的时候,比默认的值1准确率提高了20%。

建立Lookup Table

在公式(2)中,我们需要计算rx=d(x,q(x))的值和hy,x=d(y,q(x))的值。但是如果在运行的时候计算,将会耗时耗内存。并且如果原始的数据进行量化以后,无法通过量化的值来获取原始的点。所以提出了一种新的急算方法。由于rx是和查询无关的,我们可以在线下计算。在这里提出了一种lookup表结构来加速计算的过程。
首先对于每一个Li,我们需要计算原始的数据xi到它的中心ci的距离,然后按照递增的顺序进行排列。然后遍历每一个Li,得到一个最大和最小的距离。
Rm=mind(x,q(x))2,RM=maxd(x,q(x))2
然后将区间[Rm,RM]平均的划分为Z份。其中每一份的距离为ΔR=(RM?Rm)/Z。然后我们定义第j-th区间上界值为Rj=Rm+jΔR
我们定义一个lookup表。W(i,j)储存每一个倒排索引Li,距离平方小于Rj的数目。如下所示:
W(i,j)=|{x|d(x,ci)2
|.|代表集合中的数目。这个lookup表有O(MZ)的空间复杂度,并且M和Z都是和数据集无关的。

Shortlist computation

好吧,这里又开始定义了。首先将查询y和中心ci的距离平方记为:h2i=d(y,ci)2。然后又引入了一个新的函数w(y,i,t)来表示在Inverted listLi中的数据点与查询y的距离小于t的数目。
w(y,i,t)=|{x|d^(y,x)2
推导到最后,发现和公式(4)的格式很像,这就对了。当
(t?h2i)/αKRj取代的时候,这就和W(i,j)有关了。我们利用建立的W(i,j)。可以替换公式(5):
w(y,i,t)=W(i,?(t?h2i)/αK?RmΔR?),(6)
对于每一个查询在距离t以后的所有的点可以计算为∑Ki=1w(y,i,t)。因为W(i,j)是非单调递减的,所以随着t增加,w(y,i,t)也是非单调递减的。由于这个简单的属性,我们可以使用二分搜索的方法。二分搜索的范围为[minh2i+αKRm,maxh2i+αKRM]。当T<∑Ki=1w(y,i,t)满足条件时,搜索终止。

Inverted Multi-index

对于inverted Multi-index的具体介绍,可以参考博客。在数据集中的数据x_在第K个子空间的部分,在第K个子空间量化后的值为qk(xk)=argminckid(xk,xki)。首先定义距离rx,k=d(xk,qk(xk))hk,i=d(yk,cki)
对数据进行进一步处理,第k个中心的ith聚类的数据为:Xki={xk|qk(xk)=cki},根据距离rx,kXki。然后根每一个聚类Xki划分为P分Xki,1,Xki,2,Xki,3,.......Xki,P,根据Rki,j:
Xki,j={xk|Rki,j?1≤rkx,i
这里边界值
Rki,.j平均的将数据划分为P部分。其中Rki,0Rki,P被设置为子空间最小和最大的距离。这种做法和传统倒排索引的做法相同。
Inverted multi-index划分为kth个子空间。我们用同样的方法训练αK,1αK,2。我们将ith聚类也分为kth个子空间。Xki={xk|qk(xk)=cki}。对于每一个子聚类,划分为P个部分Xki,1,Xki,2,.......Xki,P
Xki,j={xk|Rki,j?1
残差距离边界
Rki,j也是平均划分为P份,R_{i,0}^kR_{i,P}^k$分别代表子空间距离的最小最大值。

在计算距离的时候,如果按照公式(2)的计算方式,那么将会是如下这种形式:
d^(y,x)2=d(y1,q1(x1)2+αK,1r2x,1+d(y2,q2(x2)2+αK,2r2x,2,(8)
因为Inverted Multi-index的List长度为k2。所以存储r2x,k的值不太现实。Inverted Multi-Index的索引长度随着划分的数目增多,指数增加,所以需要提出了一种新的代替residual distance的一种方法。作者提出了一种用平均距离代替的方法如下所示:
rˉk,i,j=∑rx,k|Xki,j|
替换以后公式(8)新的距离就写成了如下的形式:
dˉ(y,x)2=h21,i1+αK,1rˉ21,i1,j1????????????????????dˉ21,i1,j1+h22,i2+αK,2rˉ1,i2,j2????????????????????dˉ22,i2,j2
当新的查询到的时候,首先计算query和聚类中心h21,ih22,i距离。然后我们取出预先计算好的αK,k和rˉ2k,i,j的值。然后计算dˉ2k,i,j=h2k,i+αK,krˉ2k,i,j的值。所以总共会有2M次加法操作。我们把rˉ2k,i,j的值进行排序。一旦排序以后,我们同样可以采用multi-sequence algorithm用一个优先级队列来获取T长度shortlist。计算过程如下图所示:
这里写图片描述

我们可以从返回的shortlist中进一步处理。

总结

总结论文的过程就是定义一些更精确的距离度量方式来重新rerank。但是这样的做法会导致计算时间的方法,所以作者又将距离公式进行预先处理。使尽可能多的在线下计算,建立起线上计算与线下计算的关系来提高计算的时间效率。

点击复制链接 与好友分享!回本站首页
上一篇:Java泛型详解
下一篇:【caffe-matlab】权重以及特征图的可视化
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站