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}