PaperlayerView exact revision on arXiv

Source-linked AI summary

Nested conformal prediction and quantile out-of-bag ensemble methods

Chirag Gupta, Arun K. Kuchibhotla, Aaditya K. Ramdas

arXiv:1910.10562v4stat.MEcs.AImath.STstat.ML

TL;DR

Conformal prediction must provide valid uncertainty sets without distributional assumptions, but its usual score-based presentation obscures the geometry of those sets. The paper introduces nested conformal prediction, extends it to multiple aggregation schemes, and derives QOOB. QOOB achieves state-of-the-art performance on multiple real-world datasets, while retaining coverage and computational limitations described by the authors.

  • Problem

    Conformal prediction provides valid prediction sets without distributional assumptions, but the traditional nonconformity-score view does not make prediction-set geometry explicit.

  • Method

    The paper calibrates sequences of nested prediction sets, extends the framework to cross-conformal, jackknife+, and out-of-bag methods, and derives QOOB from quantile regression, cross-conformalization, ensembles, and out-of-bag predictions.

  • Results

    QOOB achieves state-of-the-art performance on multiple real-world datasets.

  • Takeaways & Limitations

    Nested conformal provides an alternative framework that translates existing nonconformity scores and opens new procedures such as QOOB.

  • Takeaways & Limitations

    Without additional assumptions, QOOB guarantees only 1−2α coverage, is designed for real-valued responses, and is computationally intensive relative to Split-CQR at high sample sizes.

Abstract

from arXiv · show

Conformal prediction is a popular tool for providing valid prediction sets for classification and regression problems, without relying on any distributional assumptions on the data. While the traditional description of conformal prediction starts with a nonconformity score, we provide an alternate (but equivalent) view that starts with a sequence of nested sets and calibrates them to find a valid prediction set. The nested framework subsumes all nonconformity scores, including recent proposals based on quantile regression and density estimation. While these ideas were originally derived based on sample splitting, our framework seamlessly extends them to other aggregation schemes like cross-conformal, jackknife+ and out-of-bag methods. We use the framework to derive a new algorithm (QOOB, pronounced cube) that combines four ideas: quantile regression, cross-conformalization, ensemble methods and out-of-bag predictions. We develop a computationally efficient implementation of cross-conformal, that is also used by QOOB. In a detailed numerical investigation, QOOB performs either the best or close to the best on all simulated and real datasets. Code for QOOB is available at https://github.com/aigen/QOOB.

1 Introduction

The paper reframes conformal prediction as calibrating nested prediction sets to provide marginally valid uncertainty without distributional assumptions. This viewpoint unifies existing scores, extends across aggregation schemes, and motivates QOOB.

  • Predictive inference replaces point predictions with prediction sets that quantify uncertainty for sensitive applications such as medicine and finance.
  • Conformal prediction guarantees marginal coverage across arbitrary distributions, whereas conditional validity is impossible without assumptions on PXY.The paper therefore targets provable marginal validity while seeking reasonable conditional coverage empirically.
  • Nested conformal makes the geometric shape of prediction sets explicit rather than beginning with a nonconformity score.The framework is presented as an equivalent viewpoint that can represent black-box conformalized predictors and existing score constructions.
  • Nested conformal prediction starts with ordered nested sets and learns a decreasing map from tolerance α to the smallest valid set parameter.Larger set parameters produce larger prediction sets, while lower tolerance values require larger sets.
  • The framework extends split conformal ideas to cross-conformal, jackknife+, and out-of-bag methods, including the new QOOB procedure.QOOB combines quantile regression, cross-conformalization, ensemble methods, and out-of-bag predictions.
  • Nested prediction sets are also natural because oracle density-level prediction sets form a nested family as the confidence tolerance changes.

2 Split conformal based on nested prediction sets

The nested framework converts a sequence of data-dependent sets into a calibration score and prediction set. Under exchangeability, the resulting split-conformal set has a finite-sample marginal coverage guarantee and recovers standard score-based methods.

  • Nested split conformal constructs data-dependent sets Ft(x), assigns each calibration point the smallest parameter whose set contains its response, and thresholds these scores by an empirical quantile.The radius score is r(x,y)=inf{t∈T:y∈Ft(x)}, and the final set is C(x)=F_Q1−α(r,I2)(x).
  • Under exchangeability, the split-conformal prediction set satisfies marginal coverage P(Yn+1∈C(Xn+1)|training split)≥1−α.
  • The framework provides a formal route from geometric intuition about prediction-set shape to nonconformity scores and supports broader data-use schemes beyond one split.The paper notes that cross-conformal, jackknife+, and related extensions can be expressed through nested sets.
  • The nested construction recovers held-out residual scores when sets are symmetric intervals around a regression estimate.For these intervals, the smallest parameter containing y equals |y−μ̂(x)|.
  • Applying the same construction to estimated lower and upper conditional quantiles recovers the conformalized-quantiles score.The resulting score is max{q̂α/2(Xi)−Yi, Yi−q̂1−α/2(Xi)}.

