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_{ ext{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
ceil$-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.