🤖 machine learning

Reliable Conformal Prediction for Ordinal Classification Using the Ranked Probability Score

This paper introduces a model-agnostic conformal prediction method for ordinal classification that utilizes the ranked probability score as a nonconformity measure to generate contiguous, median-centered prediction sets, effectively balancing set width and the severity of ordinal miscoverage across various datasets.

Original authors: Stefan Haas, Luca Killmaier, Alireza Javanmardi, Eyke Hüllermeier

Published 2026-06-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stefan Haas, Luca Killmaier, Alireza Javanmardi, Eyke Hüllermeier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Guessing with a Safety Net

Imagine you are a doctor trying to guess a patient's age, or a financial analyst trying to guess a company's risk level. In these situations, the answers aren't just random categories like "Red," "Blue," or "Green." They have a natural order: "Baby," "Child," "Teenager," "Adult," "Senior." This is called Ordinal Classification.

The problem is, even the best AI models make mistakes. Sometimes they guess "Teenager" when the person is actually a "Senior." In high-stakes fields like medicine or finance, the size of that mistake matters. Guessing "Adult" instead of "Senior" is a small error. Guessing "Baby" instead of "Senior" is a huge, dangerous error.

This paper introduces a new way to build a "safety net" around these AI predictions. Instead of giving a single guess, the AI gives a range of likely answers (a prediction set). The goal is to make sure the true answer is inside that range, while also making sure the range isn't too wide and doesn't skip over important steps in the middle.

The Problem with Old Methods: The "Greedy" Approach

Previously, most methods tried to build these safety nets by starting at the AI's "best guess" (the most likely answer) and expanding outward like a greedy eater grabbing the biggest bites of food next to it.

The Flaw: Imagine the AI is looking at a patient and thinks there's a 40% chance they are a "Teenager," a 35% chance they are a "Senior," and a tiny chance they are a "Child."

The Old Way: It starts at "Teenager" and grabs "Child" because it's the next biggest chunk of probability. It ignores "Senior" for a moment.
The Result: The safety net might end up as {Teenager, Child}. If the patient is actually a "Senior," the safety net fails completely, and the error is massive (jumping from Teenager to Senior). The old method cares more about the size of the net than the distance of the mistake.

The New Solution: The "Balanced Scale" (Ranked Probability Score)

The authors propose a new method using something called the Ranked Probability Score (RPS). Think of this as a balanced scale or a tightrope walker.

Instead of starting at the "most likely" guess and grabbing neighbors, this method looks at the entire distribution of possibilities and builds the safety net from the middle (the median) outward.

How it works:

Find the Center: It finds the middle point of the AI's uncertainty.
Expand Evenly: It adds the next most likely options to the left and right of the center, trying to keep the "weight" of the prediction balanced on both sides.
The Result: The safety net is always a contiguous block (no gaps). If the AI is unsure, the net expands to include the middle ground.

The Analogy:
Imagine you are trying to guess the temperature.

Old Method (Mode-centered): You guess "70°F" (the most likely). You add "69°F" and "71°F" because they are close. But if the real temperature is actually "50°F" (a cold snap), your net {69, 70, 71} is useless. You missed the cold entirely.
New Method (RPS/Median-centered): You look at the whole picture. If the AI is unsure between "Cold," "Mild," and "Hot," the new method builds a net that covers the entire range of "Mild" to ensure you don't miss the extremes. It prioritizes minimizing the distance of the error. If you are wrong, you want to be wrong by a little bit, not a huge bit.

Why This Matters: The "Contiguity" Rule

In ordinal problems, your safety net must be a solid block. You cannot have a net that says "It's either a Baby or a Senior, but definitely not a Child." That makes no sense.

The paper proves mathematically that their new method always produces a solid, unbroken block of answers. It doesn't need to make special assumptions about the data being "bell-shaped" (unimodal). Even if the AI is confused and thinks the answer could be two very different things (like "Baby" and "Senior" with nothing in between), this method fills in the gaps to ensure the safety net is continuous.

