Bayesian Networks and Probabilistic Inference

Bayes' theorem tells you how to update one belief on one piece of evidence. A real agent holds beliefs about dozens of variables at once, and the joint distribution over them - the object that answers every question - has $2^n$ entries for $n$ Boolean variables. Nobody can write it down. This article is about the representation that makes the joint usable, and the algorithms that query it.

A. The network is the joint

A Bayesian network is a directed acyclic graph. Each node is a random variable; an arrow from $X$ to $Y$ makes $X$ a parent of $Y$; and each node carries a conditional probability table giving $P(X_i \mid \mathrm{Parents}(X_i))$, one row per combination of parent values. A Boolean node with $k$ Boolean parents needs $2^k$ numbers.

Russell and Norvig's example is an alarm. It responds to burglary and, less reliably, to earthquakes; two neighbours, John and Mary, call when they hear it, John sometimes confusing the phone for the alarm and Mary sometimes missing it behind loud music. Arrows $B \to A$, $E \to A$, $A \to J$, $A \to M$, and ten numbers:

$$\begin{array}{ll} P(b) = 0.001 & P(e) = 0.002 \\[4pt] P(a \mid b, e) = 0.95 & P(a \mid b, \lnot e) = 0.94 \\ P(a \mid \lnot b, e) = 0.29 & P(a \mid \lnot b, \lnot e) = 0.001 \\[4pt] P(j \mid a) = 0.90 & P(j \mid \lnot a) = 0.05 \\ P(m \mid a) = 0.70 & P(m \mid \lnot a) = 0.01 \end{array}$$

The meaning of the picture is one equation. For any complete assignment,

$$P(x_1, \dots, x_n) = \prod_{i=1}^{n} P\big(x_i \mid \mathrm{parents}(X_i)\big).$$

So the probability that the alarm sounds with no burglary and no earthquake, and both neighbours call, is

$$P(j, m, a, \lnot b, \lnot e) = 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 = 0.000628 .$$

Every one of the 32 joint entries is available this way, from ten numbers rather than 31. The saving is not a trick: it is the claim, made by the missing arrows, that each variable is conditionally independent of its non-descendants given its parents. Stronger still, every node is independent of all other nodes given its Markov blanket - parents, children, and children's other parents. Given the alarm and the earthquake, the phone calls say nothing further about a burglary.

B. Exact inference

A query asks for $\mathbf{P}(X \mid \mathbf{e})$. Since every joint entry is a product of CPT entries, the query is a normalised sum of products over the hidden variables. Both neighbours have called; is it a burglary?

$$P(b \mid j, m) = \alpha\, P(b) \sum_{e} P(e) \sum_{a} P(a \mid b, e)\,P(j \mid a)\,P(m \mid a).$$

Four terms for $b$, four for $\lnot b$, each a product of five numbers:

$$\mathbf{P}(B \mid j, m) = \alpha\, \langle 0.00059224,\ 0.00149186 \rangle = \langle 0.284,\ 0.716 \rangle .$$

Two independent reports lift a one-in-a-thousand prior to 28 percent, and no further, because the no-burglary mass arrives by three comparable routes: a causeless alarm then both calls, $0.000628$; no alarm but both calls anyway, $0.000498$; and an earthquake alarm then both calls, $0.000365$. Together they outweigh the burglary route, $0.000592$, by 2.5 to one.

Enumeration evaluates this as a depth-first tree, and the tree repeats itself: the product $P(j \mid a)\,P(m \mid a)$ is computed once under $e$ and again under $\lnot e$. On $n$ Boolean variables the cost is $O(2^n)$ - better than the $O(n\,2^n)$ of building each joint entry separately, but most of it recomputation. Variable elimination stores each piece as a factor - a table over the variables it still depends on - and combines factors by pointwise product and by summing out. Summing out $A$ gives a factor over $(B, E)$:

$$f_6(B, E) = \begin{array}{c|cc} & e & \lnot e \\ \hline b & 0.598525 & 0.592230 \\ \lnot b & 0.183055 & 0.001130 \end{array}$$

Summing out $E$ against $P(E)$ leaves $f_7(B) = \langle 0.592243,\ 0.001493 \rangle$, and multiplying by $P(B)$ and normalising returns $\langle 0.284, 0.716 \rangle$ with every leaf product done once.

Whether this is fast depends on the shape of the graph. On a polytree - at most one undirected path between any two nodes, as here - variable elimination is linear in the size of the network. Add a second path and the intermediate factors can grow exponentially in the worst case. The general problem is #P-hard: as hard as counting the satisfying assignments of a propositional formula. That is the reason the rest of this article exists.

The network below is this one, and every number in it is exact - the posteriors come from summing all 32 assignments, not from sampling. Click a node to say what you know. Start with both neighbours calling: a burglary goes to 28.4%, which is already worth sitting with, since the calls are excellent evidence about the alarm and the alarm is a poor witness to burglary. Then add the earthquake. It makes the calls more likely, and it sends the burglary back towards nothing.

