Stanford CS221 | Autumn 2025 | Lecture 13: Bayesian Networks and Gibbs Sampling

Joint distribution as product of local conditionals

The joint probability over all variables equals the product of each node's conditional probability given its parents, such as P(B,E,A) = P(B)P(E)P(A|B,E) where P(B=1)=0.05 and P(E=1)=0.05, avoiding the need to specify 2^100 entries for 100 variables.

Graph structure encodes dependencies

Directed edges represent direct dependencies—such as Alarm (A) depending on Burglary (B) and Earthquake (E)—while lack of edges indicates conditional independence assumptions that make the representation compact.

Exact inference via conditioning and marginalization

To compute P(B|A=1)=0.51, slice the joint distribution to evidence (A=1), marginalize out irrelevant variables (E) by summing, and normalize by dividing by P(A=1).

Simple but wasteful sampling mechanism

Rejection sampling generates independent samples from the probabilistic program and discards any where evidence fails (e.g., A≠1), using only matching samples to estimate query probabilities like P(B|A=1)≈0.44 with 300 samples.

Catastrophic inefficiency with rare evidence

When evidence has exponentially small probability (e.g., 10^-30), the algorithm rejects nearly all samples, requiring prohibitive computation time to obtain sufficient valid observations.

Evidence-blind generation

Samples are generated without considering the target evidence, making the algorithm 'blind' to constraints until the rejection check occurs.

MCMC with dependent samples

Gibbs sampling generates a Markov chain where each sample depends on the previous one, starting with an arbitrary assignment that satisfies the evidence and avoiding rejection entirely.

Iterative single-variable updates

The algorithm cycles through variables, resampling each one conditioned on the current values of all other variables (its Markov blanket), gradually converging to the target conditional distribution.

Efficiency trade-off

While samples are correlated—requiring more samples than independent draws for equivalent accuracy—the method avoids exponential rejection rates, making it practical for rare evidence.

Modeling noisy communication chains

A 3-node chain (A→B→C) represents message passing where each hop preserves the bit with probability 0.8 and flips it with probability 0.2.

Inference with rare evidence

Given the final recipient hears C=1, Gibbs sampling can efficiently estimate P(A=1|C=1)≈0.65 without rejecting samples, whereas rejection sampling struggles if C=1 is unlikely.