Similarity Learning for Provably Accurate Sparse Linear Classification

Understand

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.