Prediction Set
Prediction Sets are set-valued predictions with formal statistical coverage guarantees — instead of outputting a single class label, the model outputs a set of plausible labels that is guaranteed to contain the true label with specified probability (e.g., 90%) — representing a paradigm shift from point predictions to honest uncertainty communication, constructed primarily through conformal prediction methods that provide distribution-free, finite-sample valid guarantees for any base model.
What Are Prediction Sets?
- Output Format: Instead of "cat" (single prediction), the model outputs {"cat", "lynx"} (prediction set) with a 90% guarantee that the true label is included.
- Adaptive Size: Easy inputs get small sets (often singletons) while ambiguous inputs get larger sets — the set size itself communicates uncertainty.
- Coverage Property: $P(Y_{\text{true}} \in C(X)) \geq 1 - \alpha$ — the true label is in the set with probability at least $1 - \alpha$.
- Construction: Typically built using conformal prediction by including all labels whose nonconformity scores fall below a calibrated threshold.
Why Prediction Sets Matter
- Honest Uncertainty: A set of size 5 honestly communicates "I'm confused between these 5 options" rather than hiding uncertainty behind a single overconfident prediction.
- Safety-Critical Applications: Medical diagnosis — include all plausible conditions so none are missed; autonomous driving — consider all possible pedestrian trajectories.
- Decision Support: Human experts can focus attention on the set members rather than reviewing all possibilities.
- Guaranteed Coverage: Unlike top-k predictions (which have no statistical guarantee), prediction sets come with formal coverage proofs.
- Fairness: Coverage guarantees can be enforced per demographic group, ensuring equitable uncertainty across populations.
Constructing Prediction Sets
Step 1: Train any base classifier to produce scores $\hat{p}(y|x)$ for each class.
Step 2: On calibration data, compute nonconformity scores $s_i = 1 - \hat{p}(y_i|x_i)$.
Step 3: Find threshold $\hat{q}$ as the $\lceil(1-\alpha)(n+1)/n\rceil$-quantile of calibration scores.
Step 4: For new input $x$, include label $y$ if $1 - \hat{p}(y|x) \leq \hat{q}$.
Prediction Set Properties
| Property | Description |
|---|---|
| Marginal Coverage | Guaranteed: true label is in set with probability $\geq 1 - \alpha$ |
| Adaptive Size | Harder inputs produce larger sets automatically |
| Set Efficiency | Better base models produce smaller average sets |
| Singleton Rate | Fraction of predictions with set size 1 — measures practical usability |
| Empty Set Rate | Should be zero for valid conformal methods |
Applications
- Medical Imaging: Prediction set = {melanoma, benign nevus, dermatofibroma} ensures the true diagnosis is captured for specialist review.
- Autonomous Vehicles: Trajectory prediction sets covering all plausible future paths within 95% guarantee.
- Drug Discovery: Include all plausible molecular conformations satisfying coverage constraint.
- NLP Classification: Prediction sets over intents or sentiments for ambiguous queries.
Prediction Sets are AI's way of saying "I'm not sure, but the answer is definitely one of these" — transforming opaque model uncertainty into actionable, guaranteed, and appropriately-sized sets of possibilities that enable safe and informed decision-making.