Conformal Prediction

Conformal prediction uses past experience to determine precise levels of confidence in new predictions. Given an error probability $\epsilon$, together with a method that makes a point prediction of a label $y$, it produces a set of labels, typically containing the point prediction, that also contains $y$ with probability $1-\epsilon$. Conformal prediction can be applied to any method for producing point predictions: the nearest-neighbour method, support-vector machines, ridge regression, etc.

Conformal prediction is designed for the 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 (randomness assumption), then the successive predictions will be right $1-\epsilon$ of the time, even though they are based on an accumulating dataset rather than on independent datasets.

The main classes of algorithms in conformal prediction and their variations are (the classes listed below are not disjoint):

Standard techniques used in conformal prediction include:

In addition to the model under which successive examples are sampled independently, other on-line compression models can also use conformal prediction. Examples are:

Some open problems for conformal prediction: