nx_conformal.nx source
↩ module page · 400 lines · 13917 B
1// nx_conformal.nx -- distribution-free prediction intervals.
2//
3// Vovk/Gammerman/Shafer 2005 ("Algorithmic Learning in a Random
4// World"): for any black-box predictor f, conformal prediction
5// builds a prediction SET around f(x_new) with EMPIRICAL COVERAGE
6// guarantee. No distributional assumption. No model retraining.
7//
8// Given calibration set {(x_i, y_i)} of size n and a non-
9// conformity score s_i = |y_i - f(x_i)|:
10//
11// q_alpha = ceil((n+1)(1-alpha)) / n quantile of {s_i}
12//
13// Predicted set for x_new: [f(x_new) - q_alpha, f(x_new) + q_alpha]
14//
15// Guarantee (Vovk Theorem 2.1):
16// P(y_new in predicted_set) >= 1 - alpha
17// for exchangeable data.
18//
19// The structural answer to "i want to predicitably make an 18 year
20// old human whether male or female or have you not hallucinate
21// into c, i cant get that in the current setup." Without conformal,
22// model says "age 22" but true age is some random thing. WITH
23// conformal: "age 22; with 90% coverage, true age in [19, 27]"
24// (distribution-free, model-agnostic).
25//
26// Two modes:
27// SPLIT -- standard split-conformal (Papadopoulos 2002):
28// calibration set held out; gives a single q_alpha.
29// ADAPTIVE -- locally-weighted conformal (Lei/Wasserman 2014):
30// nonconformity scores weighted by feature density;
31// narrower intervals where data is dense. (Stub --
32// returns SPLIT result with weights=1 for v1.)
33//
34// genealogy_id: vovk_2005_papadopoulos_2002
35// lineage_id: substrate_conformal_v1
36//
37// 5W+H+GLP linkage: per-prediction emit VERDICT record with
38// what=VERDICT, how=conformal, performance=interval_width_q10.
39
40// nx_safety_envelope:
41// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
42// sil_target: SIL1
43// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
44// verdict: NOT_YET_EVALUATED
45
46import "nx_syscalls.nx"
47import "nx_runtime.nx"
48import "nx_tier.nx"
49
50// ===== Q10 =========================================================
51
52const NX_CONF_Q10: nx_int = 1024
53
54// ===== bounds ======================================================
55
56const NX_CONF_MAX_CAL: nx_int = 1048576
57const NX_CONF_MIN_CAL: nx_int = 5
58
59// ===== sealed enum: mode ===========================================
60
61const NX_CONF_MODE_SPLIT: nx_int = 0
62const NX_CONF_MODE_ADAPTIVE: nx_int = 1
63
64// ===== sealed enum: verdict ========================================
65//
66// Per-prediction sealed verdict based on interval width vs target.
67
68const NX_CONF_VERDICT_TIGHT: nx_int = 0 // width < tight_thr
69const NX_CONF_VERDICT_USABLE: nx_int = 1 // width < usable_thr
70const NX_CONF_VERDICT_WIDE: nx_int = 2 // width < wide_thr
71const NX_CONF_VERDICT_BROKEN: nx_int = 3 // width >= wide_thr
72
73// ===== prediction-interval struct ==================================
74
75struct NxConformalInterval {
76 point_estimate: nx_int,
77 lower_bound: nx_int,
78 upper_bound: nx_int,
79 width: nx_int,
80 alpha_q10: nx_int,
81 verdict: nx_int,
82 q_alpha: nx_int,
83}
84
85const NX_CONF_INTERVAL_BYTES: nx_size = 56
86
87// ===== calibration model ===========================================
88//
89// Holds the sorted nonconformity scores for fast quantile lookup.
90
91struct NxConformalModel {
92 n_cal: nx_int,
93 mode: nx_int,
94 scores_sorted: *nx_int,
95}
96
97const NX_CONF_MODEL_BYTES: nx_size = 24
98
99// ===== insertion sort (ascending) for nonconformity scores ========
100//
101// Conformal calibration sets are typically small (hundreds-low-
102// thousands). Insertion sort O(n^2) is fine + branch-light.
103
104func _conf_sort_ascending(arr: *nx_int, n: nx_int) -> nx_int {
105 var i: nx_int = 1
106 while i < n {
107 let key: nx_int = arr[i]
108 var j: nx_int = i - 1
109 while j >= 0 {
110 if arr[j] > key {
111 arr[j + 1] = arr[j]
112 j = j - 1
113 } else {
114 j = -1
115 }
116 }
117 arr[j + 1] = key
118 i = i + 1
119 }
120 return 0
121}
122
123// ===== calibration: build sorted nonconformity score table ========
124//
125// Inputs:
126// preds: predictor f(x_i) values
127// targets: ground-truth y_i values
128// n_cal: calibration set size
129// Computes s_i = |targets[i] - preds[i]|, sorts ascending.
130
131func nx_conformal_calibrate(
132 preds: *nx_int, targets: *nx_int, n_cal: nx_int,
133 mode: nx_int) -> *NxConformalModel {
134
135 if n_cal < NX_CONF_MIN_CAL { return 0 as *NxConformalModel }
136 if n_cal > NX_CONF_MAX_CAL { return 0 as *NxConformalModel }
137 if mode != NX_CONF_MODE_SPLIT {
138 if mode != NX_CONF_MODE_ADAPTIVE { return 0 as *NxConformalModel }
139 }
140
141 let bytes: nx_size = (n_cal as nx_size) * 8
142 let scores: *nx_int = (sys_mmap(bytes)) as *nx_int
143
144 var i: nx_int = 0
145 while i < n_cal {
146 var diff: nx_int = targets[i] - preds[i]
147 if diff < 0 { diff = 0 - diff }
148 scores[i] = diff
149 i = i + 1
150 }
151
152 _conf_sort_ascending(scores, n_cal)
153
154 let model_ptr: *u8 = sys_mmap(NX_CONF_MODEL_BYTES)
155 let model: *NxConformalModel = model_ptr as *NxConformalModel
156 model.n_cal = n_cal
157 model.mode = mode
158 model.scores_sorted = scores
159 return model
160}
161
162// ===== conformal quantile lookup ==================================
163//
164// q_alpha = the score at index ceil((n+1)(1-alpha)) - 1 (zero-based).
165// alpha_q10 in [0, 1024]; alpha=Q10*0.1 -> 90% coverage.
166//
167// Implementation:
168// one_minus_alpha_q10 = Q10 - alpha_q10
169// target_idx = ceil( (n+1) * one_minus_alpha_q10 / Q10 ) - 1
170// Clamped to [0, n-1].
171
172func _conf_quantile_q_alpha(model: *NxConformalModel, alpha_q10: nx_int) -> nx_int {
173 let n: nx_int = model.n_cal
174 let one_minus_alpha: nx_int = NX_CONF_Q10 - alpha_q10
175 let n_plus_1: nx_int = n + 1
176 // ceil((n+1) * (1-alpha) / Q10) = ((n+1)*(1-alpha) + Q10-1) / Q10
177 let num: nx_int = n_plus_1 * one_minus_alpha
178 let num_plus_eps: nx_int = num + NX_CONF_Q10 - 1
179 let ceil_idx: nx_int = num_plus_eps / NX_CONF_Q10
180 var idx: nx_int = ceil_idx - 1
181 if idx < 0 { idx = 0 }
182 if idx >= n { idx = n - 1 }
183 return model.scores_sorted[idx]
184}
185
186// ===== predict with interval ======================================
187//
188// f_x_new = predictor output for the new point.
189// alpha_q10 = miscoverage rate in Q10 (e.g. 102 = 0.1 = 90% coverage).
190// Returns predicted set [f_x_new - q_alpha, f_x_new + q_alpha].
191
192func nx_conformal_predict(
193 model: *NxConformalModel, f_x_new: nx_int, alpha_q10: nx_int,
194 tight_thr: nx_int, usable_thr: nx_int, wide_thr: nx_int) -> *NxConformalInterval {
195
196 if alpha_q10 < 0 { return 0 as *NxConformalInterval }
197 if alpha_q10 >= NX_CONF_Q10 { return 0 as *NxConformalInterval }
198
199 let q: nx_int = _conf_quantile_q_alpha(model, alpha_q10)
200
201 let interval_ptr: *u8 = sys_mmap(NX_CONF_INTERVAL_BYTES)
202 let interval: *NxConformalInterval = interval_ptr as *NxConformalInterval
203
204 interval.point_estimate = f_x_new
205 interval.lower_bound = f_x_new - q
206 interval.upper_bound = f_x_new + q
207 interval.width = 2 * q
208 interval.alpha_q10 = alpha_q10
209 interval.q_alpha = q
210
211 if 2 * q < tight_thr {
212 interval.verdict = NX_CONF_VERDICT_TIGHT
213 } else {
214 if 2 * q < usable_thr {
215 interval.verdict = NX_CONF_VERDICT_USABLE
216 } else {
217 if 2 * q < wide_thr {
218 interval.verdict = NX_CONF_VERDICT_WIDE
219 } else {
220 interval.verdict = NX_CONF_VERDICT_BROKEN
221 }
222 }
223 }
224 return interval
225}
226
227// ===== empirical-coverage check on held-out test set ==============
228//
229// For each (pred, target) in the test set, ask: does the interval
230// [pred - q_alpha, pred + q_alpha] contain target? Return hit count
231// + total, plus empirical-coverage as Q10.
232
233struct NxConformalCoverage {
234 n_test: nx_int,
235 n_hit: nx_int,
236 coverage_q10: nx_int,
237 expected_q10: nx_int,
238 delta_q10: nx_int,
239 passes: nx_int,
240}
241
242const NX_CONF_COVERAGE_BYTES: nx_size = 48
243
244// Pass margin: empirical coverage must be within 10% of expected.
245const NX_CONF_COVERAGE_TOLERANCE_Q10: nx_int = 102
246
247func nx_conformal_check_coverage(
248 model: *NxConformalModel, alpha_q10: nx_int,
249 test_preds: *nx_int, test_targets: *nx_int, n_test: nx_int) -> *NxConformalCoverage {
250
251 if n_test <= 0 { return 0 as *NxConformalCoverage }
252 let q: nx_int = _conf_quantile_q_alpha(model, alpha_q10)
253 var hits: nx_int = 0
254 var i: nx_int = 0
255 while i < n_test {
256 let pred: nx_int = test_preds[i]
257 let tgt: nx_int = test_targets[i]
258 let lo: nx_int = pred - q
259 let hi: nx_int = pred + q
260 if tgt >= lo {
261 if tgt <= hi { hits = hits + 1 }
262 }
263 i = i + 1
264 }
265 let cov_q10: nx_int = (hits * NX_CONF_Q10) / n_test
266 let expected: nx_int = NX_CONF_Q10 - alpha_q10
267 var delta: nx_int = cov_q10 - expected
268 if delta < 0 { delta = 0 - delta }
269
270 let cov_ptr: *u8 = sys_mmap(NX_CONF_COVERAGE_BYTES)
271 let cov: *NxConformalCoverage = cov_ptr as *NxConformalCoverage
272 cov.n_test = n_test
273 cov.n_hit = hits
274 cov.coverage_q10 = cov_q10
275 cov.expected_q10 = expected
276 cov.delta_q10 = delta
277 if delta < NX_CONF_COVERAGE_TOLERANCE_Q10 {
278 cov.passes = 1
279 } else {
280 cov.passes = 0
281 }
282 return cov
283}
284
285// ===== self-test ===================================================
286
287func main() -> nx_int {
288 // ---- calibration set ----
289 //
290 // f(x_i) = 100 for all i; targets jitter +-30 around 100.
291 // n_cal = 9 calibration points -> nonconformity scores
292 // |[70, 110, 80, 105, 95, 120, 85, 130, 100] - 100|
293 // = [30, 10, 20, 5, 5, 20, 15, 30, 0]
294 // sorted = [0, 5, 5, 10, 15, 20, 20, 30, 30]
295
296 let preds_cal: *nx_int = (sys_mmap(72)) as *nx_int
297 let tgts_cal: *nx_int = (sys_mmap(72)) as *nx_int
298 var i: nx_int = 0
299 while i < 9 {
300 preds_cal[i] = 100
301 i = i + 1
302 }
303 tgts_cal[0] = 70
304 tgts_cal[1] = 110
305 tgts_cal[2] = 80
306 tgts_cal[3] = 105
307 tgts_cal[4] = 95
308 tgts_cal[5] = 120
309 tgts_cal[6] = 85
310 tgts_cal[7] = 130
311 tgts_cal[8] = 100
312
313 let model: *NxConformalModel = nx_conformal_calibrate(
314 preds_cal, tgts_cal, 9, NX_CONF_MODE_SPLIT)
315 if model == (0 as *NxConformalModel) { return 1 }
316 if model.n_cal != 9 { return 2 }
317
318 // sorted scores: [0, 5, 5, 10, 15, 20, 20, 30, 30]
319 if model.scores_sorted[0] != 0 { return 3 }
320 if model.scores_sorted[1] != 5 { return 4 }
321 if model.scores_sorted[3] != 10 { return 5 }
322 if model.scores_sorted[8] != 30 { return 6 }
323
324 // ---- quantile at alpha=0.1 (Q10=102): 90% coverage ----
325 //
326 // (n+1)(1-alpha) = 10 * 0.9 = 9; ceil = 9; idx = 9 - 1 = 8.
327 // q_alpha = scores_sorted[8] = 30.
328 let q_90: nx_int = _conf_quantile_q_alpha(model, 102)
329 if q_90 != 30 { return 10 }
330
331 // ---- predict at f(x_new) = 200 with 90% coverage ----
332 //
333 // Interval = [200 - 30, 200 + 30] = [170, 230], width 60.
334 let interval_90: *NxConformalInterval = nx_conformal_predict(
335 model, 200, 102, 50, 100, 200)
336 if interval_90 == (0 as *NxConformalInterval) { return 20 }
337 if interval_90.point_estimate != 200 { return 21 }
338 if interval_90.lower_bound != 170 { return 22 }
339 if interval_90.upper_bound != 230 { return 23 }
340 if interval_90.width != 60 { return 24 }
341 if interval_90.q_alpha != 30 { return 25 }
342 // width 60 < usable_thr 100 -> USABLE
343 if interval_90.verdict != NX_CONF_VERDICT_USABLE { return 26 }
344
345 // ---- quantile at alpha=0.5 (Q10=512): 50% coverage ----
346 //
347 // (n+1)(1-alpha) = 10 * 0.5 = 5; ceil = 5; idx = 5 - 1 = 4.
348 // q_alpha = scores_sorted[4] = 15. Narrower than 90% interval.
349 let q_50: nx_int = _conf_quantile_q_alpha(model, 512)
350 if q_50 != 15 { return 30 }
351 // 50% interval narrower than 90% -- monotone in alpha.
352 if q_50 >= q_90 { return 31 }
353
354 // ---- coverage check on held-out test set ----
355 //
356 // Test: preds = [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
357 // targets = [120, 90, 130, 75, 100, 110, 80, 100, 95, 105]
358 // With q_alpha=30 (90% interval): targets in [70, 130].
359 // All 10 should hit -> coverage 100% = 1024. Test passes
360 // (delta from expected 922 is 102, equal to tolerance, treat
361 // as marginal -- adjust to 9-of-10 to make delta = 102 - 922 = ...)
362 //
363 // Simpler: use 4 targets where 3 hit and 1 misses -> coverage 768.
364 // Expected at alpha=0.1 is 922. Delta = 154 > tolerance 102 -> fail.
365
366 let preds_test: *nx_int = (sys_mmap(32)) as *nx_int
367 let tgts_test: *nx_int = (sys_mmap(32)) as *nx_int
368 i = 0
369 while i < 4 {
370 preds_test[i] = 100
371 i = i + 1
372 }
373 tgts_test[0] = 120 // in [70, 130] - hit
374 tgts_test[1] = 90 // in [70, 130] - hit
375 tgts_test[2] = 130 // in [70, 130] - hit
376 tgts_test[3] = 200 // out of [70, 130] - miss
377 let cov: *NxConformalCoverage = nx_conformal_check_coverage(
378 model, 102, preds_test, tgts_test, 4)
379 if cov == (0 as *NxConformalCoverage) { return 40 }
380 if cov.n_test != 4 { return 41 }
381 if cov.n_hit != 3 { return 42 }
382 // coverage = 3/4 * 1024 = 768
383 if cov.coverage_q10 != 768 { return 43 }
384 // expected = 1024 - 102 = 922
385 if cov.expected_q10 != 922 { return 44 }
386 // delta = |768 - 922| = 154; > 102 tolerance -> fails
387 if cov.delta_q10 != 154 { return 45 }
388 if cov.passes != 0 { return 46 }
389
390 // ---- input validation ----
391 let bad_cal: *NxConformalModel = nx_conformal_calibrate(
392 preds_cal, tgts_cal, 3, NX_CONF_MODE_SPLIT)
393 if bad_cal != (0 as *NxConformalModel) { return 50 }
394
395 let bad_alpha: *NxConformalInterval = nx_conformal_predict(
396 model, 200, NX_CONF_Q10, 50, 100, 200)
397 if bad_alpha != (0 as *NxConformalInterval) { return 51 }
398
399 return 0
400}