A tutorial on conformal prediction

Glenn Shafer; Vladimir Vovk

Source-linked AI summary

A tutorial on conformal prediction

Glenn Shafer, Vladimir Vovk

arXiv:0706.3188v1Jun 21, 2007cs.LGstat.ML

TL;DR

Conformal prediction addresses how to assign precise confidence to successive predictions made from accumulating data. It develops an online framework based on exchangeability and related models, showing that successive prediction regions achieve the target long-run error rate under those assumptions, while practical validity depends on their adequacy.

Problem
Standard prediction methods answer confidence questions roughly from past experience, while online prediction requires validity for successive predictions based on an accumulating dataset.
Method
The tutorial develops conformal prediction for online settings, using exchangeability and other online compression models to construct prediction regions around outputs from general prediction methods.
Results
Under exchangeability, successive conformal prediction regions are correct at least 1 − ε of the time, including the 95% case, across numerical examples and supported models.
Takeaways & Limitations
Conformal prediction provides an unusually direct interpretation of being right 95% of the time because its successive errors are probabilistically independent.
Takeaways & Limitations
The guarantees depend on assumptions such as exchangeability, which may fail in practice, and some late-date conditional probabilities remain unavailable without unknown distribution parameters.

Abstract

from arXiv · show

Conformal prediction uses past experience to determine precise levels of confidence in new predictions. Given an error probability $ε$, together with a method that makes a prediction $\hat{y}$ of a label $y$, it produces a set of labels, typically containing $\hat{y}$, that also contains $y$ with probability $1-ε$. Conformal prediction can be applied to any method for producing $\hat{y}$: a nearest-neighbor method, a support-vector machine, ridge regression, etc. Conformal prediction is designed for an on-line setting in which labels are predicted successively, each one being revealed before the next is predicted. The most novel and valuable feature of conformal prediction is that if the successive examples are sampled independently from the same distribution, then the successive predictions will be right $1-ε$ of the time, even though they are based on an accumulating dataset rather than on independent datasets. In addition to the model under which successive examples are sampled independently, other on-line compression models can also use conformal prediction. The widely used Gaussian linear model is one of these. This tutorial presents a self-contained account of the theory of conformal prediction and works through several numerical examples. A more comprehensive treatment of the topic is provided in "Algorithmic Learning in a Random World", by Vladimir Vovk, Alex Gammerman, and Glenn Shafer (Springer, 2005).

1 Introduction

Conformal prediction converts any point-prediction method into prediction regions with calibrated confidence, designed for sequential prediction on accumulating data. Under exchangeability and related models, it provides on-line validity while efficiency depends on the data distribution and nonconformity measure.

General applicability: It can wrap classification or regression methods including support-vector machines, decision trees, boosting, neural networks, and Bayesian prediction.The algorithm uses a nonconformity measure to convert the underlying point-prediction method into prediction regions.
Prediction regions: Conformal prediction turns a point prediction into a region Γε containing the true label with probability at least 1 − ε.Regions are nested across error probabilities, and classification regions may ideally contain only the predicted label.
On-line setting: The method predicts labels successively, revealing each outcome before using the accumulating examples to predict the next one.Both the point prediction and region size may depend on the new object’s observed features and preceding examples.
On-line validity: 95% on-line validity means that 95% of successive predictions are correct despite their reliance on an accumulating dataset rather than independent datasets.This is the paper’s central shift from validity over independent repetitions to validity across sequentially updated predictions.
Assumptions and efficiency: Validity holds under exchangeability, including independently sampled examples from a fixed unknown distribution, and extends to models such as the Gaussian linear model.Efficiency is separate from validity: region size depends on the distribution and chosen nonconformity measure.

2 Valid prediction regions

The paper frames prediction-region validity in an on-line setting, where intervals are repeatedly updated from overlapping observations. It explains Fisher’s normal-theory interval, shows why its successive hits remain independent, and distinguishes confidence from conditional probability.

On-line validity: 95% prediction means the interval contains the next observation 95% of the time across successive on-line predictions.The repeated predictions use accumulating information, so the envisioned repetitions differ from applying a method to independent datasets.
Fisher’s prediction interval: Fisher’s rule predicts zn from the preceding observations’ average, sample variance, and a t-distribution percentile.The resulting interval is constructed using n − 2 degrees of freedom.
Fisher’s prediction interval: The interval contains zn with probability 95% regardless of the normal distribution’s unknown mean and variance.This follows because the relevant standardized quantity has a symmetric t-distribution with n − 2 degrees of freedom.
Numerical example: For Czuber’s data, the 95% prediction interval for z20 was [9.55, 23.51], or integers 10 through 23, and the observed value was 16.The t-distribution percentile used was 2.101 with 18 degrees of freedom.
On-line validity: Successive on-line hits remain probabilistically independent despite overlapping observations, so the law of large numbers applies.The same independence extends to the generalized linear-regression setting.
Confidence versus probability: The available assumptions do not generally justify claiming a 95% conditional probability for zn after observing the preceding data.The conditional probability depends on the unknown mean and variance of the normal distribution.

