Skip to content

Yet Another Primer on Bayes Nets

A walking-pace introduction to exact inference for discrete Bayesian networks: what they are, what we ask of them, why naive inference is intractable, and how junction trees turn it into a sequence of local computations. Aimed at someone who knows probability and graphs but hasn't worked with Bayesian networks specifically. By the end you should be able to read the algorithm in a graphical-models paper, recognise when exact inference is tractable for a given network, and trace why two variables are or aren't conditionally independent given some set of observations. The running example is the Asia network (Lauritzen and Spiegelhalter 1988); each algorithm is walked through end-to-end on it.

What is a Bayesian network?

A Bayesian network is a compact representation of a joint probability distribution over a set of random variables. It consists of a directed acyclic graph (DAG) over the variables, together with a conditional probability table (CPT) for each node \(X_i\) giving \(P(X_i \mid \mathrm{parents}(X_i))\). The structural assumption is that the joint factors as the product of those CPTs — one per variable, conditioned on its parents in the DAG.

The DAG also encodes conditional independence relations among the variables, and those independences are what make inference tractable. The next section makes this concrete on the running example; the d-separation section later cashes out exactly which independences the DAG implies.

The Asia network

A toy diagnostic network from Lauritzen and Spiegelhalter (1988), eight binary variables modeling the relationship between a recent visit to Asia, smoking, and respiratory complaints. Each node carries a CPT; the second line of every node label below is the CPT it owns:

flowchart TB
    Asia["Visit to Asia (V)<br/>P(V)"] --> Tub["Tuberculosis (T)<br/>P(T|V)"]
    Smoke["Smoker (S)<br/>P(S)"] --> LungC["Lung Cancer (L)<br/>P(L|S)"]
    Smoke --> Bronc["Bronchitis (B)<br/>P(B|S)"]
    Tub --> TbOrCa["Tb or Cancer (E)<br/>P(E|T,L)"]
    LungC --> TbOrCa
    TbOrCa --> XRay["Abnormal X-Ray (X)<br/>P(X|E)"]
    TbOrCa --> Dysp["Dyspnea (D)<br/>P(D|E,B)"]
    Bronc --> Dysp

Reading the labels: each node has a full name, a single-letter abbreviation in parentheses, and on the line below, the conditional probability table that node owns. Root nodes (no parents) get an unconditional table — P(V) is just two numbers, the prior probability that a patient did or didn't recently visit Asia. Non-root nodes get a table conditioned on each parent — P(T|V) is four numbers, the probability of tuberculosis for each value of V. Multi-parent nodes get larger tables: P(D|E,B) is eight numbers, one for each combination of E and B.

The full joint over all eight variables is the product of these tables, read directly off the diagram:

\[ P(V,T,S,L,B,E,X,D) \;=\; P(V)\,P(T|V)\,P(S)\,P(L|S)\,P(B|S)\,P(E|T,L)\,P(X|E)\,P(D|E,B). \]

The DAG encodes structural beliefs about which variables influence which. Visiting Asia influences dyspnea only through tuberculosis and the intermediate Tb or Cancer node — there's no edge from V straight to D, and no path through the smoking subtree. That structural assumption is exactly the conditional independence that makes inference tractable.

What is evidence, and what's a query?

The point of all this machinery is to answer questions. The questions have a standard form: given that we have observed the values of some variables (the evidence), what is the probability distribution of the remaining variables?

For Asia, a clinician might observe that a patient has an abnormal X-ray and dyspnea (X = T, D = T) and ask:

  • "What is the probability the patient has tuberculosis?" — \(P(T \mid X{=}T,\, D{=}T)\)
  • "What is the probability they have lung cancer?" — \(P(L \mid X{=}T,\, D{=}T)\)
  • "What is the probability they are a smoker?" — \(P(S \mid X{=}T,\, D{=}T)\)

