Split conformal prediction set for classification

Let $K\ge 2$, let the feature space be a measurable space $\mathcal{X}$, and let the label set be $\mathcal{Y}=\{1,\dots ,K\}$ with all subsets measurable. Let $H$ be a training statistic valued in a measurable rule space $\mathcal{H}$, and let $s:\mathcal{H}\times \mathcal{X}\times \mathcal{Y}\to \mathbb{R}$ be a jointly measurable score rule. The rule is fixed after training and is used unchanged on calibration and test examples. Given $m\ge 0$ calibration examples $(X_i,Y_i)$ and $0<\alpha <1$, compute $R_i=s(H,X_i,Y_i),k=\lceil (m+1)(1-\alpha )\rceil \mathrm{.}$ If $k\le m$, sort the calibration scores by the ordered keys $(R_i,i)$ and let $q$ be the score value at position $k$. If $k=m+1$, set $q=+\mathrm{\infty }$. For a feature value $x$, return the prediction set

$$C(x)=\{y\in \mathcal{Y}:s(H,x,y)\le q\}\mathrm{.}$$

For the optional tie-randomized version, use one random variable $U$ that is uniform on $[0,1]$ and independent of the training information and all calibration and test examples, shared across the candidate-label scan. For $r_y=s(H,x,y)$, define $p_U(y)=\frac{\mathrm{\#}\{i\le m:R_i>r_y\}+U(1+\mathrm{\#}\{i\le m:R_i=r_y\})}{m+1},C_U(x)=\{y\in \mathcal{Y}:p_U(y)>\alpha \}\mathrm{.}$ The candidate is included in its own tie group. The algorithm defines these sets; any coverage claim requires separate distributional hypotheses.

Statistics and estimators: a training statistic is a measurable map into its stated measurable rule space.

Conformal scores and rank p-values: fixes the split-score convention, upper-rank formula, tie randomization, and independent uniform input.

Split conformal prediction set: supplies the general split-conformal quantile construction, including the $+\mathrm{\infty }$ sentinel.

Finite order statistics and rank maps are measurable: gives measurability of the finite score order statistic and rank maps.

Independent sigma-algebras and independent events: defines independence of the optional uniform variable from the data.

Lei et al., full paper, Section 2.2 and Appendix A.1: gives the split-conformal order-statistic construction and its finite-sample exchangeable-rank argument for regression.

Tibshirani, full lecture notes, Sections 1.2–2: derives the adjusted rank, split calibration score, sentinel convention, and optional exact tie randomization.