Accuracy of distance metric learning algorithms

ABSTRACT

In this paper, we wanted to compare distance metric-learning algorithms on UCI datasets. We wanted to assess the accuracy of these algorithms in many situations, perhaps some that they were not initially designed for. We looked for many algorithms and chose four of them based on our criteria. We also selected six UCI datasets. From the data's labels, we create similarity dataset that will be used to train and test the algorithms. The nature of each dataset is different (size, dimension), and the algorithms' results may vary because of these parameters. We also wanted to have some robust algorithms on dataset whose similarity is not perfect, whose the labels are no well defined. This occurs in multi-labeled datasets or even worse in human-built ones. To simulate this, we injected contradictory data and observed the behavior of the algorithms. This study seeks for a reliable algorithm in such scenarios keeping in mind future uses in recommendation processes.

REFERENCES

• 1: Aharon Bar-Hillel , Tomer Hertz , Noam Shental , Daphna Weinshall, Learning a Mahalanobis Metric from Equivalence Constraints, The Journal of Machine Learning Research, 6, p.937-965, 12/1/2005
• 2: L. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. In USSR Computational Math. and Math. Physics, 1967.
• 3: Jason V. Davis , Brian Kulis , Prateek Jain , Suvrit Sra , Inderjit S. Dhillon, Information-theoretic metric learning, Proceedings of the 24th international conference on Machine learning, p.209-216, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273523]
• 4: A. Globerson and S. Roweis. Metric learning by collapsing classes, 2005.
• 5: J. Goldberger, S. Roweis, G. Hinton, and R. Salakhutdinov. Neighbourhood components analysis. In NIPS, 2004.
• 6: Aharon Bar Hillel , Daphna Weinshall, Learning distance function by coding similarity, Proceedings of the 24th international conference on Machine learning, p.65-72, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273505]
• 7: E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems 15, pages 505--512. MIT Press, 2003.
• 8: L. Yang and R. Jin. An efficient algorithm for local distance metric learning. In Proceedings of AAAI, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
      G.1.6 Optimization

Keywords:
Bregman divergences, Mahalanobis distance, metric learning