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

Marginal coverage does not ensure conditional coverage, and common probability-based conformal scores can perform poorly across easy and difficult classification cases. The paper introduces a new conformity score for hold-out classification methods, which in experiments generally achieved better conditional coverage than alternatives while retaining marginal coverage.

  • Problem

    Marginal coverage does not imply conditional coverage, and common probability-based conformity scores can perform poorly across easy and difficult classification cases.

    Source: §1 · p. 1, §2.4 · p. 5

  • Method

    The paper pairs new classification conformity scores with split-conformal, cross-validation+, or jackknife+ calibration around black-box classifiers.

    Source: §3.2 · p. 6, §5 · p. 8

  • Results

    Across reported experiments, the proposed methods generally achieved better conditional coverage than alternatives while retaining marginal coverage, with prediction-set sizes comparable to selected alternatives.

    Source: §3.2 · p. 6, §4 · p. 7

  • Takeaways & Limitations

    The framework offers practitioners black-box-compatible prediction sets with options to balance computational efficiency, data parsimony, and power.

    Source: §5 · p. 8

    The cross-validation+ and jackknife+ implementation's stated coverage bound is slightly below 1−2α; guaranteeing 1−α coverage requires reducing the input α or using a conservative variant.

    Source: §2.3 · p. 5

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 introduction frames classification prediction sets as a tradeoff: guarantee marginal coverage while approximating conditional coverage and keeping sets small. It presents an oracle benchmark and previews methods that adapt black-box predictions to obtain finite-sample coverage.

1 Introduction

  • For exchangeable data, the goal is a prediction set with guaranteed marginal coverage, while approximating conditional coverage and minimizing set size.Conditional coverage cannot be achieved in theory without strong modeling assumptions, which the paper does not impose.Source: §1 · p. 1

1.1 The oracle classifier

  • The oracle’s smallest deterministic set includes the most probable labels until their conditional probabilities sum to at least 1−α; randomization can yield still tighter sets.The oracle assumes knowledge of the conditional label distribution, which is unknown in practice.Source: §1.1 · p. 2

1.2 Preview of our methods

  • The proposed methods use exchangeability-invariant black-box classifiers and adapt the threshold to account for probability-estimation errors, guaranteeing finite-sample coverage.They can use probability estimates whether or not those estimates are well-calibrated.Source: §1.2 · p. 2

1.3 Related work

  • Prior conformal classification methods target marginal coverage [7], whereas this work’s novel aim is to approximate the oracle, drawing on adaptive conformal regression [5] [8] [9] [10] [18].The paper reports better conditional coverage than direct conformal inference and distinguishes its approach from independent work.Source: §1.3 · pp. 2–3
  • The approach also accommodates cross-validation+ and jackknife+ calibration [4], while probability-calibration post-processing [6] [11] [22] is complementary but lacks provable finite-sample coverage.The paper notes it did not test post-processing empirically for space reasons.Source: §1.3 · p. 3

2 Methods

The methods use a generalized inverse-quantile score to adapt prediction sets to classification difficulty, then calibrate that score with split-conformal or cross-validation+ procedures. Their coverage guarantees rely on exchangeability, while the cross-validation+ guarantee has a stated conservativeness caveat.

2.1 Generalized inverse quantile conformity scores

  • The generalized inverse-quantile score measures the smallest threshold whose prediction set contains a label, making scores comparable across inputs under ideal probabilities.With ˆπ = π, the scores are conditionally uniform given X; the paper contrasts this with alternative scores whose distributions can vary across X.Source: §2.1 · p. 3

2.2 Adaptive classification with split-conformal calibration

  • Split-conformal calibration uses hold-out scores to choose a threshold and guarantees marginal coverage under exchangeability and a permutation-invariant learning algorithm.When scores are distinct, coverage is near tight; the guarantee holds regardless of black-box quality, while consistency can make predictions approach the oracle procedure.Source: §2.2 · pp. 3–4

