Understand Bayesian
Networks

Chapter 1: DAGs — Directed Acyclic Graphs

A Bayesian network is a DAG: a Directed Acyclic Graph. Each node is a random variable. Each directed edge (arrow) means "this variable directly influences that one." The "acyclic" part means no loops — you can't follow arrows and end up where you started.

The graph encodes the factorization of the joint probability. For variables X₁, ..., X_n with parents Pa(X_i):

This factorization is why Bayes nets are efficient. Instead of one giant table with 2ⁿ entries, we have n small tables, each conditioned on only a few parents.

Chapter 2: Conditional Probability Tables

Each node stores a CPT (Conditional Probability Table). For a root node (no parents), it's just a prior: P(Rain) = 0.2. For a node with parents, it specifies the probability for each combination of parent states: P(Wet Grass | Rain=T, Sprinkler=T) = 0.99.

The CPT is where domain knowledge lives. A doctor building a medical Bayes net fills in CPTs like P(Cough | Flu=yes, Smoker=yes) = 0.85 based on clinical experience or data.

python
import numpy as np

# CPTs are just arrays indexed by parent states
P_rain = np.array([0.2, 0.8])           # [T, F]
P_sprinkler_given_rain = np.array([       # [rain_state, sprinkler_state]
    [0.4, 0.6],    # Rain=T: 40% sprinkler on
    [0.01, 0.99]   # Rain=F: 1% sprinkler on
])
P_wet_given_sr = np.array([              # [sprinkler, rain, wet_state]
    [[0.99, 0.01], [0.80, 0.20]],  # S=T
    [[0.90, 0.10], [0.01, 0.99]]   # S=F
])

# Total params: 2 + 4 + 8 = 14
# Full joint would be 2^3 = 8 (modest savings)
# With 20 sparse variables: ~100 vs 2^20 = 1,048,576

Chapter 3: Conditional Independence

The whole point of a Bayes net is to encode conditional independencies. Two variables X and Y are conditionally independent given Z (written X ⊥ Y | Z) if knowing Z makes X irrelevant for predicting Y.

Example: Does knowing the season help you predict if the grass is wet? Yes. But if you already know whether it rained AND whether the sprinkler was on, then season adds nothing. Grass is conditionally independent of Season given {Rain, Sprinkler}.

In practice, this means conditional independence lets you drop variables from computations. If you know Rain and Sprinkler, you don't need to ask about Season to predict Wet Grass. Every dropped variable halves (for binary) the size of the table you need to compute. With 5 irrelevant variables dropped, that's a 2&sup5; = 32x speedup.

Chapter 4: D-Separation

How do you read off conditional independencies from the graph structure? The answer is d-separation. It's a purely graphical criterion: check if information can flow between two nodes along a path, given what you've observed.

There are three fundamental structures. Each behaves differently when the middle node is observed vs. unobserved:

Chapter 5: Exact Inference — Variable Elimination

Given evidence (some variables observed), we want to compute the posterior probability of a query variable. The brute-force way: sum over all combinations of unobserved variables. But that's exponential. Variable elimination does it smarter by summing out variables one at a time, exploiting the factored structure.

Let's trace through with actual numbers. Query: P(Rain=T | Wet=T). Our factors are P(R), P(S|R), P(W|R,S). We set W=T and eliminate S first, then normalize.

python
# P(Rain=T | Wet=T) — worked example

# Step 1: Set evidence W=T in P(W|R,S)
#   f(R=T,S=T) = P(W=T|R=T,S=T) = 0.99
#   f(R=T,S=F) = P(W=T|R=T,S=F) = 0.80
#   f(R=F,S=T) = P(W=T|R=F,S=T) = 0.90
#   f(R=F,S=F) = P(W=T|R=F,S=F) = 0.01

# Step 2: Eliminate S — sum over S in P(S|R)*f(R,S)
#   g(R=T) = P(S=T|R=T)*f(T,T) + P(S=F|R=T)*f(T,F)
#          = 0.40*0.99 + 0.60*0.80 = 0.396 + 0.480 = 0.876
#   g(R=F) = P(S=T|R=F)*f(F,T) + P(S=F|R=F)*f(F,F)
#          = 0.01*0.90 + 0.99*0.01 = 0.009 + 0.0099 = 0.0189

# Step 3: Multiply by P(R) and normalize
#   h(R=T) = P(R=T)*g(R=T) = 0.2 * 0.876  = 0.1752
#   h(R=F) = P(R=F)*g(R=F) = 0.8 * 0.0189 = 0.01512
#   P(R=T|W=T) = 0.1752 / (0.1752+0.01512) = 0.920

python
from itertools import product

