Supervised Metric Learning with Generalization Guarantees
arXiv:1307.4514
Abstract
The crucial importance of metrics in machine learning algorithms has led to an increasing interest in optimizing distance and similarity functions, an area of research known as metric learning. When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance. Less work has been devoted to metric learning from structured objects (such as strings or trees), most of it focusing on optimizing a notion of edit distance. We identify two important limitations of current metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not been studied so far. Second, the question of the generalization ability of metric learning methods has been largely ignored. In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (e,g,t)-good similarity functions. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend these ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (e,g,t)-goodness. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms based on a notion of algorithmic robustness.
arXiv commentPhD thesis defended on December 11, 2012 (Laboratoire Hubert Curien, University of Saint-Etienne)
References in corpus (9)
- Domain Adaptation: Learning Bounds and Algorithms
- Robustness and Generalization for Metric Learning
- Positive Semidefinite Metric Learning with Boosting
- Distance Metric Learning for Kernel Machines
- Similarity Learning for Provably Accurate Sparse Linear Classification
- Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss
- Similarity-based Learning via Data Driven Embeddings
- Adaptive Regularization for Weight Matrices
- Supervised Learning with Similarity Functions