C. Sampling when exact is impossible

The sprinkler network has four Boolean variables and two paths from $\mathit{Cloudy}$ to $\mathit{WetGrass}$, one through the sprinkler and one through rain:

$$\begin{array}{ll} P(c) = 0.5 & \\[4pt] P(s \mid c) = 0.10 & P(s \mid \lnot c) = 0.50 \\ P(r \mid c) = 0.80 & P(r \mid \lnot c) = 0.20 \\[4pt] P(w \mid s, r) = 0.99 & P(w \mid s, \lnot r) = 0.90 \\ P(w \mid \lnot s, r) = 0.90 & P(w \mid \lnot s, \lnot r) = 0.00 \end{array}$$

Prior sampling draws each variable from its CPT in parent-first order. The probability of producing an event is the product of the entries consulted, which is the joint itself: $[c, \lnot s, r, w]$ comes out with probability $0.5 \times 0.9 \times 0.8 \times 0.9 = 0.324$. Frequencies therefore converge to probabilities, and the estimate is consistent.

Rejection sampling answers a conditional query by discarding every sample that disagrees with the evidence. For $P(\mathit{Rain} \mid \mathit{Sprinkler} = \text{true})$, exact value $0.3$, a seeded run of 1,000 prior samples rejected 703 and kept 79 with rain against 218 without, for an estimate of $0.266$. Seventy percent of the effort went nowhere, and that is the benign case: the survival rate is $P(\mathbf{e})$, which falls exponentially with the number of evidence variables. Ask the burglary network for $\mathbf{P}(B \mid j, m)$ and about 21 samples in 10,000 survive.

Likelihood weighting fixes the evidence variables instead of sampling them, so every event is consistent, and weights each event by the probability of the evidence given the parents the sampler chose. For $\mathbf{P}(\mathit{Rain} \mid c, w)$ with ordering $C, S, R, W$: the weight starts at $1$, $C$ is evidence so $w \leftarrow 0.5$; $S$ is sampled from $\langle 0.1, 0.9 \rangle$, say false; $R$ from $\langle 0.8, 0.2 \rangle$, say true; $W$ is evidence so $w \leftarrow 0.5 \times P(w \mid \lnot s, r) = 0.45$. The event is tallied under rain with weight $0.45$. Nothing is discarded, and because sampling probability times weight equals the joint, the weighted tally is consistent: a thousand samples on the same seed give $0.9758$ against an exact $0.9758$. The method degrades when the evidence is improbable under the sampled values, because a few heavy weights then dominate everything.

Gibbs sampling is Markov chain Monte Carlo. Fix the evidence, start from any state, and repeatedly resample one non-evidence variable conditioned on its Markov blanket. That conditional is a product of a handful of CPT entries:

$$P(x_i' \mid \mathrm{mb}(X_i)) = \alpha\, P\big(x_i' \mid \mathrm{parents}(X_i)\big) \prod_{Y_j \in \mathrm{Children}(X_i)} P\big(y_j \mid \mathrm{parents}(Y_j)\big).$$

For $\mathbf{P}(\mathit{Rain} \mid s, w)$ from the state $[c, s, \lnot r, w]$, resampling $C$ uses $P(C)\,P(s \mid C)\,P(\lnot r \mid C)$, which gives $P(c \mid s, \lnot r) = 0.048$; say it comes out false. Resampling $R$ then uses $P(R \mid \lnot c)\,P(w \mid s, R)$, which gives $P(r \mid \lnot c, s, w) = 0.216$. Every state visited is a sample. A thousand steps on a fixed seed estimate $0.315$ against the exact $0.320$.

The reason this works is that the chain has a stationary distribution and the Gibbs step satisfies detailed balance with respect to the posterior, which forces the two to coincide: the long-run fraction of time in each state is $P(\mathbf{x} \mid \mathbf{e})$. No sample is rejected and no weight collapses. The cost is correlation between consecutive states, so the chain needs time to forget where it started.

Consistency is a claim about a limit, so the figure below puts the limit on the screen: the dashed line is the exact posterior, obtained by enumerating the joint and sharing no code with either sampler. Drag the sample size and watch the two estimates walk toward it. Then switch to the burglary query, where rejection sampling keeps 21 samples in 10,000 and likelihood weighting keeps all of them and still struggles, because fixing the evidence removes the waste rather than the variance.

Where this leaves you

A Bayesian network is a joint distribution you can actually write down. Exact inference is a sum of products that variable elimination performs without repetition, cheap on polytrees and intractable in general. When the graph is too tangled, sampling gives consistent estimates at a cost that depends on how the evidence is handled: rejection wastes, weighting concentrates, and Gibbs wanders - each of which is the right choice somewhere. The training path Probabilistic Reasoning with Bayesian Networks works every one of these computations by hand and by code.