def variable_elimination(network, evidence, query, elim_order):
    # Step 1: Build initial factors from CPTs
    factors = []
    for node, info in network.items():
        scope = info['parents'] + [node]
        cpt = info['cpt']
        table = {}
        for assignment in product([0,1], repeat=len(scope)):
            # Index into nested CPT
            val = cpt
            for idx in assignment:
                val = val[idx]
            table[assignment] = val
        factors.append((scope, table))

    # Step 2: Restrict evidence
    for i, (scope, table) in enumerate(factors):
        new_scope = [v for v in scope if v not in evidence]
        if new_scope == scope:
            continue
        new_table = {}
        for assignment in product([0,1], repeat=len(new_scope)):
            full = list(assignment)
            for j, v in enumerate(scope):
                if v in evidence:
                    full.insert(j, evidence[v])
            new_table[assignment] = table[tuple(full)]
        factors[i] = (new_scope, new_table)

    # Step 3: Eliminate variables one by one
    for var in elim_order:
        # Collect factors mentioning var
        relevant = [(s,t) for s,t in factors if var in s]
        remaining = [(s,t) for s,t in factors if var not in s]

        # Multiply all relevant factors
        combined_scope = list(dict.fromkeys(
            v for s,_ in relevant for v in s))
        combined = {}
        for assignment in product([0,1], repeat=len(combined_scope)):
            amap = dict(zip(combined_scope, assignment))
            val = 1.0
            for s, t in relevant:
                key = tuple(amap[v] for v in s)
                val *= t[key]
            combined[assignment] = val

        # Sum out var
        var_idx = combined_scope.index(var)
        new_scope = [v for v in combined_scope if v != var]
        new_table = {}
        for assignment in product([0,1], repeat=len(new_scope)):
            total = 0.0
            for val in [0, 1]:
                full = list(assignment)
                full.insert(var_idx, val)
                total += combined[tuple(full)]
            new_table[assignment] = total
        remaining.append((new_scope, new_table))
        factors = remaining

    # Step 4: Multiply remaining, normalize
    result = [0.0, 0.0]
    for qval in [0, 1]:
        p = 1.0
        for scope, table in factors:
            key = tuple(qval if v == query else evidence[v]
                        for v in scope)
            p *= table.get(key, table.get((qval,), 1.0))
        result[qval] = p
    total = sum(result)
    return [r/total for r in result]

Chapter 6: Belief Propagation

For tree-structured networks (no undirected loops), there's an elegant alternative: belief propagation (the sum-product algorithm). Each node sends messages to its neighbors summarizing what it knows. After two passes (leaves to root, root to leaves), every node has the exact marginal posterior.

A message from node i to node j says: "Based on everything I've seen on my side of the tree, here's what I believe about your state." It's local computation with global results.

In implementation, each message is just an array of floats — one entry per state of the receiving node. For binary variables, every message is a [2] vector. A node computes its belief by multiplying all incoming messages element-wise and normalizing. For our 7-node tree, that's 12 messages (one per edge direction), each of size 2. Total computation: 24 multiplications + 7 normalizations. Compare that to the full joint: 2&sup7; = 128 entries.

Chapter 7: Interactive DAG Builder

Build your own Bayesian network! Click to add nodes, drag between nodes to add edges. Set CPTs and run inference queries. This is the full SLAM experience — but for probability.

Chapter 8: Learning Structure

So far we've assumed the graph structure is given. But what if you have data and need to discover the dependencies? This is structure learning — arguably the hardest problem in Bayesian networks.

There are two main approaches: score-based (search over possible graphs, score each one) and constraint-based (test conditional independencies in the data, build the graph from the results).

Chapter 9: Connections & Beyond

Bayesian networks are everywhere. An HMM (Hidden Markov Model) is a special case — a chain-structured Bayes net where hidden states emit observations. A Kalman filter is a continuous Gaussian Bayes net with linear dynamics.

python
# A Bayes net = DAG + CPTs. That's it.
network = {
    'Rain':      { 'parents': [],
                   'cpt': [0.2, 0.8] },
    'Sprinkler': { 'parents': ['Rain'],
                   'cpt': [[0.4, 0.6], [0.01, 0.99]] },
    'Wet':       { 'parents': ['Sprinkler', 'Rain'],
                   'cpt': [[[0.99,0.01],[0.8,0.2]],
                           [[0.9,0.1],[0.01,0.99]]] }
}
# Inference = message passing on this data structure
# To query P(Rain|Wet=T): variable elimination over this dict

This computational wall is a key reason neural networks replaced Bayes nets for perception tasks. A Bayes net for image classification would need one node per pixel, with hand-designed dependencies between neighboring pixels — thousands of nodes, each with CPTs you'd somehow need to specify. A neural network learns these dependencies automatically via gradient descent, scaling to millions of parameters without anyone specifying a single conditional probability. The tradeoff: neural networks are black boxes, while Bayes nets give you interpretable, auditable reasoning.