---
title: Bayesian Networks
module: Uncertainty
moduleNumber: 4
lessonNumber: 3
order: 403
summary: >
  A Bayesian network is a directed acyclic graph of random variables in which
  each node carries a conditional probability table for itself given its parents.
  That structure factors the full joint distribution into a product of local
  terms, turning an exponential table into a linear one, and it makes the
  conditional independences of the domain explicit. We build the canonical
  burglary–alarm network, read compactness and d-separation off the graph, run
  exact inference by variable elimination, and, where that is intractable,
  estimate answers by sampling.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 14 — Probabilistic Reasoning; §14.1 Representing Knowledge in an Uncertain Domain; §14.2 The Semantics of Bayesian Networks"
  - book: AIMA
    ref: "§14.4 Exact Inference in Bayesian Networks; §14.5 Approximate Inference in Bayesian Networks"
  - book: AIMA
    ref: "§14.6 Relational and First-Order Probability Models; §14.7 Other Approaches to Uncertain Reasoning"
---

The [full joint distribution](/artificial-intelligence/uncertainty/probability-and-bayes)
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.[^aima-intro]

## The network

> **Definition (Bayesian network).** A directed acyclic graph in which each node
> is a random variable and each edge $X \to Y$ marks $X$ as a **parent** of $Y$.
> Every node $X_i$ carries a **conditional probability table** giving $\mathbf{P}(X_i
> \mid \text{parents}(X_i))$, the distribution of $X_i$ for each combination of
> values of its parents. The acyclicity is essential: it is what lets the local
> tables compose into a single coherent joint.

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.[^aima-syntax]

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.

