PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditional validity of inductive conformal predictors

Vladimir Vovk

arXiv:1209.2673v2cs.LG

TL;DR

The paper addresses the limited understanding of conditional coverage for inductive conformal predictors, beyond their established unconditional validity. It analyzes several conditional-validity notions and develops or characterizes ICP-based approaches, showing automatic training conditional validity, label-conditional validity through modification, and practical boundaries for object conditional validity.

  • Problem

    Inductive conformal predictors were known to control unconditional coverage, while the paper asks how stronger forms of conditional validity can be achieved.

  • Method

    The paper studies conditional-validity definitions and uses inductive conformal predictors, conditional ICPs, and related theoretical analyses to address them.

  • Results

    ICPs achieve training conditional validity automatically in PAC form, conditional ICPs achieve label conditional validity, and precise object conditional validity is generally unavailable without positive test-object probability.

  • Takeaways & Limitations

    With larger training sets, ICPs approach training conditional validity; conditional ICPs can approach example conditional validity when categories remain sufficiently large, and label-conditional ICPs can control false-positive and false-negative rates.

  • Takeaways & Limitations

    The simple training-conditional bound is somewhat crude because it is derived using Hoeffding’s inequality.

Abstract

from arXiv · show

Conformal predictors are set predictors that are automatically valid in the sense of having coverage probability equal to or exceeding a given confidence level. Inductive conformal predictors are a computationally efficient version of conformal predictors satisfying the same property of validity. However, inductive conformal predictors have been only known to control unconditional coverage probability. This paper explores various versions of conditional validity and various ways to achieve them using inductive conformal predictors and their modifications.

1 Introduction

The paper studies conditional validity for inductive conformal predictors, which offer computational efficiency but were previously known mainly for unconditional coverage. It distinguishes multiple conditioning notions and identifies which can be achieved automatically or through modifications.

  • Inductive conformal predictors improve conformal prediction’s computational efficiency while retaining finite-sample validity guarantees.
  • Figure 1 organizes eight conditional-validity notions, from TOL conditioning on everything to U unconditional validity.
  • The paper assumes independently generated examples in its standard setting, with weaker exchangeability assumptions sufficient for some results.
  • Validity requires prediction-set coverage to meet a preset level, while efficiency favors smaller prediction sets.
  • Training conditional validity is achieved automatically by ICPs in PAC form, while label and object conditional validity require different treatment.
  • Label conditional validity supports controlling set-prediction analogues of false-positive and false-negative rates, whereas precise object conditional validity is generally unavailable without positive test-object probability.

2 Inductive conformal predictors

An inductive conformal predictor splits data into proper training and calibration sets, converts conformity scores into p-values, and predicts labels using a set-valued rule. Under exchangeability, its error probability is at most the chosen significance level.

  • Each example combines an object and label, with classification and regression represented by finite-label and real-valued label spaces.
  • The training data are split into a proper training set and a calibration set used to assess conformity on new examples.
  • A conformity measure assigns scores to examples according to how well they conform to the proper training set, often using a prediction rule and similarity measure.
  • The ICP prediction set contains labels whose p-values exceed the chosen significance level ϵ.
  • Under exchangeability, the probability that the true label is excluded from the ICP prediction set does not exceed ϵ.
  • In practice, the error probability is usually close to ϵ, according to the paper’s empirical studies.

3 Training conditional validity

Training conditional validity strengthens unconditional validity by requiring high conditional coverage for most training sets. ICPs achieve this automatically through PAC-style guarantees, with exact binomial conditions refining a simpler Hoeffding-based bound.

  • Training conditional validity is formalized using two parameters: target coverage 1 − ϵ and attainment probability 1 − δ.
  • ICPs achieve (E, δ)-validity for suitable ϵ and δ, meaning conditional coverage is at least 1 − E with probability at least 1 − δ over training sets.
  • The guarantee requires a sufficiently large calibration set, with a simple recipe using n significantly larger than (−ln δ)/(2ϵ^2).
  • The proof relates ICP errors to the lower tail of a binomial distribution determined by calibration conformity scores.
  • Solving the Hoeffding bound yields a sufficient condition for Γϵ to be (E, δ)-valid.
  • The simpler Proposition 2a inequality is somewhat crude because it relies on Hoeffding’s inequality; Proposition 2b gives a more precise condition.
  • These training-conditional guarantees closely resemble PAC-type guarantees for hold-out estimates, but ICPs are not example conditional.

4 Conditional inductive conformal predictors

