Bayesian Networks

The full joint distribution answers every question you can ask about a domain — but its size grows exponentially. A joint over $n$ Boolean variables has $2^n$ entries; thirty variables already demand a billion numbers, none of which a human could estimate or a machine store. The previous lesson addressed this with independence: knowing that $Weather$ has nothing to do with a toothache lets you factor its probability out and stop enumerating combinations that never mattered. A Bayesian network is the data structure that makes that factoring systematic. It is a graph whose edges record exactly which variables depend on which, and whose local tables reconstruct the entire joint from a linear number of numbers instead of an exponential one.¹

The network

The edges are meant to be read causally. An arrow $X\to Y$ says $X$ exerts a direct influence on $Y$, and the intuition that causes should be parents of effects is what makes networks easy to build: a domain expert can usually name the direct influences long before they could write down a single probability. Once the topology is fixed, the only remaining work is to fill each node's conditional probability table — the local rule for that variable given its immediate causes.²

Return to the dental world of the previous lesson: $Toothache$, $Cavity$, $Catch$ (a probe catching in the tooth), and $Weather$. We argued that $Weather$ is independent of the rest, and that $Toothache$ and $Catch$ are conditionally independent given $Cavity$ — a cavity is the common cause of both, and once you know whether it is present, the probe tells you nothing further about the ache. The network encodes this directly.

The burglary network

The example that carries the rest of the chapter is a little richer.³ You have a burglar alarm at home. It is fairly reliable at detecting a break-in, but it also trips occasionally on a minor earthquake. Two neighbors, John and Mary, have promised to call you at work when they hear it. John nearly always calls when the alarm sounds, but sometimes confuses the ringing telephone for the alarm and calls anyway; Mary likes loud music and often misses the alarm altogether. Given who has and has not called, you want the probability of a burglary.

Five Boolean variables — $Burglary$, $Earthquake$, $Alarm$, $JohnCalls$, $MaryCalls$ — carry the domain. The causal structure is plain: a burglary or an earthquake can set off the alarm, and the alarm is the only thing John or Mary react to. Neither neighbor perceives burglaries or earthquakes directly, and they do not confer before calling, so each call depends on the alarm and nothing else.

Each row of a conditional probability table (CPT) is a conditioning case — a possible combination of parent values, a miniature possible world. The alarm's table has four rows because it has two Boolean parents; each row gives the probability the alarm fires in that case, and its $false$ complement is $1$ minus that, so we list only one number. A root node with no parents, like $Burglary$, has a single row: its prior. In general a Boolean node with $k$ Boolean parents needs $2^k$ numbers.⁴

The tables absorb a great deal of the world's untidiness. There is no node for Mary is listening to loud music or the phone is ringing; those factors are folded into the uncertainty on the links — the reason John's call probability given the alarm is $0.90$ rather than $1$. A small agent copes with a large, messy world by summarizing an unbounded set of unmentioned circumstances into a few conditional probabilities.

Semantics: the network is the joint

The network above is syntax — a graph with numbers. Its meaning is a specific full joint distribution, recovered by one formula. A generic joint entry is the probability of an assignment to every variable, $P(x_1,\dots ,x_n)$, and a Bayesian network defines it as the product of the local tables:⁵

Each joint entry is a product of one entry from each node's CPT, picking the row that matches the parents' values in that assignment. This is the whole content of a Bayesian network: the graph plus the local tables is the joint distribution, factored. To find the probability that the alarm sounds but neither a burglary nor an earthquake occurs and both neighbors call, read off five numbers and multiply:

Since the network reconstructs the joint, it can answer any query the joint could — by summing the relevant entries. The rest of the lesson is about doing that summation without ever writing the joint out in full.

Constructing a network

Where does the factorization come from? Apply the chain rule to the joint — it holds for any distribution — decomposing it into a product of conditionals in some fixed variable order $X_1,\dots ,X_n$:

Compare this with the network's product. The two agree exactly when, for every variable,

provided $\text{parents}(X_i)\subseteq \{X_{i-1},\dots ,X_1\}$.⁶ In words: a node must be conditionally independent of its other predecessors, given its parents. This gives a procedure. Order the variables so that causes precede effects; then for each $X_i$ in turn, choose as its parents the minimal set of already-placed nodes it directly depends on, add the edges, and write the CPT.

