Confidence Predictor

A confidence predictor is essentially a prediction algorithm producing prediction regions. In the context of conformal prediction, we assume that Reality outputs successive pairs

  (x_1, y_1), (x_2, y_2), \ldots

called observations. The objects $x_i$ are elements of a measurable space $\mathbf{X}$ and the labels $y_i$ are elements of a measurable space $\mathbf{Y}$.

We call $\mathbf{Z}:=\mathbf{X}\times\mathbf{Y}$ the observation space, $\epsilon\in(0,1)$ the significance level, and the complimentary value $1 - \epsilon$ the confidence level.

A confidence predictor is a measurable function $\Gamma: \mathbf{Z}^*\times \mathbf{X}\times (0,1)\to 2^Y$ ($2^{\mathbf{Y}}$ is a set of all subsets of $\mathbf{Y}$) that satisfies

  \Gamma^{\epsilon_1}(x_1, y_1, \ldots, x_n, y_n, x_{n+1})
  \Gamma^{\epsilon_2}(x_1, y_1, \ldots, x_n, y_n, x_{n+1})

for all significance levels $\epsilon_1\ge\epsilon_2$, all positive integers $n$, and all incomplete data sequences $x_1, y_1, \ldots, x_n, y_n, x_{n+1}$. Thus, a confidence predictor is an algorithm that given an incomplete data sequence and $\epsilon \in (0,1)$ (the significance level), outputs a subset $ \Gamma^\epsilon(x_1, y_1, \ldots, x_n, y_n, x_{n+1})$ of $\mathbf{Y}$ (the prediction region) so that the condition above is satisfied.