Conditional inductive conformal predictors refine inductive conformal prediction by conditioning calibration on categories, enabling category-specific validity. Under exchangeability, their error probability within each category is at most the significance level.

  • Conditional inductive conformal predictors: Conditional inductive conformal predictors group calibration examples by an inductive taxonomy before computing prediction-set p-values.The category may depend on the proper training set and the example being evaluated.
  • Conditional inductive conformal predictors: The conditional p-value compares conformity scores only among examples sharing the candidate example's category.The denominator counts calibration examples in the same category, while the numerator counts those whose scores are no larger, with smoothing by 1.
  • Conditional inductive conformal predictors: A label conditional ICP uses the label itself as the taxonomy category.This modification targets validity conditional on the observed label.
  • Conditional inductive conformal predictors: Label conditional validity matters because it controls set-prediction analogues of false positive and false negative rates.The paper motivates this conditioning because overall validity can hide different error probabilities across groups.
  • Conditional inductive conformal predictors: Under exchangeability, conditional ICP error probability given the new example's category does not exceed ϵ.This holds for any ϵ and any conditional ICP corresponding to the taxonomy.

5 Object conditional validity

Precise object conditional validity is incompatible with useful nontrivial prediction sets on rich object spaces at non-atomic test objects. In regression it forces infinite prediction-set measure with probability at least 1−ϵ, while in classification it forces large sets; atoms and asymptotic methods remain exceptions.

  • Object conditional validity: For rich object spaces such as R, precise object conditional validity cannot be achieved nontrivially at non-atomic objects.The negative result applies to set predictors required to satisfy object conditional validity for all distributions.
  • Object conditional validity: In regression, object conditional validity implies P^l(Λ(Γ(Z1, . . . , Zl, x)) = ∞) ≥ 1−ϵ for almost all non-atomic x.Thus, at such objects, prediction sets have infinite Lebesgue measure with probability at least 1−ϵ.
  • Object conditional validity: In classification, object conditional validity implies P^l(y ∈ Γ(Z1, . . . , Zl, x)) ≥ 1−ϵ for every label y and almost all non-atomic x.Each label is therefore likely to be included in the prediction set.
  • Object conditional validity: The expected classification prediction-set size is at least (1−ϵ)|Y|.For small ϵ, this means the prediction set is likely to be large.
  • Object conditional validity: The non-atomic restriction is essential: at an atom, an inductive conformal predictor can ignore other objects and produce narrow predictions given enough repeated training examples.This provides a concrete boundary where useful precise object conditional validity can be possible.
  • Object conditional validity: The negative result does not exclude efficient asymptotically conditionally valid predictors, including the regression construction of Lei and Wasserman (2012).The impossibility concerns precise finite-sample object conditional validity, not all asymptotic approaches.

6 Experiments

Experiments on Spambase examine unconditional and conditional behavior of inductive conformal predictors, comparing email and spam labels and object-defined regions. The results show approximate overall validity but reveal label and object-dependent differences, while log-scale plots make ICP differences from label conditional ICP more noticeable.

  • Data and setup: The Spambase experiments use 4601 examples containing email and spam classes, with a 3065-example training set and 1536-example test set.MART is used as the underlying predictor, with randomized results across different data splits and random seeds.
  • Scatter plots: The ICP and label conditional ICP look almost identical on the ordinary scatter plots, but their difference becomes more noticeable on the log scale.Figure 2 plots (pemail, pspam) for all test examples and separately by label; Figure 3 shows the analogous log-scale plots.
  • Data and setup: At 5% significance, Table 1 evaluates errors, multiple predictions, and empty predictions overall, separately by label, and across object-defined groups.The object groups split the space according to the percentage of the character $ in each message, using $ < 5.55% and $ > 5.55% as categories.
  • Observed conditional behavior: Errors, multiple predictions, and empty predictions tend to be greater for spam than for email and for email-like objects containing few $ characters.Multiple and empty predictions remain relatively uncommon because the underlying predictor’s error rate is close to 5%.
  • Practical considerations: Using a fixed significance level such as 5% facilitates comparison with theoretical results but is not recommended as the sole practical choice.The paper recommends examining behavior at several significance levels in practice.
  • Observed conditional behavior: The label conditional ICP produces error rates that are approximately equal for email and spam, as expected.The experiments do not report analogous predictable statistics for the object-conditional categories defined by the $ threshold.
  • Calibration: ICP calibration is approximately valid for email and spam separately except in the lower-left corners, where the lack of conditional validity becomes evident.The corresponding label conditional ICP calibration is shown for comparison in Figure 6.
  • Training conditional validity: Training conditional validity is not grossly violated in the reported confidence intervals, although the eight training sets are not completely independent and randomness may not be fully satisfied.Permuting the data ensures exchangeability but not necessarily randomness.

