nx_knn.nx source
↩ module page · 346 lines · 12432 B
1// nx_knn.nx -- k-Nearest-Neighbors classifier.
2//
3// The cardinal feedback-loras-and-negatives-are-patches-not-systems
4// names "classifiers" as a load-bearing piece: inputs from
5// classifiers lead to known outputs with statistical measurement.
6// This file ships the most bits-up classifier in the literature.
7//
8// kNN (Cover & Hart 1967):
9// - No training phase.
10// - No model weights to load.
11// - Just a labeled point cloud + a distance metric.
12// - Given query: find k closest labeled points, return majority
13// class + confidence.
14//
15// Why kNN as the FIRST substrate classifier:
16//
17// 1. Bits-up minimum. No FPU dep, no matrix factorisation, no
18// training optimiser, no hyperparameter tuning beyond k.
19// 2. Theoretical guarantee. Cover & Hart proved kNN error is
20// bounded by twice the Bayes error rate. No deep-learning
21// magic.
22// 3. Composes naturally with the closed-loop + Monte Carlo
23// primitives. Each kNN prediction is a measurable verdict;
24// confidence becomes the variance input to MC.
25// 4. Pluggable into ANY downstream domain. Age, pose, gender,
26// style -- all become kNN problems if the caller provides
27// labeled feature vectors.
28//
29// Distance metric: Euclidean squared (sum of (a-b)^2 across
30// features). We avoid sqrt because ranking-by-distance is the
31// same with or without it; the substrate caller can sqrt if they
32// want a true distance value via nx_isqrt_q10.
33//
34// genealogy_id: cover_hart_1967_kNN + fix_hodges_1951_discriminatory_analysis +
35// duda_hart_2001_pattern_classification
36// lineage_id: substrate_knn_v1
37//
38// nx_safety_envelope:
39// intended_use: "k-Nearest Neighbors classifier (Cover & Hart
40// 1967) -- substrate baseline classifier; also
41// used as triangulation foil against neural
42// approaches"
43// sil_target: SIL2 (classifier; misclassification
44// weight depends on consumer)
45// asil_target: QM
46// dal_target: DAL C
47// evidence: [Cover_Hart_1967_canonical_basis, no_FP,
48// bounded_pairwise_distance_computation,
49// deterministic_tie_break]
50// hazard_register: [bug-tape-class-imbalance-bias,
51// bug-tape-distance-metric-mismatch-with-data,
52// bug-tape-k-too-small-overfitting]
53// residual_risk: "Caller chooses k; substrate documents
54// odd-k recommendation for binary classes.
55// Distance-metric appropriateness is
56// domain-specific."
57// verdict: NOT_YET_EVALUATED
58
59import "nx_syscalls.nx"
60import "nx_tier.nx"
61import "nx_loop.nx"
62
63// ===== Sealed-enum: KnnVerdict ====================================
64
65const NX_KNN_OK: nx_int = 0
66const NX_KNN_ERR_BAD_DIMS: nx_int = 1
67const NX_KNN_ERR_BAD_K: nx_int = 2
68const NX_KNN_ERR_AMBIGUOUS: nx_int = 3 // tied majority vote
69const NX_KNN_N_VERDICTS: nx_int = 4
70
71func nx_knn_verdict_is_valid(v: nx_int) -> nx_int {
72 if v < 0 { return 0 }
73 if v >= NX_KNN_N_VERDICTS { return 0 }
74 return 1
75}
76
77// ===== Classifier container ======================================
78//
79// All buffers caller-owned via sys_mmap. Substrate doesn't allocate
80// (caller controls memory layout for cache-locality decisions).
81//
82// features: [n_points * n_features] row-major Q10 i64
83// labels: [n_points] class IDs (any i64 range; classifier
84// doesn't enforce contiguous class IDs)
85
86struct NxKnnClassifier {
87 n_points: nx_int,
88 n_features: nx_int,
89 n_classes: nx_int, // max-label-id-plus-1; used for voting
90 features: *i64,
91 labels: *i64
92}
93
94const NX_KNN_BYTES: nx_int = 40
95
96// ===== Result envelope ============================================
97
98struct NxKnnResult {
99 verdict: nx_int, // NX_KNN_*
100 predicted: nx_int, // class label
101 confidence_q10:nx_int, // votes_for_winner / k * Q10
102 k_used: nx_int // echo of k for caller
103}
104
105const NX_KNN_RESULT_BYTES: nx_int = 32
106
107// ===== Squared Euclidean distance ================================
108
109func _knn_dist_sq(features: *i64, n_features: nx_int,
110 point_idx: nx_int, query: *i64) -> i64 {
111 var sum: i64 = 0
112 var f: nx_int = 0
113 var iter: nx_int = 0
114 var verdict: nx_int = NX_LOOP_RUNNING
115 let BUDGET: nx_int = n_features
116 let base: nx_int = point_idx * n_features
117 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
118 let d: i64 = features[base + f] - query[f]
119 sum = sum + d * d
120 f = f + 1
121 iter = iter + 1
122 }
123 return sum
124}
125
126// ===== Linear k-nearest scan =====================================
127//
128// For each labeled point, compute distance to query. Track the k
129// smallest in a flat array. Insert-sort to maintain order.
130//
131// O(n * k) per classification. For n <= 10000 + k <= 32 (typical)
132// that's 320k ops -- fine. KD-tree / ball-tree are queued perf
133// upgrades when n grows.
134//
135// out_indices[k] receives the k nearest neighbour indices in
136// ascending-distance order. out_distances[k] receives their
137// squared distances.
138
139func _knn_find_k_nearest(clf: *NxKnnClassifier, query: *i64, k: nx_int,
140 out_indices: *i64, out_distances: *i64) -> nx_int {
141 // Initialize with sentinel max-distance.
142 var i: nx_int = 0
143 while i < k {
144 out_indices[i] = 0 - 1
145 out_distances[i] = 0x7FFFFFFFFFFFFFFF
146 i = i + 1
147 }
148
149 var p: nx_int = 0
150 var p_iter: nx_int = 0
151 var p_verdict: nx_int = NX_LOOP_RUNNING
152 let P_BUDGET: nx_int = clf.n_points
153 while p_verdict == NX_LOOP_RUNNING && p_iter < P_BUDGET {
154 let d: i64 = _knn_dist_sq(clf.features, clf.n_features, p, query)
155 // Insert into out_distances if d < out_distances[k-1].
156 if d < out_distances[k - 1] {
157 // Shift down from end.
158 var j: nx_int = k - 1
159 var shifted: nx_int = 0
160 var s_iter: nx_int = 0
161 var s_verdict: nx_int = NX_LOOP_RUNNING
162 while s_verdict == NX_LOOP_RUNNING && s_iter < k {
163 if j > 0 {
164 if out_distances[j - 1] > d {
165 out_distances[j] = out_distances[j - 1]
166 out_indices[j] = out_indices[j - 1]
167 j = j - 1
168 shifted = 1
169 } else {
170 s_verdict = NX_LOOP_DONE_EXIT
171 }
172 } else {
173 s_verdict = NX_LOOP_DONE_EXIT
174 }
175 s_iter = s_iter + 1
176 }
177 out_distances[j] = d
178 out_indices[j] = p
179 }
180 p = p + 1
181 p_iter = p_iter + 1
182 }
183 return 0
184}
185
186// ===== Majority vote =============================================
187//
188// Counts class labels across the k nearest neighbours and returns
189// the winning class + vote count. Ties resolved by the FIRST class
190// encountered in iteration order (deterministic given same data).
191// If ties are common, caller should increase k or fall back to
192// nx_knn_classify_distance_weighted (queued).
193
194func _knn_majority_vote(clf: *NxKnnClassifier, k_indices: *i64, k: nx_int,
195 out_label: *i64, out_votes: *i64) -> nx_int {
196 let counts: *i64 = sys_mmap(clf.n_classes * 8) as *i64
197 var c: nx_int = 0
198 while c < clf.n_classes { counts[c] = 0; c = c + 1 }
199
200 var i: nx_int = 0
201 var iter: nx_int = 0
202 var verdict: nx_int = NX_LOOP_RUNNING
203 let BUDGET: nx_int = k
204 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
205 let nbr_idx: nx_int = k_indices[i]
206 if nbr_idx >= 0 {
207 let lbl: nx_int = clf.labels[nbr_idx]
208 if lbl >= 0 {
209 if lbl < clf.n_classes {
210 counts[lbl] = counts[lbl] + 1
211 }
212 }
213 }
214 i = i + 1
215 iter = iter + 1
216 }
217
218 // Find max.
219 var best_lbl: nx_int = 0
220 var best_cnt: i64 = counts[0]
221 var ties: nx_int = 0
222 var ci: nx_int = 1
223 while ci < clf.n_classes {
224 if counts[ci] > best_cnt {
225 best_cnt = counts[ci]
226 best_lbl = ci
227 ties = 0
228 }
229 if counts[ci] == best_cnt {
230 if ci != best_lbl { ties = ties + 1 }
231 }
232 ci = ci + 1
233 }
234 out_label[0] = best_lbl
235 out_votes[0] = best_cnt
236 return ties
237}
238
239// ===== Public: classify a query vector ===========================
240
241func nx_knn_classify(clf: *NxKnnClassifier, query: *i64, k: nx_int) -> *NxKnnResult {
242 let r: *NxKnnResult = sys_mmap(NX_KNN_RESULT_BYTES) as *NxKnnResult
243 r.verdict = NX_KNN_ERR_BAD_DIMS
244 r.predicted = 0
245 r.confidence_q10 = 0
246 r.k_used = k
247
248 if k <= 0 { r.verdict = NX_KNN_ERR_BAD_K; return r }
249 if k > clf.n_points { r.verdict = NX_KNN_ERR_BAD_K; return r }
250 if clf.n_features <= 0 { return r }
251 if clf.n_points <= 0 { return r }
252
253 let k_idx: *i64 = sys_mmap(k * 8) as *i64
254 let k_dist: *i64 = sys_mmap(k * 8) as *i64
255 _knn_find_k_nearest(clf, query, k, k_idx, k_dist)
256
257 let out_label: *i64 = sys_mmap(8) as *i64
258 let out_votes: *i64 = sys_mmap(8) as *i64
259 let ties: nx_int = _knn_majority_vote(clf, k_idx, k, out_label, out_votes)
260
261 r.predicted = out_label[0]
262 // Confidence: winner_votes / k in Q10.
263 r.confidence_q10 = (out_votes[0] * 1024) / k
264
265 if ties > 0 { r.verdict = NX_KNN_ERR_AMBIGUOUS }
266 if ties == 0 { r.verdict = NX_KNN_OK }
267 return r
268}
269
270// ===== Self-test ==================================================
271//
272// 6 labeled points in 2D, 2 classes:
273// class 0: (0,0), (1,0), (0,1) -- a cluster around origin
274// class 1: (10,10), (11,10), (10,11) -- a cluster around (10,10)
275//
276// Query (0.5, 0.5) should predict class 0 with high confidence.
277// Query (10.5, 10.5) should predict class 1 with high confidence.
278// Query (5, 5) is between: kNN k=3 should give class 0 (cluster 0
279// has 3 points; cluster 1 has 3 points; with k=3 we pick the 3
280// nearest; closer cluster wins).
281//
282// All values in Q10.
283
284func main() -> i64 {
285 let N_POINTS: nx_int = 6
286 let N_FEATURES: nx_int = 2
287 let N_CLASSES: nx_int = 2
288
289 let feats: *i64 = sys_mmap(N_POINTS * N_FEATURES * 8) as *i64
290 let labs: *i64 = sys_mmap(N_POINTS * 8) as *i64
291
292 // Class 0 (around origin)
293 feats[0]=0; feats[1]=0; labs[0]=0
294 feats[2]=1024;feats[3]=0; labs[1]=0
295 feats[4]=0; feats[5]=1024; labs[2]=0
296 // Class 1 (around (10, 10))
297 feats[6]=10240;feats[7]=10240; labs[3]=1
298 feats[8]=11264;feats[9]=10240; labs[4]=1
299 feats[10]=10240;feats[11]=11264;labs[5]=1
300
301 let clf: *NxKnnClassifier = sys_mmap(NX_KNN_BYTES) as *NxKnnClassifier
302 clf.n_points = N_POINTS
303 clf.n_features = N_FEATURES
304 clf.n_classes = N_CLASSES
305 clf.features = feats
306 clf.labels = labs
307
308 let q: *i64 = sys_mmap(N_FEATURES * 8) as *i64
309
310 // --- (a) Near class 0: q = (0.5, 0.5) in Q10 ---
311 q[0] = 512; q[1] = 512
312 let r1: *NxKnnResult = nx_knn_classify(clf, q, 3)
313 if r1.verdict != NX_KNN_OK { return 10 }
314 if r1.predicted != 0 { return 11 }
315 // Confidence: all 3 nearest are class 0 -> 3/3 = Q10 (1024).
316 if r1.confidence_q10 != 1024 { return 12 }
317
318 // --- (b) Near class 1: q = (10.5, 10.5) ---
319 q[0] = 10752; q[1] = 10752
320 let r2: *NxKnnResult = nx_knn_classify(clf, q, 3)
321 if r2.verdict != NX_KNN_OK { return 20 }
322 if r2.predicted != 1 { return 21 }
323 if r2.confidence_q10 != 1024 { return 22 }
324
325 // --- (c) Bad k ---
326 let r3: *NxKnnResult = nx_knn_classify(clf, q, 0)
327 if r3.verdict != NX_KNN_ERR_BAD_K { return 30 }
328 let r4: *NxKnnResult = nx_knn_classify(clf, q, 99)
329 if r4.verdict != NX_KNN_ERR_BAD_K { return 31 }
330
331 // --- (d) k=1 single-nearest ---
332 q[0] = 0; q[1] = 0
333 let r5: *NxKnnResult = nx_knn_classify(clf, q, 1)
334 if r5.verdict != NX_KNN_OK { return 40 }
335 if r5.predicted != 0 { return 41 }
336 if r5.confidence_q10 != 1024 { return 42 }
337
338 // --- (e) Verdict gate ---
339 var vi: nx_int = 0
340 while vi < NX_KNN_N_VERDICTS {
341 if nx_knn_verdict_is_valid(vi) != 1 { return 50 + vi }
342 vi = vi + 1
343 }
344
345 return 0
346}