AI AI-03.02
Bayesian networks
Directed graphs of variables with conditional probability tables, how evidence flows (d-separation), and exact and sampling-based inference.
The big idea
A full table of probabilities over 100 variables is impossible. But nobody thinks about the world that way. You know that clouds make rain more likely, that rain and sprinklers both wet the grass, and that, once you know whether it rained and whether the sprinkler ran, the clouds tell you nothing more about the grass. Those few statements of direct influence carry almost all the structure.
A Bayesian networkA directed acyclic graph whose nodes are random variables and whose edges show direct influence, with a conditional probability table at each node giving its distribution for each combination of parent values. writes that structure down as a graph: an arrow from cause to effect, and at each node a small table saying how it depends on its parents. The graph plus tables define the whole joint distribution, usually with a tiny fraction of the numbers. And because the structure mirrors how people think about causes, the networks are readable, and evidence can be fed in anywhere, flowing both downstream (from causes to effects) and upstream (from effects back to their likely causes).
Think of a detective's evidence board: photos connected by string. You do not need a table of every combination of suspects, alibis and clues; you need to know which clue bears directly on which suspect. Change one fact on the board and you can trace exactly which conclusions move.
How it works
Step 1: The graph and its tables
Here is the classic textbook network. Each node is a yes/no variable; each has a conditional probability tableA table at each node of a Bayesian network giving the probability of each of its values for every combination of its parents' values. (CPT) giving the probability it is true for each combination of its parents:
Step 2: The joint distribution is a product
The network's meaning is one formula: the probability of any complete world is the product of each node's entry given its parents,
For example, the probability that it is cloudy, the sprinkler is off, it rains and the grass is wet is
A full joint table over these four variables needs 15 independent numbers; the network needs 9. With 100 variables that each have at most 3 parents, the network needs at most 800 numbers instead of about . The saving comes from conditional independence: each variable, given its parents, is independent of everything that is not its descendant.
Step 3: How evidence flows (d-separation)
When does learning one variable change your belief about another? Three patterns cover every case:
- Chain, (Cloudy, Rain, Wet): evidence flows from A to C through B, unless B is observed. Once you know it rained, the clouds add nothing about the grass.
- Common cause, (Sprinkler, Cloudy, Rain): the two effects are correlated through their cause, unless the cause is observed. Learning the sprinkler ran suggests a clear day and so less rain; knowing it was cloudy breaks that link.
- Common effect, (Sprinkler, Wet, Rain): the two causes are independent, until the effect (or one of its descendants) is observed. Then they compete to explain it: explaining away.
The general rule, d-separationA graphical test for whether two variables in a Bayesian network are independent given some evidence: they are if every path between them is blocked by the chain, fork and collider rules., says two variables are independent given the evidence when every path between them is blocked by one of these rules. It lets you read independence straight off the graph, without a single calculation.
Try it
Try this:
- Set wet grass to true. Rain jumps from 0.5 to 0.708 and the sprinkler from 0.3 to 0.430: evidence flows upstream to both causes, and on to Cloudy (0.576).
- Now also set sprinkler to true. Rain drops to 0.320: the sprinkler explains the wet grass, so rain is less needed. That is explaining away through the common effect.
- Clear those, then set cloudy to true. Sprinkler falls to 0.1 and rain rises to 0.8. Now set rain too: the sprinkler stays at exactly 0.1, because once Cloudy is observed, the common cause no longer links them.
- Switch inference to exact + 1,000 samples and set rain true and wet grass false, an unusual combination. Only 36 of 1,000 samples match the evidence, and the pink estimate for the sprinkler (0.056) is well off the exact 0.021.
Going deeper
Exact inference
The lab enumerates all 16 worlds, which is fine for four variables. Real networks need cleverer algorithms. Variable elimination sums variables out one at a time, caching intermediate tables so shared sub-results are computed once, and junction tree methods reorganise the graph into clusters to answer many queries efficiently. On networks shaped like trees (polytrees), exact inference is linear in the network size. In general, though, exact inference is NP-hard, and densely connected networks defeat it.
Approximate inference by sampling
The alternative is to simulate. Rejection sampling draws worlds from the network, top-down, and keeps only those that match the evidence; the answer is the fraction of kept samples where the query is true. It is simple but wasteful: as step 4 showed, unlikely evidence means almost every sample is thrown away. Likelihood weighting fixes the evidence variables instead of sampling them, and weights each sample by how likely the evidence was:
import random
from itertools import product
# Each node: (parents, table of P(node = True | parent values)).
NET = {
"cloudy": ((), {(): 0.5}),
"sprinkler": (("cloudy",), {(True,): 0.1, (False,): 0.5}),
"rain": (("cloudy",), {(True,): 0.8, (False,): 0.2}),
"wet": (("sprinkler", "rain"),
{(True, True): 0.99, (True, False): 0.9,
(False, True): 0.9, (False, False): 0.0}),
}
ORDER = list(NET) # parents come before children
def p_node(var, value, world):
parents, table = NET[var]
p = table[tuple(world[q] for q in parents)]
return p if value else 1 - p
def exact(query, evidence):
"""Enumerate worlds; P(world) is a product of one entry per node."""
num = den = 0.0
for values in product([True, False], repeat=len(ORDER)):
w = dict(zip(ORDER, values))
if any(w[k] != v for k, v in evidence.items()):
continue
pw = 1.0
for var in ORDER:
pw *= p_node(var, w[var], w)
den += pw
num += pw if w[query] else 0
return num / den
def likelihood_weighting(query, evidence, n, rng):
"""Sample the free variables; weight each sample by the evidence."""
num = den = 0.0
for _ in range(n):
w, weight = {}, 1.0
for var in ORDER:
if var in evidence:
w[var] = evidence[var]
weight *= p_node(var, w[var], w)
else:
w[var] = rng.random() < p_node(var, True, w)
den += weight
num += weight if w[query] else 0
return num / den
params = sum(len(table) for _, table in NET.values())
print(f"numbers stored: {params} (a full joint table needs 2^4 - 1 = 15)")
ev = {"wet": True}
print(f"P(rain | wet) exact = {exact('rain', ev):.4f}")
rng = random.Random(1)
for n in (100, 1_000, 10_000, 100_000):
est = likelihood_weighting("rain", ev, n, rng)
print(f" likelihood weighting, {n:>7,} samples: {est:.4f}")Output
numbers stored: 9 (a full joint table needs 2^4 - 1 = 15)
P(rain | wet) exact = 0.7079
likelihood weighting, 100 samples: 0.7436
likelihood weighting, 1,000 samples: 0.6905
likelihood weighting, 10,000 samples: 0.7055
likelihood weighting, 100,000 samples: 0.7095 The network stores 9 numbers instead of 15. Exact enumeration gives , and likelihood weighting converges toward it as samples grow: off by about 0.04 with 100 samples and by about 0.002 with 100,000. The error shrinks roughly with the square root of the number of samples, so each extra decimal place of accuracy costs about 100 times more samples. Markov chain Monte Carlo methods such as Gibbs sampling take a different route, wandering through worlds consistent with the evidence, and scale to very large models.
Where the structure comes from
Networks can be built by experts, learned from data, or both. Learning the tables given the graph is counting, as in Probability for AI (recap) . Learning the graph itself is harder, and data alone cannot always tell from . Reading arrows as causes is tempting but needs care: a Bayesian network encodes dependence, and only with extra assumptions, or experiments, does it encode causation.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Bayesian network, exact inference | Small or tree-like networks where exact answers matter | Densely connected networks: exact inference is NP-hard |
| Bayesian network, sampling | Large networks where an approximate answer is enough | Rare evidence (rejection) or slow convergence; results are noisy |
| Full joint table | A few variables, no structure to exploit | Exponential size; needs data for every combination |
| Discriminative model (e.g. a classifier) | One fixed prediction task with lots of labelled data | Cannot answer arbitrary queries or reason backwards from effects |
Common mistakes
- Drawing arrows from effect to cause because that is the direction of the question. Arrows should follow direct influence; inference handles questions in any direction.
- Forgetting explaining away. Two independent causes become dependent once their common effect is observed.
- Assuming observing a middle variable never matters. In a chain it blocks the flow of evidence.
- Using rejection sampling with rare evidence and trusting the result. Check how many samples survived.
- Reading every arrow as a proven causal claim.
In the wild
Where you will see this: Bayesian networks have been used for medical diagnosis support, fault diagnosis in printers, aircraft and telecom networks, spam filtering (naive Bayes is the simplest Bayesian network), risk assessment in engineering and finance, and forensic reasoning about evidence. Probabilistic programming languages let developers write such models as code and run sampling-based inference automatically, and the same graphical-model ideas underpin hidden Markov models ( Hidden Markov models ) and parts of modern causal inference.
Check yourself
-
What does each node of a Bayesian network store?
Show answer
B. A table of its probabilities given each combination of its parents Each conditional probability table only involves the node and its parents, which is why the network is compact.
-
P(cloudy) = 0.5, P(sprinkler | cloudy) = 0.1, P(rain | cloudy) = 0.8, P(wet | sprinkler, rain) = 0.99. What is P(cloudy, sprinkler, rain, wet)?
Show answer
B. 0.0396 Multiply one entry per node: 0.5 x 0.1 x 0.8 x 0.99 = 0.0396.
-
Sprinkler and Rain are both parents of Wet. With no evidence they are independent given Cloudy. What happens when Wet is observed?
Show answer
B. They become dependent: evidence for one makes the other less likely Observing a common effect couples its causes: explaining away.
-
In the chain Cloudy -> Rain -> Wet, you observe Rain. Does learning Cloudy change your belief about Wet?
Show answer
B. No: observing Rain blocks the chain Wet depends on Cloudy only through Rain. Once Rain is known, Cloudy adds nothing.
-
Why can rejection sampling give poor answers for unlikely evidence?
Show answer
B. Most samples are discarded, leaving too few to estimate from If the evidence has probability 0.04, only about 4 percent of samples are kept. Likelihood weighting avoids this by fixing the evidence.
Recap
- A Bayesian network is a directed graph of variables with a conditional probability table at each node.
- The joint probability of a world is the product of one table entry per node, which makes the model compact.
- Evidence flows along chains and common causes unless blocked by observation, and through common effects only when they are observed (explaining away).
- Exact inference uses enumeration, variable elimination or junction trees; it is NP-hard in general.
- Sampling (rejection, likelihood weighting, MCMC) gives approximate answers that improve with more samples.