Because each node links only to earlier ones, the graph is automatically acyclic, and because no probability is stored twice there is no way to make the tables mutually inconsistent — a domain expert literally cannot build a network that violates the axioms of probability.

Order matters

The procedure works for any ordering, but a bad one is costly. Add the burglary variables in the anti-causal order $MaryCalls$, $JohnCalls$, $Alarm$, $Burglary$, $Earthquake$ and you are forced into tenuous links: if Mary called, John is more likely to have called too (both point to the alarm), so $JohnCalls$ needs $MaryCalls$ as a parent; assessing $\mathbf{P}(Earthquake\mid Burglary,Alarm)$ demands an unnatural judgment about how a burglary explains away the alarm.

Both networks represent exactly the same joint distribution. The diagnostic one simply fails to expose the conditional independences, so it stores redundant numbers to compensate. The lesson is that causal models are the compact ones: arrows from causes to effects require the fewest, most natural probabilities, which is why expert physicians reliably give better numbers for causal rules (what does this disease cause?) than for diagnostic ones.

Compactness

Compactness is the reason the whole apparatus exists. A Bayesian network is a locally structured (or sparse) system: each variable is directly influenced by only a bounded number of others, no matter how large the domain. Suppose each of $n$ Boolean variables has at most $k$ parents. Each CPT holds at most $2^k$ numbers, so the entire network needs at most $n{2}^k$ — linear in $n$. The full joint needs $2^n$ — exponential.⁷

Concretely, with $n=30$ nodes and $k=5$ parents each, the network needs $960$ numbers and the joint over a billion. The saving is not free: it holds only when the domain really is sparse. If every variable influences every other, the graph is fully connected and the network stores as much as the joint. But most real domains are sparse, and when a dependence is genuine but weak — whether an earthquake, having tripped the alarm, should also make John more likely to call — you may drop the link, trading a little accuracy for a much smaller model.

Conditional independence and d-separation

The graph does more than compress numbers; it declares which independences hold. The topological semantics states them directly: a node is conditionally independent of its non-descendants, given its parents.⁸ In the burglary network, $JohnCalls$ is independent of $Burglary$, $Earthquake$, and $MaryCalls$ once you know $Alarm$ — the alarm screens off everything upstream. A second, stronger statement uses the Markov blanket of a node — its parents, its children, and its children's other parents. A node is independent of all other nodes in the network given its Markov blanket. To isolate a node, these are the variables you must condition on, and they will reappear when we sample.

To decide independence for any two sets of nodes given a third, there is a graphical criterion called d-separation. It rests on three ways a path can run through an intermediate node $Z$, and whether evidence at $Z$ blocks the path or opens it.⁹

The chain $X\to Z\to Y$ passes influence from $X$ to $Y$ through $Z$; observing $Z$ cuts the flow, so $X\perp Y\mid Z$. A burglary influences John's call only through the alarm, and once you know the alarm's state the burglary adds nothing. The common cause $X\leftarrow Z\to Y$ behaves the same way: $Toothache$ and $Catch$ are correlated because $Cavity$ drives both, but fix the cavity and the correlation vanishes.

The common effect $X\to Z\leftarrow Y$, also called a collider, is the subtle case, and it runs backward. Two independent causes of the same effect are marginally independent — $Burglary$ and $Earthquake$ have nothing to do with each other a priori — but observing their shared effect $Alarm$ makes them dependent. If the alarm is sounding and you learn it was an earthquake, the probability of a burglary drops: the earthquake explains away the alarm. A path through a collider is blocked until the collider (or one of its descendants) is observed, at which point it opens. Explaining away is the signature of probabilistic reasoning that pure logic cannot capture.

Exact inference by variable elimination

We can now store a joint compactly; the next question is how to query it. The naive way — write out the whole sum over hidden variables — throws away the compactness we just gained and costs $O(2^n)$ again. The fix is an accounting trick: factor out the terms that do not depend on the variable being summed, so each partial sum is computed once and reused. That is variable elimination, and it is the same dynamic-programming idea that turns an exponential recursion into a polynomial one.

The basic query asks for the posterior $\mathbf{P}(X\mid \mathbf{e})$ of a query variable $X$ given observed evidence $\mathbf{e}$, with the remaining variables $\mathbf{Y}$ hidden. Because the network is the joint, any such query is a sum of products of CPT entries. Written out for $\mathbf{P}(Burglary\mid JohnCalls=true,MaryCalls=true)$, marginalizing the hidden variables $Earthquake$ and $Alarm$:¹⁰