3 Exchangeability

Exchangeability means that the joint distribution is unchanged by reordering examples, a condition satisfied by independent identically distributed variables but not equivalent to independence. Its backward-looking interpretation treats ordered values as random draws without replacement from their observed bag, supporting a law of large numbers for rare events.

Definition: Exchangeability requires the same joint distribution after every permutation of the variables.The definition extends to infinite sequences when every finite prefix is exchangeable.
Exchangeability and independence: Independent identically distributed variables are exchangeable, but exchangeable variables need not be independent.Exchangeability preserves identical marginal distributions while allowing dependence.
Backward-looking definitions: Conditioning on an observed bag makes every compatible ordering equally likely under exchangeability.The five-tile example has 30 compatible assignments, each with probability 1/30, and gives Pr(z5 = 4) = 2/5.
Backward-looking definitions: Backward-looking exchangeability says each next value is drawn from the current bag, with later variables independent of earlier variables conditional on that bag.The bag shrinks by one element after each backward draw.
Rare events: For large exchangeable sequences, ε-rare events occur no more than approximately an ε fraction of the time with very high probability.The betting interpretation supplies the law-of-large-numbers step used later for conformal validity.

4 Conformal prediction under exchangeability

Under exchangeability, conformal prediction applies a nonconformity measure in an on-line sequence where each label is revealed before the next prediction. The framework covers predictions from old examples alone and predictions using features of the new object, while also addressing exchangeability failure.

Framework: The conformal algorithm under exchangeability produces valid nested prediction regions.Its validity is established after choosing a nonconformity measure.
On-line prediction: In on-line prediction, each new label is predicted after observing the preceding examples and is then revealed before the next prediction.With features, the current object’s features are also available when predicting its label.
Prediction settings: The prediction-with-features setting generalizes prediction from old examples alone, whose simplicity makes it useful for explaining the algorithm.Features may be uninformative in the special case of old-examples-only prediction.
Section scope: The section organizes the method around nonconformity measures, examples with and without new-object features, optimal valid regions, and failure of exchangeability.The numerical examples are recommended as largely self-contained introductions to implementation.

4.1 Nonconformity measures

A nonconformity measure quantifies how different an example is from a reference bag and is the key link between a point predictor and conformal prediction regions. Validity tolerates any real-valued measure, whereas efficiency depends on how well it captures unusualness.

Definition: A nonconformity measure A(B, z) is a real-valued function measuring how different z is from examples in bag B.The conformal algorithm can use any such function to produce valid nested regions.
Efficiency: Efficiency depends on choosing a point predictor and nonconformity measure that represent unusual examples well.Monotonic transformations of A, such as squaring a nonnegative score, do not change the prediction regions.
Classification: Nearest-neighbor classification can measure nonconformity by comparing distances to the nearest same-label and different-label neighbors.The candidate label is evaluated using the distance structure among prior examples.
Regression: For regression, a least-squares line supplies a point prediction, and its prediction error can serve as a nonconformity measure.The fitted coefficients depend only on the bag and therefore not on example ordering.
Equivalent formulations: Including the new example when computing least-squares nonconformity scores does not change the prediction regions.The alternative formulation can simplify implementation or explanation, while the original form generalizes to on-line compression models.

4.2 Conformal prediction from old examples alone

With exchangeable examples and a chosen nonconformity measure, conformal prediction includes a candidate label when its p-value exceeds the error level. This yields valid on-line regions and, in the worked integer example, the same 95% interval as Fisher’s method without normality.

Algorithm: The conformal region consists of candidate values whose p-value pz exceeds ε.pz is the fraction of augmented examples at least as unusual as the candidate under A.
Algorithm: The algorithm provisionally adds the candidate, computes all nonconformity scores, counts scores at least as large as the candidate’s, and includes it iff pz > ε.This is the stated brute-force procedure for deciding membership in γ_ε.
Validity: Under exchangeability, successive regions are based on overlapping observations yet at least 1 − ε of them are expected to be correct.Each error is an ε-rare event, so the exchangeable-sequence law of large numbers applies.
Worked example: 95% prediction placed integer z20 between 10 and 23, inclusive, after replacing normality with exchangeability.The same interval was obtained from Fisher’s method under independent normal observations.

