Why a graph is needed
A joint distribution over binary variables has free parameters. Specifying it directly is impractical, and the table hides which variables influence which. A Bayesian network replaces the full table by a directed acyclic graph together with one small conditional table per variable. The graph records the modeling assumption that each variable depends directly only on its parents. This unit shows that the resulting product is a genuine probability distribution, and that the graph determines a family of conditional independences that can be read off by a purely graphical test, d-separation. It builds on the unit on conditional independence and evidence, and it prepares the unit on variable elimination, whose factors are exactly the tables defined here.
Definitions
Definition 33.1.1
(Bayesian network and its joint distribution)
Let be random variables, each with a finite non-empty set of values. A Bayesian network consists of
- a directed acyclic graph (DAG) whose nodes are ; write for the set of parents of , and
- for each , a conditional probability table (CPT): numbers for every value and every joint value of the parents, with for each . A node with no parents has an ordinary table .
The network defines the joint distribution
where is the restriction of to the parents of . A topological order lists the nodes so that every parent precedes its children; one exists because is acyclic. A distribution is said to factorize according to if it equals such a product for some CPTs.
Definition 33.1.2
(Conditional independence)
For three disjoint sets of variables , we say is conditionally independent of given , written , if for all values with .
The factorization theorem
Theorem 33.1.3
(Factorization of a Bayesian network)
Let be listed in a topological order. The product above is a probability distribution, and for every and every assignment with ,
Proof
(Summing out the last variable)
The product is nonnegative. Sum over first. Since the order is topological, is not a parent of any with , so only the last factor depends on , and . Hence the sum of the product over is the product of the first factors, which is the same kind of expression for the network with deleted. Repeating, the total sum over all variables equals , and the marginal distribution of is . Dividing the marginal for by the marginal for gives the second claim.
Proof X-ray
Where acyclicity is used
The proof removes variables one at a time from the end of the order. Acyclicity enters at exactly one place: after is removed, the remaining factors must not involve , which holds because no earlier variable has as a parent. The normalization then deletes the last factor and leaves a network of the same kind on nodes, so the induction continues. Without acyclicity the step fails. Take two binary variables with edges and , and let both tables be when the two values agree and otherwise. The product is when and otherwise, so it sums to , not .
The factorization theorem is the chain rule with each conditioning set shrunk to the parents. The shrinking is the substantive modeling claim: given its parents, a variable is independent of its other predecessors in the order. Consequently the number of free parameters is , which is small when parent sets are small.
Concept lensAlgorithmic
The product as a sampling procedure
Visit the nodes in a topological order and draw each from the table row selected by the values already drawn for its parents. Every run is well defined because parents come first, and the probability that a run produces is the product of the probabilities of its draws, which is exactly the defining product. In the alarm network, the run has probability . The network is therefore both a table of numbers and a recipe for generating data.
d-separation
Definition 33.1.4
(Paths, blocking and d-separation)
Independence statements implied by the graph are found by examining undirected paths, that is, sequences of distinct nodes with consecutive nodes joined by an edge in either direction. For a node on a path with neighbors and on the path, the triple is a
- chain if or ,
- fork if ,
- collider if .
Let be a set of observed nodes. A path is blocked by if it contains
- a chain or fork whose middle node lies in , or
- a collider whose middle node is not in and has no descendant in .
Disjoint sets and are d-separated by (disjoint from both) if every path from a node of to a node of is blocked by ; otherwise they are d-connected given .
Theorem 33.1.5
(Soundness of d-separation)
If and are d-separated by in , then in every distribution that factorizes according to .
Proof
(The chain, fork and collider cases)
We prove the three basic cases, which show where each rule comes from, and state the general case without proof. Write where conditioning.
- Chain . .
- Fork . .
- Collider . Summing out gives , so . But is in general not a product, so observing , or a descendant of , can create dependence.
The converse is false in a precise sense: d-connection means that dependence is possible for some choice of CPTs, not that it holds for every choice.
Counterexample mode
A collider is opened by its descendants
A tempting simplification says that a path through a collider is blocked unless the collider itself is observed. Take the network with a child , where and are independent fair bits, exactly when or , and . The collider is unobserved, yet conditioning on is conditioning on : , whereas , so and are not independent given . The corrected rule is the one in the definition: a collider blocks the path only when neither it nor any of its descendants is observed.
Worked examples
Worked example 33.1.6
(Reading a joint entry and counting parameters)
Take binary variables Burglary , Earthquake , Alarm , and two neighbors and , with edges , , , . The tables are
and equals for . The joint entry for is
The network has free parameters (one for each of and , four for , two each for and ), compared with for an unrestricted joint table.
Worked example 33.1.7
(d-separation queries and explaining away)
In the same graph, and are d-separated by : the only path has collider , which is unobserved with no observed descendant. Given they are d-connected, because is a descendant of . Given they are d-connected as well. Further, and are d-connected given (the fork is open) but d-separated by . Also and are d-separated by : the only path is the chain through the observed node .
The numbers show the collider effect. First, (the term contributes ). Then
Learning that an earthquake occurred lowers the probability of a burglary: the alarm is explained away, although and are independent a priori.
Worked example 33.1.8
(Dependence along a chain and independence given its middle)
Take binary variables with the chain and , , , , . The network has free parameters, against for a full table. One joint entry is .
With nothing observed the chain is open: while , so and are dependent. Given the chain is blocked: for both values of , and , so . As an edge case, if the chain is still d-connected, yet and are independent: the graph permits dependence but does not force it.
Common mistakes and subtle points
Common mistake
(Reading an edge as causation)
The factorization theorem holds for any DAG whose CPTs are specified; the direction of an edge only fixes which conditional tables are given. Different DAGs can define the same family of distributions.
Common mistake
(Reading d-connection as dependence)
d-separation certifies independence; it never certifies dependence. If is the only parent of a binary and , then in that network although the edge is a d-connecting path.
Common mistake
(Treating observation as always blocking)
Observing blocks the chain but opens the collider . The effect of observing a node depends on its role on the path, so classify each triple as chain, fork or collider before deciding.
Two further points. Conditioning on a node that neither lies on a given path nor descends from a collider on it leaves the status of that path unchanged. And conditional independence statements are meaningful only when the conditioning event has positive probability.
Exercises
Quick check
(In the alarm network of the first worked example, compute .)
Multiply one table entry per variable, using complementary probabilities where needed.
Solution · Answer
.
Quick check
(In the DAG with edges , , , , , decide whether each statement holds for d-separation: (a) and given ; (b) and given ; (c) and given ; (d) and given .)
Classify each triple on each path as chain, fork or collider, then decide whether the path is blocked.
Solution · Answer
(a) Yes. The fork is blocked because is observed; the path has the collider unobserved and its only descendant unobserved, so it is blocked. (b) No. Now , a descendant of the collider , is observed, so is open; the other path is still blocked, but one open path suffices for d-connection. (c) No. The fork has an unobserved middle node and is open. (d) Yes. Every path from to passes through as a chain node ( and ), and is observed, so both are blocked.
Quick check
(Let be independent fair bits and exactly when or . Compute , and .)
Write down the joint distribution of and condition on the event.
Solution · Answer
The event has probability , and lies inside it with probability , so the first value is . Given and , the value of is still a fair bit: . Given and , necessarily , so the value is . The three values show the explaining-away pattern.
Quick check
(For a network with edge and , show that although and are d-connected.)
Compute from the tables and compare it with .
Solution · Answer
Whatever is, for each . The marginal is , so , hence . The single edge is an open path, so they are d-connected; this illustrates that d-connection only allows dependence.