Each answer is a posterior marginal — \(P(X_i \mid \mathrm{evidence})\) — extracted from the conditioned joint \(P(X_1, \ldots, X_n \mid \mathrm{evidence}) \propto P(X_1, \ldots, X_n) \cdot \mathbf{1}[\mathrm{evidence}]\).

Evidence enters the network as a per-variable indicator function (sometimes called an evidence potential): for each observed variable, a vector that is 1 on the observed value and 0 elsewhere. Multiplying this in zeroes out joint configurations inconsistent with the observation; renormalising gives the posterior.

Why don't we just enumerate?

The joint distribution \(P(V,T,S,L,B,E,X,D)\) is conceptually a giant table: one row for every possible combination of all eight variables, with a P column holding the probability of that combination. For Asia, with eight binary variables, the table has \(2^8 = 256\) rows. Each row's P is the product of the eight CPT entries selected by that row's variable values — read directly off the factorisation in the previous section.

If we have that table, why not just use it? To answer \(P(L \mid X{=}T,\, D{=}T)\), we could:

  1. Filter the 256 rows down to the subset where X = T and D = T — the 64 rows consistent with the evidence.
  2. Sum the P column within L = T and within L = F, giving two numbers (the unnormalised posterior).
  3. Normalise by dividing each by the grand total of the 64 filtered rows.

Three operations on the joint table. For Asia it works fine.

The problem is that the table has \(2^n\) rows and \(n\) gets big fast. A real diagnostic network with 50 variables has \(2^{50} \approx 10^{15}\) rows — too large to fit on any machine. A network with a few hundred variables would need a table with more rows than there are atoms in the observable universe. Building the table is the bottleneck, not querying it.

The next idea is variable elimination: instead of materialising the joint, push the summations inside the product so we sum out one variable at a time, working with intermediate factors that are much smaller than the full joint. The summation symbol \(\sum_X\) means "sum over all values of \(X\)" — the same operation as the "sum the P column" step from the enumeration recipe, just applied one variable at a time rather than to the whole table.

Concretely, suppose we want \(P(L)\) — the lung-cancer prior, no evidence. Naive enumeration sums the joint over the other seven variables: \(2^7 = 128\) eight-CPT-product evaluations per outer value of L. Variable elimination pushes each \(\sum\) as far inward as it will go, stopping at the smallest set of factors that mention the variable being summed out:

  • D appears only in P(D|E,B), and \(\sum_D P(D|E,B) = 1\) by definition of a CPT. The sum eliminates for free.
  • X appears only in P(X|E). Same trick: \(\sum_X P(X|E) = 1\), eliminate for free.
  • V appears only in P(V) and P(T|V). The inner sum \(\sum_V P(V)\,P(T|V)\) is a 2-cell intermediate over T — call it \(m_T(T)\).

After three eliminations, the seven-variable sum has shrunk to four variables (T, S, B, E) acting on a smaller expression that includes \(m_T(T)\) instead of the original V-factors. Continuing in the same way, every intermediate factor stays bounded by a small subset of variables — never larger than the elimination clique, the set of variables that appear together in some factor still in play when a particular variable is summed out. For Asia, no factor exceeds \(2^3 = 8\) cells. Total work is roughly the sum of the intermediate-factor sizes, not the joint's \(2^8\). The exponential is now in the largest intermediate, not in the network's variable count.

But variable elimination has a caveat: every new query restarts the computation from scratch. The intermediate factors built to compute \(P(\text{Tub} \mid \text{evidence})\) are thrown away when we then ask for \(P(\text{LungC} \mid \text{evidence})\), even though both queries share most of their work.

The junction tree algorithm fixes this by organising the computation into a single shared data structure that can answer many queries with shared intermediates. The structure is a tree whose nodes are cliques (small subsets of the original variables) and whose edges carry messages — marginalised intermediate factors that propagate information between cliques. The cost of constructing the tree is exponential in the largest clique size (the network's treewidth), which is why low-treewidth networks are tractable and high-treewidth ones are not. To make this parameter feel concrete: trees have treewidth 1; an \(n \times n\) grid has treewidth proportional to \(n\); densely-connected networks like protein-interaction graphs routinely have treewidth in the hundreds, and that is exactly why exact inference doesn't scale to them.

Building the junction tree

The junction tree is constructed in three steps from the original DAG: moralization, triangulation, and clique-tree extraction. Each step has a structural reason to exist.

Moralization

Drop the edge directions, then add an edge between every pair of nodes that share a child. The added edges are called marriage edges. The resulting undirected graph is the moral graph.

Why moralize? The CPT for a node \(X\) with parents \(\{Y_1, \ldots, Y_k\}\) is a function of all \(k+1\) variables together. For the joint to factor cleanly over the cliques of an undirected graph, every CPT's variables must sit inside a single clique. The marriage edges ensure that the parents of a common child are always in the same clique — they "marry the parents," hence the name.

For Asia, moralization adds two marriage edges: Tub-LungC (joint parents of TbOrCa) and TbOrCa-Bronc (joint parents of Dysp).

Triangulation

Add chords until the moral graph is chordal: every cycle of length four or more must contain a shortcut. Chordal graphs are exactly the graphs whose maximal cliques can be arranged in a tree satisfying the running intersection property (more on that below). Without a triangulation step, the cliques of the moral graph might not admit such a tree, and message passing wouldn't be sound.

Triangulation is NP-hard to optimise (we want the smallest cliques possible), but cheap heuristics like minimum-degree elimination work well in practice. The largest clique created by the triangulation determines the cost of every subsequent computation.

For Asia, triangulation adds one chord (LungC-Bronc) to break the length-4 cycle Smoker-LungC-TbOrCa-Bronc-Smoker.

graph TB
    Asia["Visit to Asia"] --- Tub[Tuberculosis]
    Smoke[Smoker] --- LungC["Lung Cancer"]
    Smoke --- Bronc[Bronchitis]
    Tub --- TbOrCa["Tb or Cancer"]
    LungC --- TbOrCa
    TbOrCa --- XRay["Abnormal X-Ray"]
    TbOrCa --- Dysp[Dyspnea]
    Bronc --- Dysp
    Tub -.- LungC
    TbOrCa -.- Bronc
    LungC === Bronc
    linkStyle 8,9 stroke:#e74c3c,stroke-width:2.5px
    linkStyle 10 stroke:#27ae60,stroke-width:3px

Solid black: original undirected edges. Dashed red: marriage edges. Solid green: the triangulation chord.

Junction tree extraction

The maximal cliques of the chordal graph become nodes of a junction tree. The tree edges are chosen so that, for every variable, the cliques containing that variable form a connected subtree. This is the running intersection property and it's what makes message passing produce correct posteriors: a variable's information can flow from any clique that contains it to any other clique that contains it without leaving the subtree of cliques that "know about" it. Tree edges are labelled with separators, the intersection of the two cliques they join.

To see why triangulation is needed for this property to hold, take an unchorded 4-cycle A — B — C — D — A. Its maximal cliques are the four edges {A,B}, {B,C}, {C,D}, {D,A}, and any tree of those four cliques places variable A in the two end-cliques ({A,B} and {D,A}) but not in the two middle cliques — so the cliques containing A cannot form a connected subtree, and message passing breaks. Adding a chord (say B—D) collapses the cycle into two triangle-cliques {A,B,D} and {B,C,D} joined by the separator {B,D}. Now every variable's containing cliques sit in a connected subtree, and the property is restored.

flowchart LR
    C5["C5<br/>Tub, Asia"]
    C4["C4<br/>Tub, LungC, TbOrCa"]
    C3["C3<br/>Bronc, LungC, TbOrCa"]
    C2["C2<br/>Bronc, LungC, Smoker"]
    C1["C1<br/>Bronc, Dysp, TbOrCa"]
    C0["C0<br/>XRay, TbOrCa"]
    C5 ---|Tub| C4
    C4 ---|"LungC, TbOrCa"| C3
    C3 ---|"Bronc, LungC"| C2
    C3 ---|"Bronc, TbOrCa"| C1
    C1 ---|TbOrCa| C0

Six cliques, five separators. The largest clique has three variables, so this network has treewidth two — every subsequent operation costs \(O(2^3) = O(8)\) per clique, not \(O(2^8)\) per the full joint.

Calibrating the tree

Three operations do all the work, each one a familiar concept on probability tables:

  • Product (\(\prod\)) — given two distributions \(P(X)\) and \(P(Y)\), build the joint distribution \(P(X, Y)\) over the union of their variables.
  • Marginalize (\(\sum\)) — given a joint distribution \(P(X, Y)\), build the marginal distribution \(P(X)\) over a smaller subset of variables (sum over the variables you don't care about).
  • Normalize (\(\nu\)) — given any non-negative table, rescale so the values sum to 1, producing a valid probability distribution.

That's it. Calibration is a sequence of products and marginalisations on the clique potentials, with a normalisation at the end of each posterior extraction. The notation may look formal but each operation matches something you've written in SQL many times — that's the relational framing the rest of this section uses.

An analogy, not an implementation

The relational framing in the subsections below is a mental model for what \(\prod\), \(\sum\), and \(\nu\) compute, not how any real implementation stores or processes them. No serious probabilistic inference engine uses a SQL planner. See Why this is only an analogy at the end of the section for what real implementations actually look like.

Borrowing the relational framing for a moment: a potential is like a table with one row per combination of its variables and a value column holding a non-negative number. For example, the CPT \(P(T|V)\) corresponds to a 4-row table with columns V, T, value:

V T value
F F 0.99
F T 0.01
T F 0.95
T T 0.05

Product (\(\prod\)), as a relational analogy

The product of two potentials \(\phi \cdot \psi\) computes what an SQL inner join on the shared columns would compute, with the value columns multiplied. If you imagined \(\phi(V)\) as a 2-row prior table for V and \(\psi(V, T)\) as the 4-row CPT above, the SQL would read:

SELECT phi.V, psi.T, phi.value * psi.value AS value
FROM phi JOIN psi USING (V);

Two potentials with no shared variables would join into a Cartesian product (every row of one paired with every row of the other). Two potentials that share all their variables would join into a same-size table whose value column is the cell-wise product. Both extremes and everything in between are the same conceptual operation: match on what's shared, multiply the values.

Example. Combining the prior \(P(V)\) with the conditional \(P(T \mid V)\) by product gives the joint \(P(V, T)\) over both variables: each cell \(P(V{=}v, T{=}t) = P(V{=}v) \cdot P(T{=}t \mid V{=}v)\). That's the chain rule of probability falling out of a single relational join.

Marginalization (\(\sum\)), as a relational analogy

The marginal \(\sum_V \phi\) computes what a SQL aggregate over all columns except V would compute, summing the value column:

SELECT remaining_columns, SUM(value) AS value
FROM phi
GROUP BY remaining_columns;

Marginalising V from a 4-row table over (V, T) would produce a 2-row table over T whose value column is the sum across the two V values. Marginalising every variable would produce a single-row table whose value is the grand total — that's the normalisation constant.

Example. Starting from the joint \(P(V, T)\), summing out V gives the marginal \(P(T) = \sum_V P(V, T)\) — the probability of tuberculosis regardless of Asia travel.

Normalization (\(\nu\)), as a relational analogy

Take any non-negative table and rescale it so the values sum to 1. The normalisation \(\nu(\phi)\) divides every cell by the sum of the value column. In SQL:

WITH total AS (SELECT SUM(value) AS Z FROM phi)
SELECT *, value / total.Z AS value FROM phi, total;

Marginalising over every variable already produces the normalisation constant \(Z = \sum_{\text{all vars}} \phi\); normalisation just divides through by it.

Example. After incorporating evidence, the unnormalised posterior \(P(L, \text{evidence})\) sums to \(P(\text{evidence}) < 1\). Applying \(\nu\) divides every cell by that sum, producing the proper posterior \(P(L \mid \text{evidence})\) — Bayes' rule, as a relational rescaling.

Recap

That's the whole toolkit:

  • \(\prod\) joins potentials on their shared variables (chain rule of probability).
  • \(\sum\) sums out variables to leave a smaller marginal.
  • \(\nu\) divides through by the total to make a valid distribution.

Everything that follows in this section — clique potentials, message passing, posterior extraction — is an arrangement of these three operations on the junction tree's data structures.

Why this is only an analogy

Real implementations of probability tables look nothing like a relational database. Potentials are stored as dense (or sparse) multidimensional tensors — torch.Tensor, numpy.ndarray, JAX arrays are typical — and the three operations are vectorised tensor primitives: product is broadcast multiplication along aligned axes; marginalisation is a sum(dim=...) reduction; normalisation is a broadcast division by that same sum. Numerically robust implementations work in log space to avoid underflow on long products of small probabilities, so what's nominally a * b is implemented as a + b, what's nominally Σ exp(...) is implemented with logsumexp, and normalisation becomes a subtraction of the log-sum from each cell. None of this would survive contact with a SQL planner — relational engines are built around row-set semantics, not contiguous numerical arrays, and would lose every order of magnitude of performance the tensor stack exists to provide.

What the analogy preserves is meaning. Whether you implement \(\prod\), \(\sum\), and \(\nu\) with joins, with einsum calls, with hand-rolled C kernels, or with FFTs, the answer is the same. The relational framing is a way to read a calibration formula without committing to how the bits are arranged in memory.

Initial setup: clique potentials, the JT factorisation, evidence

Each clique \(c\) starts with a potential \(\psi_c\) — the join of the CPT tables whose variables all fit inside \(c\). The assignment of CPTs to cliques isn't unique; pick any clique that contains all of a CPT's variables, with each CPT used by exactly one clique. For Asia, one valid assignment is:

\[ \begin{aligned} \psi_{C_5} &= P(V)\cdot P(T|V) \\ \psi_{C_4} &= P(E|T, L) \\ \psi_{C_3} &= 1 \\ \psi_{C_2} &= P(S)\cdot P(L|S)\cdot P(B|S) \\ \psi_{C_1} &= P(D|E, B) \\ \psi_{C_0} &= P(X|E) \end{aligned} \]

\(C_3 = \{B, L, E\}\) gets the unit potential because no CPT's variables all fit inside it: every CPT either needs a variable that isn't in \(C_3\) (D, S, T, V, X) or has been claimed by another clique. The unit potential is the multiplicative identity, so \(C_3\) contributes nothing to the joint until messages start flowing through it. Every separator \(S_{ij}\) starts with the unit potential too.

This setup makes the junction-tree factorisation theorem (Lauritzen and Spiegelhalter 1988) concrete: the product over cliques divided by the product over separators equals the joint distribution,

\[ P(V, T, \ldots) \;=\; \frac{\prod_c \psi_c}{\prod_{ij} \psi_{S_{ij}}}. \]

The theorem holds for any junction tree built from a chordal graph satisfying the running intersection property. It is what makes message passing correct — every message-passing schedule preserves this identity, just rearranging which clique holds which factor.

To incorporate evidence — say X = T and D = T — multiply the relevant clique by an evidence potential \(\varepsilon_X\), a table that is 1 on the observed value and 0 elsewhere. After calibration the cliques become the posterior marginals \(P(\cdot \mid X{=}T, D{=}T)\) up to a normalising constant.

Messages: the Shafer–Shenoy schedule

The cliques are not yet consistent — marginalising \(C_5\) down to \(\{T\}\) doesn't agree with marginalising \(C_4\) down to \(\{T\}\), because each clique only knows about the CPTs it owns. They become consistent by exchanging messages along the tree edges.

In Shafer–Shenoy, the message from clique \(i\) to neighbour \(j\) is built in two database operations:

  1. Join \(i\)'s own potential with every incoming message \(i\) has received from its other neighbours (everyone except \(j\)).
  2. Aggregate that joined table down to the separator's columns, summing out everything else.
\[ m_{i \to j} \;=\; \underbrace{\sum_{C_i \setminus S_{ij}}}_{\text{GROUP BY } S_{ij}} \;\; \underbrace{\psi_{C_i} \;\cdot\!\!\!\!\!\prod_{k \in N(i),\, k \neq j}\!\!\!\!\! m_{k \to i}}_{\text{JOIN of all factors}}. \]

For the leaf clique \(C_5\) (sending toward \(C_4\), separator \(\{T\}\), no other neighbours so the inner product is empty):

\[ m_{C_5 \to C_4}(T) \;=\; \sum_{V} \psi_{C_5}(V, T) \;=\; \sum_{V} P(V)\,P(T|V). \]

That message is a 2-cell table indexed by \(T\): the marginal distribution of T after summing out V. \(C_4\) will later absorb it — that is, multiply it into the receiver's working potential — when computing its own outgoing messages.

For internal cliques the formula is the same but the inner product is non-empty. From \(C_4\) toward \(C_3\) (separator \(\{L, E\}\), incoming message from \(C_5\)):

\[ m_{C_4 \to C_3}(L, E) \;=\; \sum_{T} \psi_{C_4}(T, L, E) \cdot m_{C_5 \to C_4}(T). \]

A two-pass schedule (collect from leaves to a chosen root, then distribute from the root back out) computes every directed-edge message exactly once. Hugin (Jensen, Lauritzen and Olesen 1990) is an algebraically equivalent alternative schedule that absorbs each message into the receiver's potential in place.

Reading off posteriors

After both passes, every clique can compute its calibrated potential by multiplying its initial potential by every incoming message:

\[ \psi^{*}_{C_i} \;=\; \psi_{C_i} \,\cdot \prod_{k \in N(i)} m_{k \to i}. \]

Each calibrated potential is the marginal of the joint distribution (times any evidence potentials) over \(C_i\)'s variables — exactly what variable elimination would have computed for a query against \(C_i\), but now available simultaneously for every clique. Any individual variable's posterior is one extra marginalisation away.

To get the posterior over L, pick a clique containing L (say \(C_2\)) and sum out the rest. The result is the unnormalised posterior:

\[ \tilde P(L) \;=\; \sum_{B,S} \psi^{*}_{C_2}(B, L, S) \;=\; P(L,\,\text{evidence}). \]

It's unnormalised because the evidence potentials zero out joint configurations inconsistent with the observations: the calibrated potentials integrate to \(P(\text{evidence})\), not to 1. Apply the normalisation operation \(\nu\) — divide every cell by the sum of all cells — to get the true posterior:

\[ P(L \mid \text{evidence}) \;=\; \nu(\tilde P)(L) \;=\; \frac{\tilde P(L)}{Z}, \qquad Z \;=\; \sum_L \tilde P(L) \;=\; P(\text{evidence}). \]

This is Bayes' rule in action: \(P(L \mid \text{evidence}) = P(L, \text{evidence}) \,/\, P(\text{evidence})\). A nice side effect of the calibration: \(Z = P(\text{evidence})\) — the model's prior probability of seeing the observed data — falls out for free, useful in its own right for model comparison and outlier detection. With no evidence at all, every \(\varepsilon_X = 1\) everywhere, the calibrated potentials already sum to 1, \(Z = 1\), and the normalisation step becomes a no-op.

The dominant cost of this whole machinery is the largest clique's potential table. A clique with \(k\) variables of arities \(k_1, \ldots, k_n\) has a potential of size \(\prod_i k_i\), and each message marginalises that down to a separator subset. Total work is \(O\!\bigl(\sum_c \prod_{x\in c} k_x\bigr)\), exponential in the largest clique — which is exactly why triangulation works to minimise that clique.

d-separation and the Bayes-ball algorithm

Once you have a calibrated tree you can read posteriors. But a related question often comes up at query time: is variable \(X\) independent of variable \(Y\) given a particular set of observations? This question matters because if the answer is yes, you don't need to recompute \(P(X)\) when evidence changes only for \(Y\) — the information can't reach \(X\) anyway.

The graph-theoretic answer is d-separation (Pearl 1988). Two variables are d-separated (and hence conditionally independent in every distribution compatible with the DAG) if every undirected path between them is blocked. Whether a path is blocked depends on the shape of each three-node sub-path along it. There are three shapes, and they don't all behave the same way.

Chain: A → B → C

flowchart LR
    A((A)) --> B((B)) --> C((C))

B is on a directed path from A to C. Information flows through B — observing A shifts our belief about C via B.

  • B unobserved: the path is open. A and C are dependent.
  • B observed: the path is blocked. Knowing B makes A and C conditionally independent — once we know the intermediate state, the upstream cause and the downstream effect carry no further information about each other.

Asia example: V → T → E. Visiting Asia (V) influences Tb or Cancer (E) only through tuberculosis (T). If we already know T, learning V tells us nothing more about E.

Fork: A ← B → C

flowchart TB
    B((B))
    B --> A((A))
    B --> C((C))

B is a common cause of both A and C. They share whatever variation B induces.

  • B unobserved: open. A and C are correlated through their shared cause.
  • B observed: blocked. Knowing B accounts for the shared cause; whatever residual variation A and C have is independent.

Asia example: L ← S → B. Lung cancer and bronchitis are both caused by smoking. Among smokers (or among non-smokers) considered separately, lung cancer and bronchitis are conditionally independent. But across the population (with S unobserved), they're correlated because smokers tend to have more of both.

Collider: A → B ← C

flowchart TB
    A((A))
    C((C))
    A --> B((B))
    C --> B

B is a common effect of two independent causes. This is the case that breaks symmetry with the previous two.

  • B unobserved (and no descendant of B observed): blocked. A and C are independent in the absence of any information about B.
  • B observed (or any descendant of B observed): open. A and C become dependent through B. This is explaining away: if we observe an effect with two possible causes, learning that one cause is true makes the other cause less likely.

Asia example: T → E ← L. Tuberculosis and lung cancer are independent priors (their CPTs share no parents). But once we observe E = T ("the patient has Tb-or-Cancer"), the two compete to explain that observation: confirming tuberculosis lowers our belief in lung cancer, and vice versa. Equivalently, if we observe a descendant of E — say, X (an abnormal X-ray) — T and L also become dependent.

Putting it together

A path between two variables is blocked iff at least one triple along it is blocked under the rules above. Two variables are d-separated given a set of observations iff every path between them is blocked.

This is the algebraic reason variable elimination works. When we push a Σ over a variable inward, the sum can move past every factor that doesn't mention that variable — and the DAG structure tells us exactly which factors can mention it: the variable's own CPT and the CPTs of its children. Conditional independence (the variable is d-separated from everything else given those few factors) is the same statement, expressed graphically. Each independence the DAG encodes is one fewer factor a sum has to range over, which is one more chance to keep the intermediate factor small. The whole junction-tree pipeline — moralise, triangulate, extract cliques — is a compile-time analysis that makes this scope information explicit in the data structure: every factor a variable can ever touch lives in a single clique.

Computing d-separation by enumerating paths gets messy quickly, because the number of paths between two variables grows fast with network size. The Bayes-ball algorithm (Shachter 1998) is a linear-time procedure for the same question, framed as a reachability search: imagine a ball travelling through the DAG. At each node, the ball either passes through, bounces back the way it came, or stops, depending on the node's role on the current path (chain, fork, or collider) and whether it's observed.

The bouncing rules are exactly the three blocking rules above, written as a per-step decision the algorithm makes when the ball is at the middle node Z of a sub-path:

Sub-path through Z Z observed? descendant of Z observed? ball continues?
Chain X → Z → Y no n/a yes
Chain X → Z → Y yes n/a no
Fork X ← Z → Y no n/a yes
Fork X ← Z → Y yes n/a no
Collider X → Z ← Y no no no
Collider X → Z ← Y no yes yes
Collider X → Z ← Y yes n/a yes

Two variables are d-separated iff the ball cannot reach one from the other given the observations.

A worked example on Asia

Question: is S (Smoker) independent of V (Visit to Asia) given observation of X (Abnormal X-Ray)?

The two variables aren't directly connected. There are two undirected paths between them in the Asia DAG. Walk each one with the Bayes-ball rules.

Path 1: V → T → E ← L ← S

flowchart LR
    V((V)) --> T((T)) --> E((E))
    L((L)) --> E
    S((S)) --> L
    style X fill:#fff3a3,stroke:#a87900
    X((X<br/>observed))
    E --> X

Send the ball from S:

Node Role on this path Observed? Ball does what?
L chain (E ← L ← S) no passes through
E collider (T → E ← L) no, but X is a descendant of E and observed passes through (the descendant rule opens the collider)
T chain (V → T → E) no passes through
V endpoint — reached

The ball reaches V. Path 1 is open.

Path 2: V → T → E → D ← B ← S

Node Role on this path Observed? Ball does what?
B chain (D ← B ← S) no passes through
D collider (E → D ← B) no, no descendants observed stops

The ball is blocked at D. Path 2 is closed.

Verdict: a single open path is enough for connectivity. S and V are not d-separated given X; they are conditionally dependent.

The intuition matches the formal answer. If we observe an abnormal X-ray (X = T), we increase belief in E (Tb-or-Cancer), which has two competing causes: tuberculosis (a child of V) and lung cancer (a child of S). Confirming evidence for the child opens an explaining-away link between the two parents — and recursively, between their parents. Knowing S shifts our belief about L, which shifts our belief about E, which shifts our belief about T, which shifts our belief about V. Without any evidence on X (or any other descendant of E), the collider at E blocks this chain and V, S are independent — which is exactly what the chain-and-collider rules together encode.

Three quick variations on the same setup, each exercising a different rule:

Question Verdict Which rule fired
V ⊥ S? (no evidence) Yes, independent collider at E blocks path 1 (no descendants observed); collider at D blocks path 2
V ⊥ S given T? Yes, independent chain at T blocks path 1 (T observed); collider at D still blocks path 2
V ⊥ S given E? No, dependent collider at E is opened (E itself observed); same explaining-away as observing a descendant

Where to read more

This primer covers the core machinery: representation, inference, independence. The standard graduate references go several layers deeper — variable elimination heuristics, parameter learning, structure learning, approximate inference (loopy belief propagation, sampling, variational methods), continuous-variable extensions, and causal interpretations of the same DAG.

  • Pearl (1988), Probabilistic Reasoning in Intelligent Systems, is the foundational text.
  • Koller and Friedman (2009), Probabilistic Graphical Models: Principles and Techniques, is a comprehensive modern textbook.
  • Bishop (2006), Pattern Recognition and Machine Learning, Chapters 8 and 13, is a tighter treatment in the context of broader ML.

References

Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

Jensen, F. V., Lauritzen, S. L. and Olesen, K. G. (1990). Bayesian updating in causal probabilistic networks by local computations. Computational Statistics Quarterly, 4: 269–282.

Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.

Lauritzen, S. L. and Spiegelhalter, D. J. (1988). Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B, 50(2): 157–224.

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.

Shachter, R. D. (1998). Bayes-ball: the rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams). Proceedings of UAI '98, pp. 480–487.

Shafer, G. R. and Shenoy, P. P. (1990). Probability propagation. Annals of Mathematics and Artificial Intelligence, 2: 327–351.

Comments & reactions