Inductive Conformal Predictor
Inductive conformal predictors (IC Ps) is a modification of conformal predictors in order to improve the computational efficiency for large data sets. They are also know as "split conformal predictors".
Definition
An inductive conformal predictor (ICM) determined by a conformity measure {⚠ $A$} and an ascending sequence of positive integers {⚠ $ 0 < m_1 < m_2 < \ldots$} is a confidence predictor {⚠ $\Gamma: Z^*\times X\times (0,1)\rightarrow 2^Y$}
({⚠ $2^Y$} is a set of all subsets of {⚠ $Y$}) such that the prediction sets {⚠ $ \Gamma^\epsilon(x_1, y_1, \ldots, x_{n}, y_{n}, x_{n+1})$} are computed as follows:
- if {
⚠ $n \le m_1$}, set
{⚠ $ \Gamma^\epsilon(x_1, y_1, \ldots, x_{n}, y_{n}, x_{n+1}) := \{y \in Y: |{i = 1, \ldots,n+1: \alpha_i \le \alpha_{n+1} }| / (n+1) > \epsilon\}$},
where
{⚠ $\alpha_i := A(\{(x_1, y_1), \ldots, (x_{i-1}, y_{i-1}), (x_{i+1}, y_{i+1}), \ldots, (x_{n}, y_{n}),(x_{n+1},y)\}, (x_i, y_i)), i = 1, \ldots, n,$}
{⚠ $\alpha_{n+1} := A(\{(x_1, y_1), \ldots, (x_{n}, y_{n})\}, (x_{n+1}, y)).$}
- otherwise, find the {
⚠ $k$} such that {⚠ $m_k < n \le m_{k+1}$} and set
{⚠ $\Gamma^{\epsilon}(x_1, y_1, \ldots, x_{n}, y_{n}, x_{n+1}) := \{y \in Y: |{i = m_k + 1, \ldots,n+1: \alpha_i \le \alpha_{n+1} }| /(n + 1 - m_k) > \epsilon\}$},
where the nonconformity scores {⚠ $\alpha_i$} are defined by
{⚠ $\alpha_i := A(\{(x_1, y_1), \ldots, (x_{m_k}, y_{m_k})\}, (x_i, y_i)), i = m_k + 1, \ldots, n,$}
{⚠ $\alpha_n := A_{m_k + 1}(\{(x_1, y_1), \ldots, (x_{m_k}, y_{m_k})\}, (x_{n+1}, y))$}
and {⚠ $\{\ldots\}$} designates the bag (multiset) of observations.
The standard assumption for IC Ps as well as for conformal predictors is randomness assumption (also called the i.i.d. assumption).
Inductive conformal predictors can be generalized by Mondrian conformal predictors to a wider class of confidence predictors. Conformal predictors can be considered as an important special case of IC Ps.
Desiderata
Validity
All the statements in the section are given under the randomness assumption.
Smoothed IC Ps are defined analogously to smoothed conformal predictors:
{⚠ $ \Gamma^\epsilon(x_1, y_1, \ldots, x_{n}, y_{n}, x_{n+1})$}
is set to the set of all labels {⚠ $y \in Y$} such that
{⚠ $(|\{i=1,\ldots,n+1:\alpha_i<\alpha_{n+1}\}|+(\eta_y|\{i=1,\ldots,n+1:\alpha_i=\alpha_{n+1}\}|)/(n + 1 - m_k) > \epsilon$},
where {⚠ $j = m_k + 1, ..., n+1$}, the conformity scores {⚠ $\alpha_i$} are defined as before and {⚠ $\eta_y\in[0,1]$} is a random number.
As in the case of conformal predictors, we can formulate analogous statements for IC Ps using the same terminology.
Theorem All smoothed IC Ps are exactly valid.
Corollary All smoothed IC Ps are asymptotically exact.
Corollary All IC Ps are conservatively valid.
Corollary All IC Ps are asymptotically conservative.
To put it simply, in the long run the frequency of erroneous predictions given by IC Ps does not exceed {⚠ $\epsilon$} at each confidence level {⚠ $1 - \epsilon$}.
Efficiency
As inductive conformal predictors are automatically valid, the main goal is to improve their efficiency: to make the prediction sets IC Ps output as small as possible. See criteria of efficiency.
In comparison with corresponding conformal predictors determined by the same non-conformity measure, IC Ps are inferior in terms of predictive efficiency (however, the loss in predictive efficiency appears to be small), but outperform the C Ps in computational efficiency.