nips nips2012 nips2012-148 nips2012-148-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mohammad Norouzi, David M. Blei, Ruslan Salakhutdinov
Abstract: Motivated by large-scale multimedia applications we propose to learn mappings from high-dimensional data to binary codes that preserve semantic similarity. Binary codes are well suited to large-scale applications as they are storage efficient and permit exact sub-linear kNN search. The framework is applicable to broad families of mappings, and uses a flexible form of triplet ranking loss. We overcome discontinuous optimization of the discrete mappings by minimizing a piecewise-smooth upper bound on empirical loss, inspired by latent structural SVMs. We develop a new loss-augmented inference algorithm that is quadratic in the code length. We show strong retrieval performance on CIFAR-10 and MNIST, with promising classification results using no more than kNN on the binary codes. 1
[1] http://yann.lecun.com/exdb/mnist/.
[2] R. Battiti. Accelerated backpropagation learning: Two optimization methods. Complex Systems, 1989.
[3] A. Bergamo, L. Torresani, and A. Fitzgibbon. Picodes: Learning a compact code for novel-category recognition. NIPS, 2011.
[4] M. Charikar. Similarity estimation techniques from rounding algorithms. STOC, 2002.
[5] G. Chechik, V. Sharma, U. Shalit, and S. Bengio. Large scale online learning of image similarity through ranking. JMLR, 2010.
[6] A. Coates, H. Lee, and A. Ng. An analysis of single-layer networks in unsupervised feature learning. AISTATS, 2011.
[7] J. Davis, B. Kulis, P. Jain, S. Sra, and I. Dhillon. Information-theoretic metric learning. ICML, 2007.
[8] D. Decoste and B. Sch¨ lkopf. Training invariant support vector machines. Machine Learning, 2002. o
[9] W. Dong, M. Charikar, and K. Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. SIGIR, 2008.
[10] P. Felzenszwalb, R. Girshick, D. McAllester, and D. Ramanan. Object detection with discriminatively trained part-based models. IEEE Trans. PAMI, 2010.
[11] A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. ICCV, 2007.
[12] J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood components analysis. NIPS, 2004.
[13] Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. CVPR, 2011.
[14] A. Gordo and F. Perronnin. Asymmetric distances for binary embeddings. CVPR, 2011.
[15] D. Greene, M. Parnas, and F. Yao. Multi-index hashing for information retrieval. FOCS, 1994.
[16] G. Hinton and R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 2006.
[17] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. STOC, 1998.
[18] H. J´ gou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. e PAMI, 2011.
[19] A. Krizhevsky. Learning multiple layers of features from tiny images. MSc. thesis, Univ. Toronto, 2009.
[20] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. NIPS, 2009.
[21] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. ICCV, 2009.
[22] W. Liu, J. Wang, R. Ji, Y. Jiang, and S. Chang. Supervised hashing with kernels. CVPR, 2012.
[23] M. Muja and D. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. VISSAPP, 2009.
[24] M. Norouzi and D. J. Fleet. Minimal Loss Hashing for Compact Binary Codes. ICML, 2011.
[25] M. Norouzi, A. Punjani, and D. Fleet. Fast search in hamming space with multi-index hashing. CVPR, 2012.
[26] M. Raginsky and S. Lazebnik. Locality-sensitive binary codes from shift-invariant kernels. NIPS, 2009.
[27] D. Rumelhart, G. Hinton, and R. Williams. Learning internal representations by error propagation. MIT Press, 1986.
[28] R. Salakhutdinov and G. Hinton. Semantic hashing. Int. J. Approximate Reasoning, 2009.
[29] G. Shakhnarovich, P. A. Viola, and T. Darrell. Fast pose estimation with parameter-sensitive hashing. ICCV, 2003.
[30] S. Shalev-Shwartz, Y. Singer, and A. Ng. Online and batch learning of pseudo-metrics. ICML, 2004.
[31] P. Simard, D. Steinkraus, and J. Platt. Best practice for convolutional neural networks applied to visual document analysis. ICDR, 2003.
[32] A. Torralba, R. Fergus, and Y. Weiss. Small codes and large image databases for recognition. CVPR, 2008.
[33] J. Wang, S. Kumar, and S. Chang. Sequential Projection Learning for Hashing with Compact Codes. ICML, 2010.
[34] K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. NIPS, 2006.
[35] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. NIPS, 2008.
[36] E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. NIPS, 2002.
[37] C. N. J. Yu and T. Joachims. Learning structural SVMs with latent variables. ICML, 2009. 9