Bayesian Networks
Compact joint distributions from conditional independence.
Thirty yes-or-no variables have a joint distribution with more than a billion entries. If each variable depends directly on at most three others, a Bayesian network stores the same distribution in at most 240 numbers, and the graph alone tells you which variables are independent. This lesson builds the machinery: the factorization, d-separation, exact inference by variable elimination, and sampling when exact inference is too expensive.
What you’ll learn
- Derive the factorization from the chain rule, count its parameters, and prove that it is equivalent to the local Markov property.
- Decide conditional independence with d-separation by analyzing chains, forks and colliders, and identify a node's Markov blanket.
- Run variable elimination on a query, bound its cost by the induced width, and explain why exact inference is NP-hard in general but linear-time on polytrees.
- Estimate posteriors by rejection sampling, likelihood weighting and Gibbs sampling, predict when each one fails, and learn CPTs from complete data by counting.
From the chain rule to a graph
A Bayesian network is a directed acyclic graph (DAG) whose nodes are random variables , together with one conditional probability table (CPT) per node, , where is the set of 's parents. The network represents one joint distribution:
Number the variables in a topological order of the graph, parents before children. The chain rule holds for every distribution:
The network's modeling assumption: given its parents, each variable is conditionally independent of its other predecessors. The parents are among the predecessors, so each chain-rule factor shrinks to a CPT entry:
A variable with values whose parents have joint configurations needs numbers, so the network needs
In the alarm network of the Input Layer that is numbers instead of . Any entry of the joint is a product of five of them, for example a false alarm that both neighbors report:
CPTs grow exponentially in the number of parents, so models with many causes use structured CPTs. In a noisy-OR, each true parent independently fails to trigger the effect with probability , so : numbers instead of .
A binary node has four binary parents, and its CPT is a full table (no noisy-OR). How many independent numbers does the CPT contain?
- 4
- 16
- 32
- 31
Show the answer
B. 16
One number, , for each of the parent configurations; follows by subtraction.
Reading independence off the graph
The factorization implies many more independences than the local ones, and three-node patterns explain them all. In each, ask whether and are dependent, first marginally and then given the middle node :
| Pattern | Graph | and marginally | Given |
|---|---|---|---|
| Chain | dependent (in general) | independent | |
| Fork (common cause) | dependent (in general) | independent | |
| Collider (common effect) | independent | dependent: explaining away |
Chain. Once is known, adds nothing about :
Collider, marginally. Summing out the effect leaves the two causes' priors:
Collider, given . Now the CPT of couples them, and the joint factors as only if happens to:
Observing a descendant of the collider partly reveals it, so it couples the causes too. In the alarm network:
One consequence is used constantly. The Markov blanket of , made of its parents, its children and its children's other parents, d-separates from every other node: once the blanket is known, nothing else in the network carries information about .
In the sprinkler network (Cloudy → Sprinkler, Cloudy → Rain, Sprinkler → WetGrass ← Rain), which statement does d-separation support?
- Sprinkler and Rain are independent, since neither is a parent of the other
- Sprinkler and Rain are independent given WetGrass
- Sprinkler and Rain are independent given Cloudy, and in general dependent given Cloudy and WetGrass
- Sprinkler and Rain are dependent given every set of the other variables
Show the answer
C. Sprinkler and Rain are independent given Cloudy, and in general dependent given Cloudy and WetGrass
Two paths join them. The fork is blocked by observing ; the collider is open only if is observed. Given alone both are blocked, and in the built-in network P(Rain | Cloudy) stays 80% whatever the sprinkler did. Given and , the collider opens: P(Rain | Cloudy, WetGrass) = 97.6% falls to 81.5% when you also learn that the sprinkler ran.
Exact inference: variable elimination
A query asks for , the distribution of a query variable given evidence , with the remaining hidden variables summed out: , where normalizes. Summing the full joint costs for binary variables.
Variable elimination (VE) pushes each sum inward past the factors that do not mention its variable, and stores the intermediate tables, called factors. It is dynamic programming over the factorization.
Write the query with each sum pushed as far right as it can go:
The evidence turns the two call CPTs into one factor of alone, listed as (true, false):
Sum out : multiply the factors that mention and sum. This creates a factor over and , for example
Sum out , weighting by (with and ):
Multiply by and normalize. The normalizer, , is itself:
function ELIMINATION-ASK(X, e, network, order):
factors ← [CPT of each node, restricted to the evidence e]
for each hidden variable Y in order: # everything except X and the evidence
related ← the factors that mention Y
g ← SUM-OUT(Y, POINTWISE-PRODUCT(related)) # one new factor, without Y
factors ← (factors − related) + [g]
return NORMALIZE(POINTWISE-PRODUCT(factors)) # a table over X aloneBefore eliminating anything, drop every variable that is not an ancestor of or of the evidence: its CPTs sum to 1. For , MaryCalls is irrelevant.
Eliminating creates a factor over all the variables that currently share a factor with , so the cost is set by the largest factor the ordering ever creates. If it has variables, VE takes time for variables with values; is the induced width of the ordering. The smallest induced width over all orderings is the treewidth of the moral graph (connect every pair of co-parents, then drop the directions). Finding the best ordering is NP-hard, but greedy rules such as min-fill (eliminate the variable whose elimination adds the fewest new edges) work well in practice.
| Structure | Treewidth | Exact inference |
|---|---|---|
| Chain, or an HMM unrolled over steps with states | 1 | |
| Polytree (no cycles even ignoring directions) | largest number of parents | linear in the total size of the CPTs |
| grid | about | exponential in |
| Arbitrary DAG | up to | NP-hard in general |
Think first A hidden cause has children , none observed, each with values. For the query , compare eliminating first with eliminating it last.
Eliminating first multiplies all CPTs into one factor over before summing out : a table of entries. Eliminating first is free, since each , and then costs about operations. Same network, induced width versus 1.
Approximate inference by sampling
When the treewidth is too large, estimate the posterior from samples instead. Each method below is consistent: its estimate converges to the exact posterior as the number of samples grows, with an error that shrinks like , though the constant in front can be enormous.
- Prior (ancestral) sampling. Sample each variable from its CPT given its already-sampled parents, in topological order. Each run is an exact draw from the joint distribution.
- Rejection sampling. Discard the samples that disagree with and count among the rest. It is correct, but only a fraction survives, and typically shrinks exponentially with the number of evidence variables.
- Likelihood weighting. Clamp the evidence variables to their observed values, sample only the others, and give each sample the weight : the probability of the evidence given its sampled parents.
- Gibbs sampling. Start from any state that agrees with , then repeatedly pick a non-evidence variable and resample it given its Markov blanket, . This is MCMC: a Markov chain whose stationary distribution is .
You draw 10,000 samples from the alarm network by prior sampling, to estimate P(Burglary | JohnCalls, MaryCalls) by rejection. About how many samples agree with the evidence?
Show the answer
21
, the normalizer from the variable-elimination step, so about 21 samples survive, and about 6 of those contain a burglary. The estimate of 28.4% then rests on roughly six events, a relative error of order . Rejection sampling threw away 99.8% of its work.
import random
P_C = 0.5 # P(Cloudy)
P_S = {True: 0.1, False: 0.5} # P(Sprinkler | Cloudy)
P_R = {True: 0.8, False: 0.2} # P(Rain | Cloudy)
P_W = {(True, True): 0.99, (True, False): 0.9, # P(WetGrass | Sprinkler, Rain)
(False, True): 0.9, (False, False): 0.0}
def bern(p):
return random.random() < p
def likelihood_weighting(n):
"""Estimate P(Rain = true | WetGrass = true)."""
num = den = 0.0
for _ in range(n):
c = bern(P_C) # sample the unobserved nodes
s = bern(P_S[c]) # in topological order ...
r = bern(P_R[c])
w = P_W[(s, r)] # ... and weight by P(evidence | parents)
num += w * r
den += w
return num / den
print(likelihood_weighting(100_000)) # exact: 0.4581 / 0.6471 = 0.708Likelihood weighting on the sprinkler network. WetGrass is never sampled; it enters only through the weight. The exact answer, , comes from variable elimination (sum out Sprinkler, then Cloudy), and the estimate converges to it.
A sample assigns values to the non-evidence variables, drawn from their CPTs with the evidence clamped, and then receives a weight:
Together the two products contain every CPT exactly once, so their product is the joint probability:
Hence the weighted count of samples with converges to , and normalizing gives the posterior. Likelihood weighting is importance sampling, with the network itself (evidence clamped) as the proposal distribution.
Learning the numbers, and where to go deeper
So far the CPTs were given. With complete records, the log-likelihood of the CPT entries splits into independent terms, one per node and parent configuration:
Rare parent configurations give zero or tiny counts. A Dirichlet prior adds pseudo-counts, for a node with values, which is the additive smoothing of Bayesian Reasoning. With missing values or hidden variables the likelihood no longer decomposes, and the EM algorithm alternates between inference (expected counts, computed with the algorithms above) and counting.
The graph can be learned from data too, but only up to a limit. Two DAGs with the same skeleton and the same v-structures ( with and not adjacent) encode exactly the same independences (Verma & Pearl, 1990), so no amount of observational data can tell from or . Only the collider stands apart, which is why colliders anchor causal discovery (Causal Inference).
Key takeaways
- A Bayesian network writes the joint distribution as , with numbers instead of . The factorization is equivalent to the local Markov property: each node is independent of its non-descendants given its parents.
- d-separation reads independence off the graph: chains and forks are blocked by observing the middle node, colliders are opened by observing them or a descendant. It is sound and complete for the independences that hold for every choice of CPTs.
- Variable elimination sums out hidden variables one at a time; its cost is exponential only in the induced width of the ordering. Polytrees take linear time, but exact inference is NP-hard and #P-hard in general.
- Rejection sampling keeps only a fraction of its samples; likelihood weighting clamps the evidence and weights each sample by ; Gibbs sampling resamples each variable given its Markov blanket. With complete data, CPTs are learned by counting.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A network has edges , , , and . What is the Markov blanket of ?
Show the answer
C.
Parents , child , and the child's other parent . belongs because is a collider between and : once is in the conditioning set, carries information about . is screened off by .
In the alarm network, which pair of variables is dependent given Alarm?
- JohnCalls and MaryCalls
- Burglary and JohnCalls
- Earthquake and MaryCalls
- Burglary and Earthquake
Show the answer
D. Burglary and Earthquake
Alarm is a collider on Burglary → Alarm ← Earthquake, so observing it opens the path: P(Burglary | alarm) = 37.4% falls to 0.33% once an earthquake is known. Every other pair is joined only through Alarm as the middle of a chain or fork, which observing Alarm blocks.
The running time of variable elimination is exponential in which quantity?
- The number of variables in the network
- The number of evidence variables
- The size of the largest factor created, set by the induced width of the elimination ordering
- The number of edges in the network
Show the answer
C. The size of the largest factor created, set by the induced width of the elimination ordering
VE costs : linear in the number of variables and exponential only in the induced width . On a polytree, a good ordering keeps at the largest number of parents, so VE runs in linear time however large the network is.
Exact inference is NP-hard in general. For which class of networks is it guaranteed to take time linear in the total size of the CPTs?
- Networks with at most three parents per node
- Polytrees
- Networks queried without any evidence
- Networks with at most 100 nodes
Show the answer
B. Polytrees
In a polytree, a good elimination ordering never builds a factor larger than the largest CPT, and Pearl's message passing computes every marginal in linear time. Loops are what make inference hard.
In the sprinkler network with evidence WetGrass = true, likelihood weighting draws Cloudy = true, Sprinkler = false, Rain = true. What weight does this sample get?
- 0.9
- 0.99
- 0.8
- 0.36
Show the answer
A. 0.9
The weight is the probability of the clamped evidence given its sampled parents: . The sampled variables already appear in the right proportions, because they were drawn from their CPTs; weighting by their probabilities as well would count them twice.
Go deeper
- d-Separation & Independence · Reading independence off a graph.
- Exact & Approximate Inference · Variable elimination, belief propagation and MCMC.
- Learning Network Structure · Scores, search and causal discovery.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 13.
- D. Koller & N. Friedman, Probabilistic Graphical Models: Principles and Techniques (MIT Press, 2009), chapters 3, 9 and 12.
- J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, 1988).
- G. F. Cooper, "The computational complexity of probabilistic inference using Bayesian belief networks," Artificial Intelligence 42(2–3), 393–405 (1990).