nips nips2009 nips2009-32 nips2009-32-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Gal Chechik, Uri Shalit, Varun Sharma, Samy Bengio
Abstract: Learning a measure of similarity between pairs of objects is a fundamental problem in machine learning. It stands in the core of classification methods like kernel machines, and is particularly useful for applications like searching for images that are similar to a given image or finding videos that are relevant to a given video. In these tasks, users look for objects that are not only visually similar but also semantically related to a given object. Unfortunately, current approaches for learning similarity do not scale to large datasets, especially when imposing metric constraints on the learned similarity. We describe OASIS, a method for learning pairwise similarity that is fast and scales linearly with the number of objects and the number of non-zero features. Scalability is achieved through online learning of a bilinear model over sparse representations using a large margin criterion and an efficient hinge loss cost. OASIS is accurate at a wide range of scales: on a standard benchmark with thousands of images, it is more precise than state-of-the-art methods, and faster by orders of magnitude. On 2.7 million images collected from the web, OASIS can be trained within 3 days on a single CPU. The nonmetric similarities learned by OASIS can be transformed into metric similarities, achieving higher precisions than similarities that are learned as metrics in the first place. This suggests an approach for learning a metric from data that is larger by orders of magnitude than was handled before. 1
[1] A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning Distance Functions using Equivalence Relations. In Proc. of 20th International Conference on Machine Learning (ICML), pages 11–18, 2003.
[2] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressive algorithms. JMLR, 7:551–585, 2006.
[3] J.V. Davis, B. Kulis, P. Jain, S. Sra, and I.S. Dhillon. Information-theoretic metric learning. In ICML 24, pages 209–216, 2007.
[4] A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. In International Conference on Computer Vision, pages 1–8, 2007.
[5] A. Globerson and S. Roweis. Metric Learning by Collapsing Classes. NIPS, 18:451, 2006.
[6] D. Grangier and S. Bengio. A discriminative kernel-based model to rank images from text queries. Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(8):1371– 1384, 2008.
[7] G. Griffin, A. Holub, and P. Perona. Caltech-256 object category dataset. Technical Report 7694, CalTech, 2007.
[8] R. Hadsell, S. Chopra, and Y. LeCun. Dimensionality reduction by learning an invariant mapping. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 2, 2006.
[9] P. Jain, B. Kulis, I. Dhillon, and K. Grauman. Online metric learning and fast similarity search. In NIPS, volume 22, 2008.
[10] B. Kulis, M.A. Sustik, and I.S. Dhillon. Low-rank kernel learning with bregman matrix divergences. Journal of Machine Learning Research, 10:341–376, 2009.
[11] G.R.G. Lanckriet, N. Cristianini, P. Bartlett, L. El Ghaoui, and M.I. Jordan. Learning the kernel matrix with semidefinite programming. JMLR, 5:27–72, 2004.
[12] W. S. Noble. Multi-kernel learning for biology. In NIPS workshop on kernel learning, 2008.
[13] N. Rasiwasia and N. Vasconcelos. A study of query by semantic example. In 3rd International Workshop on Semantic Learning and Applications in Multimedia, 2008.
[14] R. Rosales and G. Fung. Learning sparse metrics via linear programming. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 367–373. ACM New York, NY, USA, 2006.
[15] A. Tversky. Features of similarity. Psychological Review, 84(4):327–352, 1977.
[16] K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. NIPS, 18:1473, 2006.
[17] K.Q. Weinberger and L.K. Saul. Fast solvers and efficient implementations for distance metric learning. In ICML25, pages 1160–1167, 2008.
[18] E.P. Xing, A.Y. Ng, M.I. Jordan, and S. Russell. Distance metric learning with application to clustering with side-information. In S. Becker, S. Thrun, and K. Obermayer, editors, NIPS 15, pages 521–528, Cambridge, MA, 2003. MIT Press.
[19] L. Yang. Distance metric learning: A comprehensive survey. Technical report, Michigan State Univ., 2006. 9