PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification with Valid and Adaptive Coverage

Yaniv Romano, Matteo Sesia, Emmanuel J. Candès

arXiv:2006.02544v1stat.MEstat.ML

TL;DR

Marginally valid classification prediction sets need not achieve conditional coverage, and common conformity scores can perform poorly across samples of differing difficulty. This paper introduces adaptive conformity scores calibrated through split-conformal, cross-validation+, or jackknife+ procedures; experiments show improved conditional coverage while maintaining marginal validity and competitive set sizes.

  • Problem

    Marginal coverage does not imply conditional coverage, while typical classification conformity scores can perform poorly across samples with differing classification difficulty.

  • Method

    The paper constructs modular multi-class prediction sets using black-box classifiers with split-conformal, cross-validation+, or jackknife+ calibration procedures.

  • Results

    90% marginal coverage is achieved, while the proposed methods generally attain conditional coverage and remain competitive in prediction-set size against alternatives.

  • Takeaways & Limitations

    The approach offers practitioners flexible options to balance computational efficiency, data parsimony, and prediction-set power when calibrating black-box classifiers.

  • Takeaways & Limitations

    The cross-validation+ and jackknife+ implementation can fall slightly below 1−2α coverage, requiring a smaller input α or a conservative variant for 1−α guarantees.

Abstract

from arXiv · show

Conformal inference, cross-validation+, and the jackknife+ are hold-out methods that can be combined with virtually any machine learning algorithm to construct prediction sets with guaranteed marginal coverage. In this paper, we develop specialized versions of these techniques for categorical and unordered response labels that, in addition to providing marginal coverage, are also fully adaptive to complex data distributions, in the sense that they perform favorably in terms of approximate conditional coverage compared to alternative methods. The heart of our contribution is a novel conformity score, which we explicitly demonstrate to be powerful and intuitive for classification problems, but whose underlying principle is potentially far more general. Experiments on synthetic and real data demonstrate the practical value of our theoretical guarantees, as well as the statistical advantages of the proposed methods over the existing alternatives.

1 Introduction

The paper develops classification prediction sets with guaranteed finite-sample marginal coverage while sensibly approximating conditional coverage, which is generally unattainable without strong modeling assumptions. Its methods adapt conformal inference to classification using exchangeable black-box classifiers and adaptive thresholding.

  • Problem setup: Given exchangeable feature-label data, the goal is a prediction set for a new categorical label with marginal coverage at level 1−α.The guarantee is required for any fixed α, sample size n, and data distribution PXY.
  • Coverage objective: Marginal coverage does not imply coverage conditional on a specific feature value, and exact conditional coverage is impossible without strong modeling assumptions.The paper therefore seeks methods that are valid marginally while sensibly approximating conditional coverage.
  • Oracle benchmark: An oracle with known PY|X forms the smallest deterministic prediction set by including the highest conditional class probabilities until their cumulative mass reaches 1−α.Randomized oracle sets can be even tighter while retaining conditional coverage at level 1−α.
  • Proposed approach: The proposed procedures approximate the unknown conditional label distribution with any order-invariant black-box classifier, including neural networks, random forests, and support vector classifiers.Naive substitution lacks guarantees, so the methods adaptively choose the threshold to account for prediction errors and guarantee finite-sample coverage.
  • Contribution: The paper’s novel contribution is explicitly approximating the classification oracle through conformal inference, with extensions using cross-validation+ and the jackknife+ for calibration.The authors report that the procedure empirically achieves better conditional coverage than direct conformal classification.

2 Methods

