Inference

Chapter 1: Exact Inference by Enumeration

The blunt-force approach to inference is to directly apply the definition of conditional probability. We want P(Q = q | E = e). By definition, this equals P(Q = q, E = e) / P(E = e). Both of these are just marginals of the joint distribution.

The joint distribution over all variables X_1:n in a Bayesian network factorizes as a product of conditional probability tables (CPTs):

To compute P(Q = q, E = e), we sum this joint over all configurations of the remaining hidden variables H (those not in Q or E):

This is inference by enumeration: enumerate every possible assignment to the hidden variables, evaluate the joint for each, and sum up. It works. It is also catastrophically slow for large networks — if there are k hidden binary variables, there are 2^k terms to sum.

The enumeration algorithm has exponential time complexity in the number of hidden variables. For 30 binary hidden variables, that is over a billion terms. We need something smarter.

Chapter 2: Variable Elimination — Smarter Summing

Enumeration is slow because it repeatedly computes the same sub-products. Variable elimination fixes this by pushing sums inside products — eliminating one variable at a time, caching the intermediate results as factors.

A factor is a function from a set of variables to a non-negative real number. Every CPT in the network is a factor. We can multiply two factors (produce a new factor over their union of variables) and marginalize a factor (sum out one variable to get a factor over fewer variables).

The algorithm:

The cost of variable elimination depends critically on the elimination order. A good order keeps intermediate factors small. Finding the optimal order is itself NP-hard, but good heuristics (eliminate the variable that creates the smallest new factor) work well in practice.

Chapter 3: Belief Propagation

Variable elimination answers a single query efficiently. But what if we want to compute posteriors for every variable simultaneously? Running elimination separately for each variable wastes computation. Belief propagation does all of them at once on tree-structured networks.

On a tree (a network with no undirected cycles), we pick any node as root and run two passes: a collect pass (leaves send messages to root) and a distribute pass (root sends messages back to leaves). After two passes, every node has the information it needs to compute its own marginal.

Formally, the message from node i to node j is:

The posterior at node j after collecting all messages is proportional to its own CPT times the product of all incoming messages:

Belief propagation is exact on trees. On networks with cycles (loopy graphs), the same message-passing equations are applied iteratively — this is called loopy belief propagation. It often converges to good approximate answers, but correctness is not guaranteed.

Chapter 4: Computational Complexity

Here is the sobering truth: exact inference in general Bayesian networks is NP-hard. This means no algorithm can efficiently solve all instances unless P = NP. The hardness comes from networks with tightly coupled loops that prevent the factorization tricks from reducing the problem size.

The key quantity governing difficulty is treewidth — roughly, how tree-like is the network? A tree has treewidth 1. Each extra edge that creates a loop can increase treewidth. Variable elimination runs in time O(n · d^w+1) where d is the domain size and w is the treewidth. On a tree (w=1), this is linear. On a dense network, it is exponential.

The NP-hardness motivates two responses: (1) restrict to tractable network structures (trees, polytrees, networks with small treewidth), or (2) use approximate inference via sampling. The next chapters cover sampling methods.

Chapter 5: Direct Sampling

Sampling methods sidestep the complexity barrier by estimating probabilities from random samples. The simplest approach is direct sampling (also called prior sampling or ancestral sampling): generate complete assignments to all variables by following the network structure from parents to children.

The algorithm is elegantly simple. Process variables in topological order (parents before children). For each variable, look up its CPT given the already-sampled values of its parents, then draw a random sample from that distribution. Repeat N times, then count.

Chapter 6: Likelihood Weighted Sampling

Likelihood weighted (LW) sampling solves the rejection problem by forcing every sample to be consistent with the evidence. Instead of sampling evidence variables, we fix them to their observed values. To compensate for this "cheating," each sample gets a weight equal to the probability of the evidence given the sampled non-evidence variables.

For a sample x with evidence E = e, the weight is:

We then estimate the posterior as a weighted frequency:

LW sampling is much more efficient than rejection sampling for low-probability evidence. Every sample contributes, though samples with very low weights contribute little. The algorithm degrades gracefully: rare evidence leads to low-weight samples, not wasted samples.

python
def likelihood_weighted_sample(bn, evidence):
    # bn: Bayesian network with topo_order, cpd(node, parent_vals)
    w = 1.0
    sample = {}
    for node in bn.topo_order:
        parents = bn.parents[node]
        parent_vals = tuple(sample[p] for p in parents)
        if node in evidence:
            val = evidence[node]
            w *= bn.cpd(node, parent_vals)[val]  # multiply likelihood
            sample[node] = val
        else:
            dist = bn.cpd(node, parent_vals)
            sample[node] = np.random.choice(len(dist), p=dist)
    return sample, w

Chapter 7: Gibbs Sampling — MCMC Inference

Both direct and LW sampling draw each sample independently. Gibbs sampling takes a completely different approach: it constructs a Markov chain whose stationary distribution is the posterior P(X | E = e). We run the chain for many steps and collect samples from it.

Start from any complete assignment consistent with the evidence. Then repeatedly: pick a non-evidence variable X_i at random, and resample it from its full conditional — the distribution P(X_i | all other variables fixed).

The full conditional for X_i given all others x_−i is proportional to:

python
def gibbs_sample(bn, evidence, n_samples, burn_in=100):
    state = {**evidence}
    for node in bn.non_evidence_nodes:
        state[node] = np.random.choice(bn.domain_size[node])

    samples = []
    for step in range(burn_in + n_samples):
        node = np.random.choice(bn.non_evidence_nodes)
        # Full conditional from Markov blanket (local CPT lookups only)
        probs = bn.markov_blanket_conditional(node, state)
        state[node] = np.random.choice(len(probs), p=probs)
        if step >= burn_in:
            samples.append(state.copy())
    return samples

Chapter 8: Inference in Gaussian Models

When all variables are jointly Gaussian, inference has a beautiful closed-form solution. No sampling, no enumeration, no message passing — just matrix algebra.

If X and Y are jointly Gaussian with covariance structure Σ, then conditioning on Y = y gives:

This is the conditional Gaussian formula. The posterior mean is the prior mean plus a correction proportional to how surprising the observation was. The posterior covariance is the prior covariance minus the information gained from observing Y — observing evidence always reduces uncertainty.

A Gaussian Bayesian network is one where every CPD is a linear Gaussian: X_i | pa(X_i) ~ N(μ_i + β_i^T pa(X_i), σ_i²). The joint over all variables is then a single multivariate Gaussian, and inference reduces to the conditional formula above.

python
import numpy as np

def gaussian_inference(mu_x, mu_y, sigma_xx, sigma_xy, sigma_yy, y_obs):
    # Scalar case: P(X | Y=y_obs) given joint Gaussian parameters
    K = sigma_xy / sigma_yy              # Kalman gain
    mu_post = mu_x + K * (y_obs - mu_y) # Updated mean
    sigma_post = sigma_xx - K * sigma_xy # Updated variance
    return mu_post, sigma_post

# Example: rho=0.7, observe Y=1.0
mu_p, s_p = gaussian_inference(
    mu_x=0, mu_y=0, sigma_xx=1.0, sigma_xy=0.7, sigma_yy=1.0, y_obs=1.0
)
# mu_post = 0.70, sigma_post = 0.51

Chapter 9: Connections & What Comes Next

Inference is the computational engine underlying everything else in this book. Every algorithm that reasons about uncertainty — filtering, planning, learning — calls some form of inference as a subroutine.

How this connects to later chapters

Related micro-lessons

"In the long run it's not just whether you're right or wrong, but how confident you are, and how you respond to the evidence."
— Nate Silver, The Signal and the Noise