nips nips2009 nips2009-142 nips2009-142-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maxim Raginsky, Svetlana Lazebnik
Abstract: This paper addresses the problem of designing binary codes for high-dimensional data such that vectors that are similar in the original space map to similar binary strings. We introduce a simple distribution-free encoding scheme based on random projections, such that the expected Hamming distance between the binary codes of two vectors is related to the value of a shift-invariant kernel (e.g., a Gaussian kernel) between the vectors. We present a full theoretical analysis of the convergence properties of the proposed scheme, and report favorable experimental performance as compared to a recent state-of-the-art method, spectral hashing.
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117–122, 2008.
[2] K. Clarkson. Nearest-neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15–59. MIT Press, 2006.
[3] S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In STOC, 2008.
[4] S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Alg., 22(1):60–65, 2003.
[5] J. Heinonen. Lectures on Analysis on Metric Spaces. Springer, New York, 2001.
[6] P. Indyk and A. Naor. Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms, 3(3):Art. 31, 2007.
[7] A. Oliva and A. Torralba. Modeling the shape of the scene: a holistic representation of the spatial envelope. Int. J. Computer Vision, 42(3):145–175, 2001.
[8] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In NIPS, 2007.
[9] M. Reed and B. Simon. Methods of Modern Mathematical Physics II: Fourier Analysis, Self-Adjointness. Academic Press, 1975.
[10] B. Russell, A. Torralba, K. Murphy, and W. T. Freeman. LabelMe: a database and web-based tool for image annotation. Int. J. Computer Vision, 77:157–173, 2008.
[11] R. Salakhutdinov and G. Hinton. Semantic hashing. In SIGIR Workshop on Inf. Retrieval and App. of Graphical Models, 2007.
[12] B. Sch¨ lkopf and A. J. Smola. Learning With Kernels. MIT Press, 2002. o
[13] A. Torralba, R. Fergus, and Y. Weiss. Small codes and large databases for recognition. In CVPR, 2008.
[14] A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer, 1996.
[15] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, 2008.