  In classification with a reject option, the classifier is allowed in
uncertain cases to abstain from prediction. The classical cost-based model of a
reject option classifier 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 coin a symmetric definition, the bounded-coverage model,
which seeks for a classifier with minimal selective risk and guaranteed
coverage. We prove that despite their different formulations the three
rejection models lead to the same prediction strategy: a Bayes classifier
endowed with a randomized Bayes selection function. We define a notion of a
proper uncertainty score as a scalar summary of prediction uncertainty
sufficient to construct the randomized Bayes selection function. We propose two
algorithms to learn the proper uncertainty score from examples for an arbitrary
black-box classifier. We prove that both algorithms provide Fisher consistent
estimates of the proper uncertainty score and we demonstrate their efficiency
on different prediction problems including classification, ordinal regression
and structured output classification.
