Fast Similarity Search for Learned Metrics

Kulis, B.; Jain, P.; Grauman, K.;  
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 31 , Issue: 12
Digital Object Identifier: 10.1109/TPAMI.2009.151 
Publication Year: 2009 , Page(s): 2143 - 2157

IEEE Journals

Abstract  |  Full Text: PDF (1348 KB)

Kulis, B., Jain, P., & Grauman, K. (2009). Fast Similarity Search for Learned Metrics IEEE Transactions on Pattern Analysis and Machine Intelligence, 31 (12), 2143-2157 DOI: 10.1109/TPAMI.2009.151

在图像检索中，如何学习一种又快又好的距离测度，这是个问题。

为了解决这个问题，作者实际上做了两个贡献：

第一，学习了一种“好”的距离测度：Mahalanobis distance function：

第二，用hash表的方法，让这种距离测度能“又快又好”：

下面就挨个介绍他们：

1.Metric Learning

Mahalanobis Metrics的定义是：

怎么让它更好呢?作者希望能把A作为一个参数来自己学习。

在学习A的时候，在半监督条件下，作者希望能把一些约束条件也用上。什么约束条件？就是一些确定相似或不相似的样本对：保证这些相似样本对距离小于u，不相似样本对大于l条件下，最小化A与一个初始化的A_0的LogDet loss（为啥用这个目标函数？主要是为了它的解可以kernelized）：

这个问题有如下的解答：

对于低维的数据，实际上问题已经结束了；可是高维的怎么办？作者说：

嘿嘿～哥哥早已经做下铺垫，用这个LogDet loss就是为了能将其kernelized！

 

2.Hashing

如何提高检索的速度，尤其是数据库很大的时候？

可以用hash的方式（称为locality-sensitive hash (LSH)），先用r个随机编码器，把每个样本编码为二进制的代码。如下图所示 ：当一个查询样本Q来的时候，也把它变成 r 个二进制，然后看跟那些样本二进制码相似。

这样的编码方式，应该满足一下这个性质：X跟Y的相似度，应该跟他们的某个二进制码相等的几率相等，才能保证hash能得到相似的样本。

然后就是，如何定义h让它能达到以上的目的？

随便找个单位向量r

考虑到用

，于是上面的公式变化为：

用A（r变成rG）有啥差别呢？看下面：r是胡乱挑选的，不一定能保证很好地区分相似和不相似的样本，而rG是经过约束得到的，r只能分布在能区分的范围里。

这就是低维的解决方案，但是当维数很高的时候，计算起来就很麻烦了，于是想用核的方法：


注意作者的巧妙之处：把求A的式子的特性，巧妙地用在hash上，从而大大降低了计算的复杂度！

3.Embedding

这篇文章的内容挺多的，出了给出了一个距离测度，还给出了hash的方法，另外，针对bag-of-words的方法，给出了两种匹配的方法：

第一种：对histogram的Pyramid Match Embedding

第二种：对三维histogram，

求一个Proximity Distribution Embedding：

给出一个核函数，能匹配两个histogram，怎么能求一个hash能迅速匹配他们呢？

总算介绍完了。

有何收获？

启发：

1. 用相似和不相似的样本对做约束，这个思想不错，用在另外两个方法上都看到不错的结果；

2. 提出一种距离测度，是否也考虑下如何能用hash的方法加速？

3. 这篇文章里的两种histogram，还有他们匹配的方法都挺有意思的，不如考虑一下用在image patch和SIFI的医学图像检索上？

最后上作者王道：伯克利的高材生！