Bayesian Networks and the Joint Distribution

The full joint distribution answers every probabilistic question, and it is useless in practice: over $n$ Boolean variables it has $2^n$ entries, nobody can supply them, and nobody could store them. A Bayesian network keeps the power of the joint while paying for only the dependences that actually exist.

What a network is

A Bayesian network is a directed acyclic graph in which

• each node is a random variable,
• an arrow from $X$ to $Y$ says that $X$ is a parent of $Y$, so $X$ has a direct influence on $Y$, and
• each node $X_i$ carries a conditional probability table (CPT) giving $P(X_i \mid \mathrm{Parents}(X_i))$, one row per combination of parent values.

Each CPT row must sum to one, so for a Boolean variable only the probability of true is written and the other follows. A Boolean node with $k$ Boolean parents therefore needs $2^k$ numbers, and a root node needs exactly one.

The burglary network

The example that carries this whole path is Judea Pearl's burglar alarm, the one Russell and Norvig use to introduce Bayesian networks. You are at work. A burglar alarm at home responds fairly reliably to burglary and, being an earthquake detector of sorts, occasionally to minor earthquakes. Two neighbours, John and Mary, have promised to call when they hear it. John nearly always calls when he hears the alarm but sometimes mistakes the telephone for it; Mary likes loud music and often misses the alarm altogether.

$$\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 graph has arrows $B \to A$, $E \to A$, $A \to J$, $A \to M$, and nothing else. That is a set of claims: John and Mary do not perceive burglaries directly, they do not notice minor earthquakes, and they do not confer before calling. Everything that could make the alarm fail - a dead battery, a cut wire - or make a neighbour fail to report it is folded into the numbers rather than modelled. That is not sloppiness; it is how a small agent copes with a large world.

What a network means

The semantics is a single equation. For any complete assignment $x_1, \dots, x_n$ to all the variables,

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

where $\mathrm{parents}(X_i)$ denotes the values of $X_i$'s parents inside the assignment. The network is the joint distribution, written as a product of its CPT entries.

Worked example: one full event

The alarm has sounded, neither a burglary nor an earthquake has happened, and both neighbours call. Reading one entry from each table:

$$\begin{aligned} P(j, m, a, \lnot b, \lnot e) &= P(j \mid a)\,P(m \mid a)\,P(a \mid \lnot b, \lnot e)\,P(\lnot b)\,P(\lnot e) \\ &= 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 \\ &= 0.000628 . \end{aligned}$$

Because every one of the 32 joint entries can be produced this way, anything the full joint could answer, the network can answer too - by summing the relevant entries. The next lesson is about doing that without producing all 32.

Why the network is so much smaller

Count the numbers. Burglary and Earthquake need one each, Alarm has two parents and needs four, and each call has one parent and needs two:

$$1 + 1 + 4 + 2 + 2 = 10$$

against $2^5 - 1 = 31$ independent entries in the full joint table. The gap widens explosively: with 30 Boolean variables, each with at most five parents, the network needs at most $30 \times 2^5 = 960$ numbers where the joint needs over a billion. The saving is locality: each variable is influenced directly by only a few others.

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.

The independences the graph asserts

Apply the chain rule to any ordering of the variables:

$$P(x_1, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_{i-1}, \dots, x_1).$$

Comparing with the semantics above, the network is a correct representation exactly when, for every variable,

$$P(X_i \mid X_{i-1}, \dots, X_1) = P\big(X_i \mid \mathrm{Parents}(X_i)\big)$$

for some ordering in which every node comes after its parents. In words: each variable is conditionally independent of its other predecessors given its parents. Two further consequences follow from the graph alone.

• A node is conditionally independent of its non-descendants given its parents. In the burglary network, $J$ is independent of $B$, $E$ and $M$ once $A$ is known.
• A node is conditionally independent of every other node given its Markov blanket: its parents, its children, and its children's other parents. $B$'s blanket is $\{A, E\}$, so given the alarm state and the earthquake state, the two phone calls tell you nothing further about a burglary.

Ordering matters when you build one. Add the nodes in the order $M, J, A, B, E$ and you are forced to draw $M \to J$, then both calls into $A$, then $A \to B$, then $A \to E$ and $B \to E$: two more links and three more numbers than the causal network, some of them describing relationships that are genuinely hard to assess. Putting causes before effects is what keeps the network small.

Before the quiz

Be able to write down the product that defines the joint, evaluate it for a complete event, count the numbers a network needs against the full table, and say what a Markov blanket is and why conditioning on it isolates a node.