The "Speed" Advantage

Usually, finding the perfect safety net requires a lot of computer searching (like trying every possible combination of numbers). The authors show that their method is super fast. It's like having a shortcut that lets you calculate the perfect net in one pass, rather than searching through a maze. This makes it practical for real-world use.

The Results: A Better Balance

The authors tested this on images (like estimating age from faces or detecting disease severity in medical scans) and data tables (like credit scores).

Efficiency: The new method creates safety nets that are reasonably small (efficient).
Safety: Crucially, when the safety net does fail (the true answer is outside the net), the error is much smaller than with old methods.
- Old Method: "I guessed Teenager, but you were a Senior." (Huge error).
- New Method: "I guessed Teenager, but you were an Adult." (Small error).

Summary

This paper introduces a smarter way for AI to say, "I'm not 100% sure, but I'm pretty sure the answer is in this range."

Instead of blindly grabbing the most popular guesses, it builds a balanced, continuous safety net that ensures if the AI is wrong, it's only slightly wrong, not catastrophically wrong. It's like a tightrope walker who always keeps their balance in the middle, ensuring they never take a giant, dangerous step off the edge.

Technical Summary: Reliable Conformal Prediction for Ordinal Classification Using the Ranked Probability Score

Problem Statement

Ordinal classification (OC) involves predicting discrete labels with a natural linear order (e.g., disease severity, age groups, credit ratings). While significant progress has been made in point prediction for OC, uncertainty quantification (UQ) remains underdeveloped, particularly in high-stakes domains like medicine and finance. Standard Conformal Prediction (CP) offers distribution-free prediction sets with marginal coverage guarantees but faces specific challenges in the ordinal setting:

Contiguity: Prediction sets must be contiguous intervals (e.g., {child, teenager, adult}) to respect the label ordering. Non-contiguous sets (e.g., {child, senior}) are semantically unreasonable.
Ordinal Risk: When a true label falls outside the prediction set (miscoverage), the severity of the error depends on the ordinal distance. A method that minimizes set size (efficiency) might produce sets that, when they fail, miss the true label by a large margin, leading to catastrophic risk misestimation.
Distribution Assumptions: Existing methods often rely on greedy search procedures or enforce unimodality (a single peak in the predictive distribution) to ensure contiguity. These assumptions may not hold for complex data (e.g., bimodal distributions arising from expert disagreement) and can lead to biased uncertainty estimates.

Current approaches struggle to balance set efficiency with the minimization of ordinal miscoverage magnitude without imposing strong structural biases on the underlying predictive model.

Methodology

The authors propose a model-agnostic CP method for ordinal classification based on the Ranked Probability Score (RPS).

Core Mechanism:

Nonconformity Score: Instead of using mode-centered scores (like Least Ambiguous Set-valued Classifier or Adaptive Prediction Sets), the method uses the RPS as the nonconformity measure. The RPS is a strictly proper scoring rule defined over cumulative predictive distributions:
$\text{RPS}(X, Y) = \frac{1}{K-1} \sum_{k=1}^{K-1} (F_X(k) - \mathbb{1}\{Y \leq y_k\})^2$
where $F_X(k)$ is the predicted cumulative distribution function (CDF) and $K$ is the number of classes.
Prediction Set Construction: For a test instance $X_{n+1}$ and a miscoverage rate $\alpha$ , the prediction set is defined as:
$C_\alpha(X_{n+1}) = \{y \in \mathcal{Y} : \text{RPS}(X_{n+1}, y) \leq \hat{q}_{1-\alpha} \}$
where $\hat{q}_{1-\alpha}$ is the empirical $(1-\alpha)$ -quantile of RPS scores computed on a calibration set.

Theoretical Properties:
The paper establishes three key properties of RPS-based conformal sets:

