nx_sketch_naive_bayes.nx source
↩ module page · 198 lines · 7089 B
1// sketch_naive_bayes.nx -- streaming binary Naive Bayes classifier.
2//
3// Online supervised-learning primitive. Maintains per-class feature
4// counts and class priors. Classify in log-space via:
5//
6// score(class) = log P(class) + Σ_f log P(f | class)
7// predict = arg max class { score(class) }
8//
9// where:
10// P(class) = class_count / total_obs
11// P(feature|class) = (feature_class_count + alpha) / (class_count + alpha * V)
12// alpha = 1 for Laplace smoothing (avoids -inf for unseen features)
13// V = vocabulary size (caller's responsibility to bound)
14//
15// LOG-SPACE PROBABILITIES (integer):
16// log_2(p) approximated via bitlen(p) - 1 + linear fractional bits.
17// Sum-of-logs in PPM.
18//
19// COMPOSES against sketch_hash_map for sparse feature storage.
20//
21// USE CASES:
22// - spam vs ham email classification
23// - log-line severity (error/warning/info)
24// - sentiment (positive/negative)
25// - URL category (safe / suspicious)
26//
27// API:
28// train(class, feature_id) // observe (class, feature) pair
29// predict(features, n_features) -> class label (0 or 1)
30// score(class, features, n) -> log-prob in PPM
31//
32// LOSSLESS-LANGUAGE DISCIPLINE:
33// Prediction is a sealed binary value (0 or 1).
34// Posterior probability returned in PPM with NX_ENV_REL_STDDEV.
35
36// nx_safety_envelope:
37// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
38// sil_target: SIL1
39// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
40// verdict: NOT_YET_EVALUATED
41
42import "nx_syscalls.nx"
43import "nx_sketch_hash_map.nx"
44import "nx_sketch_types.nx"
45
46const NX_NB_CLASS_NEG: i64 = 0
47const NX_NB_CLASS_POS: i64 = 1
48
49struct NaiveBayes {
50 // Per-class total observation counts.
51 n_neg: i64,
52 n_pos: i64,
53 // Per-class feature counts via two separate hash maps.
54 // Feature ID is composed as feature_id directly.
55 feat_neg: *HashMap,
56 feat_pos: *HashMap,
57 // Smoothing parameter (Laplace alpha) and vocabulary size.
58 alpha: i64,
59 vocab_size: i64,
60}
61
62// === construction =================================================
63
64func nx_nb_alloc(feature_capacity: i64, alpha: i64, vocab_size: i64) -> *NaiveBayes {
65 if alpha <= 0 { return 0 as *NaiveBayes }
66 if vocab_size < 2 { return 0 as *NaiveBayes }
67 let feat_neg: *HashMap = nx_hmap_alloc(feature_capacity)
68 if feat_neg == (0 as *HashMap) { return 0 as *NaiveBayes }
69 let feat_pos: *HashMap = nx_hmap_alloc(feature_capacity)
70 if feat_pos == (0 as *HashMap) { return 0 as *NaiveBayes }
71 let raw: *u8 = sys_mmap(48)
72 let nb: *NaiveBayes = raw as *NaiveBayes
73 nb.n_neg = 0
74 nb.n_pos = 0
75 nb.feat_neg = feat_neg
76 nb.feat_pos = feat_pos
77 nb.alpha = alpha
78 nb.vocab_size = vocab_size
79 return nb
80}
81
82// === train =======================================================
83//
84// Observe a (class, feature_id) pair. Increments class count once per
85// distinct observation set; feature counts incremented per feature.
86//
87// Caller pattern: for each labeled sample, call observe_class once then
88// observe_feature for each feature.
89
90func nx_nb_observe_class(nb: *NaiveBayes, cls: i64) -> i64 {
91 if cls == NX_NB_CLASS_NEG { nb.n_neg = nb.n_neg + 1 }
92 if cls == NX_NB_CLASS_POS { nb.n_pos = nb.n_pos + 1 }
93 return 0
94}
95
96func nx_nb_observe_feature(nb: *NaiveBayes, cls: i64, feature_id: i64) -> i64 {
97 if feature_id <= 0 { return -1 }
98 var map: *HashMap = 0 as *HashMap
99 if cls == NX_NB_CLASS_NEG { map = nb.feat_neg }
100 if cls == NX_NB_CLASS_POS { map = nb.feat_pos }
101 if map == (0 as *HashMap) { return -1 }
102 let cur: i64 = nx_hmap_get(map, feature_id)
103 nx_hmap_put(map, feature_id, cur + 1)
104 return 0
105}
106
107// === log-probability ============================================
108//
109// Integer log_2 floor via bitlen(x) - 1.
110// log_p(class | features) ~ log_p(class) + Σ log_p(f_i | class)
111// All in PPM scale.
112
113func nx_nb_log2_ppm(x: i64) -> i64 {
114 if x <= 1 { return 0 }
115 var n: i64 = 0
116 var t: i64 = x
117 while t > 1 {
118 t = t >> 1
119 n = n + 1
120 }
121 return n * 1000000
122}
123
124// log P(class) = log(class_count / total). Return in PPM.
125func nx_nb_log_class_prior_ppm(nb: *NaiveBayes, cls: i64) -> i64 {
126 let total: i64 = nb.n_neg + nb.n_pos
127 if total == 0 { return 0 }
128 var cnt: i64 = 0
129 if cls == NX_NB_CLASS_NEG { cnt = nb.n_neg }
130 if cls == NX_NB_CLASS_POS { cnt = nb.n_pos }
131 if cnt == 0 { return -100000000 } // very negative for impossible class
132 // log(cnt/total) = log(cnt) - log(total). Both in PPM.
133 return nx_nb_log2_ppm(cnt) - nx_nb_log2_ppm(total)
134}
135
136// log P(feature | class) = log((feature_count + alpha) / (class_count + alpha * V))
137func nx_nb_log_feature_likelihood_ppm(nb: *NaiveBayes, cls: i64, feature_id: i64) -> i64 {
138 var map: *HashMap = 0 as *HashMap
139 var n_class: i64 = 0
140 if cls == NX_NB_CLASS_NEG { map = nb.feat_neg; n_class = nb.n_neg }
141 if cls == NX_NB_CLASS_POS { map = nb.feat_pos; n_class = nb.n_pos }
142 if map == (0 as *HashMap) { return -100000000 }
143 let f_count: i64 = nx_hmap_get(map, feature_id)
144 let numer: i64 = f_count + nb.alpha
145 let denom: i64 = n_class + nb.alpha * nb.vocab_size
146 if denom <= 0 { return -100000000 }
147 return nx_nb_log2_ppm(numer) - nx_nb_log2_ppm(denom)
148}
149
150// === score and predict ==========================================
151//
152// score(class, features) = log_prior(class) + Σ log_likelihood(f, class)
153// predict = arg max class.
154
155func nx_nb_score_ppm(nb: *NaiveBayes, cls: i64,
156 features: *i64, n_features: i64) -> i64 {
157 var score: i64 = nx_nb_log_class_prior_ppm(nb, cls)
158 var i: i64 = 0
159 while i < n_features {
160 score = score + nx_nb_log_feature_likelihood_ppm(nb, cls, features[i])
161 i = i + 1
162 }
163 return score
164}
165
166func nx_nb_predict(nb: *NaiveBayes, features: *i64, n_features: i64) -> i64 {
167 let s_neg: i64 = nx_nb_score_ppm(nb, NX_NB_CLASS_NEG, features, n_features)
168 let s_pos: i64 = nx_nb_score_ppm(nb, NX_NB_CLASS_POS, features, n_features)
169 if s_pos > s_neg { return NX_NB_CLASS_POS }
170 return NX_NB_CLASS_NEG
171}
172
173// === typed envelope =============================================
174//
175// Returns the predicted class with NX_ENV_ABS / Production tier.
176
177func nx_nb_query(nb: *NaiveBayes, features: *i64, n_features: i64) -> *ApproxI64 {
178 let pred: i64 = nx_nb_predict(nb, features, n_features)
179 return nx_approx_new(pred, NX_ENV_ABS, 0, 1000000000,
180 NX_MATURITY_REFERENCE_IMPL,
181 NX_ADV_HONEST)
182}
183
184// === introspection ==============================================
185
186func nx_nb_n_total(nb: *NaiveBayes) -> i64 {
187 return nb.n_neg + nb.n_pos
188}
189
190func nx_nb_n_class(nb: *NaiveBayes, cls: i64) -> i64 {
191 if cls == NX_NB_CLASS_NEG { return nb.n_neg }
192 if cls == NX_NB_CLASS_POS { return nb.n_pos }
193 return 0
194}
195
196func nx_nb_memory_bytes(nb: *NaiveBayes) -> i64 {
197 return 48 + nx_hmap_memory_bytes(nb.feat_neg) + nx_hmap_memory_bytes(nb.feat_pos)
198}