2.3 Adaptive classification with cross-validation+ and jackknife+ calibration

  • Cross-validation+ replaces data splitting with fold-specific fits, using more data for prediction but at greater computational cost and often with tighter sets.Its stated coverage is slightly below 1−2α; the authors suggest using an input near α/2 for a 1−α target, while noting observed coverage is typically at least 1−α and a conservative variant guarantees that level.Source: §2.3 · pp. 4–5
  • With exact probabilities and large samples, cross-validation+ approaches the oracle decision rule by applying the score threshold 1−α.The same framework is called jackknife+ when the number of folds K equals n.Source: §2.3 · p. 5

2.4 Comparison with alternative conformal methods

  • Homogeneous conformal classification can have poor conditional coverage because one threshold treats easy and hard inputs alike, even with correct probabilities.The cited quantile-regression alternative requires extra data splitting and consistency of two black boxes; experiments suggest the proposed method gives superior conditional coverage and often smaller sets.Source: §2.4 · p. 5

3 Experiments with simulated data

In simulated classification, the proposed SC, CV+, and JK+ methods maintain stronger conditional coverage than HCC and CQC across black-box choices, while generally producing competitive prediction-set sizes. The experiments compare methods using marginal and worst-slice coverage and prediction-set cardinality.

3.1 Methods and metrics

  • The experiments compare SC and CV+/JK+ using generalized inverse quantile conformity scores with HCC and CQC, across oracle, SVC, and RFC black boxes.They focus on two settings where marginal coverage is not a good proxy for conditional coverage.Source: §3.1 · pp. 5–6
  • Evaluation fixes α = 0.1 and measures marginal coverage, estimated worst-slice conditional coverage, and prediction-set cardinality marginally and conditional on coverage.The simulated setting has 10 classes; X1 equals 1 with probability 1/5 and −8 otherwise, while X2 through X10 are independent standard normal features.Source: §3.1 · p. 6, §3.2 · p. 6, Figure 1 · p. 6

3.2 Experiments with multinomial model and inhomogeneous features

  • With oracle probabilities, SC, CV+, and JK+ achieve valid conditional coverage; with estimated probabilities, coverage is near 1 − α for SVC and only slightly below it for RFC, unlike HCC and CQC [2].The proposed methods’ sets are typically smaller than CQC’s and only slightly larger than HCC’s when probabilities are estimated; JK+ is most powerful, followed by CV+, while SC is more computationally affordable.Source: Figure 1 · p. 6, §3.2 · p. 6

4 Experiments with real data

Across Mice Protein Expression and MNIST, the proposed methods attain marginal coverage and show stronger conditional-coverage performance than HCC and CQC variants, with efficiency depending on the data and base classifier.

4 Experiments with real data

  • The original CQC calibration using a quantile neural network can be unstable and yield very wide predictions, motivating CQC-RF with quantile random forests.The study compares SC, CV+, and JK+ using generalized inverse quantile conformity scores with HCC and CQC.Source: §4 · p. 7
  • Experiments use α = 0.1 with kernel SVC, random forest, and two-layer neural network classifiers on Mice Protein Expression and MNIST.Supplementary experiments cover Fashion-MNIST and CIFAR10; JK+ is omitted on MNIST because of its higher computational cost.Source: §4 · p. 7
  • On Mice Protein Expression, all methods attain valid marginal coverage, while SC/CV+/JK+ achieve conditional coverage and HCC/CQC/CQC-RF do not.CV+ and JK+ sets are smaller than SC sets and comparable in size to HCC; original CQC performs poorly on conditional coverage and cardinality, while CQC-RF is less unstable but not much better than HCC.Source: Figure 2 · p. 7, §4 · p. 7
  • On MNIST, all methods reach 90% marginal coverage, but proposed methods achieve conditional coverage with NNet/SVC; CV+ retains coverage by true class, while HCC/CQC/CQC-RF fail.With RFC, all methods tend to undercover and the proposed methods produce larger sets than CQC-RF and HCC; with NNet, their set sizes are comparable to those baselines, and SC performs slightly worse than CV+ for coverage by true class.Source: §4 · p. 7, Figure 3 · p. 8

5 Conclusions

The paper presents a modular approach to prediction sets for multi-class classification that combines provable finite-sample coverage with favorable conditional coverage relative to alternatives.

