Abstract
In multiclass classification, the goal is to learn how to predict a random label Y, valued in Y = {1,;...,;K} with K ≥ 3, based upon observing a r.v. X, taking its values in ℝq with q ≥ 1 say, by means of a classification rule g : ℝq → Y with minimum probability of error ℙ{Yeqg(X)}. However, in a wide variety of situations, the task targeted may be more ambitious, consisting in sorting all the possible label values y that may be assigned to X by decreasing order of the posterior probability ηy(X) = ℙ{Y = y | X }. This article is devoted to the analysis of this statistical learning problem, halfway between multiclass classification and posterior probability estimation (regression) and referred to as label ranking here. We highlight the fact that it can be viewed as a specific variant of ranking median regression (RMR), where, rather than observing a random permutation Σ assigned to the input vector X and drawn from a Bradley-Terry-Luce-Plackett model with conditional preference vector (η1(X),;...; ηK(X)), the sole information available for training a label ranking rule is the label Y ranked on top, namely Σ-1(1). Inspired by recent results in RMR, we prove that under appropriate noise conditions, the One-Versus-One (OVO) approach to multiclassification yields, as a by-product, an optimal ranking of the labels with overwhelming probability. Beyond theoretical guarantees, the relevance of the approach to label ranking promoted in this article is supported by experimental results.
Original language | English |
---|---|
Title of host publication | Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics |
Editors | Silvia Chiappa, Roberto Calandra |
Publisher | PMLR |
Pages | 1421-1430 |
Number of pages | 9 |
Volume | 108 |
Publication status | Published - 1 Feb 2020 |
Event | 23rd International Conference on Artificial Intelligence and Statistics - Teatro Politeama, Online, Italy Duration: 26 Aug 2020 → 28 Aug 2020 Conference number: 23 https://www.aistats.org/ |
Publication series
Name | Proceedings of Machine Learning Research |
---|---|
Publisher | PMLR |
Volume | 108 |
ISSN (Electronic) | 2640-3498 |
Conference
Conference | 23rd International Conference on Artificial Intelligence and Statistics |
---|---|
Abbreviated title | AISTATS 2020 |
Country/Territory | Italy |
City | Online |
Period | 26/08/20 → 28/08/20 |
Internet address |