Skip to main content

qualia_core_db/modalities/
probabilistic.rs

1use crate::NQuin;
2
3/// `true` when `weight >= threshold`.
4pub 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,              // Variable hash
13    pub parent_ids: [u64; 4], // Max 4 parents to keep it fixed size
14    pub num_parents: usize,
15    pub probabilities: [f32; 16], // 2^4 = 16 conditional probabilities
16    pub evidence: Option<bool>,   // Observed state if any
17}
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    /// Creates a default `BayesianNetwork`.
38    pub fn new() -> Self {
39        Self {
40            nodes: [BayesianNode::default(); MAX_BAYESIAN_NODES],
41            num_nodes: 0,
42        }
43    }
44
45    /// Adds a node; error on duplicate.
46    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    /// Extract probability encoded in the Quin's metadata field (canonical
56    /// truth-degree via the FrameLayout ABI — shared with fuzzy/stochastic).
57    pub fn extract_weight(quin: &NQuin) -> f32 {
58        crate::frame_layout::truth_degree(quin.metadata)
59    }
60
61    /// Exact inference via variable enumeration.
62    /// Fully zero-allocation, iteratively evaluates joint probability table on the stack.
63    /// Max unobserved variables allowed is 16 to prevent excessive CPU loop blocking (O(2^N)).
64    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; // Too complex for zero-heap full enumeration
85        }
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    /// The **Markov blanket** of `node_id`: its parents, its children, and its children's OTHER
168    /// parents (co-parents). Conditioned on its blanket a node is independent of all others —
169    /// the locality used for rapid conditional-independence testing and Gibbs sampling. Writes the
170    /// member ids into `out`, returns the count. Zero-heap.
171    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); // a child
190                for p in 0..child.num_parents {
191                    add(child.parent_ids[p], out, &mut n); // its co-parents
192                }
193            }
194        }
195        n
196    }
197
198    /// `P(node = state | parents)` from the node's CPT, reading parents' states out of `assign`
199    /// (indexed by node order).
200    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    /// Unnormalised `P(node_idx = state | rest)` ∝ `P(node|parents) · Π_children P(child|parents)`
223    /// — the Gibbs full-conditional over the Markov blanket.
224    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    /// **Gibbs sampling** (MCMC) estimate of `P(target = true | evidence)` — approximate inference
240    /// for networks too large for exact enumeration. `samples` sweeps, `seed` for the PRNG. Each
241    /// non-evidence variable is resampled from its Markov-blanket conditional. Zero-heap (bounded
242    /// stack arrays). `None` if `target_id` is not in the network.
243    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
283/// Deterministic xorshift PRNG → a uniform `f32` in `[0,1)`. Zero-heap.
284fn 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/// **PC-algorithm skeleton** (constraint-based structure learning): two variables are adjacent
294/// (share an edge) iff their `correlation` is at/above `threshold` in absolute value — i.e. they
295/// are NOT marginally independent. This is the order-0 skeleton; the full PC additionally removes
296/// edges via conditional-independence tests over separating sets.
297#[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        // Node 0: Rain (no parents, P(Rain)=0.2)
311        let mut node0 = BayesianNode::default();
312        node0.id = 100;
313        node0.probabilities[0] = 0.2;
314        network.add_node(node0).unwrap();
315
316        // Node 1: Sprinkler (parent: Rain)
317        // P(Sprinkler|Rain) = 0.01
318        // P(Sprinkler|NoRain) = 0.40
319        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; // Rain=True -> bit 0 is 1
324        node1.probabilities[0] = 0.40; // Rain=False -> bit 0 is 0
325        network.add_node(node1).unwrap();
326
327        // Node 2: Grass Wet (parents: Rain, Sprinkler)
328        // Rain is bit 0, Sprinkler is bit 1
329        // F, F (idx 0) = 0.0
330        // T, F (idx 1) = 0.8
331        // F, T (idx 2) = 0.9
332        // T, T (idx 3) = 0.99
333        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        // Let's observe the grass is wet
344        node2.evidence = Some(true);
345        network.add_node(node2).unwrap();
346
347        // Query: What is probability it rained, given grass is wet?
348        let p_rain = network.update_beliefs(100).unwrap();
349
350        // Approximate expected result: P(Rain|Wet) ≈ 0.3577
351        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        // Blanket(Rain) = children {Sprinkler, GrassWet} + co-parents (Sprinkler already in).
386        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(); // ≈ 0.3577
396        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}