Learning with rejection

Overview

A standard classifier returns a label for every input, even when the label is a guess. Where a wrong label is costly, a model with a reject option can instead return a reject symbol and hand the case to another process, usually a person 2107.11277 §1. The model is a pair of a predictor h and a rejector r. It returns h(x) when the rejector accepts x and rejects otherwise 2107.11277 §2.1 2107.11277 eq. 2.

The survey separates two reasons to reject. Ambiguity rejection covers inputs whose target the features do not determine, for example overlapping classes or a poor hypothesis space 2107.11277 §2.2.1. Novelty rejection covers inputs that are rare or absent in the training data 2107.11277 §2.2.2. The underlying causes are listed as R1 to R4 2107.11277 §2.2.

Every variant follows the same decision rule: compute a score, compare it with a threshold, and reject when the score falls below it. The variants differ in where the score comes from and in whether the reject step is a separate component or part of the model.

Scoring a model with rejection

Coverage is the fraction of inputs the model answers. Accuracy on answered inputs trades off against coverage 2107.11277 §3. Outcomes are read from a confusion matrix with four cells: true accept, false accept, false reject and true reject 2107.11277 tab. 1. Accuracy alone favours low coverage, and rejection rate alone favours few rejections, so report coverage with accuracy or use the combined quality measure 2107.11277 §3.1. The rejection quality ratio divides by the misclassification rate over all inputs, not over the accepted ones 2107.11277 §3.1. The survey compares accuracy-reject curves only qualitatively 2107.11277 fig. 7 2107.11277 §3.2.

Variants

Three architectures are described. Cards: Machine Learning with a Reject Option: A survey, the only card for this concept.

Separated rejector

The rejector sees only the input. The model rejects when r(x) falls below τ; otherwise it calls the predictor 2107.11277 eq. 3 2107.11277 §4. The rejector can be a density estimate such as a Gaussian mixture or a variational autoencoder, a one-class classifier such as a one-class SVM, or a novelty score squashed into a probability 2107.11277 §4. This design fits novelty rejection. It cannot handle ambiguity, because ambiguity depends on the predictor's output 2107.11277 §4. A novelty score in which higher means more novel must be inverted or transformed before the threshold rule applies. The survey gives no standard transform 2107.11277 §4.

Card: Machine Learning with a Reject Option: A survey.

Dependent rejector

The predictor produces a confidence c_h(x) in [0, 1], and the model rejects when that confidence falls below τ 2107.11277 §5 2107.11277 eq. 4. The survey lists four ways to build the confidence 2107.11277 §5:

• Largest class posterior, max_k P(Y=k | X=x) 2107.11277 eq. 5. It targets ambiguity. The posteriors can come from a softmax, from a sigmoid calibration, or from agreement between several predictors 2107.11277 §5.
• Largest class-conditional density, max_k p(X=x | Y=k) 2107.11277 eq. 6. It targets novelty. The density is estimated with a Gaussian mixture or with nearest-neighbour heuristics, which the survey treats as heuristics and does not analyse for error 2107.11277 §5.
• Sensitivity analysis. The confidence measures how stable the prediction is under small perturbations of the parameters or the input, for example one minus the variance over perturbed predictors, or the probability that the prediction survives a perturbation 2107.11277 §5. This applies to ambiguity only 2107.11277 §5.
• Predictor properties. The confidence is read from the predictor's structure, such as the configuration of tree leaves or the weights of a self-organising map 2107.11277 §5.

Choosing the threshold τ

The survey gives four ways to set τ 2107.11277 §5:

• a target rejection rate ρ, so that P_X(c_h(x) < τ) = ρ;
• a rejection-rate bound 𝔑: minimise the error on accepted inputs while the rejection rate stays under the bound;
• an error bound 𝔐: minimise the rejection rate while the error on accepted inputs stays under the bound;
• an objective-based choice. Chow's rule picks the threshold that minimises a risk integral over the confidence distribution 2107.11277 eq. 7. Chow's rule needs calibrated posteriors; the survey says a cost-based threshold should be used when posteriors are estimated 2107.11277 §5. Tortorella's two-threshold rule instead chooses a reject band between two thresholds, using ROC-based cost terms 2107.11277 eq. 8 2107.11277 eq. 9 2107.11277 eq. 10.

