Learning sparse metrics via linear programming

ABSTRACT

Calculation of object similarity, for example through a distance function, is a common part of data mining and machine learning algorithms. This calculation is crucial for efficiency since distances are usually evaluated a large number of times, the classical example being query-by-example (find objects that are similar to a given query object). Moreover, the performance of these algorithms depends critically on choosing a good distance function. However, it is often the case that (1) the correct distance is unknown or chosen by hand, and (2) its calculation is computationally expensive (e.g., such as for large dimensional objects). In this paper, we propose a method for constructing relative-distance preserving low-dimensional mapping (sparse mappings). This method allows learning unknown distance functions (or approximating known functions) with the additional property of reducing distance computation time. We present an algorithm that given examples of proximity comparisons among triples of objects (object i is more like object j than object k), learns a distance function, in as few dimensions as possible, that preserves these distance relationships. The formulation is based on solving a linear programming optimization problem that finds an optimal mapping for the given dataset and distance relationships. Unlike other popular embedding algorithms, this method can easily generalize to new points, does not have local minima, and explicitly models computational efficiency by finding a mapping that is sparse, i.e. one that depends on a small subset of features or dimensions. Experimental evaluation shows that the proposed formulation compares favorably with a state-of-the art method in several publicly available datasets.

REFERENCES

• 1: V. Athitsos, J. Alon, S. Sclaroff, and G. Kollios. Boostmap: A method for efficient approximate similarity rankings. In Computer Vision and Pattern Recognition, 2004.
• 2: Kristin P. Bennet , Ayhan Demiriz , John Shawe-Taylor, A Column Generation Algorithm For Boosting, Proceedings of the Seventeenth International Conference on Machine Learning, p.65-72, June 29-July 02, 2000
• 3: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1 ]
• 4: Paul S. Bradley , O. L. Mangasarian, Feature Selection via Concave Minimization and Support Vector Machines, Proceedings of the Fifteenth International Conference on Machine Learning, p.82-90, July 24-27, 1998
• 5: T. Cox and M. Cox. Multidimensional Scaling. Chapman & Hall, London, 1994.
• 6: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 7: Glenn M. Fung , Olvi L. Mangasarian , Alexander J. Smola, Minimal kernel classifiers, The Journal of Machine Learning Research, 3, p.303-321, 3/1/2003
• 8: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 9: I. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 1989.
• 10: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 11: S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323--2326, 2000.
• 12: M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In Advances in Neural Information Processing Systems, 2003.
• 13: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319--2323, 2000.
• 14: K. C. Toh, M. J. Todd, and R. Tutuncu. SDPT3 - a Matlab software package for semidefinite programming. Optimization Methods and Software, 11:545--581, 1999.
• 15: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 16: K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. In Advances in Neural Information Processing Systems 18, 2006.
• 17: K. Q. Weinberger, B. D. Packer, and L. K. Saul. Unsupervised learning of image manifolds by semidefinite programming. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, Barbados, January 2005.
• 18: E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side information. In Advances in Neural Information Processing Systems, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Measurement, Performance

Keywords:
convex optimization, dimensionality reduction, linear programming, linear projections, metric learning, relative distance constraints