New Paradigms in Modern Statistics I

Algorithm

The general split conformal algorithm, starting from adaptive prediction sets for classification, with application examples.

A standard conformal prediction procedure starts from a supervised dataset, i.e., data with labels. We denote the calibration dataset by $\mathcal D = \{(X_i, Y_i)\}_{i=1}^{n} \in (\mathcal X \times \mathcal Y)^n$ , kept separate from the training data used to fit the model, and the new target test point by $X_{\text{new}}$ . Given a black-box model $\hat f$ , we also start from some heuristic notion of uncertainty, which we call the score function. For example, the score can simply be the softmax score of a classification model, or the residual if we are doing regression.

For a target coverage level $1-\alpha$ , the general conformal prediction algorithm is:¹

Compute the scores. $S = \{ s(X_i, Y_i) \}_{i=1}^{n}$ .
Compute the quantile. $\hat q = \mathrm{Quantile}\big(S;\ \lceil (n+1)(1-\alpha) \rceil / n\big)$ .
Return the prediction set. $\mathcal C(X_{\text{new}}) = \{ y \in \mathcal Y : s(X_{\text{new}}, y) \le \hat q \}$ .

For example, consider the Adaptive Prediction Sets (APS) algorithm, which is best known for the discrete case, i.e., $\mathcal Y = \{1, \dots, K\}$ . Here, we set the score function as

s(x, y) = \sum_{k=1}^{K} \hat\pi_k(x)\, \mathbf{1}\{\hat\pi_k(x) \ge \hat\pi_y(x)\},

where $\hat\pi_k(x)$ is the softmax output of $\hat f$ for class $k$ , and $y \in \mathcal Y$ denotes the true label of $x$ . In other words, the score function indicates how difficult it is, for a given input, to guess its label correctly.² The full method is described below.

Classification example: APS

Split the labeled data into three disjoint parts: a training set of size $N$ that fits the black box $\hat f$ , a calibration set of size $n$ , and a validation set of size $n_{\text{val}}$ held out to check coverage.
Pass every calibration and validation point through $\hat f$ once and cache its score $S_i = s(X_i, Y_i)$ . For APS, sort the softmax outputs and add them up from the top until you reach the true label.
Collect the calibration scores $S_1, \dots, S_n$ and set $\hat q$ to their $\lceil (n+1)(1-\alpha) \rceil / n$ empirical quantile.
Run $\hat f$ on the new input, sort its softmax outputs again, and keep the labels whose cumulative mass stays below $\hat q$ : $\mathcal C(x_{\text{new}}) = \{ y : s(x_{\text{new}}, y) \le \hat q \}$ .

This is called split conformal prediction. An algorithm without an explicit calibration set is called full conformal prediction. ↩
The score is defined this way in order to satisfy adaptiveness. ↩

Classification example: APS

Footnotes