Conformal Prediction: General Case and Regression

In this chapter we formally introduce conformal predictors. After giving the necessary definitions, we will prove that when a conformal predictor is used in the online mode, its output is valid, not only in the asymptotic sense that the sets it predicts for any fixed confidence level 1 − 𝜖 will be wrong with frequency at most 𝜖 (approaching 𝜖 in the case of smoothed conformal predictors) in the long run, but also in a much more precise sense: the error probability of a smoothed conformal predictor is 𝜖 at every trial and errors happen independently at different trials. In Sect. 2.6 we will see that conformal prediction is indispensable for achieving this kind of validity. The basic procedure of conformal prediction might look computationally inefficient when the label set is large, but in Sect. 2.3 we show that in the case of, e.g., least squares regression (where the label space ℝ $$\mathbb {R}$$ is uncountable) there are ways of making conformal predictors much more efficient. In addition to validity, we also discuss the efficiency of conformal predictors.