3 Cross-conformal and Jackknife+ using nested sets

The nested framework extends conformal prediction to cross-conformal and jackknife+ aggregation while retaining coverage guarantees and enabling efficient computation. It also yields interval constructions that contain the cross-conformal prediction set.

  • Cross-conformal: Multiple data splits make nested conformal statistically more efficient than split conformal by using more data for training and calibration.Cross-conformal and jackknife+ require training algorithms on different subsets, while K-fold variants reduce the number of trainings.
  • Cross-conformal: Under exchangeability and permutation-invariant nested sets, leave-one-out cross-conformal coverage is at least 1 − 2α.The guarantee applies to CLOO constructed from leave-one-out nested sets.
  • Jackknife+: CLOO is contained in the jackknife+ interval, so the jackknife+ interval inherits the cross-conformal coverage guarantee.For interval-valued nested sets, the jackknife+ construction is available; general nonconformity scores need not admit such an interval.
  • Jackknife+: The convex hull of CLOO is the smallest interval containing it and does not require the nested sets themselves to be intervals.It provides an interval representation while preserving the coverage guarantee inherited from CLOO.
  • Efficient computation: The cross-conformal prediction set can be computed in O(n log n) time, matching jackknife+ prediction time when each prediction costs T.The algorithm sorts interval endpoints and processes them in one pass; its total runtime is O(n log n) + Tn.

4 Extending ensemble based out-of-bag conformal methods using nested sets

The nested framework extends out-of-bag conformal methods to ensemble-based prediction sets, using out-of-bag predictions to aggregate data-efficiently. These methods retain formal coverage guarantees and can produce interval supersets of the core OOB set.

  • Out-of-bag aggregation: Ensemble-based out-of-bag conformalization uses one ensemble to obtain multiple data splits, avoiding retraining while using all training data for prediction.This can make the procedure computationally efficient and often produce shorter prediction sets than split conformal.
  • Out-of-bag aggregation: For each training point, out-of-bag trees are those whose training bags exclude that point, and their predictions are aggregated into nested sets.Subsampling and bootstrap generate the bags used to define these out-of-bag predictions.
  • Jackknife+ after bootstrap: COOB is contained in COOB-JP, so the jackknife+ after-bootstrap interval inherits the same validity guarantee.This containment holds for every x, including when nested sets may contain empty sets.
  • Coverage: The generalized OOB method satisfies P(Yₙ₊₁ ∈ COOB(Xₙ₊₁)) ≥ 1 − 2α under the theorem’s exchangeability construction.The construction extends OOB-conformal and jackknife+ after bootstrap to arbitrary nested-set sequences.
  • Design choices: Quantile-based nested sets and OOB-style aggregation can be combined because both are expressed within the nested conformal framework.The paper contrasts mean-variance OOB sets with quantile-based sets and uses the latter in its proposed method.

5 QOOB: A novel conformal method using nested sets

QOOB combines quantile regression, cross-conformalization, ensemble methods, and out-of-bag predictions in one nested conformal method. The resulting procedure is computationally efficient and achieves strong empirical prediction-set width across the paper’s evaluation.

  • Method: QOOB merges information-efficient nested-set design with sample-efficient aggregation while maintaining conformal validity.The method combines quantile regression with out-of-bag ensemble aggregation.
  • Method: QOOB trains a quantile-regression random forest using subsampling or bootstrap, then uses each point’s out-of-bag trees to estimate lower and upper quantiles.These estimates define the nested intervals used for conformal aggregation.
  • Computation: QOOB’s aggregation step can be performed in O(n log n) time.It uses the efficient cross-conformal aggregation procedure developed earlier in the paper.
  • Validity: QOOB inherits an assumption-free 1 − 2α coverage guarantee when the ensemble count is drawn from the theorem’s appropriate binomial distribution.With fixed K, the paper reports typically obtaining 1 − α coverage in practice.
  • Empirical evaluation: QOOB achieves state-of-the-art performance across multiple real-world datasets, with competitive prediction-set width empirically.The paper also studies the effect of tree count and compares the QOOB-JP variant.

6 Numerical comparisons

