Similarity Learning for Provably Accurate Sparse Linear Classification

By Aurélien Bellet, Amaury Habrard, Marc Sebban. 2012

57 citations recorded by the source corpus.

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 (e, γ, τ)-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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Contrastive Multiview Coding (2019, background): “Closely related to self-supervised learning is the idea of multi-view learning, which is a general term involving many different approaches such as co-training [6], multi-kernel learning [11] and metric learning [4]; for comprehensive surveys please see [59, 34].”
A Theoretical Analysis of Contrastive Unsupervised Representation Learning (2019, background): “Similarity/metric learning (Bellet et al., 2012; 2013) learns a linear feature map that gives low distance to similar points and high to dissimilar.”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “Similarity Learning for Linear Classification (Bellet et al., 2012b) takes an original angle by focusing on metric learning for linear classification.”
Robustness and generalization for metric learning (2012, methodology): “Example 5 Consider Algorithm (9) with bilinear similarity f(M, xi, xj) = x T i Mxj instead of the Mahalanobis distance, as studied in [10, 11, 12].”
Learning with Similarity Functions on Graphs using Matchings of Geometric Embeddings (2015, background): “Bellet, Habrard & Sebban [3] considered the problem of learning good, linear similarity functions from data.”
A Theoretical Analysis of Metric Hypothesis Transfer Learning (2015, background): “Building upon this work, (Perrot et al., 2014) give theoretical guarantees for a local metric learning algorithm and (Bellet et al., 2012) derive generalization guarantees for a similarity learning algorithm.”