Skip to main content

hyprstream_calibration/
conformal.rs

1//! Conformal nonconformity scores and prediction sets.
2//!
3//! Split-conformal usage: compute a nonconformity score per calibration observation, take
4//! the finite-sample-corrected quantile ([`conformal_quantile`]) at the target
5//! miscoverage `α`, and construct prediction sets on new observations from the same
6//! score. All scores are deterministic (no randomized tie-breaking), which makes them
7//! slightly conservative and fully reproducible.
8//!
9//! - **Nominal** (`noul`/`choice`): [`aps_nonconformity`] / [`aps_set`] (Romano et al.
10//!   2020) and [`raps_nonconformity`] / [`raps_set`] (Angelopoulos et al. 2021).
11//! - **Ordinal** (`score`): probability-sorted sets are order-blind and can be
12//!   non-contiguous over an ordered scale, which is semantically broken for a score
13//!   (S6b2). This module provides the ordinal alternatives MAPIE does not ship:
14//!   - [`rps_nonconformity`] / [`ordinal_set_rps`] — RPS-based nonconformity; sets are
15//!     median-centered contiguous intervals by construction (Haas et al. 2026,
16//!     arXiv:2606.24959);
17//!   - [`ordinal_aps_interval`] — contiguous interval grown around the mode (Ordinal APS;
18//!     Lu, Angelopoulos, Pomerantz 2022, arXiv:2207.02238);
19//!   - [`min_cps_nonconformity`] / [`min_cps_interval`] — minimum-length contiguous
20//!     sliding-window sets (min-CPS style; Zhang et al. 2025, arXiv:2511.16845).
21//!
22//! Ordinal sets are returned as inclusive index intervals `(lo, hi)` over levels and are
23//! always contiguous; any score-defined label set is returned as its contiguous hull.
24
25use crate::error::MetricError;
26use crate::metrics::{argmax, rps_single};
27
28/// Finite-sample-corrected split-conformal quantile of calibration nonconformity scores:
29/// the `⌈(n+1)(1−α)⌉`-th smallest score. Returns [`f64::INFINITY`] when the rank exceeds
30/// `n` (the prediction set is then "everything" — the guarantee is uninformative at
31/// requested `α` for this calibration size).
32///
33/// # Errors
34/// [`MetricError::EmptyInput`] on empty scores; [`MetricError::InvalidLevel`] for `α`
35/// outside `(0, 1)`.
36pub fn conformal_quantile(scores: &[f64], alpha: f64) -> Result<f64, MetricError> {
37    if scores.is_empty() {
38        return Err(MetricError::EmptyInput("conformal quantile"));
39    }
40    if !(0.0..1.0).contains(&alpha) {
41        return Err(MetricError::InvalidLevel { value: alpha });
42    }
43    let mut sorted: Vec<f64> = scores.to_vec();
44    sorted.sort_by(f64::total_cmp);
45    #[allow(clippy::cast_precision_loss)]
46    let n = sorted.len() as f64;
47    let rank = ((n + 1.0) * (1.0 - alpha)).ceil();
48    #[allow(clippy::cast_sign_loss)]
49    if rank > n {
50        return Ok(f64::INFINITY);
51    }
52    let idx = (rank as usize).max(1) - 1;
53    Ok(sorted[idx])
54}
55
56/// Class indices sorted by descending probability, earliest index first on ties (profile
57/// decision D6).
58fn rank_order(probs: &[f64]) -> Vec<usize> {
59    let mut order: Vec<usize> = (0..probs.len()).collect();
60    order.sort_by(|&a, &b| f64::total_cmp(&probs[b], &probs[a]));
61    order
62}
63
64/// APS nonconformity: cumulative probability mass, in descending-probability order, up to
65/// and including the realized label. Deterministic (the full label mass is included),
66/// hence slightly conservative vs the randomized form.
67#[must_use]
68pub fn aps_nonconformity(probs: &[f64], label: usize) -> f64 {
69    let order = rank_order(probs);
70    let mut cumulative = 0.0;
71    for &idx in &order {
72        cumulative += probs[idx];
73        if idx == label {
74            break;
75        }
76    }
77    cumulative
78}
79
80/// APS prediction set: labels in descending-probability order until the cumulative mass
81/// reaches `qhat`; the crossing label is included.
82#[must_use]
83pub fn aps_set(probs: &[f64], qhat: f64) -> Vec<usize> {
84    let order = rank_order(probs);
85    let mut set = Vec::new();
86    let mut cumulative = 0.0;
87    for &idx in &order {
88        set.push(idx);
89        cumulative += probs[idx];
90        if cumulative >= qhat {
91            break;
92        }
93    }
94    set
95}
96
97/// RAPS nonconformity: APS cumulative mass plus the regularization penalty
98/// `lambda · max(rank(label) − k_reg, 0)` where `rank` is the 1-based rank in
99/// descending-probability order (Angelopoulos et al. 2021). `k_reg` is the number of
100/// penalty-free top ranks.
101#[must_use]
102pub fn raps_nonconformity(probs: &[f64], label: usize, k_reg: usize, lambda: f64) -> f64 {
103    let order = rank_order(probs);
104    let mut cumulative = 0.0;
105    for (zero_rank, &idx) in order.iter().enumerate() {
106        cumulative += probs[idx];
107        if idx == label {
108            let rank = zero_rank + 1;
109            #[allow(clippy::cast_precision_loss)]
110            let penalty = lambda * rank.saturating_sub(k_reg) as f64;
111            return cumulative + penalty;
112        }
113    }
114    cumulative
115}
116
117/// RAPS prediction set: labels in rank order while the penalized cumulative mass stays
118/// below `qhat`; the crossing label is included.
119#[must_use]
120pub fn raps_set(probs: &[f64], qhat: f64, k_reg: usize, lambda: f64) -> Vec<usize> {
121    let order = rank_order(probs);
122    let mut set = Vec::new();
123    let mut cumulative = 0.0;
124    for (zero_rank, &idx) in order.iter().enumerate() {
125        let rank = zero_rank + 1;
126        #[allow(clippy::cast_precision_loss)]
127        let penalty = lambda * rank.saturating_sub(k_reg) as f64;
128        set.push(idx);
129        cumulative += probs[idx] + penalty;
130        if cumulative >= qhat {
131            break;
132        }
133    }
134    set
135}
136
137/// RPS-based ordinal nonconformity: the ranked probability score of the candidate label
138/// against the predicted histogram (Haas et al. 2026). Cheap and model-agnostic; the
139/// induced sets are median-centered and contiguous by construction.
140#[must_use]
141pub fn rps_nonconformity(probs: &[f64], label: usize) -> f64 {
142    rps_single(probs, label)
143}
144
145/// RPS-CP prediction interval: the contiguous hull of `{k : rps_nonconformity(p, k) ≤
146/// qhat}`. (The raw set is already contiguous for unimodal histograms; the hull
147/// guarantees the interval contract for multimodal ones.) Falls back to the
148/// lowest-nonconformity single level if no level clears `qhat`.
149#[must_use]
150pub fn ordinal_set_rps(probs: &[f64], qhat: f64) -> (usize, usize) {
151    let mut lo = usize::MAX;
152    let mut hi = 0usize;
153    let mut best = 0usize;
154    let mut best_score = f64::INFINITY;
155    for k in 0..probs.len() {
156        let s = rps_single(probs, k);
157        if s < best_score {
158            best_score = s;
159            best = k;
160        }
161        if s <= qhat {
162            lo = lo.min(k);
163            hi = hi.max(k);
164        }
165    }
166    if lo > hi {
167        (best, best)
168    } else {
169        (lo, hi)
170    }
171}
172
173/// Ordinal APS interval (Lu, Angelopoulos, Pomerantz 2022): start at the modal level and
174/// grow a contiguous interval, always extending toward the adjacent side with the larger
175/// probability, until the enclosed mass reaches `qhat`.
176#[must_use]
177pub fn ordinal_aps_interval(probs: &[f64], qhat: f64) -> (usize, usize) {
178    if probs.is_empty() {
179        return (0, 0);
180    }
181    let mode = argmax(probs);
182    let (mut lo, mut hi) = (mode, mode);
183    let mut mass = probs[mode];
184    while mass < qhat && (lo > 0 || hi + 1 < probs.len()) {
185        let left = if lo > 0 {
186            probs[lo - 1]
187        } else {
188            f64::NEG_INFINITY
189        };
190        let right = if hi + 1 < probs.len() {
191            probs[hi + 1]
192        } else {
193            f64::NEG_INFINITY
194        };
195        if left >= right {
196            lo -= 1;
197            mass += probs[lo];
198        } else {
199            hi += 1;
200            mass += probs[hi];
201        }
202    }
203    (lo, hi)
204}
205
206/// The minimum-length contiguous window whose mass is at least `threshold`; ties break
207/// toward higher mass, then toward the leftmost window. `O(K²)` via prefix sums.
208fn min_length_window(probs: &[f64], threshold: f64) -> (usize, usize) {
209    let k = probs.len();
210    let mut prefix = vec![0.0f64; k + 1];
211    for (i, &p) in probs.iter().enumerate() {
212        prefix[i + 1] = prefix[i] + p;
213    }
214    let mass = |a: usize, b: usize| prefix[b + 1] - prefix[a];
215    for len in 1..=k {
216        let mut best: Option<(usize, usize)> = None;
217        for a in 0..=(k - len) {
218            let b = a + len - 1;
219            if mass(a, b) < threshold {
220                continue;
221            }
222            match best {
223                None => best = Some((a, b)),
224                Some((ba, bb)) => {
225                    if mass(a, b) > mass(ba, bb) {
226                        best = Some((a, b));
227                    }
228                }
229            }
230        }
231        if let Some(w) = best {
232            return w;
233        }
234    }
235    (0, k.saturating_sub(1))
236}
237
238/// min-CPS-style nonconformity (Zhang et al. 2025): the smallest mass threshold `τ` at
239/// which the minimum-length contiguous window with mass `≥ τ` contains the realized
240/// label. Computed by enumerating candidate thresholds (distinct contiguous-window
241/// masses); `O(K³)` worst case, intended for calibration-fitting batches, with the
242/// serving-time set constructed by [`min_cps_interval`].
243#[must_use]
244pub fn min_cps_nonconformity(probs: &[f64], label: usize) -> f64 {
245    let k = probs.len();
246    let mut prefix = vec![0.0f64; k + 1];
247    for (i, &p) in probs.iter().enumerate() {
248        prefix[i + 1] = prefix[i] + p;
249    }
250    let mut masses: Vec<f64> = Vec::with_capacity(k * (k + 1) / 2);
251    for a in 0..k {
252        for b in a..k {
253            masses.push(prefix[b + 1] - prefix[a]);
254        }
255    }
256    masses.sort_by(f64::total_cmp);
257    masses.dedup();
258    for &tau in &masses {
259        let (lo, hi) = min_length_window(probs, tau);
260        if lo <= label && label <= hi {
261            return tau;
262        }
263    }
264    // The full-range window always contains the label, so this is unreachable for a
265    // valid label; fall back to the total mass defensively.
266    prefix[k]
267}
268
269/// min-CPS prediction interval: the contiguous hull of `{k : min_cps_nonconformity(p, k)
270/// ≤ qhat}` — the minimum-length contiguous set with the calibrated coverage guarantee.
271#[must_use]
272pub fn min_cps_interval(probs: &[f64], qhat: f64) -> (usize, usize) {
273    if probs.is_empty() {
274        return (0, 0);
275    }
276    let mut lo = usize::MAX;
277    let mut hi = 0usize;
278    for k in 0..probs.len() {
279        if min_cps_nonconformity(probs, k) <= qhat {
280            lo = lo.min(k);
281            hi = hi.max(k);
282        }
283    }
284    if lo > hi {
285        (0, probs.len() - 1)
286    } else {
287        (lo, hi)
288    }
289}
290
291/// Validate that a distribution is usable for conformal scoring.
292///
293/// # Errors
294/// [`MetricError::InvalidDistribution`] on empty, negative, or non-finite entries.
295pub fn check_distribution(probs: &[f64], index: usize) -> Result<(), MetricError> {
296    if probs.is_empty() {
297        return Err(MetricError::InvalidDistribution {
298            index,
299            reason: "empty distribution".to_owned(),
300        });
301    }
302    for &p in probs {
303        if !p.is_finite() || p < 0.0 {
304            return Err(MetricError::InvalidDistribution {
305                index,
306                reason: format!("non-finite or negative probability {p}"),
307            });
308        }
309    }
310    Ok(())
311}