The survey also covers local thresholds, one per region, such as one per class, per Voronoi cell, or per class cost 2107.11277 §5.

Card: Machine Learning with a Reject Option: A survey.

Integrated rejector

The model itself outputs a label or the reject symbol, m(x) in Y ∪ {reject} 2107.11277 eq. 11 2107.11277 §6. The model-agnostic option trains with a cost-based loss, where the rejection cost C_r lies in (0, 1/2] for classification. For optimisation the loss is replaced by a convex surrogate, logistic or hinge 2107.11277 §6. An extra output class for rejection is another route 2107.11277 §6.

Model-specific options 2107.11277 §6:

• an SVM with two hyperplanes, either one per class or two parallel hyperplanes around the boundary, so that inputs between them are rejected 2107.11277 fig. 8;
• a sigmoid rejection head m_r(x) in a neural network, which rejects when its output is below 0.5;
• two networks that reject where their signs disagree.

Card: Machine Learning with a Reject Option: A survey.

Combining rejectors

If the rejection regions of several rejectors do not overlap, reject when any of them fires. If they overlap, apply them in a fixed order, one after the other, and record which one fired 2107.11277 §7.

Card: Machine Learning with a Reject Option: A survey.

When to use which

The survey does not rank the architectures empirically, and it reports no numbers for their comparison 2107.11277 fig. 7 2107.11277 §3.2. The choices below follow from the constraints the survey states.

Cost limits depend on the normalisation the survey uses. With normalised costs, a rejection cost above 1/K for K classes makes random guessing cheaper, so rejection should not be that expensive 2107.11277 §3.3. For imbalanced classes the survey gives a tighter bound of 1 − max_k P(Y=k) 2107.11277 §3.3. The integrated convex hinge surrogate needs C_r ≤ 1/2 for convexity 2107.11277 §6.

Implementation sketch

Pseudocode in our own words. Each variant is a rule over a score. Names are illustrative.

# Separated rejector  [arxiv:2107.11277 §4] [arxiv:2107.11277 eq. 3]
# Input:  example x, rejector r, threshold tau, predictor h
# Output: a label, or REJECT

def predict_separated(x, rejector, tau, predictor):
    # The rejector sees only the input, never the predictor's output
    score = rejector(x)
    if score < tau:
        return REJECT
    return predictor(x)

# Dependent rejector  [arxiv:2107.11277 §5] [arxiv:2107.11277 eq. 4]
# Input:  example x, predictor h, confidence c_h in [0, 1], tau
# Output: a label, or REJECT

def predict_dependent(x, predictor, confidence, tau):
    # Confidence is derived from the predictor's output or internals
    if confidence(x, predictor) < tau:
        return REJECT
    return predictor(x)

# Threshold for a target rejection rate  [arxiv:2107.11277 §5]
# Input:  confidences on held-out examples, rho in [0, 1]
# Output: tau

def threshold_for_rate(confidences, rho):
    # Sort held-out confidences from lowest to highest
    ranked = sort(confidences)
    # Pick tau so that about a fraction rho falls below it. This is an
    # empirical quantile, not a guarantee; the survey states the target
    # as P_X(c_h < tau) = rho.
    tau = ranked[floor(rho * len(ranked))]
    return tau

Notes on where the variants differ. The separated rejector takes a score from the input alone. The dependent rejector takes it from the predictor, and the choice of confidence function decides whether the design targets ambiguity or novelty 2107.11277 §5. The integrated rejector has no separate step: the reject output is part of the model 2107.11277 §6.

Contradictions

None known. The survey reports no new results, and the concept has one card, so there are no competing numbers to set side by side. It does say there is no standard benchmark for models with rejection, and that most papers use custom or proprietary data, so numbers from different studies are not comparable 2107.11277 §10.2.

Papers

• Machine Learning with a Reject Option: A survey: a taxonomy of rejection types, metrics, and separated, dependent and integrated rejectors, with no experiments of its own.