The methods combine a novel generalized-quantile conformity score with split-conformal, cross-validation+, and jackknife+ calibration for adaptive classification prediction sets. The procedures retain marginal coverage under exchangeability while approximating oracle conditional coverage when the black-box class-probability estimates are accurate.

  • Black-box classifier: The classifier may be any standardized black-box estimator of class probabilities, with its threshold calibrated using independent hold-out samples.Examples include neural-network softmax outputs, random forests, k-nearest neighbors, and support vector machines.
  • Conformity score: The conformity score is the smallest generalized quantile threshold whose prediction set contains the observed label.With independent uniform randomization, these scores are uniformly distributed conditional on X when ˆπ = π.
  • Split-conformal calibration: Split-conformal calibration uses exchangeable samples and a permutation-invariant learning procedure to provide the stated marginal coverage guarantee, with near-tight coverage when scores are distinct.The method splits the data into two subsets and calibrates the threshold from hold-out conformity scores.
  • Coverage and adaptivity: Marginal coverage does not depend on black-box quality, while consistent estimates with abundant data make the prediction sets approach the oracle procedure with optimal conditional coverage.This connects the finite-sample guarantee to adaptive performance under accurate probability estimation.

3 Experiments with simulated data

The simulated-data experiments compare the proposed SC, CV+, and JK+ methods with HCC and CQC across two settings where marginal coverage poorly reflects conditional coverage. With α = 0.1, evaluations show that the proposed methods maintain substantially better conditional coverage while producing slightly larger prediction sets.

  • Experimental design: The experiments compare SC and CV+/JK+ using generalized inverse quantile conformity scores against homogeneous conformal classification and conformal quantile classification.They explore two data-generating scenarios and three black-boxes: an oracle, a support vector classifier, and a random forest classifier.
  • Evaluation criteria: With α = 0.1, performance is assessed by marginal coverage, worst-slice conditional coverage, and prediction-set cardinality.Cardinality is evaluated both marginally and conditional on the true label being included in the prediction set.
  • Results: The proposed methods achieve valid conditional coverage with oracle probabilities, near-perfect coverage with SVC, and only slightly sub-nominal coverage with RFC.Alternative methods have substantially lower conditional coverage than 1 − α even when supplied with oracle probabilities.
  • Results: The proposed methods produce slightly larger prediction sets than the alternatives.This size increase accompanies their stronger conditional-coverage performance in the simulated experiments.
  • Results: 90% marginal coverage is achieved by all methods across 100 independent experiments with 1000 training samples and 5000 test samples per experiment.Figure 1 reports worst-slice conditional coverage and prediction-set size for 10-class simulated data.

4 Experiments with real data

Real-data experiments compare SC, CV+, and JK+ with HCC, CQC, and CQC-RF on Mice Protein Expression and MNIST. The proposed methods maintain marginal validity and generally provide better conditional coverage, with CV+ and JK+ retaining competitive prediction-set sizes where evaluated.

  • Experimental setup: The experiments compare SC, CV+, and JK+ against HCC, CQC, and CQC-RF using kernel SVC, random forests, and two-layer neural networks.All experiments use α = 0.1 and evaluate validity and efficiency on Mice Protein Expression and MNIST.
  • Calibration methods: The original CQC calibration can be unstable and yield very wide predictions, motivating CQC-RF as a random-forest-based alternative to its quantile neural-network estimator.CQC-RF replaces the quantile neural network estimator used in the original CQC suggestion.
  • Mice Protein Expression: On Mice Protein Expression, all methods achieve valid marginal coverage, but only SC, CV+, and JK+ attain conditional coverage.CV+ and JK+ produce smaller prediction sets than SC and sizes comparable to HCC, while CQC performs poorly on conditional coverage and efficiency.
  • MNIST: On MNIST, all methods achieve 90% marginal coverage, while the proposed methods attain valid conditional coverage with NNet or SVC base models.JK+ is omitted because of its higher computational cost; with RFC, all methods tend to undercover, suggesting poor class-probability estimates.

5 Conclusions

