Skip to Main content Skip to Navigation
Conference papers

A Probabilistic Theory of Supervised Similarity Learning for Pointwise ROC Curve Optimization

Robin Vogel 1 Aurélien Bellet 2 Stéphan Clémençon 1
2 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : The performance of many machine learning techniques depends on the choice of an appropriate similarity or distance measure on the input space. Similarity learning (or metric learning) aims at building such a measure from training data so that observations with the same (resp. different) label are as close (resp. far) as possible. In this paper, similarity learning is investigated from the perspective of pairwise bipartite ranking, where the goal is to rank the elements of a database by decreasing order of the probability that they share the same label with some query data point, based on the similarity scores. A natural performance criterion in this setting is pointwise ROC optimization: maximize the true positive rate under a fixed false positive rate. We study this novel perspective on similarity learning through a rigorous probabilistic framework. The empirical version of the problem gives rise to a constrained optimization formulation involving U-statistics, for which we derive universal learning rates as well as faster rates under a noise assumption on the data distribution. We also address the large-scale setting by analyzing the effect of sampling-based approximations. Our theoretical results are supported by illustrative numerical experiments.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Aurélien Bellet Connect in order to contact the contributor
Submitted on : Wednesday, November 14, 2018 - 7:11:47 PM
Last modification on : Friday, January 21, 2022 - 3:11:08 AM
Long-term archiving on: : Friday, February 15, 2019 - 4:58:56 PM


Files produced by the author(s)


  • HAL Id : hal-01922988, version 1


Robin Vogel, Aurélien Bellet, Stéphan Clémençon. A Probabilistic Theory of Supervised Similarity Learning for Pointwise ROC Curve Optimization. International Conference on Machine Learning (ICML 2018), 2018, Stockholm, Sweden. ⟨hal-01922988⟩



Les métriques sont temporairement indisponibles