On the Consistency of Top-k Surrogate Losses
The top-$k$ error is often employed to evaluate performance for challenging classification tasks in computer vision as it is designed to compensate for ambiguity in ground truth labels. This practical success motivates our theoretical analysis of consistent top-$k$ classification. Surprisingly, it is not rigorously understood when taking the $k$-argmax of a vector is guaranteed to return the $k$-argmax of another vector, though doing so is crucial to describe Bayes optimality; we do both tasks. Then, we define top-$k$ calibration and show it is necessary and sufficient for consistency. Based on the top-$k$ calibration analysis, we propose a class of top-$k$ calibrated Bregman divergence surrogates. Our analysis continues by showing previously proposed hinge-like top-$k$ surrogate losses are not top-$k$ calibrated and suggests no convex hinge loss is top-$k$ calibrated. On the other hand, we propose a new hinge loss which is consistent. We explore further, showing our hinge loss remains consistent under a restriction to linear functions, while cross entropy does not. Finally, we exhibit a differentiable, convex loss function which is top-$k$ calibrated for specific $k$.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationSimilar Papers 제목 키워드 기반
Structured Prediction with Stronger Consistency Guarantees
We present an extensive study of surrogate losses for structured prediction supported by *$H$-consistency bounds*. These are recently introduced guarantees that are more relevant to learning than Bayes-consistency, since…
Multi-Label Learning with Stronger Consistency Guarantees
We present a detailed study of surrogate losses and algorithms for multi-label learning, supported by $H$-consistency bounds. We first show that, for the simplest form of multi-label loss (the popular Hamming loss), the …
Multi-Label LearningRealizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer
We present a comprehensive study of surrogate loss functions for learning to defer. We introduce a broad family of surrogate losses, parameterized by a non-increasing function $\Psi$, and establish their realizable $H$-c…
Calibration and Consistency of Adversarial Surrogate Losses
Adversarial robustness is an increasingly critical property of classifiers in applications. The design of robust algorithms relies on surrogate losses since the optimization of the adversarial loss with most hypothesis s…
Adversarial RobustnessA Universal Growth Rate for Learning with Smooth Surrogate Losses
This paper presents a comprehensive analysis of the growth rate of $H$-consistency bounds (and excess error bounds) for various surrogate losses used in classification. We prove a square-root growth rate near zero for sm…
Binary ClassificationClassificationMulti-class Classification