Title: Study of error rate reduction in mono-label classification using adaptive set-valued prediction
Authors: Titouan Lorieul - Zenith, LIRMM, University of Montpellier, Inria (France) [presenting]
Alexis Joly - Inria (France)
Dennis Shasha - New York University (United States)
Abstract: In presence of ambiguity in a multi-class classification task, usual single label predictions may be too limited. Set-valued predictions, on the other hand, provide answers similar to a human expert by allowing a predictor to output a set of candidate classes. Several formulations of this problem proposed in the literature result in an optimal strategy consisting in thresholding the regression function. We study the class of problems which would benefit most from such formulations of set-valued classification. In particular, the probability of error of the Bayes optimal classifier is compared to, (i) the best top-k classifier always predicting the k most probable classes, and, (ii) the previously mentioned optimal set-valued classifier resulting in an adaptive set size strategy. Conditions on the regression function quantifying the error rate reduction in the different cases are given. Experiments are carried out in order to test these assumptions on real-world datasets showing the usefulness of set-valued prediction in practice.