5 Conclusions

  • The modular method uses any black-box classifier and hold-out calibration procedures to construct multi-class prediction sets with provable finite-sample coverage and favorable conditional coverage.Conformal splitting, CV+, and the jackknife+ offer options for balancing computational efficiency, data parsimony, and power.Source: §5 · p. 8
  • The authors propose exploring conformity scores based on the threshold relaxation needed for coverage in regression, beyond scores based on distance from predicted intervals [4, 18].They leave the performance of these metrics in other settings to future work.Source: §5 · p. 8
  • The Python package implements the methods and includes code to reproduce the experiments.Source: §5 · p. 8

Broader Impact

The paper presents uncertainty calibration as a way to communicate prediction reliability and compare predictors beyond accuracy, with potential relevance to fairness. Its coverage guarantees depend on exchangeability, which practitioners should assess for their data and application.

Broader Impact

  • Prediction-set size and conditional coverage can compare candidate predictors beyond accuracy, while approximate conditional coverage may reduce unwanted bias and equalized coverage can explicitly address discrimination.The authors note that equalized coverage can be incorporated into their methods, following work in a regression setting.Source: Broader Impact · p. 9
  • Coverage validity relies on exchangeability; when it is violated, as may occur with time-series data, prediction sets may lack the right coverage.The authors recommend judging whether exchangeability is reasonable using application knowledge and empirically checking predictions with the data-splitting techniques in Section 4.Source: Broader Impact · p. 9

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

The supplementary methods describe a minimax-calibrated jackknife+ variant and a finite-sample procedure for assessing conditional coverage. They also caution that the slab-based measure alone cannot establish conditional coverage more generally.

Supplementary Material for Classification with Valid and Adaptive Coverage

S1.1 Adaptive classification with minimax jackknife+ calibration

  • The minimax-calibrated jackknife+ variant uses a larger prediction set to obtain rigorous marginal coverage at level 1 − α without changing the input level.The supplement considers K = n for simplicity and applies the minimax calibration technique of.Source: S1.1 Adaptive classification with… · p. 11

S1 Supplementary methods

S1.1 Adaptive classification with minimax jackknife+ calibration

  • Under Theorem 1’s assumptions, Theorem S1 addresses Algorithm 2 with K = n and prediction set (11) replaced by (S1).The supplied passage ends before stating the theorem’s conclusion.Source: S1.1 Adaptive classification with… · p. 11

S1.2 Quantifying conditional coverage in finite samples

  • Conditional coverage is assessed over a feature-space slab whose direction and interval are chosen adversarially but independently of the data.The approach is similar to.Source: S1.2 Quantifying conditional coverage… · p. 11
  • In practice, the slab search samples 1000 unit-sphere directions, grid-searches a and b, and sets δ = 0.1.The procedure splits test data, for example 25%/75%, using the first subset to select v*, a*, b* and the second to evaluate conditional coverage.Source: S1.2 Quantifying conditional coverage… · p. 11
  • The slab-based quantity should equal nominal coverage 1 − α for a method with valid conditional coverage, regardless of optimization quality.Controlling this quantity does not establish conditional coverage more generally, so the supplement also examines coverage conditional on features such as X1 or on the true label Y.Source: S1.2 Quantifying conditional coverage… · p. 12

S2 Supplementary proofs

The supplementary proofs establish Theorem 1’s coverage bounds using exchangeability and reduce Theorem 2 to a fold-symmetric result from. Theorem S1 follows the argument for Theorem 3 in.

S2 Supplementary proofs

  • Theorem 1’s coverage proof starts from construction of prediction set (8); exchangeability of En+1 and {Ei}i∈I2 bounds the probability of event (S4) by 1 − α.The upper-bound proof follows from (S4) by applying Lemma 2 in.Source: S2 Supplementary proofs · p. 12
  • Theorem 2 is reduced to the result in by augmenting the data with test points and using fold-preserving permutation invariance plus exchangeability.The proof fits estimators after excluding pairs of folds and invokes Lemma S1 once the required invariance is verified.Source: S2 Supplementary proofs · pp. 12–13

S3 Supplementary experiments with simulated data

Supplementary simulations examine classifier and data-distribution effects: SC and CV+ show favorable approximate conditional coverage when class probabilities are learned accurately, while performance depends on the black-box classifier. The section also specifies the classifiers and simulated settings used.

