sketch_naive_bayes.nx source
↩ module page · 192 lines · 7021 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
36import "syscalls.nx"
37import "sketch_hash_map.nx"
38import "sketch_types.nx"
39
40const NX_NB_CLASS_NEG: i64 = 0
41const NX_NB_CLASS_POS: i64 = 1
42
43struct NaiveBayes {
44 // Per-class total observation counts.
45 n_neg: i64,
46 n_pos: i64,
47 // Per-class feature counts via two separate hash maps.
48 // Feature ID is composed as feature_id directly.
49 feat_neg: *HashMap,
50 feat_pos: *HashMap,
51 // Smoothing parameter (Laplace alpha) and vocabulary size.
52 alpha: i64,
53 vocab_size: i64,
54}
55
56// === construction =================================================
57
58func nx_nb_alloc(feature_capacity: i64, alpha: i64, vocab_size: i64) -> *NaiveBayes {
59 if alpha <= 0 { return 0 as *NaiveBayes }
60 if vocab_size < 2 { return 0 as *NaiveBayes }
61 let feat_neg: *HashMap = nx_hmap_alloc(feature_capacity)
62 if feat_neg == (0 as *HashMap) { return 0 as *NaiveBayes }
63 let feat_pos: *HashMap = nx_hmap_alloc(feature_capacity)
64 if feat_pos == (0 as *HashMap) { return 0 as *NaiveBayes }
65 let raw: *u8 = sys_mmap(48)
66 let nb: *NaiveBayes = raw as *NaiveBayes
67 nb.n_neg = 0
68 nb.n_pos = 0
69 nb.feat_neg = feat_neg
70 nb.feat_pos = feat_pos
71 nb.alpha = alpha
72 nb.vocab_size = vocab_size
73 return nb
74}
75
76// === train =======================================================
77//
78// Observe a (class, feature_id) pair. Increments class count once per
79// distinct observation set; feature counts incremented per feature.
80//
81// Caller pattern: for each labeled sample, call observe_class once then
82// observe_feature for each feature.
83
84func nx_nb_observe_class(nb: *NaiveBayes, cls: i64) -> i64 {
85 if cls == NX_NB_CLASS_NEG { nb.n_neg = nb.n_neg + 1 }
86 if cls == NX_NB_CLASS_POS { nb.n_pos = nb.n_pos + 1 }
87 return 0
88}
89
90func nx_nb_observe_feature(nb: *NaiveBayes, cls: i64, feature_id: i64) -> i64 {
91 if feature_id <= 0 { return -1 }
92 var map: *HashMap = 0 as *HashMap
93 if cls == NX_NB_CLASS_NEG { map = nb.feat_neg }
94 if cls == NX_NB_CLASS_POS { map = nb.feat_pos }
95 if map == (0 as *HashMap) { return -1 }
96 let cur: i64 = nx_hmap_get(map, feature_id)
97 nx_hmap_put(map, feature_id, cur + 1)
98 return 0
99}
100
101// === log-probability ============================================
102//
103// Integer log_2 floor via bitlen(x) - 1.
104// log_p(class | features) ~ log_p(class) + Σ log_p(f_i | class)
105// All in PPM scale.
106
107func nx_nb_log2_ppm(x: i64) -> i64 {
108 if x <= 1 { return 0 }
109 var n: i64 = 0
110 var t: i64 = x
111 while t > 1 {
112 t = t >> 1
113 n = n + 1
114 }
115 return n * 1000000
116}
117
118// log P(class) = log(class_count / total). Return in PPM.
119func nx_nb_log_class_prior_ppm(nb: *NaiveBayes, cls: i64) -> i64 {
120 let total: i64 = nb.n_neg + nb.n_pos
121 if total == 0 { return 0 }
122 var cnt: i64 = 0
123 if cls == NX_NB_CLASS_NEG { cnt = nb.n_neg }
124 if cls == NX_NB_CLASS_POS { cnt = nb.n_pos }
125 if cnt == 0 { return -100000000 } // very negative for impossible class
126 // log(cnt/total) = log(cnt) - log(total). Both in PPM.
127 return nx_nb_log2_ppm(cnt) - nx_nb_log2_ppm(total)
128}
129
130// log P(feature | class) = log((feature_count + alpha) / (class_count + alpha * V))
131func nx_nb_log_feature_likelihood_ppm(nb: *NaiveBayes, cls: i64, feature_id: i64) -> i64 {
132 var map: *HashMap = 0 as *HashMap
133 var n_class: i64 = 0
134 if cls == NX_NB_CLASS_NEG { map = nb.feat_neg; n_class = nb.n_neg }
135 if cls == NX_NB_CLASS_POS { map = nb.feat_pos; n_class = nb.n_pos }
136 if map == (0 as *HashMap) { return -100000000 }
137 let f_count: i64 = nx_hmap_get(map, feature_id)
138 let numer: i64 = f_count + nb.alpha
139 let denom: i64 = n_class + nb.alpha * nb.vocab_size
140 if denom <= 0 { return -100000000 }
141 return nx_nb_log2_ppm(numer) - nx_nb_log2_ppm(denom)
142}
143
144// === score and predict ==========================================
145//
146// score(class, features) = log_prior(class) + Σ log_likelihood(f, class)
147// predict = arg max class.
148
149func nx_nb_score_ppm(nb: *NaiveBayes, cls: i64,
150 features: *i64, n_features: i64) -> i64 {
151 var score: i64 = nx_nb_log_class_prior_ppm(nb, cls)
152 var i: i64 = 0
153 while i < n_features {
154 score = score + nx_nb_log_feature_likelihood_ppm(nb, cls, features[i])
155 i = i + 1
156 }
157 return score
158}
159
160func nx_nb_predict(nb: *NaiveBayes, features: *i64, n_features: i64) -> i64 {
161 let s_neg: i64 = nx_nb_score_ppm(nb, NX_NB_CLASS_NEG, features, n_features)
162 let s_pos: i64 = nx_nb_score_ppm(nb, NX_NB_CLASS_POS, features, n_features)
163 if s_pos > s_neg { return NX_NB_CLASS_POS }
164 return NX_NB_CLASS_NEG
165}
166
167// === typed envelope =============================================
168//
169// Returns the predicted class with NX_ENV_ABS / Production tier.
170
171func nx_nb_query(nb: *NaiveBayes, features: *i64, n_features: i64) -> *ApproxI64 {
172 let pred: i64 = nx_nb_predict(nb, features, n_features)
173 return nx_approx_new(pred, NX_ENV_ABS, 0, 1000000000,
174 NX_MATURITY_REFERENCE_IMPL,
175 NX_ADV_HONEST)
176}
177
178// === introspection ==============================================
179
180func nx_nb_n_total(nb: *NaiveBayes) -> i64 {
181 return nb.n_neg + nb.n_pos
182}
183
184func nx_nb_n_class(nb: *NaiveBayes, cls: i64) -> i64 {
185 if cls == NX_NB_CLASS_NEG { return nb.n_neg }
186 if cls == NX_NB_CLASS_POS { return nb.n_pos }
187 return 0
188}
189
190func nx_nb_memory_bytes(nb: *NaiveBayes) -> i64 {
191 return 48 + nx_hmap_memory_bytes(nb.feat_neg) + nx_hmap_memory_bytes(nb.feat_pos)
192}