The paper introduces a modular classification method that combines provable finite-sample coverage with favorable conditional-coverage behavior, using black-box classifiers and flexible hold-out calibration. It also points toward adapting similar conformity scores to regression and provides an implementation package with reproducible experiment code.

  • Conclusions: The method constructs multi-class prediction sets with provable finite-sample coverage and favorable conditional-coverage behavior relative to alternatives.It is principled, versatile, and modular.
  • Conclusions: The approach supports any black-box machine-learning classifier and can be calibrated through conformal splitting, CV+, or the jackknife+.These hold-out procedures make the method broadly usable and easily calibrated.
  • Conclusions: Similar conformity scores could potentially calibrate hold-out procedures for regression, especially beyond homoscedastic settings.The paper notes that prior regression scores measure distance from predicted intervals on the Y scale, which may not be optimal otherwise.
  • Conclusions: A Python package implements the proposed methods and includes code to reproduce the experiments.The repository is available at https://github.com/msesia/arc.

Broader Impact

The paper frames its calibration methods as a step toward combining machine-learning predictive performance with practical reliability and uncertainty guarantees. Their coverage validity depends on exchangeability, motivating domain-specific assessment and empirical checks when that assumption may fail.

  • Practical reliability: The calibration methods aim to pair complex machine-learning predictions with practical guarantees about output reliability and uncertainty.The paper presents uncertainty estimation as a way to quantify and communicate machine-learning benefits and limitations.
  • Limitations: The methods’ prediction-set coverage may fail when data points are not exchangeable, such as with time-series data.The authors explicitly state that validity relies on exchangeability.
  • Limitations: Users should judge exchangeability using application-domain knowledge and can use the paper’s data-splitting techniques for empirical verification.This recommendation is intended to assess whether the assumption is reasonable in a specific setting.

Supplementary Material for Classification with Valid and Adaptive Coverage · S1 Supplementary methods

The supplementary methods introduce a minimax-calibrated jackknife+ variant with rigorous marginal coverage and describe a finite-sample procedure for assessing conditional coverage over adversarial feature-space slabs.

  • S1.1 Adaptive classification with minimax jackknife+ calibration: Minimax calibration modifies Algorithm 2 by replacing prediction set (11) with a larger set while preserving the current input level.The construction specializes to the jackknife+ case K = n.
  • S1.2 Quantifying conditional coverage in finite samples: Conditional coverage is measured over a feature-space slab whose v, a, and b values are chosen adversarially but independently of the data.This follows the approach of for quantifying conditional coverage in finite samples.
  • S1.2 Quantifying conditional coverage in finite samples: In practice, WSC is estimated using 1000 random unit-sphere directions, grid search over a and b, and δ = 0.1.The procedure partitions test data into 25% for optimization and 75% for evaluating conditional coverage.
  • S1.2 Quantifying conditional coverage in finite samples: The held-out evaluation quantity should equal nominal coverage 1 −α for methods with valid conditional coverage, regardless of optimization quality.Using separate subsets avoids finite-sample negative bias when estimating v∗, a∗, and b∗.
  • S1.2 Quantifying conditional coverage in finite samples: Controlling the slab-based quantity does not establish conditional coverage more generally, motivating alternative checks based on features or the true label.The supplementary methods therefore consider additional conditional-coverage measures beyond the slab optimization.

S2 Supplementary proofs

The supplementary proofs establish coverage by exchangeability and derive the second theorem through a fold-based reduction to prior results. They also verify the required permutation invariance and apply a supporting lemma, with a simplified bound when K=n.

  • Proof of Theorem 1: Theorem 1 obtains the lower coverage bound from the prediction-set construction and exchangeability of the conformity scores.The upper bound follows from the same event together with Lemma 2 in.
  • Proof of Theorem 2: Theorem 2 augments the training data with m test points, partitions observations into K+1 folds, and fits pairwise leave-two-fold-out class-probability estimators.The test points form fold I_K+1, while estimators involving that fold recover the original fold-specific estimators.
  • Proof of Theorem 2: The reduction verifies that the relevant random matrix is invariant under permutations that do not mix folds, using estimator order-invariance and exchangeability of the data.This establishes the symmetry condition needed to invoke Lemma S1 below.
  • Supporting lemma: Lemma S1 converts fold-preserving permutation invariance into a bound for the set F(A) at any fixed α∈(0,1), simplifying when K=n.The lemma applies to partitions of n+m points into K+1 folds with m=n/K.
  • Proof of Theorem S1: Theorem S1 is proved by the same argument as Theorem 3 in, paralleling the proof strategy for Theorem 2.Its proof is described as effectively identical to the cited result.

