todo clean this up/add extensions.
Conformal prediction is a popular and practical tool in uncertainty quantification. We’re in a supervised learning setting and have a black-box model . Given a new observation , we want to develop a confidence set for its label .
It turns out we can do this simply by having access to predictions and outcomes . We need only make the assumption that the data are exchangeable, nothing else.
There are several flavors of conformal prediction, split conformal being the easiest both conceptually and in terms of implementation.
Split conformal prediction
Introduce an arbitrary score function which maps observation-label pairs to a positive number. We should think of as quantifying a heuristic notion of uncertainty, but it can be anything. If is a regressor then a popular choice is . For classification we might take if is the probability that assigns to being in class .
Our algorithm is as follows: Compute the quantile of . Call this . Then our confidence set for a new observation is
and it obeys $$ 1-\delta\leq \Pr_{(X,Y), (X_i,Y_i)_1^n}(Y\in C(X))\leq 1-\delta + 1/n,
where we note that the probability is over both the new test point and the training data. The intuition is very straightforward: we're just letting the holdout set $s(X_1,Y_1),\dots,s(X_n,Y_n)$ tell us what the most extreme values of $s(X,Y)$ are empirically. If we had access to the full distribution $s(X,Y)$, then we could compute the precise $1-\delta$ quantile $q$ and our set $C(X)$ would be an exact $1-\delta$ CI. The extra factor of $(n+1)/n$ is a finite sample correction.