Across synthetic and real-data comparisons, QOOB generally achieves the shortest or nearly shortest prediction intervals while maintaining the 1 − α coverage guarantee. Its advantages are strongest with tuned quantiles, more trees, and small training samples, although it requires more prediction computation than Split-CQR.

  • QOOB achieves the shortest or close to the shortest mean-width among compared methods while satisfying the 1 − α coverage guarantee.Split-CQR is its closest competitor.
  • QOOB typically has low standard deviation of average mean-width, indicating more reliable interval widths across simulations.This stability persists across different numbers of trees and nominal quantile levels.
  • QOOB achieves coverage 1–3% higher than the prescribed 1 − α value on every dataset, including cases where it has the shortest mean-width.The authors identify this over-coverage as a possible opportunity for further mean-width improvement.
  • 6.3 QOOB outperforms Split-CQR at small sample sizes: QOOB significantly outperforms Split-CQR on all six datasets for training sizes n ≤ 100, where sample-splitting losses are most pronounced.The study uses 100 dataset versions with 768 training and 232 testing points, and evaluates mean-width and mean-coverage.
  • 6.1 Nominal quantile selection has a significant effect on QOOB: At nominal quantile level 2α, QOOB and Split-CQR perform well, while nominal quantile selection significantly affects both methods.OOB-NCC provides a fixed baseline without nominal quantile tuning.
  • 6.2 QOOB has shorter prediction intervals as we increase the number of trees: Increasing trees improves QOOB’s interval width, unlike Split-CQR beyond 100 trees; at 400 trees, QOOB matches or exceeds Split-CQR on the highlighted datasets.QOOB also has lower standard deviation of average mean-width, while QOOB-D performs worse on every dataset.

7 Conclusion

The paper presents nested conformal prediction as an alternative framework and develops QOOB by combining quantile regression, cross-conformalization, ensembles, and out-of-bag predictions. QOOB achieves strong empirical performance, while its guarantees and computational cost remain limited.

  • Nested conformal prediction represents conformal inference through sequences of nested prediction sets.
  • QOOB combines quantile regression, cross-conformalization, ensemble methods, and out-of-bag predictions.
  • At n = 400, QOOB has MW = 2.10 and MC = 0.91, while Split-CQR has MW = 2.09 and MC = 0.90.
  • QOOB achieves state-of-the-art performance on multiple real-world datasets.
  • QOOB is guaranteed only 1 − 2α coverage without additional assumptions, is designed for real-valued responses, and can be computationally intensive.

A.1 Equivalence for non-transductive conformal methods

The appendix establishes that nested conformal prediction and score-based conformal prediction are equivalent. It also gives validity and computational results for cross-conformal constructions in the nested framework.

  • Conversely, nested sets produce nonconformity scores by taking the smallest t for which a candidate outcome enters the set.
  • Every nonconformity score induces a nested family through Ft(x) = {y : r(x,y) ≤ t}.
  • The resulting nested conformal predictor can match the original conformal prediction set for any nonconformity measure.
  • Cross-conformal validity holds under exchangeability when the fold-based nested-set constructions are permutation-invariant.
  • For interval-valued nested sets, cross-conformal aggregation after residual computation takes O(n log n) time.

B.2 Extending CV+ using nested sets

The nested framework extends CV+ and related aggregation schemes beyond one partition, including repeated subsampling and bootstrap constructions. These procedures preserve validity under exchangeability and support efficient interval computation in appropriate cases.

  • An explicit interval can contain the K-fold cross-conformal set when the nested sets are intervals.
  • The convex hull of the K-fold cross-conformal set is smaller than the CV+ interval and is recommended over CV+ in some cases.
  • Subsampling conformal combines prediction sets across repeated random subsets, with validity established under exchangeability.
  • Averaging repeated p-values is presented as a natural stabilizer because it gives equal contribution to each p-value.
  • Bootstrap aggregation is the with-replacement analogue of subsampling and corresponds to bagging.

C.2 Bootstrap conformal based on nested prediction sets

Bootstrap conformal prediction forms nested prediction sets from bootstrap bags and calibrates them using observations outside each bag. The resulting method has a validity bound, but aggregated conformal methods can be conservative.

  • Bootstrap conformal uses independently sampled bags with replacement to construct nested prediction sets.
  • For each observation outside a bootstrap bag, the method computes a score based on the nested sets trained on that bag.
  • The bootstrap prediction interval aggregates these out-of-bag scores across the sampled bags.
  • Bootstrap conformal prediction has a validity bound under exchangeability.
  • Aggregated conformal methods tend to be conservative, so the paper excludes them from its experiments.

D.2 Jackknife+ and efficiently computing CLOOpxq in the presence of empty sets

