qualia_core_db/modalities/
probabilistic.rs1use crate::NQuin;
2
3pub fn evaluate_threshold(weight: f32, threshold: f32) -> bool {
5 weight >= threshold
6}
7
8pub const MAX_BAYESIAN_NODES: usize = 32;
9
10#[derive(Debug, Clone, Copy, PartialEq)]
11pub struct BayesianNode {
12 pub id: u64, pub parent_ids: [u64; 4], pub num_parents: usize,
15 pub probabilities: [f32; 16], pub evidence: Option<bool>, }
18
19impl Default for BayesianNode {
20 fn default() -> Self {
21 Self {
22 id: 0,
23 parent_ids: [0; 4],
24 num_parents: 0,
25 probabilities: [0.0; 16],
26 evidence: None,
27 }
28 }
29}
30
31pub struct BayesianNetwork {
32 pub nodes: [BayesianNode; MAX_BAYESIAN_NODES],
33 pub num_nodes: usize,
34}
35
36impl BayesianNetwork {
37 pub fn new() -> Self {
39 Self {
40 nodes: [BayesianNode::default(); MAX_BAYESIAN_NODES],
41 num_nodes: 0,
42 }
43 }
44
45 pub fn add_node(&mut self, node: BayesianNode) -> Result<(), &'static str> {
47 if self.num_nodes >= MAX_BAYESIAN_NODES {
48 return Err("Max nodes exceeded");
49 }
50 self.nodes[self.num_nodes] = node;
51 self.num_nodes += 1;
52 Ok(())
53 }
54
55 pub fn extract_weight(quin: &NQuin) -> f32 {
58 crate::frame_layout::truth_degree(quin.metadata)
59 }
60
61 pub fn update_beliefs(&self, target_id: u64) -> Option<f32> {
65 let mut target_idx = None;
66 for i in 0..self.num_nodes {
67 if self.nodes[i].id == target_id {
68 target_idx = Some(i);
69 break;
70 }
71 }
72 let target_idx = target_idx?;
73
74 let mut num_unobserved = 0;
75 let mut unobserved_indices = [0; MAX_BAYESIAN_NODES];
76 for i in 0..self.num_nodes {
77 if self.nodes[i].evidence.is_none() && i != target_idx {
78 unobserved_indices[num_unobserved] = i;
79 num_unobserved += 1;
80 }
81 }
82
83 if num_unobserved > 16 {
84 return None; }
86
87 let num_assignments = 1 << num_unobserved;
88
89 let mut prob_target_true = 0.0;
90 let mut prob_target_false = 0.0;
91
92 for assignment in 0..num_assignments {
93 for target_state in [true, false] {
94 let mut joint_prob = 1.0;
95
96 for i in 0..self.num_nodes {
97 let node = &self.nodes[i];
98
99 let state = if i == target_idx {
100 target_state
101 } else if let Some(e) = node.evidence {
102 e
103 } else {
104 let mut bit_idx = 0;
105 for j in 0..num_unobserved {
106 if unobserved_indices[j] == i {
107 bit_idx = j;
108 break;
109 }
110 }
111 ((assignment >> bit_idx) & 1) == 1
112 };
113
114 let mut parent_idx = 0;
115 for p in 0..node.num_parents {
116 let pid = node.parent_ids[p];
117 let mut p_state = false;
118 for j in 0..self.num_nodes {
119 if self.nodes[j].id == pid {
120 p_state = if j == target_idx {
121 target_state
122 } else if let Some(e) = self.nodes[j].evidence {
123 e
124 } else {
125 let mut bit_idx = 0;
126 for k in 0..num_unobserved {
127 if unobserved_indices[k] == j {
128 bit_idx = k;
129 break;
130 }
131 }
132 ((assignment >> bit_idx) & 1) == 1
133 };
134 break;
135 }
136 }
137 if p_state {
138 parent_idx |= 1 << p;
139 }
140 }
141
142 let p_node = if state {
143 node.probabilities[parent_idx]
144 } else {
145 1.0 - node.probabilities[parent_idx]
146 };
147
148 joint_prob *= p_node;
149 }
150
151 if target_state {
152 prob_target_true += joint_prob;
153 } else {
154 prob_target_false += joint_prob;
155 }
156 }
157 }
158
159 let total = prob_target_true + prob_target_false;
160 if total > 0.0 {
161 Some(prob_target_true / total)
162 } else {
163 None
164 }
165 }
166
167 pub fn markov_blanket(&self, node_id: u64, out: &mut [u64]) -> usize {
172 let mut n = 0usize;
173 let add = |id: u64, out: &mut [u64], n: &mut usize| {
174 if id != node_id && id != 0 && !out[..*n].contains(&id) && *n < out.len() {
175 out[*n] = id;
176 *n += 1;
177 }
178 };
179 for i in 0..self.num_nodes {
180 if self.nodes[i].id == node_id {
181 for p in 0..self.nodes[i].num_parents {
182 add(self.nodes[i].parent_ids[p], out, &mut n);
183 }
184 }
185 }
186 for i in 0..self.num_nodes {
187 let child = self.nodes[i];
188 if child.parent_ids[..child.num_parents].contains(&node_id) {
189 add(child.id, out, &mut n); for p in 0..child.num_parents {
191 add(child.parent_ids[p], out, &mut n); }
193 }
194 }
195 n
196 }
197
198 fn node_cpt(&self, node_idx: usize, state: bool, assign: &[bool]) -> f32 {
201 let node = &self.nodes[node_idx];
202 let mut parent_idx = 0usize;
203 for p in 0..node.num_parents {
204 let pid = node.parent_ids[p];
205 for j in 0..self.num_nodes {
206 if self.nodes[j].id == pid {
207 if assign[j] {
208 parent_idx |= 1 << p;
209 }
210 break;
211 }
212 }
213 }
214 let pt = node.probabilities[parent_idx];
215 if state {
216 pt
217 } else {
218 1.0 - pt
219 }
220 }
221
222 fn gibbs_conditional(&self, node_idx: usize, state: bool, assign: &[bool]) -> f32 {
225 let mut a = [false; MAX_BAYESIAN_NODES];
226 a[..self.num_nodes].copy_from_slice(&assign[..self.num_nodes]);
227 a[node_idx] = state;
228 let mut prob = self.node_cpt(node_idx, state, &a);
229 let this_id = self.nodes[node_idx].id;
230 for c in 0..self.num_nodes {
231 let child = self.nodes[c];
232 if child.parent_ids[..child.num_parents].contains(&this_id) {
233 prob *= self.node_cpt(c, a[c], &a);
234 }
235 }
236 prob
237 }
238
239 pub fn gibbs_estimate(&self, target_id: u64, samples: u32, seed: u64) -> Option<f32> {
244 let mut target_idx = None;
245 for i in 0..self.num_nodes {
246 if self.nodes[i].id == target_id {
247 target_idx = Some(i);
248 }
249 }
250 let target_idx = target_idx?;
251 let mut rng = seed | 1;
252 let mut assign = [false; MAX_BAYESIAN_NODES];
253 for i in 0..self.num_nodes {
254 assign[i] = match self.nodes[i].evidence {
255 Some(e) => e,
256 None => next_unit(&mut rng) < 0.5,
257 };
258 }
259 let mut count_true = 0u32;
260 for _ in 0..samples {
261 for i in 0..self.num_nodes {
262 if self.nodes[i].evidence.is_some() {
263 continue;
264 }
265 let pt = self.gibbs_conditional(i, true, &assign);
266 let pf = self.gibbs_conditional(i, false, &assign);
267 let denom = pt + pf;
268 let prob = if denom > 0.0 { pt / denom } else { 0.5 };
269 assign[i] = next_unit(&mut rng) < prob;
270 }
271 if assign[target_idx] {
272 count_true += 1;
273 }
274 }
275 if samples == 0 {
276 None
277 } else {
278 Some(count_true as f32 / samples as f32)
279 }
280 }
281}
282
283fn next_unit(state: &mut u64) -> f32 {
285 let mut x = *state;
286 x ^= x << 13;
287 x ^= x >> 7;
288 x ^= x << 17;
289 *state = x;
290 ((x >> 40) as f32) / ((1u32 << 24) as f32)
291}
292
293#[inline]
298pub fn pc_adjacent(correlation: f32, threshold: f32) -> bool {
299 correlation.abs() >= threshold
300}
301
302#[cfg(test)]
303mod tests {
304 use super::*;
305
306 #[test]
307 fn test_bayesian_network() {
308 let mut network = BayesianNetwork::new();
309
310 let mut node0 = BayesianNode::default();
312 node0.id = 100;
313 node0.probabilities[0] = 0.2;
314 network.add_node(node0).unwrap();
315
316 let mut node1 = BayesianNode::default();
320 node1.id = 200;
321 node1.parent_ids[0] = 100;
322 node1.num_parents = 1;
323 node1.probabilities[1] = 0.01; node1.probabilities[0] = 0.40; network.add_node(node1).unwrap();
326
327 let mut node2 = BayesianNode::default();
334 node2.id = 300;
335 node2.parent_ids[0] = 100;
336 node2.parent_ids[1] = 200;
337 node2.num_parents = 2;
338 node2.probabilities[0] = 0.0;
339 node2.probabilities[1] = 0.8;
340 node2.probabilities[2] = 0.9;
341 node2.probabilities[3] = 0.99;
342
343 node2.evidence = Some(true);
345 network.add_node(node2).unwrap();
346
347 let p_rain = network.update_beliefs(100).unwrap();
349
350 assert!((p_rain - 0.3577).abs() < 0.001);
352 }
353
354 fn sprinkler(with_wet_evidence: bool) -> BayesianNetwork {
355 let mut net = BayesianNetwork::new();
356 let mut n0 = BayesianNode::default();
357 n0.id = 100;
358 n0.probabilities[0] = 0.2;
359 net.add_node(n0).unwrap();
360 let mut n1 = BayesianNode::default();
361 n1.id = 200;
362 n1.parent_ids[0] = 100;
363 n1.num_parents = 1;
364 n1.probabilities[1] = 0.01;
365 n1.probabilities[0] = 0.40;
366 net.add_node(n1).unwrap();
367 let mut n2 = BayesianNode::default();
368 n2.id = 300;
369 n2.parent_ids[0] = 100;
370 n2.parent_ids[1] = 200;
371 n2.num_parents = 2;
372 n2.probabilities = [
373 0.0, 0.8, 0.9, 0.99, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
374 ];
375 if with_wet_evidence {
376 n2.evidence = Some(true);
377 }
378 net.add_node(n2).unwrap();
379 net
380 }
381
382 #[test]
383 fn markov_blanket_of_a_node() {
384 let net = sprinkler(false);
385 let mut out = [0u64; 8];
387 let n = net.markov_blanket(100, &mut out);
388 assert_eq!(n, 2);
389 assert!(out[..n].contains(&200) && out[..n].contains(&300));
390 }
391
392 #[test]
393 fn gibbs_approximates_the_exact_posterior() {
394 let net = sprinkler(true);
395 let exact = net.update_beliefs(100).unwrap(); let approx = net.gibbs_estimate(100, 40_000, 0x9E3779B97F4A7C15).unwrap();
397 assert!(
398 (approx - exact).abs() < 0.08,
399 "Gibbs {approx} should approximate exact {exact}"
400 );
401 }
402
403 #[test]
404 fn pc_skeleton_uses_absolute_correlation() {
405 assert!(pc_adjacent(0.6, 0.3));
406 assert!(!pc_adjacent(0.1, 0.3));
407 assert!(pc_adjacent(-0.5, 0.3), "structure depends on |correlation|");
408 }
409}