S3.1 Implementation details for black-box classifiers

  • The black-box probability estimators were linear-kernel SVC and a 1,000-tree random forest (depth 5; p features per split), while CQC used quantile regression with the deep network from.The classifiers were implemented with sklearn defaults, except for the random forest’s specified number of features per split.Source: S3.1 Implementation details for… · p. 13

S3.2 Experiments with multinomial model and inhomogeneous features

  • Figure S1 covers 10-class simulations across calibration and black-box choices (100 repetitions; 10,000 training and 5,000 test samples), omitting JK+ for computational reasons.Source: Figure S1 · p. 14

S3.3 Experiments with heteroscedastic decision-tree model and discrete features

  • The four-class decision-tree experiment used five features, with labels depending on the first four; it ran 100 repetitions at 10,000 training and 5,000 test samples, with a 1,000-training-sample JK+ comparison.The large-sample experiments omit JK+ for computational convenience; Figure S4 gives the smaller-sample comparison.Source: S3.3 Experiments with heteroscedastic… · p. 15, Figure S2 · p. 15, Figure S4 · p. 17
  • With the RFC, SC and CV+ perform on par with the oracle, especially CV+, while alternatives fail to achieve conditional coverage even with the oracle; SVC-based marginal-coverage methods have poor conditional coverage and low power.Across the comparison, the proposed methods retain good approximate conditional coverage without significant power loss. The SVC fails to learn class probabilities accurately, unlike the RFC.Source: S3.3 Experiments with heteroscedastic… · p. 15, Figure S3 · p. 16

S4 Supplementary experiments with real data

Supplementary experiments compare the calibration methods with HCC and CQC on four real-data benchmarks. All methods achieve exact 90% marginal coverage, but differ in conditional coverage and prediction-set length.

S4 Supplementary experiments with real data

  • The benchmarks are MNIST, CIFAR10, Fashion-MNIST, and Mice Protein Expression.The image datasets use PCA features of length 50; the cleaned mice dataset has 1,080 samples, 77 features, and 8 classes.Source: S4 Supplementary experiments with real… · p. 18
  • Predictive models include the baseline algorithms, a 64-unit ReLU neural network, and CQC-RF, which replaces CQC’s quantile neural network with quantile random forest.For the neural network, the experiments use Adam, minibatches of 128, a learning rate of 0.01, and 20 epochs.Source: S4 Supplementary experiments with real… · p. 18
  • At a 90% target coverage, experiments compare coverage, conditional coverage, and set length, averaging performance over 100 experiments.Mice experiments use 500 or 1,000 training examples; image experiments use 500, 1,000, 5,000, or 10,000 training examples and 5,000 disjoint test samples.Source: S4 Supplementary experiments with real… · p. 18
  • All calibration methods achieve exact 90% marginal coverage; CV+ and JK+ tend to attain conditional coverage, while SC performs slightly worse and CQC, CQC-RF, and HCC fail in most cases.HCC often produces the shortest prediction sets despite failing to attain conditional coverage; the authors’ methods are typically competitive and sometimes produce smaller sets.Source: S4 Supplementary experiments with real… · p. 18

S5 Supplementary tables

Supplementary Tables S1–S4 report classification experiments on Mice Protein Expression, MNIST, Fashion-MNIST, and CIFAR10, with marginal coverage, worst-slab conditional coverage, and average prediction-set size conditional on coverage.

S5 Supplementary tables.

  • Table S1 presents Mice Protein Expression results across different training-set sizes.It reports standard deviations in parentheses and uses colors to mark conditional coverage below 0.88, above 0.9, and the smallest mean prediction-set size conditional on coverage.Source: Table S1 · p. 19

S5 Supplementary tables

  • Table S2 presents MNIST results using the same coverage and prediction-set-size measures as Table S1.Source: Table S2 · p. 20
  • Table S3 presents Fashion-MNIST results using the same measures and conventions as Table S1.Source: Table S3 · p. 21
  • Table S4 presents CIFAR10 results using the same measures and conventions as Table S1.Source: Table S4 · p. 22

Related papers

Loading 2006.02544v1…