7 ICPs and ROC curves

The paper connects probability-type label conditional ICPs to ROC curves and shows that their p-value pairs lie close to the corresponding ROC curve. It also contrasts empirical, minimax, and Laplace ROC constructions.

  • 7 ICPs and ROC curves: Probability-type label conditional ICPs have a close connection to ROC curves.The paper studies this connection for ICPs whose conformity measure is probability-type.
  • 7 ICPs and ROC curves: The calibration plots show approximate validity overall and separately for email and spam, except in the lower-left corners.Figures 5 and 6 isolate these corners and compare the ordinary ICP with the label conditional ICP.
  • 7 ICPs and ROC curves: Type I error α(c) counts calibration examples with label 0 and f(xi) ≥ c, while type II error β(c) counts label-1 examples with f(xi) ≤ c.The definitions conservatively count equality at the threshold as an error.
  • 7 ICPs and ROC curves: For any object x, the pair (p0, p1) is within a bounded distance of the ROC curve.Proposition 5 gives the distance bound in terms of calibration-set class counts.
  • 7 ICPs and ROC curves: The empirical ROC curve uses k/n, whereas minimax and Laplace curves use (k+1/2)/(n+1) and (k+1)/(n+2).Figure 9 overlays these ROC variants on the lower-left region of Figure 2.
  • 7 ICPs and ROC curves: For asymmetric spam-detection costs, a one-sided label conditional ICP controls the tolerated email-as-spam rate through p0 ≤ ϵ.The paper motivates this because classifying email as spam is more harmful than allowing occasional spam.

8 Conclusion

The paper examines several forms of conditional validity and identifies when inductive conformal predictors or their conditional modifications can achieve them. It also notes practical scope limits and the efficiency cost of splitting data for training and calibration.

  • 8 Conclusion: With small training sets, the paper recommends relying on unconditional validity rather than stronger conditional guarantees.For larger training sets, training conditional validity is approached automatically by ICPs.
  • 8 Conclusion: Training conditional validity is approached automatically for larger training sets, while example conditional validity requires conditional ICPs with sufficiently large categories.The paper suggests avoiding typical categories smaller than about 100 examples.
  • 8 Conclusion: In binary classification, label conditional ICPs can control false positive and false negative rates.This is the paper’s stated application of conditional validity to the two class-specific error rates.
  • 8 Conclusion: Inductive conformal predictors provide both expectation tolerance regions and PAC-type 1 −δ tolerance regions for a proportion 1 −ϵ.The PAC-type statement is identified with Proposition 2a.
  • 8 Conclusion: For probability-type ICPs, the additional rule changing spam to email when p1 is also small can be disregarded unless ϵ is very lax.This boundary follows from Proposition 5.
  • 8 Conclusion: A limitation of ICPs is potential predictive inefficiency because separate data portions are used to develop f and calibrate conformity scores.Full conformal predictors use the full training set for both purposes.

A Training conditional validity for classical tolerance regions

The appendix relates inductive conformal predictors to classical tolerance regions through beta-distribution identities and an interpretation based on conformity scores. It shows that the relevant classical condition coincides with the ICP condition under the integer assumption on ϵ(n + 1).

  • Classical tolerance regions are a special case of conformal predictors and traditionally discard ϵ(n + 1) of n + 1 statistically equivalent blocks.The comparison assumes ϵ(n + 1) is an integer and invokes classical results on tolerance-region coverage.
  • The cumulative beta distribution function Betα,β provides the probabilistic expression used for the tolerance-region coverage calculation.Here, Betα,β denotes the cumulative beta distribution function with parameters α and β.
  • Lemma 3 establishes the beta-function identity needed to connect the appendix’s coverage expression with the ICP condition.The lemma applies for n ≥ 1, k ∈ {0, 1, …, n}, and E ∈ [0, 1].
  • The identity follows because the kth order statistic exceeding E is equivalent to at most k − 1 uniform observations falling in [0, E].This event probability yields the beta-distribution expression in equation (23).
  • ICP prediction can be viewed as a conditional version of Wilks’s predictors applied to calibration conformity scores, then transformed back into label predictions.After the proper training set, Wilks’s predictors estimate a test conformity-score range from calibration scores.
Loading 1209.2673v2…