The section handles empty prediction sets in jackknife+ and cross-conformal procedures, while preserving marginal coverage guarantees and enabling efficient computation. It also develops exchangeability-based validity arguments for out-of-bag methods.

  • Efficient computation: Only indices whose nested prediction intervals are non-empty need consideration when computing jackknife+ and cross-conformal prediction sets.The set Λ_x collects precisely those indices whose intervals contain at least one candidate response.
  • Empty sets: The jackknife+ and cross-conformal intervals may be empty when too few indexed intervals are defined, yet the 1 − 2α marginal coverage guarantee remains valid.The relevant order statistic can exceed the number of eligible intervals, in which case the prediction set is defined as empty.
  • OOB validity: The lifted OOB-conformal construction makes all data points exchangeable by drawing bootstrap or subsampling sets from the enlarged index set.For each pair of excluded points, ensembles are trained on samples omitting both points and then used to form pairwise residuals.
  • OOB validity: Exchangeability of the matrix of pairwise residuals yields the OOB error bound Pr(j ∉ I(D)) ≤ 2α for every index j.The matrix construction is permutation-equivariant, allowing the theorem to apply to the lifted OOB procedure.
  • Efficient computation: Algorithm 1 computes the prediction set by sweeping sorted interval endpoints, maintaining a count of active intervals and comparing it with a conformal threshold.The count tracks the left-hand side of the membership condition, while threshold stores its right-hand side.

E.6 Proofs of results in Appendix C

The proofs establish validity of ensemble-based conformal p-values by conditioning on bootstrap randomness and exploiting exchangeability of the resulting scores. A factor-of-two adjustment yields the stated guarantee for aggregated p-values.

  • Validity proofs: Averaging the ensemble-specific p-values with a factor 2/K produces a valid aggregated p-value conditional on the ensemble samples.The proof invokes the stated aggregation result for K ≥ 2; when K = 1, the factor 2 is unnecessary.
  • Validity proofs: Conditioned on the bootstrap samples, non-test scores are exchangeable with the test score, making each ensemble-specific p-value valid.For each bag, the scores on points outside the bag and on the test point are exchangeable conditional on the bag.

F Imitating the optimal conditionally-valid prediction set

This section adapts the nested framework to approximate optimal conditionally valid prediction regions based on conditional-density level sets. The resulting conformalized sets are marginally valid, while broader optimal-region questions remain open.

  • Optimal prediction regions: For an ordered or unordered response space, the smallest prediction region achieving 1 − α conditional coverage is a conditional-density upper level set.The threshold depends on both x and α, and the resulting regions need not be intervals, making them applicable to classification.
  • Nested approximation: Estimating conditional density level-set thresholds produces a nested sequence that approximates the oracle prediction regions.The plugin threshold estimator is calibrated through the nested split-conformal procedure rather than used directly.
  • Validity and scope: The discussion focuses on regression intervals and leaves optimal prediction regions for complicated response spaces for future investigation.The authors note that interval prediction is the practical focus even though the nested density framework also supports non-interval regions.
  • Validity and scope: The conformalized density-level-set prediction set is only marginally valid, despite being motivated by conditionally valid oracle regions.The paper explicitly distinguishes the oracle motivation from the validity guarantee obtained for the estimated set.
  • Alternative estimators: The paper conjectures that a revised profile distance emphasizing similar threshold functions could improve estimation relative to an alternative profile-distance method.Suggested estimators include nearest-neighbor and kernel-smoothed variants.

G.1 Experiments with additional datasets

Additional UCI experiments broaden the comparison under default hyperparameters and show that QOOB remains competitive. Quantile methods can nevertheless overcover on light-tailed Wine datasets because conditional quantile estimation may fail away from the median.

  • Results: On 3 of 6 additional datasets QOOB performs best, while OOB-CC performs best on the other 3.These results use default settings: 100 trees, nominal quantile level 2α, and 1000 samples.
  • Results: QOOB performs better than Split-CQR on every additional dataset except WineRed.This appendix contrasts with the main-paper results, where Split-CQR was best on some datasets.
  • Dataset-specific behavior: On both Wine datasets, QOOB and Split-CQR overcover and have substantially larger mean-widths than non-quantile methods.Their coverage exceeds 0.96, unlike the other experimental results reported in the paper.
  • Dataset-specific behavior: The authors attribute the Wine behavior to very light-tailed outcomes concentrated mainly at values 5, 6, and 7.Conditional quantile estimation can fail at some points for quantile levels away from 0.5 in this setting.
  • Conclusion: The authors recommend QOOB as the most reliable general-purpose conformal method based on Tables 2 and 7.This recommendation follows the reported comparisons across the main and additional experiments.
Loading 1910.10562v4…