Consistent Algorithms for Multiclass Classification with a Reject Option

Abstract

We consider the problem of n-class classification (n 2), where the classifier can choose to abstain from making predictions at a given cost, say, a factor of the cost of misclassification. Designing consistent algorithms for such n-class classification problems with a `reject option' is the main goal of this paper, thereby extending and generalizing previously known results for n=2. We show that the Crammer-Singer surrogate and the one vs all hinge loss, albeit with a different predictor than the standard argmax, yield consistent algorithms for this problem when =12. More interestingly, we design a new convex surrogate that is also consistent for this problem when =12 and operates on a much lower dimensional space ((n) as opposed to n). We also generalize all three surrogates to be consistent for any [0, 12].

Tasks

Reproductions