Reading Paper: ACL2014-Two-Stage Hashing for Fast Document Retrieval

基本思路:LSH + ITQ 的两阶段方法,思路比较清晰明了。

该Paper基于如下两个方法:
LSH: A. Andoni and P. Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. ommunications of the ACM, 51(1):117–122.

ITQ: Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. 2013. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(12):2916–2929.

Questions:
1. 图2中横坐标number of hash tables是什么意思呢?由于对LSH不是很熟悉,烦请告知。
2. 图2(a)中ITQ已经优于传统方法,但是文中提出的two stage hashing在图(c)(e)中并没有优于传统方法。请问two stage hashing方法的优势是什么?

Answers:
1.用LSH一次随机生成的hash function给所有文章产生的fingerprints (binary codes)组成一个hash table。因为他的随机性,所以需要生成多个table来提高两个近似的document被hash到同一个bucket里面(得到相同的fingerprint)的概率。

2.图2(a)的图是对ITQ生成的codes进行hamming distance ranking,就是brute force search每一个database里面的文章和query文章之间的hamming distance。结果比传统IR方法好是因为在ITQ部分我们对BoW vector进行了LSA降维,然后再做ITQ生成binary codes,等于是考虑了文章的topic的相关性。一般情况下ITQ的codes的质量应该是接近于传统方法的效果。

3.为什么图(c)(e)结果没有优于传统方法?因为ITQ的code没有办法用hash table lookup的办法找NNs,而这篇文章的目的就是要给本来没有办法做hash table lookup操作的ITQ的codes提供做的可能性:通过LSH的hash table lookup找到大致近似的candidates,然后在ITQ质量很好的code上面做reranking — 这样可以趋近于对ITQ的codes做hamming distance ranking得到的结果。这样做有两个好处:

a) 第一不需要visit所有的数据就可以享受到ITQ生成的质量好的fingerprint,并且可以根据你top-K的K值大小改变LSH的设置来控制进入reranking步骤的文章数 (当K很小的时候LSH可以prune的比较狠一点儿,这样rerank速度快最后的结果也会很好; K比较大的时候,需要LSH稍微让多一点儿的candidates进入到reranking,不然会有一些真正相似的文章在第一步被去掉了)。
b) 第二是两步可以考虑两种不同的similarity measure,文章中第一步hash的是BoW vectors,第二步hash的是LSA降维后的topic vectors。你也可以根据需要换成第一步hash文章题目的vector,第二步hash整个文章的vector,等等。

two stage hashing的优势是在接近传统方法查找精度的同时,速度提高一个量级,比如文章中提到找Top10 和Top100的时候,大概只需要1/30的时间。如果K更小, 比如1, 我估计只需要几百分之一。

感谢Hao Li同学的耐心解答。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>