Bayes nets and factor graphs

Structure is the only thing that makes inference possible

Probability theory gives you one operation that does everything: sum out the variables you do not care about. Given a joint distribution $p(x_1,\dots,x_n)$ you can answer any question by marginalising, conditioning, or maximising. The difficulty is never the operation, it is the size of the object you apply it to. A full joint over n binary variables needs 2^n-1 independent numbers, and computing a single marginal costs a sum with 2^{n-1} terms. At n=30 that is more terms than there are seconds in the age of the universe.

Yet we routinely reason about models with hundreds of variables. The reason is that the joint distribution has a special form: it factors. Rain depends on clouds and season, not on the price of tea in the shop across the street. If you write each variable as a function of a small set of others — its parents — the full table never has to be stored, because it is a product of many small tables. This part is about the two standard languages for saying exactly which small tables, and the algorithms that run on them.

The first language is the Bayesian network, a directed acyclic graph whose arrows point from cause to effect. It says that the joint is the product of one conditional per node, conditioned on that node's parents. The second is the factor graph, a bipartite picture of variables and the functions they appear in, which drops the directionality and makes the algorithm for computing marginals look like messages passed along wires. The two are translations of each other, and together they turn a problem that is exponential in the number of variables into one that is exponential only in the width of the graph.

Along the way we meet the two facts that surprise everyone. Independence is a property of the graph and the observations together, not of the graph alone: two variables can be independent until you learn the value of a third, and dependent until you learn the value of a fourth. And explaining away — the reason a diagnosis becomes less likely once a second cause is confirmed — is not a quirk of human reasoning but a theorem about colliders.

One small table per node, and the chain rule does the rest

Start with a joint distribution over $x_1,\dots,x_n$ and apply the chain rule in any order you like. Pick an order that respects the causal story: $p(x_1,\dots,x_n)=\prod_i p(x_i\mid x_1,\dots,x_{i-1})$. That identity is exact but useless, because each conditional still mentions everything before it. The modelling step is to assert that most of those conditionals do not actually depend on most of those predecessors. The variable WetGrass depends on Rain and Sprinkler; whether it is wet has nothing more to say once you know those two, regardless of the season or the barometer. Strike the irrelevant arguments and you are left with a set of parents $\mathrm{pa}(i)$ and the defining equation of a Bayesian network.

Read the equation as a storage budget. Each factor $p(x_i\mid x_{\mathrm{pa}(i)})$ is a table indexed by x_i and its parents. A binary node with no parents costs one number; a binary node with one parent costs two; with two parents, four. In the classic four-node weather model — Cloudy feeding Sprinkler and Rain, both of which feed WetGrass — the network stores 1+2+2+4=9 numbers instead of the 15 a full joint over four binary variables would need. The saving looks modest here and becomes the difference between feasible and impossible at thirty variables, where the network might store a few hundred numbers against a billion.

The arrows are not decoration. If you draw one from A to B, the factorisation includes A in B's conditional; if you do not, it excludes it. A missing arrow is a positive claim: x_i is conditionally independent of that variable given its parents. This is the local Markov property, and it is where all the graph-reading rules in the next section come from. A node is independent of everything that is neither its parent, its child, nor a parent of one of its children, once you condition on those neighbours.

The direction of the arrows is a choice, not a fact about the world. Any DAG that encodes the same conditional independencies describes the same distribution; you can reverse an arrow if you pay for it by enlarging a conditional. But causal directions are usually the ones that keep the tables small, because causes tend to be roughly independent of each other while their effects are correlated. Drawing arrows from cause to effect is therefore a compression strategy as much as a statement of belief.

Notice that the blue bars are almost flat on this scale. A chain over n binary variables needs 1+2(n-1) numbers, so doubling the number of variables roughly doubles the storage, while the full joint squares it. That is the entire promise of graphical models in one picture: the graph buys you a joint that grows linearly instead of exponentially, at the cost of asserting a structure you must be willing to defend.

Independence you can read off the picture

Suppose you want to know whether X and Y are independent given a set of observed variables Z. In a Bayes net you answer this without touching a single probability: walk the graph. Look at every undirected path from X to Y and ask whether information could flow along it. If every path is blocked, the variables are d-separated given Z, and d-separation implies conditional independence in every distribution that factorises according to the graph.

A path is a sequence of distinct nodes connected by edges, traversed in either direction. Each interior node on the path is either a collider, with both path edges pointing into it, or a non-collider, with at least one edge pointing out. The blocking rules are different for the two cases, and that asymmetry is the heart of the subject.

The collider rule is the one that feels wrong until it clicks. Two independent causes, a sprinkler and rain, each make the grass wet. Before you look outside, learning that the sprinkler ran tells you nothing about the rain. But if you observe that the grass is wet, the two causes are suddenly correlated: rain becomes less likely once you learn the sprinkler was on, because the sprinkler already accounts for the evidence. Information flowed between two variables that had no arrow between them, and it flowed because we conditioned on their shared effect.

The canvas below lets you build this intuition by hand. It shows the four-node weather network: Cloudy is a fork into Sprinkler and Rain, and those two are a collider into WetGrass. Click any node to mark it observed, choose two query nodes, and the page colours each path green when active and red when blocked, then reports whether the queries are d-separated. Try observing Cloudy with Sprinkler and Rain as queries, then clear it and observe WetGrass instead.

