Prediction Intervals and Split Conformal Prediction

Definition Let $(\mathbf{X}, Y)$ be a new case whose outcome $Y$ has not been observed. A prediction interval with level $1 - \alpha$, for $0 < \alpha < 1$, is an interval $C(\mathbf{X}) = [L(\mathbf{X}), U(\mathbf{X})]$, computed from observed data and the new features but not from $Y$, such that

under stated assumptions, where the probability is taken over the data used to build the interval and the new case. A confidence interval targets a fixed quantity, such as the conditional mean $E[Y \mid \mathbf{X} = \mathbf{x}]$ or a model coefficient, while a prediction interval targets one random future outcome.

Definition For the given features write $\mu(\mathbf{x}) = E[Y \mid \mathbf{X} = \mathbf{x}]$ and $\sigma^2(\mathbf{x}) = \operatorname{Var}(Y \mid \mathbf{X} = \mathbf{x})$. Aleatoric uncertainty is the variation of the outcome that remains even when the conditional distribution of $Y$ given $\mathbf{X} = \mathbf{x}$ is known exactly. Epistemic uncertainty is uncertainty about that conditional distribution itself, such as the value of $\mu(\mathbf{x})$, arising from limited data, an imperfect model or limited knowledge. For squared loss and a prediction $\hat{y} = \hat{f}(\mathbf{x})$ computed from data independent of the new outcome,

The first term is aleatoric. The second is the error of the learned function at $\mathbf{x}$, which is unknown in practice, and epistemic uncertainty is uncertainty about its size. More data or a better model with the same features can reduce the second term but not the first.

Definition A conformity score is a function $s(\mathbf{x}, y)$, chosen before any calibration label is seen and computed with the frozen predictor $\hat{f}$, that measures how poorly an outcome $y$ agrees with the prediction at $\mathbf{x}$. Here a larger score means worse agreement. Many texts call a score with this direction a nonconformity score, and some use conformity scores in which larger means better, so a score is always given with its formula. For regression the usual choice is the absolute residual

Given a threshold $q$, the prediction set at $\mathbf{x}$ contains every $y$ with $s(\mathbf{x}, y) \le q$. For the absolute residual this is the interval from $\hat{f}(\mathbf{x}) - q$ to $\hat{f}(\mathbf{x}) + q$, endpoints included, with the same width $2q$ at every input. A scaled residual $\lvert y - \hat{f}(\mathbf{x}) \rvert / \hat{\sigma}(\mathbf{x})$, with a positive spread estimate $\hat{\sigma}$ fitted on the fitting data, gives intervals $\hat{f}(\mathbf{x}) \pm q\,\hat{\sigma}(\mathbf{x})$ that widen where outcomes are expected to vary more.

Definition Split conformal prediction builds a prediction interval from a frozen predictor and a separate calibration set. The development data are split into a fitting set and a calibration set of $m \ge 1$ cases, with no case in both. The predictor $\hat{f}$ is fitted and tuned on the fitting set only and then frozen. The calibration scores $s_i = \lvert y_i - \hat{f}(\mathbf{x}_i) \rvert$ for $i = 1, \dots, m$ are sorted as $s_{(1)} \le \dots \le s_{(m)}$. For a miscoverage level $\alpha$ in $(0, 1)$ chosen in advance, the rank and the radius are

and the interval $C(\mathbf{x})$ for a new input $\mathbf{x}$ runs from $\hat{f}(\mathbf{x}) - q$ to $\hat{f}(\mathbf{x}) + q$, endpoints included. Because $0 < \alpha < 1$, the rank $k$ is always between 1 and $m + 1$, and $k = m + 1$ happens exactly when $\alpha < 1/(m + 1)$. Suppose that, given the fitting set, the $m$ calibration cases and the new case $(\mathbf{X}_{m+1}, Y_{m+1})$ are exchangeable, and that $\hat{f}$ and the score were fixed without using them. Then

If in addition the scores are distinct with probability one and $k \le m$, the coverage equals $k/(m + 1)$, which is less than $1 - \alpha + 1/(m + 1)$.

Definition Random cases $Z_1, \dots, Z_N$, here $Z_i = (\mathbf{X}_i, Y_i)$, are exchangeable if for every permutation $\pi$ of $\{1, \dots, N\}$ the reordered sequence $(Z_{\pi(1)}, \dots, Z_{\pi(N)})$ has the same joint distribution as $(Z_1, \dots, Z_N)$. Independent and identically distributed cases are exchangeable. Exchangeable cases need not be independent, as with draws without replacement from a finite pool. Split conformal prediction needs the $m$ calibration cases and the new case, so $N = m + 1$, to be exchangeable given the fitting data. Applying the same fixed score function to each of them then makes the scores $s_1, \dots, s_{m+1}$ exchangeable as well.

Definition Marginal coverage is the probability

taken jointly over the calibration set and the new case. Split conformal prediction guarantees that it is at least $1 - \alpha$ under the conditions above. Stronger properties are not guaranteed. Conditional coverage would require the same bound given $\mathbf{X}_{m+1} = \mathbf{x}$ for every input $\mathbf{x}$, and coverage within each subgroup would require it given membership in the group, and either can fail. The coverage of one realized calibration set, the fraction of future cases covered once $q$ is fixed, is itself random. When the cases are independent and identically distributed, the scores have a continuous distribution and $k \le m$, this fraction follows a beta distribution with parameters $k$ and $m + 1 - k$, whose mean is $k/(m + 1)$.