sketch_naive_bayes_vs_majority_bench.nx source
↩ module page · 127 lines · 4407 B
1// sketch_naive_bayes_vs_majority_bench.nx -- classification accuracy bench.
2//
3// CLAIM TO VALIDATE:
4// Naive Bayes (Maron 1961) outperforms a majority-class baseline
5// when features actually carry signal about the class. Without
6// real per-feature likelihood, classification = majority class.
7//
8// Test: a streaming binary classification task where class 1 has
9// features {1, 2, 3, 4} with high probability and class 0 has
10// features {5, 6, 7, 8} with high probability. Some overlap to
11// make it non-trivial.
12//
13// WORKLOAD:
14// Train: 200 samples per class (400 total).
15// Test: 100 fresh samples per class.
16// Majority baseline: always predicts the more frequent class
17// (both 50% here so any constant prediction → 50% accuracy).
18//
19// NaiveBayes should hit >=80% accuracy by learning the feature
20// distribution.
21//
22// MEASUREMENT:
23// ACCURACY axis: NB correct count vs majority correct count.
24
25import "syscalls.nx"
26import "sketch_naive_bayes.nx"
27import "sketch_comparator.nx"
28import "sketch_types.nx"
29
30const NX_NBB_LCG_A: i64 = 1103515245
31const NX_NBB_LCG_C: i64 = 12345
32const NX_NBB_LCG_MOD: i64 = 0x7FFFFFFF
33
34func main() -> i64 {
35 let nb: *NaiveBayes = nx_nb_alloc(32, 1, 16)
36 if nb == (0 as *NaiveBayes) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
37
38 // ---- Train ----
39 let feat_raw: *u8 = sys_mmap(8 * 8)
40 let feats: *i64 = feat_raw as *i64
41
42 var sim: i64 = 42
43 var i: i64 = 0
44 while i < 200 {
45 // Class 1 samples: features biased toward {1,2,3,4}
46 nx_nb_observe_class(nb, 1)
47 var f: i64 = 0
48 while f < 4 {
49 sim = ((sim * NX_NBB_LCG_A) + NX_NBB_LCG_C) & NX_NBB_LCG_MOD
50 // 80% chance pick from class-1 feature set {1,2,3,4}
51 // 20% from full {1..8}
52 var feature: i64 = 1 + (sim % 4)
53 if (sim & 0x3FF) >= 819 { // 20% from full
54 feature = 1 + (sim % 8)
55 }
56 nx_nb_observe_feature(nb, 1, feature)
57 f = f + 1
58 }
59 // Class 0: features biased toward {5,6,7,8}
60 nx_nb_observe_class(nb, 0)
61 f = 0
62 while f < 4 {
63 sim = ((sim * NX_NBB_LCG_A) + NX_NBB_LCG_C) & NX_NBB_LCG_MOD
64 var feature: i64 = 5 + (sim % 4)
65 if (sim & 0x3FF) >= 819 {
66 feature = 1 + (sim % 8)
67 }
68 nx_nb_observe_feature(nb, 0, feature)
69 f = f + 1
70 }
71 i = i + 1
72 }
73
74 // ---- Test: 200 samples (100 per class) ----
75 var nb_correct: i64 = 0
76 var majority_correct: i64 = 0
77 let majority_class: i64 = 1 // both classes 50% — pick 1
78
79 i = 0
80 while i < 100 {
81 // Class 1 test sample
82 var f: i64 = 0
83 while f < 4 {
84 sim = ((sim * NX_NBB_LCG_A) + NX_NBB_LCG_C) & NX_NBB_LCG_MOD
85 var feature: i64 = 1 + (sim % 4)
86 if (sim & 0x3FF) >= 819 { feature = 1 + (sim % 8) }
87 feats[f] = feature
88 f = f + 1
89 }
90 let pred1: i64 = nx_nb_predict(nb, feats, 4)
91 if pred1 == 1 { nb_correct = nb_correct + 1 }
92 if majority_class == 1 { majority_correct = majority_correct + 1 }
93
94 // Class 0 test sample
95 f = 0
96 while f < 4 {
97 sim = ((sim * NX_NBB_LCG_A) + NX_NBB_LCG_C) & NX_NBB_LCG_MOD
98 var feature: i64 = 5 + (sim % 4)
99 if (sim & 0x3FF) >= 819 { feature = 1 + (sim % 8) }
100 feats[f] = feature
101 f = f + 1
102 }
103 let pred0: i64 = nx_nb_predict(nb, feats, 4)
104 if pred0 == 0 { nb_correct = nb_correct + 1 }
105 if majority_class == 0 { majority_correct = majority_correct + 1 }
106
107 i = i + 1
108 }
109
110 // ---- NaiveBayes >= 80% accuracy ----
111 if nb_correct < 160 { return __syscall(93, 10, 0, 0, 0, 0, 0) }
112 // ---- Majority ~ 50% by definition ----
113 if majority_correct < 80 { return __syscall(93, 11, 0, 0, 0, 0, 0) }
114 if majority_correct > 120 { return __syscall(93, 12, 0, 0, 0, 0, 0) }
115
116 // ---- ACCURACY axis: closer to truth=200 wins ----
117 let acc: *ComparisonResult = nx_cmp_accuracy(nb_correct, majority_correct, 200, 50000)
118 if acc.verdict != NX_CMP_VERDICT_BEATS {
119 return __syscall(93, 20, 0, 0, 0, 0, 0)
120 }
121 // Require >=20% improvement of truth
122 if acc.delta_ppm < 200000 {
123 return __syscall(93, 21, 0, 0, 0, 0, 0)
124 }
125
126 return 0
127}