Two warnings about reading too much into the picture. First, d-separation is sufficient for independence but not necessary: a particular distribution may have independencies that its graph does not show, and then the graph is merely not the tightest description. Second, the rules apply to the graph as drawn, so if you reverse an arrow the d-separation verdicts can change even though the distribution has not. The graph is a tool for deriving consequences of a factorisation, and different graphs of the same distribution derive different (all valid) consequences.

The collider, measured

Here is the smallest possible collider model. Two independent binary causes A and B, each with its own prior, both feed a binary effect C. The network asserts $p(a,b,c)=p(a)\,p(b)\,p(c\mid a,b)$. Because the joint factorises as a product of a term in a alone and a term in b alone, the marginals satisfy p(a,b)=p(a)p(b) exactly: A and B are independent. No conditioning on C has happened yet, and none is needed.

Now condition on the effect. By Bayes' rule, $p(a,b\mid c)\propto p(a)p(b)p(c\mid a,b)$, and the third factor couples a to b unless c is independent of one of them given the other. In general it is not, so A and B become dependent once C is known. The strength and direction of that dependence are exactly what the sliders below control. Watch three numbers as you move them: the marginal probabilities, which never move; the conditional probabilities given C=1, which both rise when the effect is a noisy OR; and the conditional probability of A given both C=1 and B=1, which falls back below the value given C=1 alone.

That last drop is explaining away. Once you already know the sprinkler was on, the wet grass is explained, and the evidence no longer supports rain as strongly. Nothing in the arithmetic knows about causes or explanations; it is a consequence of dividing two sums that share a factor. The same computation is why a medical test result becomes less alarming once a second, unrelated condition that produces the same marker is confirmed, and why a fault diagnosis system has to reason about multiple simultaneous faults rather than assuming the simplest single explanation.

There is a numerical signature of the effect that is worth carrying away. Define the conditional mutual information $I(A;B\mid C)$. In a collider it is strictly positive whenever the effect depends on both causes, while the plain mutual information I(A;B) is exactly zero. The readout below reports both a difference-of-products test and this mutual information, so you can see the independence at the top of the model and the dependence created at the bottom in the same units.

Set the two middle sliders equal and the collider is symmetric; make them different and the two causes explain away at different rates. Push $P(C=1\mid A=0,B=0)$ toward its maximum and the effect fires regardless, so C carries little information and the conditional dependence shrinks. Push it to the minimum and C=1 becomes almost a proof that at least one cause fired, which is precisely the regime where explaining away is strongest.

The same model, with the arrows removed and the algorithm revealed

The directed graph is convenient for reading independencies, but the algorithm that computes marginals does not care about direction. Write the joint as a product of factors, each a function of a small set of variables. The directed factorisation $\prod_i p(x_i\mid x_{\mathrm{pa}(i)})$ is already such a product, one factor per node. A factor graph is a bipartite graph with a circle for every variable and a square for every factor, connected exactly when the variable appears in the factor. Nothing is lost and a great deal is gained: the directed structure has become an undirected wiring diagram of the arithmetic.

The classic computation on this graph is the sum-product algorithm. Its rule is local. A variable sends to each factor it touches the product of the messages it received from all the other factors. A factor sends to each variable the sum over all its other variables of the factor value times the incoming messages. Compose the rules and every variable receives, from each factor, a summary of everything the rest of the graph knows about that variable.

For the collider model, absorb the two priors into a single factor $f(a,b,c)=p(a)p(b)p(c\mid a,b)$. The factor graph then has three variable circles and one factor square, connected to all three. The message from the factor to A is $\mu_{f\to A}(a)=\sum_{b,c} f(a,b,c)\,\mu_{B\to f}(b)\,\mu_{C\to f}(c)$, and the marginal is proportional to that message. It is a two-dimensional sum, not a five-dimensional one, and if the graph were a long chain the same local rule would cost a constant amount per node instead of an exponential amount per query. That is the entire content of the phrase "inference is local".

On trees the algorithm terminates in two sweeps and the messages are exact marginals. On graphs with cycles the same updates can be run until they settle, which is loopy belief propagation; it has no general guarantee but works well enough in practice that it underpins error-correcting codes and much of the inference in vision. The reason trees are special is that a tree has no path that carries information around a loop and back, so no message can depend on itself. Loops reintroduce the circularity that the whole graph was supposed to remove.

One translation detail is worth stating because it trips people up. A directed graph and a factor graph of the same distribution are not in one-to-one correspondence: several factor graphs can describe the same distribution, and converting a Bayes net to a factor graph loses the directionality permanently. What is preserved is the set of conditional independencies implied by the factorisation, which is why the two pictures answer the same d-separation questions. The factor graph is the better picture for the algorithm; the Bayes net is the better picture for the story.

Graphs as the default modelling language

Every formula in one place

Where to go deeper

• Judea Pearl, Probabilistic Reasoning in Intelligent Systems, 1988 — the book that introduced Bayesian networks and the d-separation criterion.
• Daphne Koller and Nir Friedman, Probabilistic Graphical Models: Principles and Techniques, 2009 — the standard reference; chapters 3 and 8–9 cover representation and exact inference.
• Christopher Bishop, Pattern Recognition and Machine Learning, chapter 8 — factor graphs and the sum-product algorithm, worked through on trees and chains.
• Frank Jensen, An Introduction to Bayesian Networks, 1996 — a gentle treatment of the independence semantics, with many small examples.
• Martin Wainwright and Michael Jordan, "Graphical Models, Exponential Families, and Variational Inference", Foundations and Trends in Machine Learning, 2008 — the variational view of the same machinery.