S3 Supplementary experiments with simulated data

Supplementary simulations evaluate the proposed classification methods across black-box probability models and calibration settings, including a more complex four-class decision-tree distribution. The results are qualitatively consistent with Section 3.2: the methods achieve good approximate conditional coverage without significant power loss, although the SVC fails to estimate class probabilities well in the complex setting.

  • Methods: The experiments use linear-kernel SVC and 1000-tree random forests as black-box classifiers, while CQC uses quantile regression with the deep neural network from.The random forest has maximum depth 5 and considers p features at each split.
  • Ten-class simulation: A separate ten-class simulation evaluates different calibration and black-box choices over 100 experiments with 10000 training and 5000 test samples, omitting JK+ for computational reasons.Other experimental details follow Figure 1.
  • Four-class simulation: A four-class simulation generates mixed discrete and continuous features, with Y|X following a decision tree based on the first four features.The feature dimension is p = 5, and the fifth feature is standard normal.
  • Four-class simulation: The four-class experiments use 10000 training samples and 5000 test samples, repeated 100 times, omitting JK+ for computational convenience.A separate Figure S4 compares methods including JK+ with smaller sample sizes.
  • Results: The proposed methods show good approximate conditional coverage relative to alternatives without significant power loss, but SVC cannot learn good class-probability estimates despite the large sample.The findings are qualitatively consistent with Section 3.2, and the more complicated conditional distribution motivates the larger sample size.

S4 Supplementary experiments with real data

Supplementary experiments on four benchmark data sets compare the proposed calibration methods with HCC and CQC under a 90% target coverage level. Across 100 experiments, all methods attain exact 90% marginal coverage, while CV+ and JK+ generally provide better conditional coverage than competing methods.

  • The study compares the proposed methods with HCC and CQC on four popular benchmark data sets.
  • MNIST and CIFAR10 are 10-class image datasets whose features are reduced to p = 50 using PCA.MNIST contains 60000 grayscale 28 × 28 images, while CIFAR10 contains 50000 RGB 32 × 32 × 3 images.
  • Experiments target 90% coverage, evaluate coverage, conditional coverage, and length, and average metrics over 100 experiments.Training examples are randomly selected from the Mice Protein Expression data set, with ntrain ∈{500, 1000} and ntest ∈{580, 80}.
  • All calibration methods achieve exact 90% marginal coverage, while CV+ and JK+ tend to achieve conditional coverage and SC performs slightly worse.In most cases, CQC, CQC-RF, and HCC fail to obtain the desired conditional coverage; HCC often produces the shortest prediction sets.

S5 Supplementary tables

The supplementary tables report experiments across four datasets, evaluating mean marginal coverage, worst-slab conditional coverage, and average prediction-set size conditional on coverage. Results are grouped by training-set size, with standard deviations and color coding highlighting coverage and set-size outcomes.

  • Mice Protein Expression: Table S1 reports results on Mice Protein Expression data using mean marginal coverage, worst-slab conditional coverage, and average prediction-set size conditional on coverage.Experiments are grouped by training-set size, with standard deviations and color coding for conditional-coverage thresholds and the smallest prediction-set size.
  • MNIST: Table S2 reports experiments on MNIST data, with the same evaluation details as Table S1.The reported setup includes the same coverage and prediction-set-size measures, training-set-size groupings, standard deviations, and color coding.
  • Fashion-MNIST: Table S3 reports experiments on Fashion-MNIST data, with the same evaluation details as Table S1.The reported setup includes the same coverage and prediction-set-size measures, training-set-size groupings, standard deviations, and color coding.
  • CIFAR10: Table S4 reports experiments on CIFAR10 data, with the same evaluation details as Table S1.The reported setup includes the same coverage and prediction-set-size measures, training-set-size groupings, standard deviations, and color coding.
Loading 2006.02544v1…