Demonstration 33 · Review
Certified uncertainty bounds
Karimi and Samavi certify upper and lower bounds on the uncertainty of a single input from the size of its conformal prediction set. The bounds come from substituting the marginal coverage guarantee into a per-input formula. Two groups of inputs with valid marginal coverage and different conditional coverage both land outside the certified interval. The close reading works the same example by hand.
Setup
Ten classes with equal frequency and a classifier that outputs a probability vector for each input. Inputs come from two groups. A group A input gets probability \(0.9\) on its true class and \(0.1/9\) on each other class. A group B input gets probability \(p\) on one favoured class and \((1-p)/9\) on each other class, and the favoured class is the true class with probability \(p\). The conformal score is \(s(x, y) = 1 - \hat\pi_y(x)\), the paper’s equation (3), and the set at error level \(\delta\) is
$$C(x) = \{\, y : \hat\pi_y(x) \ge 1 - \hat q \,\}, \qquad \hat q = \text{the } \lceil (n+1)(1-\delta) \rceil\text{-th smallest calibration score}.$$For an input whose set has \(m\) elements, Theorem 2 of the paper certifies
$$L_C \le U_C(x) \le H_C, \qquad \hat u_C = \frac{m+\delta-1}{K}, \quad L_C = \hat u_C(1-\delta) + \delta - \frac{1}{n+1}, \quad H_C = \hat u_C \frac{n+2}{n+1} + \delta(1-\hat u_C),$$where \(U_C(x) = \hat u_C\,\mathbb{P}(y \in C(x)) + \mathbb{P}(y \notin C(x))\) is the paper’s equation (13). The panel draws \(n\) calibration points and 20,000 test points, computes \(\hat q\) and the sets, and evaluates (13) for each group with that group’s own probability of covering the truth. The certified interval is drawn as a bar. It has width at most \(2/(n+1)\), so at the default \(n = 1000\) it is a line.
At the defaults every set is a singleton, marginal coverage is 91%, and the certified interval for \(m = 1\) is \([0.108, 0.109]\). A group A input is covered with probability one, so (13) gives \(U_C = 0.01\). A group B input is covered with probability \(0.65\), so (13) gives \(U_C = 0.36\). Both are outside the interval, in opposite directions. The right panel sweeps the group B probability \(p\). The certified bounds do not move with \(p\) except where the threshold jumps and the group B sets change size, because they depend on the input only through \(m\). The uncertainty they are supposed to bound moves the whole way.
Raising the share of group B or lowering \(p\) eventually pushes marginal coverage below \(1-\delta\) at \(\hat q = 1-p\), and the threshold jumps to the next block of calibration scores. Group B sets then contain all ten classes, their certified interval becomes the one for \(m = 10\), and their conditional coverage becomes one. Group A sets stay singletons with conditional coverage one and \(U_C = 0.01\), still outside their interval.
Takeaway. The coverage guarantee is an average over inputs. Theorem 2 spends it as if it were a statement about each input, and the bounds that result depend on nothing but the set size. The example is a valid split conformal predictor at 91% marginal coverage in which no input satisfies the certified bounds. The two groups are atoms, so calibrating within each would give both exact coverage. The bounds fail where the conditional quantity is attainable, not only where it is not.
The paper is Karimi and Samavi, Quantifying Deep Learning Model Uncertainty in
Conformal Prediction, AAAI 2023 Summer Symposium Series, arXiv:2306.00876v2. A Python check of
the default setting is at data/reviews/karimi_check.py. Source:
js/demo33.js.