Marginal Coverage: The method satisfies the standard marginal coverage guarantee ( $P(Y \in C(X)) \geq 1-\alpha$ ) under the exchangeability assumption, regardless of the underlying predictive model.
Contiguity and Median-Centering: Unlike mode-based approaches, RPS-based sets are contiguous by construction. The RPS score function is V-shaped around the median of the predictive distribution. Consequently, the resulting prediction sets are contiguous intervals centered at the median, not the mode. This holds even for multimodal distributions where the mode and median differ.
Ordinal Risk Optimality: Under an oracle conditional coverage setting (where the true conditional distribution is known), RPS-based sets minimize the expected $L_1$ distance (ordinal risk) between the true label and the prediction set. The method optimizes for the reduction of ordinal risk rather than just set cardinality.

Computational Efficiency:
The method is computationally efficient. While naively computing RPS for all $K$ labels takes $O(K^2)$ , the authors demonstrate a recurrence relation allowing all scores to be computed in linear time $O(K)$ . The overall complexity scales linearly with both the number of calibration points and the number of labels.

Key Contributions

Novel Nonconformity Measure: Introduction of the Ranked Probability Score (RPS) as a proper, model-agnostic nonconformity measure specifically for ordinal conformal prediction.
Theoretical Guarantees: Proof that RPS-based sets satisfy marginal coverage, are nested with respect to $\alpha$ , and are inherently contiguous and median-centered without requiring unimodality assumptions.
Risk Optimization: Demonstration that RPS-based sets directly optimize ordinal risk (set-based $L_1$ error) under oracle conditional coverage, contrasting with mode-centered methods that prioritize set efficiency.
Efficiency: A linear-time implementation algorithm that avoids the greedy search or binary search procedures required by existing ordinal CP methods.
Empirical Validation: Comprehensive evaluation across ordinal image (BACH, RetinaMNIST, FGNet) and tabular datasets, comparing against baselines like min-CPS, COPOC (LAC/APS), and OCDF.

Experimental Results

The authors evaluated the method on multiple datasets using metrics that capture both efficiency and ordinal risk:

Miscoverage Magnitude: Measured by Mean Absolute Miscoverage Magnitude (MAMM) and Worst-Case Absolute Miscoverage Magnitude (WAMM). RPS-based sets consistently achieved lower MAMM and WAMM compared to mode-centered methods (min-CPS, COPOCL, COPOCA), indicating that when errors occur, the true label is closer to the prediction set.
Efficiency vs. Risk Trade-off: Measured by the Average Interval Score Loss (AISL), which penalizes both wide intervals and large miscoverage distances. RPS-based sets achieved a favorable balance, often outperforming baselines in AISL.
Contiguity: All RPS-based sets were contiguous (CV = 0), whereas non-ordinal baselines (LAC, APS) frequently violated contiguity.
Robustness: In cases with multimodal predictive distributions (e.g., bimodal expert opinions), RPS maintained robust performance, whereas mode-centered methods tended to underestimate ordinal risk by focusing on the single highest probability peak.

Significance and Claims

The paper claims that RPS-based conformal prediction provides a robust and versatile solution for ordinal uncertainty quantification. Its primary significance lies in:

Faithful Uncertainty Representation: By being median-centered and contiguous by design, it accurately reflects the full ordinal structure and associated risks, particularly in scenarios with skewed or multimodal distributions where mode-based approaches fail.
High-Stakes Applicability: The method minimizes the severity of miscoverage, a critical requirement in domains like medical diagnosis and financial risk assessment where the cost of an error is proportional to its ordinal distance.
Practicality: It offers a computationally efficient, model-agnostic framework that does not rely on specific architectural constraints (like unimodality) or expensive search procedures, making it applicable to any underlying probabilistic predictor.

The authors conclude that while RPS-based sets may not always yield the smallest possible prediction sets (maximizing efficiency), they strike a superior balance between interval width and the magnitude of ordinal miscoverage, making them a reliable choice for real-world ordinal prediction tasks. Future work suggested includes decomposing uncertainty into epistemic and aleatoric components within this framework.