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.

该论文从交叉匹配角度分析了相似性学习，提出了一种基于ROC优化的点级优化标准，通过一种概率框架对此进行了深入研究，给出了基于U-统计的约束优化表达式，推导出相应的普适性学习速率以及在数据分布噪声假设下更快速的学习速率，同时考虑了采样近似近似的效果，同时通过量化实验得到了与理论相称的实验结果。

点对点 ROC 曲线优化的监督相似性学习概率理论