4.3 Conformal prediction using a new object

Conformal prediction extends classification to a new object by testing each candidate label against nonconformity scores computed from the preceding examples and the provisional candidate. In the iris example, different measures yield valid but differently informative regions, illustrating the trade-off between confidence, credibility, and efficiency.

Algorithm: The algorithm predicts a label for new object x_n by provisionally pairing it with each candidate y and computing its nonconformity relative to the preceding examples.It includes y in Γ_ε when its p-value p_y exceeds ε.
Iris example: For the sampled iris classification, the nearest-neighbor measure gives Γ0.08 = {v}, correctly predicting versicolor with 92% confidence.The observed 25th plant has sepal length 6.8, and the prediction is correct because y25 = v.
Iris example: Petal width separates the 50 setosa and 50 versicolor flowers perfectly, whereas sepal length has substantial overlap in the full dataset.All versicolor petals are at least 1 inch wide, while all setosa petals are narrower than 1 inch.
Empirical comparison: Across 1,000 samples, species-average regions were correct 918 times and produced 447 informative hits, while the three methods had similarly low rates of misleading singleton errors.The species-average method also produced empty 92% regions 5% of the time; the other measures were correct about 96% of the time.
Regression extension: For regression, conformal prediction can produce intervals comparable to conventional intervals without assuming normally distributed errors, using nearest-neighbor or least-squares nonconformity measures.The example reports intervals adjusted for measurements recorded to one decimal place.

4.4 Optimality

Conformal predictors satisfy invariance, validity, and nestedness, and are optimal among region predictors with these properties. An appropriate nonconformity measure can produce regions no larger than those of any such predictor and may tighten overly conservative confidence levels.

Conformal predictors satisfy invariance to old-example ordering, advertised coverage under exchangeability, and nested prediction regions.
Any region predictor satisfying these three conditions can be improved by a conformal predictor constructed from a suitable nonconformity measure.The constructed predictor is contained in the original predictor for every bag and significance level.
The natural nonconformity measure assigns the largest confidence level at which a candidate example is excluded by the region predictor.This measure preserves the predictor’s ranking of candidates by nonconformity.
The resulting conformal predictor may produce tighter regions when the original predictor is too conservative in its asserted confidence levels.
The optimality result relies on invariance, although non-invariant predictors may be useful for exploiting departures from exchangeability or for practical reasons.

4.5 Examples are seldom exactly exchangeable.

Conformal prediction relies on exchangeability, but the USPS examples violate this assumption because its training and test portions differ systematically. Consequently, the observed error rate can exceed the advertised 5%.

Because exchangeability is an idealization seldom matched exactly in practice, a 95% conformal predictor may err more than 5% of the time.The passage cautions that conclusions derived under exchangeability should not be expected to hold exactly in the world.
The USPS dataset is not perfectly exchangeable: its first 7291 examples differ systematically from the remaining 2007.The first group is commonly treated as training data and the second as test data.
Approximately 5% errors occur when all 9298 examples are presented in random order, satisfying exchangeability.The random ordering provides the comparison in which the conformal guarantee is observed.
The error rate is higher, especially on the test set, when the original training-then-test order is used.This ordering exposes the practical effect of the dataset's non-exchangeability.
An observed error rate of 8% instead of the promised 5% may or may not be practically acceptable.The practical importance depends on the circumstances surrounding the prediction task.

5 On-line compression models

On-line compression models summarize accumulating data while retaining enough probabilistic structure to support conformal prediction. The framework extends validity beyond exchangeability, including Gaussian linear models, but efficiency is not guaranteed universally.

5 On-line compression models: On-line compression models generalize conformal prediction from exchangeability to models that update summaries as new examples arrive.Their probabilistic content is expressed through backward-looking Markov kernels conditioned on summaries.
5 On-line compression models: Conformal prediction is optimal under exchangeability but can be very inefficient in some other on-line compression models.Thus validity extends broadly, whereas efficiency depends on the specific compression model.
5 On-line compression models: Exchangeability summarizes examples as an unordered bag, with all orderings equally likely when sampled without replacement.Backward kernels reconstruct the sequence one observation at a time by removing an observed value from the bag.
5 On-line compression models: For on-line compression models, rare successive error events occur no more than approximately their nominal fraction with very high probability.This law-of-large-numbers result underpins conformal prediction validity beyond exchangeability.
5 On-line compression models: The on-line Gaussian linear model yields the same prediction regions as classical Gaussian linear theory, while validating them on accumulating data.Its assumptions also imply a t-distribution with n−p−1 degrees of freedom for the relevant statistic.