$$
% caption: The dental network. $Weather$ stands apart, independent of the others;
% $Cavity$ is the common cause of both $Toothache$ and $Catch$, and the absence of
% a link between those two encodes their conditional independence given $Cavity$.
\begin{tikzpicture}[>=stealth, font=\small,
  var/.style={draw, ellipse, minimum width=20mm, minimum height=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[var] (weather) at (-3.4,1.4) {Weather};
  \node[var, draw=acc, text=acc] (cavity) at (1.4,1.4) {Cavity};
  \node[var] (tooth) at (-0.4,-0.6) {Toothache};
  \node[var] (catch) at (3.2,-0.6) {Catch};
  \draw[->, acc, thick] (cavity) -- (tooth);
  \draw[->, acc, thick] (cavity) -- (catch);
\end{tikzpicture}
$$

## The burglary network

The example that carries the rest of the chapter is a little richer.[^aima-alarm]
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.

$$
% caption: The burglary network with its conditional probability tables. $Burglary$
% and $Earthquake$ are root nodes with prior probabilities; $Alarm$ depends on both;
% each call depends only on the alarm. The letters $B, E, A, J, M$ name the
% variables; entries give $P(\text{variable} = true)$, so the $false$ column is
% omitted.
\begin{tikzpicture}[>=stealth, font=\small,
  var/.style={draw, ellipse, minimum width=19mm, minimum height=7mm, inner sep=1pt},
  cpt/.style={draw, font=\scriptsize, align=center, inner sep=2.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[var] (b) at (0,3) {Burglary};
  \node[var] (e) at (5.4,3) {Earthquake};
  \node[var, draw=acc, text=acc] (a) at (2.7,1.2) {Alarm};
  \node[var] (j) at (0,-1) {JohnCalls};
  \node[var] (m) at (5.4,-1) {MaryCalls};
  \draw[->, acc, thick] (b) -- (a);
  \draw[->, acc, thick] (e) -- (a);
  \draw[->, acc, thick] (a) -- (j);
  \draw[->, acc, thick] (a) -- (m);
  % CPTs
  \node[cpt, anchor=west] at (1.5,3.2) {P(B)\\ .001};
  \node[cpt, anchor=east] at (3.9,3.2) {P(E)\\ .002};
  \node[cpt, anchor=west] at (4.1,1.2)
    {B \ \ E \ \ P(A)\\ t \ \ \ t \ \ \ .95\\ t \ \ \ f \ \ \ .94\\ f \ \ \ t \ \ \ .29\\ f \ \ \ f \ \ .001};
  \node[cpt, anchor=north] at (0,-1.7) {A \ \ P(J)\\ t \ \ .90\\ f \ \ .05};
  \node[cpt, anchor=north] at (5.4,-1.7) {A \ \ P(M)\\ t \ \ .70\\ f \ \ .01};
\end{tikzpicture}
$$

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.[^aima-cpt]

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, \ldots, x_n)$, and a
Bayesian network defines it as the product of the local tables:[^aima-semantics]

$$
P(x_1, \ldots, x_n) = \prod_{i=1}^{n} P\!\left(x_i \mid \text{parents}(X_i)\right).
$$

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:

$$
\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}
$$

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, \ldots, X_n$:

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

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

$$
\mathbf{P}(X_i \mid X_{i-1}, \ldots, X_1) = \mathbf{P}(X_i \mid \text{parents}(X_i)),
$$

provided $\text{parents}(X_i) \subseteq \{X_{i-1}, \ldots, X_1\}$.[^aima-construct]
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.

> **Algorithm (Network construction).** Order the variables $X_1, \ldots, X_n$ so
> that each variable's direct causes come before it. For $i = 1$ to $n$: pick from
> $\{X_1, \ldots, X_{i-1}\}$ a minimal set of parents making
> $\mathbf{P}(X_i \mid X_{i-1}, \ldots, X_1) = \mathbf{P}(X_i \mid \text{parents}(X_i))$
> hold, draw an edge from each parent to $X_i$, and fill in the CPT
> $\mathbf{P}(X_i \mid \text{parents}(X_i))$.

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.

$$
% caption: Two orderings of the burglary domain. The causal order (left)
% reproduces the compact network; the diagnostic order $MaryCalls, JohnCalls,
% Alarm, Burglary, Earthquake$ (right) forces extra links and unnatural
% probability judgments, yet both encode the very same joint distribution.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  var/.style={draw, ellipse, minimum width=17mm, minimum height=6.5mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % left: causal
  \node[var, draw=acc, text=acc] (b) at (0,3)   {Burglary};
  \node[var, draw=acc, text=acc] (e) at (2.3,3)   {Earthquake};
  \node[var] (a) at (1.15,1.7) {Alarm};
  \node[var] (j) at (0,0.4)    {JohnCalls};
  \node[var] (m) at (2.3,0.4)  {MaryCalls};
  \draw[->, acc, thick] (b) -- (a);
  \draw[->, acc, thick] (e) -- (a);
  \draw[->, acc, thick] (a) -- (j);
  \draw[->, acc, thick] (a) -- (m);
  \node[font=\footnotesize] at (1.15,-0.6) {causal order: 10 numbers};
  % right: diagnostic
  \begin{scope}[xshift=6.4cm]
    \node[var] (m2) at (0,3)    {MaryCalls};
    \node[var] (j2) at (2.4,3)  {JohnCalls};
    \node[var] (a2) at (1.2,1.7){Alarm};
    \node[var, draw=red, text=red] (b2) at (0,0.4)  {Burglary};
    \node[var, draw=red, text=red] (e2) at (2.4,0.4){Earthquake};
    \draw[->, black, thick] (m2) -- (j2);
    \draw[->, black, thick] (m2) -- (a2);
    \draw[->, black, thick] (j2) -- (a2);
    \draw[->, black, thick] (a2) -- (b2);
    \draw[->, black, thick] (a2) -- (e2);
    \draw[->, red, thick] (b2) -- (e2);
    \node[font=\footnotesize] at (1.2,-0.6) {diagnostic order: more links};
  \end{scope}
\end{tikzpicture}
$$

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**.[^aima-compact]

$$
% caption: Numbers needed to specify a network over $n$ Boolean variables with at
% most $k=5$ parents each, against the full joint distribution. The network grows
% linearly ($n \cdot 2^k$); the joint grows exponentially ($2^n$). At $n=30$ the
% network needs 960 numbers and the joint over a billion.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (6.4,0) node[anchor=west, black, font=\scriptsize] {variables n};
  \draw[->, black] (0,0) -- (0,4.2) node[anchor=south, black, font=\scriptsize] {numbers (log)};
  % exponential joint curve
  \draw[red, very thick] (0.4,0.2) .. controls (2.6,0.5) and (3.6,1.4) .. (5.4,3.7);
  \node[red, anchor=south east, font=\scriptsize] at (5.4,3.75) {joint (exponential)};
  % linear network curve (on log axis a log shape)
  \draw[acc, very thick] (0.4,0.35) .. controls (2.4,1.05) and (4.0,1.35) .. (5.9,1.55);
  \node[acc, anchor=north west, font=\scriptsize] at (5.0,1.15) {network (linear)};
  % marker at n=30
  \draw[black, dashed] (4.6,0) -- (4.6,3.15);
  \node[anchor=north, font=\scriptsize, text=black] at (4.6,-0.05) {n = 30};
  \fill[red] (4.6,3.15) circle (1.6pt);
  \node[red, anchor=south east, font=\scriptsize] at (4.45,3.2) {over a billion};
  \fill[acc] (4.6,1.44) circle (1.6pt);
  \node[acc, anchor=east, font=\scriptsize] at (4.45,1.44) {960};
\end{tikzpicture}
$$

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.[^aima-topo] 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.[^aima-dsep]

$$
% caption: The three connection types. In a chain $X \to Z \to Y$ and a common
% cause $X \leftarrow Z \to Y$, observing $Z$ (shaded) blocks the path, making $X$
% and $Y$ independent. In a common effect (collider) $X \to Z \leftarrow Y$ the
% reverse holds: $X$ and $Y$ are independent until $Z$ (or a descendant) is
% observed, which opens the path — explaining away.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  n/.style={draw, circle, minimum size=6.5mm, inner sep=0pt},
  obs/.style={draw, circle, minimum size=6.5mm, inner sep=0pt, fill=acc!14, thick}]
  \definecolor{acc}{HTML}{2348F2}
  % chain
  \node[n] (cx) at (0,0) {X};
  \node[obs] (cz) at (1.3,0) {Z};
  \node[n] (cy) at (2.6,0) {Y};
  \draw[->, thick] (cx) -- (cz);
  \draw[->, thick] (cz) -- (cy);
  \node[font=\scriptsize, align=center] at (1.3,-1.15) {chain\\Z blocks};
  % common cause
  \begin{scope}[xshift=4.6cm]
    \node[obs] (bz) at (1.3,0.55) {Z};
    \node[n] (bx) at (0,-0.5) {X};
    \node[n] (by) at (2.6,-0.5) {Y};
    \draw[->, thick] (bz) -- (bx);
    \draw[->, thick] (bz) -- (by);
    \node[font=\scriptsize, align=center] at (1.3,-1.15) {common cause\\Z blocks};
  \end{scope}
  % common effect
  \begin{scope}[xshift=9.2cm]
    \node[n] (ex) at (0,0.55) {X};
    \node[n] (ey) at (2.6,0.55) {Y};
    \node[obs] (ez) at (1.3,-0.45) {Z};
    \draw[->, thick] (ex) -- (ez);
    \draw[->, thick] (ey) -- (ez);
    \node[font=\scriptsize, align=center] at (1.3,-1.15) {common e\/f\/fect\\Z opens};
  \end{scope}
\end{tikzpicture}
$$

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.

> **Definition (d-separation).** Two sets of nodes $\mathbf{X}$ and $\mathbf{Y}$
> are **d-separated** by a set $\mathbf{Z}$ — hence conditionally independent
> given $\mathbf{Z}$ — if every undirected path between them is blocked. A path is
> blocked when it passes through a chain or common-cause node that is in
> $\mathbf{Z}$, or through a collider that is _not_ in $\mathbf{Z}$ and has no
> descendant in $\mathbf{Z}$.

## 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$:[^aima-enum]

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

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

$$
\mathbf{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).
$$

**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.[^aima-ve]

```algorithm
caption: $\textsc{Elimination-Ask}(X, \mathbf{e}, bn)$ — exact inference by variable elimination
input: $X$, the query variable; $\mathbf{e}$, observed evidence
input: $bn$, a Bayesian network over variables $\{X\} \cup \mathbf{E} \cup \mathbf{Y}$
$factors \gets [\,]$
for each $var$ in $\textsc{Order}(bn.\text{vars})$ do
  $factors \gets [\textsc{Make-Factor}(var, \mathbf{e})] + factors$
  if $var$ is a hidden variable then
    $factors \gets \textsc{Sum-Out}(var, factors)$
return $\textsc{Normalize}(\textsc{Pointwise-Product}(factors))$
```

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) = \langle 0.001, 0.999 \rangle$, $f_2(E) = \langle 0.002, 0.998
\rangle$, 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) = \langle 0.90, 0.05 \rangle$ and $f_5(A) = P(m \mid A) =
\langle 0.70, 0.01 \rangle$ (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:

$$
\begin{aligned}
f_A(b, e)  &= 0.95(0.63) + 0.05(0.0005) = 0.598525 \\
f_A(b, \lnot e) &= 0.94(0.63) + 0.06(0.0005) = 0.592230 \\
f_A(\lnot b, e) &= 0.29(0.63) + 0.71(0.0005) = 0.183055 \\
f_A(\lnot b, \lnot e) &= 0.001(0.63) + 0.999(0.0005) = 0.0011295.
\end{aligned}
$$

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

$$
\begin{aligned}
f_E(b) &= 0.002(0.598525) + 0.998(0.592230) = 0.592243 \\
f_E(\lnot b) &= 0.002(0.183055) + 0.998(0.0011295) = 0.001493.
\end{aligned}
$$

**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 $\lnot b$. These are $P(b, j, m)$ and $P(\lnot b, j, m)$; dividing by their sum
$0.002084$ normalizes:

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

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.

$$
% caption: The elimination order for the burglary query. Summing out $A$ combines
% the three factors touching it into $f_A(B, E)$; summing out $E$ combines that with
% $P(E)$ into $f_E(B)$; multiplying by $P(B)$ and normalizing gives the posterior.
% Each box is a factor and its variables; the boxes shrink as variables are removed.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  fct/.style={draw, minimum width=20mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[fct] (in) at (0,0) {f\/ive factors\\B, E, A};
  \node[fct] (fa) at (3.4,0) {fA(B, E)\\sum out A};
  \node[fct] (fe) at (6.8,0) {fE(B)\\sum out E};
  \node[fct, draw=acc, text=acc] (post) at (10.2,0) {P(B given j, m)\\= (.284, .716)};
  \draw[->, thick] (in) -- (fa);
  \draw[->, thick] (fa) -- (fe);
  \draw[->, acc, thick] (fe) -- (post);
  \node[font=\scriptsize, text=black, anchor=north] at (3.4,-0.75) {eliminate A};
  \node[font=\scriptsize, text=black, anchor=north] at (6.8,-0.75) {eliminate E};
  \node[font=\scriptsize, text=black, anchor=north] at (10.2,-0.75) {x P(B), normalize};
\end{tikzpicture}
$$

## 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.[^aima-complex]

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.

$$
% caption: Polytree versus multiply connected. In the polytree (left) a single
% path joins any two nodes and inference is linear. In the multiply connected
% network (right) two paths run from $Cloudy$ to $WetGrass$ — through $Sprinkler$
% and through $Rain$ — and exact inference can cost exponential time.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  n/.style={draw, ellipse, minimum width=14mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % polytree
  \node[n, draw=acc, text=acc] (p0) at (0,2.4) {A};
  \node[n] (p1) at (-1.4,1.2) {B};
  \node[n] (p2) at (1.4,1.2)  {C};
  \node[n] (p3) at (0,0)      {D};
  \draw[->, acc, thick] (p0) -- (p1);
  \draw[->, acc, thick] (p0) -- (p2);
  \draw[->, acc, thick] (p1) -- (p3);
  \node[font=\footnotesize] at (0,-0.9) {polytree: linear};
  % multiply connected
  \begin{scope}[xshift=6.2cm]
    \node[n] (cl) at (0,2.4) {Cloudy};
    \node[n] (sp) at (-1.6,1.2) {Sprinkler};
    \node[n] (ra) at (1.6,1.2)  {Rain};
    \node[n, draw=red, text=red] (wg) at (0,0) {WetGrass};
    \draw[->, black, thick] (cl) -- (sp);
    \draw[->, black, thick] (cl) -- (ra);
    \draw[->, red, thick] (sp) -- (wg);
    \draw[->, red, thick] (ra) -- (wg);
    \node[font=\footnotesize] at (0,-0.9) {multiply connected: NP-hard};
  \end{scope}
\end{tikzpicture}
$$

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](/artificial-intelligence/uncertainty/inference-in-bayesian-networks),
which estimates intractable posteriors by sampling and then lifts the network from a
fixed set of variables to whole populations of objects.

[^aima-intro]: **Russell & Norvig**, _AIMA_, §14.1 — Representing Knowledge in an Uncertain Domain: the full joint grows intractably with the number of variables, and independence and conditional independence relationships are what a Bayesian network encodes to represent essentially any joint distribution concisely.
[^aima-syntax]: **Russell & Norvig**, _AIMA_, §14.1 — the full specification of a Bayesian network: nodes as random variables, directed links marking parents in a DAG, a CPT $\mathbf{P}(X_i \mid Parents(X_i))$ per node, and the causal reading of arrows as direct influence that makes topology easy for an expert to supply.
[^aima-alarm]: **Russell & Norvig**, _AIMA_, §14.1, Figure 14.2 — the burglary/alarm/earthquake network due to Judea Pearl, its topology, and the conditional probability tables for $Burglary$, $Earthquake$, $Alarm$, $JohnCalls$, and $MaryCalls$.
[^aima-cpt]: **Russell & Norvig**, _AIMA_, §14.1 — conditional probability tables and conditioning cases: each row a combination of parent values summing to 1, the $false$ entry omitted for Boolean variables, and a Boolean node with $k$ Boolean parents requiring $2^k$ numbers; laziness and ignorance folded into the link uncertainties.
[^aima-semantics]: **Russell & Norvig**, _AIMA_, §14.2.1, Equations (14.1)–(14.2) — the semantics of a Bayesian network as the full joint distribution, $P(x_1, \ldots, x_n) = \prod_i P(x_i \mid parents(X_i))$, and the worked $P(j, m, a, \lnot b, \lnot e) = 0.000628$.
[^aima-construct]: **Russell & Norvig**, _AIMA_, §14.2.1 — "A method for constructing Bayesian networks": the chain rule, Equation (14.3) $\mathbf{P}(X_i \mid X_{i-1}, \ldots, X_1) = \mathbf{P}(X_i \mid Parents(X_i))$, ordering causes before effects, choosing minimal parent sets, and the guarantee of acyclicity and consistency.
[^aima-compact]: **Russell & Norvig**, _AIMA_, §14.2.1 — "Compactness and node ordering": locally structured (sparse) systems, the $n\,2^k$ versus $2^n$ count with the $n=30$, $k=5$ example (960 numbers versus over a billion), and the tradeoff of dropping tenuous links.
[^aima-topo]: **Russell & Norvig**, _AIMA_, §14.2.2, Figure 14.4 — the topological semantics: a node is conditionally independent of its non-descendants given its parents, and independent of all other nodes given its Markov blanket (parents, children, children's parents).
[^aima-dsep]: **Russell & Norvig**, _AIMA_, §14.2.2, footnote — d-separation as the general topological criterion for conditional independence of node sets, decided by whether paths are blocked; the chain, common-cause, and common-effect (collider / explaining-away) connection types and how observing the middle node blocks or opens each.
[^aima-enum]: **Russell & Norvig**, _AIMA_, §14.4.1, Equation (14.4) — inference by enumeration: a query as a sum of products of CPT entries, $\mathbf{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)$, the answer $\langle 0.284, 0.716 \rangle$, and its $O(2^n)$ cost with repeated subexpressions.
[^aima-ve]: **Russell & Norvig**, _AIMA_, §14.4.2, Figure 14.11 — the variable elimination algorithm: factors, pointwise product and summing out, right-to-left evaluation with stored intermediates, $\textsc{Elimination-Ask}$, variable-ordering heuristics, and removal of variables irrelevant to the query.
[^aima-complex]: **Russell & Norvig**, _AIMA_, §14.4.3 — the complexity of exact inference: linear time and space for singly connected networks (polytrees), exponential worst case for multiply connected networks, and the #P-hardness (NP-hard) of the general problem, with propositional inference as a special case.