where $\alpha$ normalizes the result to sum to $1$. Evaluated naively, summing over all hidden variables costs $O(2^n)$: a network of $n$ Booleans forces $2^n$ terms. But the sum has structure — $P(B)$ does not depend on $e$ or $a$ and can sit outside both sums; $P(e)$ sits outside the sum over $a$. Pushing each factor out as far as it goes gives

Variable elimination evaluates this right to left, computing each inner sum once and reusing it. Enumeration, by contrast, recomputes the shared subexpression $P(j\mid a)P(m\mid a)$ separately for each value of $e$; eliminating that repetition is where the dynamic-programming saving comes from.

The bookkeeping is done with factors — matrices indexed by the variables they mention. Each CPT is a factor; the two operations that combine them are pointwise product (a factor over the union of the operands' variables, multiplying matching entries) and summing out a variable (adding the submatrices for each of its values). To eliminate $Alarm$ from the burglary query, take the pointwise product of every factor mentioning $A$ — the factors for $P(a\mid B,e)$, $P(j\mid a)$, $P(m\mid a)$ — and sum over $a$, producing a new factor over $B$ and $E$. Then eliminate $E$ the same way. The order in which variables are eliminated does not change the answer, but it changes the size of the intermediate factors, and hence the cost. Finding the optimal ordering is itself intractable, so a greedy rule — eliminate whichever variable yields the smallest next factor — is the usual heuristic.¹¹

One further economy: any variable that is not an ancestor of the query or the evidence is irrelevant and can be deleted before the sum begins. Querying $\mathbf{P}(JohnCalls\mid Burglary=true)$, the term ${\sum }_{m}P(m\mid a)$ equals $1$ — $MaryCalls$ is a leaf that is neither queried nor observed — so $MaryCalls$ drops out entirely.

The burglary query, carried through

Run variable elimination on $\mathbf{P}(B\mid j,m)$ with the tables from the network figure. Five factors enter, one per CPT with the evidence $j,m$ substituted in: $f_1(B)=⟨0.001,0.999⟩$, $f_2(E)=⟨0.002,0.998⟩$, the three-way $f_3(A,B,E)=P(A\mid B,E)$, and the two evidence factors $f_4(A)=P(j\mid A)=⟨0.90,0.05⟩$ and $f_5(A)=P(m\mid A)=⟨0.70,0.01⟩$ (ordered $A=true,false$).

Eliminate $A$. Multiply the three factors that mention $A$ and sum $A$ out, producing a factor over $B,E$. The product $f_4(a)f_5(a)$ is $0.90\times 0.70=0.63$ at $a=true$ and $0.05\times 0.01=0.0005$ at $a=false$. For each of the four $(B,E)$ cases, weight these by $P(a\mid B,E)$ and add:

Eliminate $E$. Multiply $f_A$ by $f_2(E)$ and sum $E$ out, giving a factor over $B$:

Multiply by the prior and normalize. Scale by $f_1(B)$: $0.001\times 0.592243=0.000592$ for $b$ and $0.999\times 0.001493=0.001492$ for $\neg b$. These are $P(b,j,m)$ and $P(\neg b,j,m)$; dividing by their sum $0.002084$ normalizes:

A burglary is about $28\%$ likely given both calls. The intermediate factors never exceeded two variables, which is why this polytree query is cheap; the same right-to-left evaluation on a densely connected network would build factors over many variables at once, and that is where the cost hides.

The complexity of inference

For polytrees — singly connected networks, where at most one undirected path joins any two nodes — variable elimination runs in time and space linear in the size of the network. The burglary network is a polytree, and this is the best case.¹²

For multiply connected networks, where nodes are joined by more than one path, the intermediate factors can grow exponentially even when every node has few parents. In the worst case exact inference is intractable, and unavoidably so: the problem is NP-hard. Propositional logical inference is a special case of Bayesian network inference, so the network problem inherits its hardness — and in fact it is #P-hard, as hard as counting the satisfying assignments of a logical formula, strictly harder than deciding satisfiability.

When exact inference is out of reach, the alternative is to estimate the answer rather than compute it — and the whole framework generalizes far beyond the fixed, finite variable sets we have assumed so far.

This continues in Bayesian Networks: Inference and Relational Models, which estimates intractable posteriors by sampling and then lifts the network from a fixed set of variables to whole populations of objects.