Proceedings

Learning "Forgiving" Hash Functions: Algorithms and Large Scale Tests

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2663-2668.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

The problem of efficiently finding similar items in a large corpus of high-dimensional data points arises in many real-world tasks, such as music, image, and video retrieval. Beyond the scaling difficulties that arise with lookups in large data sets, the complexity in these domains is exacerbated by an imprecise definition of similarity. In this paper, we describe a method to learn a similarity function from only weakly labeled positive examples. Once learned, this similarity function is used as the basis of a hash function to severely constrain the number of points considered for each lookup. Tested on a large real-world audio dataset, only a tiny fraction of the points are ever considered for each lookup. To increase efficiency, no comparisons in the original high-dimensional space of points are required. The performance far surpasses, in terms of both efficiency and accuracy, a state-of-the-art Locality-Sensitive-Hashing based technique for the same problem and data set.

  1. [Baluja & Covell, 2006] S. Baluja, M. Covell. Content Fingerprinting with Wavelets. Third Conference on Visual Media Production (CVMP).
  2. [Bar Hillel et al., 2003] A. Bar-Hillel, T. Hertz, N. Shental, D. Weinshall. Learning Distance Functions using Equivalence Relations. International Conference on Machine Learning.
  3. [Burges et al., 2003] J. C. Burges, J. C. Platt, S. Jana. Distortion Discrimi- nant Analysis for Audio Fingerprinting. IEEE Trans. Speech and Audio Processing, vol. 11.
  4. [Caruana et al, 1996] R. Caruana, S. Baluja, T. Mitchell. Using the future to "sort out" the present: Rankprop and MTL. Neural Information Process- ing Systems 8.
  5. [Chow & Liu, 1968] C. Chow, C. Liu. Approximating discrete probability distributions via dependence trees. IEEE Trans. Info. Theory, vol. IT-14.
  6. [Gionis et al., 1999] A Gionis, P. Indyk, R. Motwani. Similarity search in high dimensions via hashing. 25th Very Large Data Base Conference.
  7. [Haitsma and Kalker, 2002] J. Haitsma, T. Kalker. A Highly Robust Audio Fingerprinting System. International Conference on Music Information Retrieval.
  8. [Hastie & Tibshirani, 1996] T. Hastie, R. Tibshirani. Discriminant Adap- tive Nearest Neighbor, IEEE PAMI, vol. 18.
  9. [Hertz et al., 1991] J. Hertz, A. Krogh, R. Palmer. Introduction to the The- ory of Neural Computing (Addison-Welsey).
  10. [Ke et al., 2005] Y. Ke, D. Hoiem, R. Sukthankar. Computer Vision for Music Identification, Computer Vision and Pattern Recognition.
  11. [Pollack, 1990] J.B. Pollack. Recursive Distributed Representations, Artifi- cial Intelligence, vol. 46.
  12. [Shakhnarovich, 2006] G. Shakhnarovich. Learning Task Specific Similar- ity. Ph.D. Thesis, MIT. [Shazam, 2005] Shazam Entertainment http://www.shazamentertainment.com Link
  13. [Shental et al., 2002] N. Shental, T. Hertz, D. Weinshall, M. Pavel. Ad- justment Learning and Relevant Component Analysis. ECCV.
  14. [Tsang et al., 2005] I. W. Tsang, P.-M. Cheung, J. T. Kwok. Kernel Rele- vant Component Analysis for Distance Metric Learning. IJCNN.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards