Consistent algorithms for multiclass classification with an abstain option

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 alpha of the cost of misclassification. Our goal is to design consistent algorithms for such n-class classification problems with a 'reject option'; while such algorithms are known for the binary (n = 2) case, little has been understood for the general multiclass case. We show that the well known 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 alpha = 1/2. More interestingly, we design a new convex surrogate, which we call the binary encoded predictions surrogate, that is also consistent for this problem when alpha = 1/2 and operates on a much lower dimensional space (log(n) as opposed to n). We also construct modified versions of all these three surrogates to be consistent for any given alpha is an element of [0, 1/2].