A Validity

The appendix formalizes the law-of-large-numbers argument used to establish conformal prediction validity. It presents classical and game-theoretic proof routes and extends the result to general on-line compression models.

A Validity: The appendix formalizes the proposition that exchangeable, ε-rare successive events occur no more than approximately an ε fraction of the time.This proposition is the basis for validity in the exchangeability model.
A Validity: The classical approach proves mutual independence when the events are exactly ε-rare, then applies the weak law of large numbers.A game-theoretic approach provides an alternative route to the same validity conclusion.
A Validity: The analogous proposition for general on-line compression models is also established.This extends the validity argument beyond exchangeable sequences.
A Validity: Fisher’s normal prediction interval is a special case of conformal prediction for the Gaussian linear model, whose successive hits are independent.The appendix therefore covers the classical interval through the broader compression-model result.

A.1 A classical argument for independence

The classical argument shows that exactly ε-rare online events are mutually independent, allowing the usual law of large numbers to control their frequency. The proof generalizes by replacing the observed data bag with an online-compression summary.

A.1 A classical argument for independence: An n-event is determined by the current value z_n and the preceding unordered bag, and it is ε-rare when its conditional probability is at most ε.These definitions organize the successive error events used in the validity proof.
A.1 A classical argument for independence: Exactly ε-rare events E_1,...,E_N are mutually independent under exchangeability.Conditioning on later observations leaves the preceding event probability equal to ε, and induction yields mutual independence.
A.1 A classical argument for independence: The argument extends to general on-line compression models by replacing the preceding data bag with the summary σ_n.This substitution preserves the proof’s conditional-probability structure.
A.1 A classical argument for independence: The law of large numbers then implies that no more than approximately an ε fraction of the events occur when N is sufficiently large.The same conclusion remains valid for events whose probabilities are at most ε, though that step is initially presented intuitively.
A.1 A classical argument for independence: A fully rigorous treatment requires measure-theoretic handling of conditional probabilities and randomization to convert inequalities into equalities.The preceding proof is explicitly described as less than rigorous on these two points.

A.2 A game-theoretic law of large numbers

The game-theoretic law of large numbers replaces independent-event probabilities with upper probabilities controlled by a betting strategy. It guarantees that the observed frequency of rare events is unlikely to exceed their rarity by much.

Protocol: The backward-looking protocol lets Bill bet successively on revealed values while updating his capital and the remaining bag.Bill starts with unit capital, bets at odds determined by the bag, and removes each revealed value.
Frequency bound: If each E_n is an ε-rare n-event, the frequency Freq_N measures the fraction of events that happen.The game-theoretic law concerns whether this frequency substantially exceeds ε.
Upper probability: An event is very unlikely when Bill has a strategy guaranteeing a large capital factor without risking bankruptcy.The corresponding upper probability is small, and larger guaranteed capital factors indicate greater unlikelihood.
Frequency bound: For ε < 1/2, δ_1 > 0, δ_2 > 0, and N ≥ 1/(δ_1δ_2), the upper probability that Freq_N exceeds ε + δ_2 is less than δ_1.Thus, with sufficiently large N, the frequency is unlikely to exceed ε substantially.
Relation to classical probability: The resulting upper-probability bound matches Chebyshev’s bound when the events are independent and each has probability ε.The section also supplies an elementary self-contained proof of the proposition.

A.3 The independence of hits for Fisher’s interval

The section establishes that Fisher’s successive interval hits are mutually independent under independent normal observations. This independence makes a law-of-large-numbers argument applicable to their long-run frequency.

Consequence: Because the successive interval-hit events are independent and each has probability 1 − ε, the law of large numbers applies to their frequency.The section identifies this independence as overlooked by Fisher and subsequent authors.
Distributional foundation: For independent normal observations with a common mean and standard deviation, t_n has a t-distribution with n − 2 degrees of freedom.This distributional result is used to characterize Fisher’s interval events.
Geometric conditioning: Conditional on the sample mean and variance, the observations are uniformly distributed on the surface of an n-dimensional sphere.The joint normal density depends on the observations through the sum of squared deviations.
Distributional foundation: The ratio t_n depends only on ratios among differences, so adding a constant or multiplying differences by a nonzero constant does not change it.This invariance makes the distribution independent of the sphere’s center and radius.
Independence result: The statistics t_3, ..., t_N are mutually independent under independent normal observations with a common mean and standard deviation.This follows by combining conditional independence on lower-dimensional spheres with the invariance of the joint distribution.