Conformal Prediction Sets Quantify Information Gain: A Theoretical Perspective

Core Problem and Motivation§

Conformal prediction (CP) produces prediction sets $C(x) \subseteq \mathcal{Y}$ that satisfy finite-sample marginal coverage: $\mathbb{P}(Y \in C(X)) \geq 1 - \alpha$. Practitioners often use the set size $|C(x)|$ as a heuristic for uncertainty, but the information-theoretic meaning of this quantity is unclear. This paper formalizes set-size reduction as an information gain by introducing decision-theoretic generalizations of entropy tailored to set-valued prediction.

Theoretical Framework§

Let $\pi$ be a predictive model and $C(x)$ a conformal predictor at level $\alpha$. The authors define a family of generalized information measures parameterized by a calibration-dependent function $g$:

$$H_g(Y \mid X) = \sum_{y} \int_{0}^{1} g(\alpha) \, \mathbb{1}[y \in C_\alpha(x)] \, d\alpha$$

and similarly for joint and conditional variants. The central result is that Shannon mutual information $I(Y; X)$ admits an exact integral representation in terms of these measures:

$$I(Y; X) = \int_{0}^{1} \big[ H_g(Y) - H_g(Y \mid X) \big] w(\alpha) \, d\alpha$$

for a suitable weighting $w$ determined by the calibration map. This bridges set-valued uncertainty and classical information theory.

Key Results§

1. Sandwich Bound. In standard classification, the reduction in conformal set size when adding information $Z$ satisfies:

$$L_g(I(Y; Z)) \leq \mathbb{E}[|C(X)| - |C(X, Z)|] \leq U_g(I(Y; Z))$$

where $L_g$ and $U_g$ are calibration-dependent bounds, up to finite-sample calibration and model error terms.

1. Data Processing Inequality. Set-size reduction obeys a DPI: if $Z_1 \to Z_2$ forms a Markov chain in terms of information content, then the reduction from $Z_1$ is bounded by that from $Z_2$, preserving the monotonicity expected of an information measure.

1. Ranking Discrepancies. The authors demonstrate empirically (11 classification datasets) that set-size reduction and Shannon mutual information can rank features differently in greedy feature selection, meaning the metrics are related but not interchangeable.

Implementation Details§

CP calibration is performed via split conformal: a held-out calibration set $\mathcal{D}_{cal}$ yields nonconformity scores $s_i = 1 - \hat{p}(y_i \mid x_i)$, and the quantile threshold $\hat{q}$ defines $C(x) = \{y : 1 - \hat{p}(y \mid x) \leq \hat{q}\}$. Information gain for a feature subset $S$ is computed as the expected reduction in average set size:

$$\widehat{IG}(S) = \mathbb{E}_{x \sim \mathcal{D}_{test}} \big[ |C(x_{\emptyset})| - |C(x_S)| \big]$$

A reference PyTorch implementation of the greedy feature selection loop:

import torch

def conformal_set_size(logits, qhat, alpha):
    probs = torch.softmax(logits, dim=-1)
    scores = 1.0 - probs  # nonconformity
    in_set = scores <= qhat
    return in_set.sum(dim=-1).float().mean()

def greedy_select(model, X, y, qhat, n_features):
    selected, remaining = [], list(range(X.shape[1]))
    for _ in range(n_features):
        best, best_gain = None, -float('inf')
        for f in remaining:
            cand = selected + [f]
            with torch.no_grad():
                logits = model(X[:, cand])
            size = conformal_set_size(logits, qhat, alpha)
            gain = base_size - size  # set-size reduction
            if gain > best_gain:
                best, best_gain = f, gain
        selected.append(best)
        remaining.remove(best)
        base_size = conformal_set_size(model(X[:, selected]), qhat, alpha)
    return selected

Practical Takeaways§

• Set-size reduction is a principled proxy for mutual information, but calibration choice quantifies the gap.
• Discrepancies in feature ranking warn against blindly substituting set size for MI in selection pipelines.
• The framework generalizes to any set-valued predictor with coverage guarantees, enabling uncertainty-aware feature attribution.