On discriminative learning of prediction uncertainty

In classification with reject option the classifier is allowed in uncertain cases to abstain from prediction. The classical cost based model of an optimal classifier with reject option requires the cost of rejection to be defined explicitly. An alternative bounded-improvement model, avoiding the notion of the reject cost, seeks for a classifier with a guaranteed selective risk and maximal cover. We prove that both models share the same class of optimal strategies, and we provide an explicit relation between the reject cost and the target risk being the parameters of the two models. An optimal rejection strategy for both models is based on thresholding the conditional risk defined by posterior probabilities which are usually unavailable. We propose a discriminative algorithm learning an uncertainty function which preserves ordering of the input space induced by the conditional risk, and hence can be used to construct optimal rejection strategies. We show experimentally that the proposed algorithm learns better rejection strategies than common plug-in rules and rules based on the distance to the decision boundary.