Similarity Learning for Provably Accurate Sparse Linear Classification

Abstract

In recent years, the crucial importance of metrics in machine learning algorithms has led to an increasing interest for optimizing distance and similarity functions. Most of the state of the art focus on learning Mahalanobis distances (requiring to fulfill a constraint of positive semi-definiteness) for use in a local k-NN algorithm. However, no theoretical link is established between the learned metrics and their performance in classification. In this paper, we make use of the formal framework of good similarities introduced by Balcan et al. to design an algorithm for learning a non PSD linear similarity optimized in a nonlinear feature space, which is then used to build a global linear classifier. We show that our approach has uniform stability and derive a generalization bound on the classification error. Experiments performed on various datasets confirm the effectiveness of our approach compared to state-of-the-art methods and provide evidence that (i) it is fast, (ii) robust to overfitting and (iii) produces very sparse classifiers.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (1)

• Similarity-based Learning via Data Driven Embeddings

Cited by in corpus (9)

• Contrastive Multiview Coding
• A Survey on Metric Learning for Feature Vectors and Structured Data
• Robustness and Generalization for Metric Learning
• On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
• Escaping the Curse of Dimensionality in Similarity Learning: Efficient Frank-Wolfe Algorithm and Generalization Bounds
• MirBot: A collaborative object recognition system for smartphones using convolutional neural networks
• Shared Subspace Models for Multi-Group Covariance Estimation
• Supervised Metric Learning with Generalization Guarantees
• A Probabilistic Theory of Supervised Similarity Learning for Pointwise ROC Curve Optimization