Graphical Models

A graphical model draws a joint distribution as a graph: nodes are random variables, and the missing links say which factorisation the distribution has and which conditional independences it satisfies. This chapter builds directed graphs (Bayesian networks) and undirected graphs (Markov random fields), proves the rules that read independences off a graph (d-separation and graph separation, the Hammersley-Clifford theorem), and derives the message-passing algorithms (sum-product and max-sum) that compute marginals and most probable configurations exactly on trees. Every argument that the book sketches or leaves to the reader is written out below.

TrungTin Nguyen · Following Bishop (2006), Pattern Recognition and Machine Learning, Chapter 8 · Course home · Mathematical toolkit · Python code for the figures

Ch. 1 Introduction Ch. 2 Probability distributions Ch. 3 Linear regression Ch. 4 Linear classification Ch. 5 Neural networks Ch. 6 Kernel methods Ch. 7 Sparse kernel machines Ch. 8 Graphical models Ch. 9 Mixture models and EM Ch. 10 Approximate inference Ch. 11 Sampling methods Ch. 12 Continuous latent variables Ch. 13 Sequential data Ch. 14 Combining models

8.1 Bayesian networks

pp. 359–362 Every calculation in this chapter is a repeated use of the sum rule and the product rule. Graphs add nothing to the mathematics; they make its structure visible. Start with any joint distribution of three variables. Two applications of the product rule give

\[ p(a,b,c)=p(c\given a,b)\,p(a,b), \tag{8.1} \] \[ p(a,b,c)=p(c\given a,b)\,p(b\given a)\,p(a), \tag{8.2} \]

which holds for every distribution. Draw one node per variable and, for each factor \(p(x\given \cdot)\), an arrow into \(x\) from every variable it is conditioned on: here \(a\to b\), \(a\to c\), \(b\to c\) (the book's Figure 8.1). An arrow \(a\to b\) makes \(a\) a parent of \(b\) and \(b\) a child of \(a\). The left-hand side of (8.2) is symmetric in \(a,b,c\) but the right-hand side is not: another ordering of the variables gives another graph for the same distribution. Repeating the product rule for \(K\) variables gives

\[ p(x_1,\dots,x_K)=p(x_K\given x_1,\dots,x_{K-1})\cdots p(x_2\given x_1)\,p(x_1), \tag{8.3} \]

a fully connected graph in which every node receives an arrow from every lower-numbered node. Such a graph says nothing about the distribution. Information comes from missing links. In the graph of Figure 8.2, for example, \(x_5\) has parents \(x_1,x_3\) only, and the joint distribution of the seven variables is

\[ p(x_1)\,p(x_2)\,p(x_3)\,p(x_4\given x_1,x_2,x_3)\,p(x_5\given x_1,x_3)\,p(x_6\given x_4)\,p(x_7\given x_4,x_5). \tag{8.4} \]

Proof

Ordering implies acyclic (the direction asked in Exercise 8.2). Along a directed cycle \(k_1\to k_2\to\dots\to k_m\to k_1\) the numbers would increase strictly at each step and yet return to the starting number, which is impossible.

Acyclic implies ordering. First, a finite DAG has a node without parents. Start at any node and step to one of its parents, then to a parent of that node, and so on. If every node had a parent, this could go on forever; after \(K+1\) steps some node would appear twice, and the steps between the two visits, read in the direction of the arrows, would be a directed cycle. So some node has no parents. Give it the number 1 and delete it with its links. What remains is still a DAG, so it has a node without parents (within the remaining graph): number it 2, delete it, and continue. When node \(k\) is numbered, all its parents in the original graph have already been deleted, so they carry smaller numbers. Every link therefore points from a lower to a higher number. ∎

Proof

Marginalise the last node. In a topological ordering \(x_K\) has no children (a child would carry a larger number). So \(x_K\) appears in exactly one factor, its own, and

\[ \sum_{x_K}\prod_{j=1}^{K}q_j(x_j\given\pa_j)=\Big[\prod_{j=1}^{K-1}q_j(x_j\given\pa_j)\Big]\sum_{x_K}q_K(x_K\given\pa_K)=\prod_{j=1}^{K-1}q_j(x_j\given\pa_j). \]

The result is the same kind of product over the first \(K-1\) nodes, whose parents are all among \(x_1,\dots,x_{K-2}\). Repeating the step gives \(p(x_1,\dots,x_k)=\prod_{j\le k}q_j\) for every \(k\), and finally \(\sum_{x_1}q_1(x_1)=1\): the joint is normalised (for continuous variables replace sums by integrals; Fubini's theorem allows the order).

The factors are the conditionals. Dividing the formula for \(p(x_1,\dots,x_k)\) by the one for \(p(x_1,\dots,x_{k-1})\) gives \(p(x_k\given x_1,\dots,x_{k-1})\)\({}=q_k(x_k\given\pa_k)\) wherever the denominator is positive. This depends on \(x_1,\dots,x_{k-1}\) only through \(\pa_k\subseteq\{x_1,\dots,x_{k-1}\}\). Averaging it over the other predecessors given \(\pa_k\) therefore changes nothing: \(p(x_k\given\pa_k)\)\({}=\E\big[p(x_k\given x_1,\dots,x_{k-1})\given\pa_k\big]\)\({}=q_k(x_k\given\pa_k)\).

Converse. The chain rule (8.3) holds for every \(p\). If each factor \(p(x_k\given x_1,\dots,x_{k-1})\) is a function of \(x_k\) and \(\pa_k\) only, (8.3) is a product of the form (8.5). ∎

Nodes may stand for single variables, vectors or groups of variables. Every distribution factorises over a fully connected DAG (by (8.3)), so the interest of a graph is in the links it omits.

8.1.1 Example: Polynomial regression

pp. 362–365 In the Bayesian polynomial regression of Section 1.2.6 the random variables are the coefficient vector \(\mathbf{w}\) and the targets \(\mathbf{t}=(t_1,\dots,t_N)^\T\). Given \(\mathbf{w}\) the targets are generated independently, so

\[ p(\mathbf{t},\mathbf{w})=p(\mathbf{w})\prod_{n=1}^{N}p(t_n\given\mathbf{w}). \tag{8.6} \]

The graph has an arrow from \(\mathbf{w}\) to each \(t_n\) (the book's Figure 8.3). A plate, a box labelled \(N\) around a single node \(t_n\), stands for \(N\) copies of everything inside it (Figure 8.4). Deterministic quantities (the inputs \(x_n\), the prior precision \(\alpha\), the noise variance \(\sigma^2\)) are drawn as small solid dots (Figure 8.5); with them written out, \(p(\mathbf{t},\mathbf{w}\given\mathbf{x},\alpha,\sigma^2)\)\({}=p(\mathbf{w}\given\alpha)\prod_n p(t_n\given\mathbf{w},x_n,\sigma^2)\). Observed variables are shaded (Figure 8.6). An unobserved variable such as \(\mathbf{w}\) is called latent or hidden. Bayes' theorem gives the posterior

\[ p(\mathbf{w}\given\mathbf{t})\propto p(\mathbf{w})\prod_{n=1}^{N}p(t_n\given\mathbf{w}). \tag{8.7} \]

Erratum. Some printings write \(p(\mathbf{w}\given\mathbf{T})\) on the left of (8.7); it should be \(\mathbf{t}\).

To predict the target \(\widehat t\) at a new input \(\widehat x\) (the book's Figure 8.7) add the node \(\widehat t\) with parent \(\mathbf{w}\):

\[ p(\widehat t,\mathbf{t},\mathbf{w}\given\widehat x,\mathbf{x},\alpha,\sigma^2)=\Big[\prod_{n=1}^{N}p(t_n\given x_n,\mathbf{w},\sigma^2)\Big]p(\mathbf{w}\given\alpha)\,p(\widehat t\given\widehat x,\mathbf{w},\sigma^2), \tag{8.8} \]

and the predictive distribution is \(p(\widehat t\given\widehat x,\mathbf{x},\mathbf{t},\alpha,\sigma^2)\)\({}\propto\int p(\widehat t,\mathbf{t},\mathbf{w}\given\widehat x,\mathbf{x},\alpha,\sigma^2)\,\d\mathbf{w}\) (p. 365).

8.1.2 Generative models

pp. 365–366 A DAG is also a recipe for simulation. Number the nodes topologically and draw each variable from its conditional distribution given the values already drawn for its parents.

Proof

For discrete variables, the probability of producing a particular \(\mathbf{x}\) is the probability of making each of the \(K\) draws correctly in turn, which by the product rule is

\[ \prod_{k=1}^{K}\Pr\big(\widehat x_k=x_k\given\widehat x_1=x_1,\dots,\widehat x_{k-1}=x_{k-1}\big)=\prod_{k=1}^{K}p(x_k\given\pa_k)=p(\mathbf{x}), \]

since step \(k\) uses only the parent values. For continuous variables the same argument with conditional densities shows that \((\widehat x_1,\dots,\widehat x_k)\) has joint density \(\prod_{j\le k}p(x_j\given\pa_j)\) for every \(k\) (induction on \(k\)). A sub-vector of a random vector with distribution \(p\) has the marginal distribution by definition of a marginal. ∎

In applications the observed variables are usually the last nodes (leaves), and the latent variables above them make a complicated distribution over the observations out of simple, often exponential-family, conditionals. The book's Figure 8.8 is an example: an image depends on the identity of an object and on its position and orientation, which are a priori independent; recognising the object means computing its posterior given the image, integrating over position and orientation. Because such a graph describes how the data could have been produced (the causal process, Pearl, 1988), ancestral sampling produces synthetic "fantasy" data, and these models are called generative. The regression model of Figure 8.5 is not generative: it puts no distribution on the inputs \(x_n\). For drawing samples when some nodes are observed, see logic sampling and its acceptance rate in Chapter 11, Filling the gap 11.1.

8.1.3 Discrete variables

pp. 366–369 A variable with \(K\) states, coded 1-of-\(K\) as \(\mathbf{x}=(x_1,\dots,x_K)\) with one entry equal to 1, has distribution

\[ p(\mathbf{x}\given\bm\mu)=\prod_{k=1}^{K}\mu_k^{x_k}, \tag{8.9} \]

with \(\mu_k\ge0\) and \(\sum_k\mu_k=1\), so \(K-1\) free parameters. A general joint distribution of two such variables needs \(\mu_{kl}=p(x_{1k}=1,x_{2l}=1)\): \(K^2-1\) free parameters. How many parameters does a graph need?

Proof

The counting argument. A distribution on a set of \(n\) points is a vector in the probability simplex, which has \(n-1\) free coordinates (the last one is fixed by the sum to one). The table \(p(x_k\given\pa_k)\) consists of one distribution over the \(K_k\) states of \(x_k\) for each of the \(\prod_{j\in\pa_k}K_j\) configurations of the parents, and these distributions can be chosen independently of each other. Summing over nodes gives the formula.

Fully connected. Node \(k\) has \(k-1\) parents, so the count is \(\sum_{k=1}^{M}(K-1)K^{k-1}\)\({}=(K-1)\frac{K^M-1}{K-1}\)\({}=K^M-1\) (a geometric sum). This equals the number of free parameters of an arbitrary joint distribution of \(M\) variables (a simplex with \(K^M\) vertices), as it must: by (8.3) every joint distribution factorises over this graph, and for strictly positive distributions the tables are determined by the joint (Result 8.2), so the map from tables to joints is one-to-one. For \(M=2\): \((K-1)+K(K-1)=K^2-1\) (Figure 8.9a).

No links. Each node has no parents: \(M(K-1)\) (Figure 8.9b gives \(2(K-1)\) for \(M=2\)).

Chain. \(x_1\) has no parents (\(K-1\)); each of \(x_2,\dots,x_M\) has one parent with \(K\) states (\(K(K-1)\) each).

Tied chain. \(p(x_1)\) needs \(K-1\) and the single shared table \(p(x_i\given x_{i-1})\) needs \(K(K-1)\), total \(K^2-1\), independent of \(M\). ∎

Graphs of intermediate connectivity interpolate between the two extremes: more general than full independence, cheaper than a general joint. A Bayesian treatment puts a Dirichlet prior on each table, which adds a parameter node as an extra parent of each discrete node (the book's Figure 8.11), or a single shared parameter node when the tables are tied (Figure 8.12).

A third way to control the number of parameters is a parametric conditional distribution. For binary parents \(x_1,\dots,x_M\) of a binary child \(y\) (Figure 8.13) a full table has \(2^M\) entries, but the logistic sigmoid of a linear combination,

\[ p(y=1\given x_1,\dots,x_M)=\sigma\Big(w_0+\sum_{i=1}^{M}w_ix_i\Big)=\sigma(\mathbf{w}^\T\mathbf{x}), \tag{8.10} \]

with \(\sigma(a)=(1+e^{-a})^{-1}\), \(\mathbf{x}=(1,x_1,\dots,x_M)^\T\) and \(\mathbf{w}=(w_0,\dots,w_M)^\T\), needs only \(M+1\). The noisy-OR of Exercise 8.6 is another such model.

8.1.4 Linear-Gaussian models

pp. 370–372 Now let each node be a continuous variable whose conditional distribution is Gaussian with a mean linear in its parents:

\[ p(x_i\given\pa_i)=\N\Big(x_i\;\Big|\sum_{j\in\pa_i}w_{ij}x_j+b_i,\;v_i\Big). \tag{8.11} \]

The log of the joint distribution is

\[ \ln p(\mathbf{x})=\sum_{i=1}^{D}\ln p(x_i\given\pa_i) \tag{8.12} \] \[ \phantom{\ln p(\mathbf{x})}=-\sum_{i=1}^{D}\frac{1}{2v_i}\Big(x_i-\sum_{j\in\pa_i}w_{ij}x_j-b_i\Big)^2+\const, \tag{8.13} \]

a quadratic function of \(\mathbf{x}\), so \(p(\mathbf{x})\) is Gaussian. Equivalently, each variable is generated as

\[ x_i=\sum_{j\in\pa_i}w_{ij}x_j+b_i+\sqrt{v_i}\,\epsilon_i, \tag{8.14} \]

with \(\epsilon_1,\dots,\epsilon_D\) independent standard normal (\(\E[\epsilon_i]=0\), \(\E[\epsilon_i\epsilon_j]=I_{ij}\)). Taking expectations,

\[ \E[x_i]=\sum_{j\in\pa_i}w_{ij}\E[x_j]+b_i, \tag{8.15} \]

and multiplying the centred version of (8.14) by \(x_i-\E[x_i]\),

\[ \cov[x_i,x_j]=\E\Big[(x_i-\E[x_i])\Big\{\sum_{k\in\pa_j}w_{jk}(x_k-\E[x_k])+\sqrt{v_j}\,\epsilon_j\Big\}\Big]=\sum_{k\in\pa_j}w_{jk}\cov[x_i,x_k]+I_{ij}v_j. \tag{8.16} \]

Proof

Gaussian. In matrix form (8.14) reads \(\mathbf{x}\)\({}=\mathbf{W}\mathbf{x}+\mathbf{b}\)\({}+\mathbf{V}^{1/2}\bm\epsilon\), i.e. \((\mathbf{I}-\mathbf{W})\mathbf{x}\)\({}=\mathbf{b}+\mathbf{V}^{1/2}\bm\epsilon\). Because \(\mathbf{W}\) is strictly lower triangular, \(\mathbf{I}-\mathbf{W}\) is lower triangular with unit diagonal, so its determinant is 1 and it is invertible. Hence \(\mathbf{x}\)\({}=(\mathbf{I}-\mathbf{W})^{-1}(\mathbf{b}+\mathbf{V}^{1/2}\bm\epsilon)\) is an affine function of the standard Gaussian vector \(\bm\epsilon\), so it is Gaussian with mean \((\mathbf{I}-\mathbf{W})^{-1}\mathbf{b}\) and covariance \((\mathbf{I}-\mathbf{W})^{-1}\mathbf{V}^{1/2}\mathbf{I}\mathbf{V}^{1/2}(\mathbf{I}-\mathbf{W})^{-\T}\).

Precision from (8.13). The sum in (8.13) is \(\frac12\big((\mathbf{I}-\mathbf{W})\mathbf{x}-\mathbf{b}\big)^\T\mathbf{V}^{-1}\big((\mathbf{I}-\mathbf{W})\mathbf{x}-\mathbf{b}\big)\). Its quadratic term is \(\frac12\mathbf{x}^\T\bm\Lambda\mathbf{x}\) with \(\bm\Lambda\) as stated, which confirms the precision. The constant in (8.13) is \(-\frac12\sum_i\ln(2\pi v_i)\), and \(|\bm\Lambda|=|\mathbf{V}|^{-1}\) because \(|\mathbf{I}-\mathbf{W}|=1\), so the constant is exactly the Gaussian normaliser \(\frac12\ln|\bm\Lambda|-\frac D2\ln2\pi\), as Result 8.2 promises.

The recursions. (8.15) is the expectation of (8.14). For (8.16), induction along the ordering shows that \(x_i-\E[x_i]\) is a linear combination of \(\epsilon_1,\dots,\epsilon_i\) only. Hence \(\E[(x_i-\E[x_i])\epsilon_j]\) is 0 for \(i\lt j\) (independence), and for \(i=j\) it equals \(\sqrt{v_j}\,\E[\epsilon_j^2]=\sqrt{v_j}\) (the other terms of \(x_j-\E[x_j]\) involve only \(\epsilon_k\), \(k\lt j\)). Multiplying by \(\sqrt{v_j}\) gives the term \(I_{ij}v_j\) of (8.16) for \(i\le j\). For \(i\gt j\) the formula is wrong in general: if \(x_i\) is a child of \(x_j\), then \(x_i\) depends on \(\epsilon_j\) and the missing term \(\sqrt{v_j}\E[(x_i-\E x_i)\epsilon_j]\)\({}=w_{ij}v_j\)\({}\ne0\). In practice, fill the covariance matrix row by row, \(j=1,\dots,D\), and within row \(j\) take \(i=1,\dots,j\): every entry \(\cov[x_i,x_k]\) with \(k\in\pa_j\) needed on the right of (8.16) has \(k\lt j\) and is already known (for \(i=j\) it is the entry \((k,j)\) computed earlier in the same row).

Sparsity of \(\bm\Lambda\). \(\Lambda_{ij}\)\({}=\sum_k(\mathbf{I}-\mathbf{W})_{ki}(\mathbf{I}-\mathbf{W})_{kj}/v_k\), and \((\mathbf{I}-\mathbf{W})_{ki}\ne0\) only if \(k=i\) or \(i\in\pa_k\). For \(i\ne j\) the term \(k=i\) is \(-w_{ij}/v_i\) (nonzero only if \(j\in\pa_i\)), the term \(k=j\) is \(-w_{ji}/v_j\) (only if \(i\in\pa_j\)), and a term with \(k\ne i,j\) is \(w_{ki}w_{kj}/v_k\) (only if \(i,j\in\pa_k\)). These are exactly the links of the moral graph of Section 8.3.4. ∎

p. 372 The same construction works when the nodes are Gaussian vectors,

\[ p(\mathbf{x}_i\given\pa_i)=\N\Big(\mathbf{x}_i\;\Big|\sum_{j\in\pa_i}\mathbf{W}_{ij}\mathbf{x}_j+\mathbf{b}_i,\;\bm\Sigma_i\Big), \tag{8.19} \]

with matrices \(\mathbf{W}_{ij}\) (rectangular if the dimensions differ): stacking the nodes, \(\mathbf{I}-\mathbf{W}\) is block lower triangular with identity blocks on the diagonal, hence invertible, and the proof of Result 8.5 goes through with \(\mathbf{V}=\diag(\bm\Sigma_1,\dots,\bm\Sigma_D)\). The conjugate Gaussian prior on the mean of a Gaussian (Section 2.3.6) is the two-node case \(\bm\mu\to\mathbf{x}\); a Gaussian prior on the prior mean (a hyperprior) adds a third node above it, giving a hierarchical Bayesian model that is still jointly Gaussian. Probabilistic PCA, factor analysis (Chapter 12) and linear dynamical systems (Chapter 13) are linear-Gaussian models of this kind (Roweis and Ghahramani, 1999).

8.2 Conditional independence

pp. 372–373 If the conditional distribution of \(a\) given \(b\) and \(c\) does not depend on \(b\),

\[ p(a\given b,c)=p(a\given c), \tag{8.20} \]

then, by the product rule,

\[ p(a,b\given c)=p(a\given b,c)\,p(b\given c)=p(a\given c)\,p(b\given c). \tag{8.21} \]

The requirement "for every value of \(c\)" matters: a dependence for a single value of \(c\) breaks the property. The following criterion makes most proofs in this chapter one line long.

Proof

(a) If \(a\indep b\given c\), take \(g(a,c)=p(a\given c)\) and \(h(b,c)=p(b,c)\) when \(p(c)\gt0\), and \(h(b,c)=0\) when \(p(c)=0\) (then \(p(a,b,c)=0\) too). Conversely, suppose \(p(a,b,c)=g(a,c)h(b,c)\) and put \(G(c)=\sum_ag(a,c)\), \(H(c)=\sum_bh(b,c)\). Summing over \(a\), over \(b\), or over both gives \(p(b,c)=G(c)h(b,c)\), \(p(a,c)=g(a,c)H(c)\) and \(p(c)=G(c)H(c)\). For \(p(c)\gt0\),

\[ p(a\given c)\,p(b\given c)=\frac{g(a,c)H(c)\;G(c)h(b,c)}{G(c)^2H(c)^2}=\frac{g(a,c)h(b,c)}{G(c)H(c)}=\frac{p(a,b,c)}{p(c)}=p(a,b\given c). \]

(b) By (a), \(p(a,b,d,c)=g(a,c)h(b,d,c)\). Summing over \(d\): \(p(a,b,c)=g(a,c)\,\widetilde h(b,c)\) with \(\widetilde h=\sum_dh\), so \(a\indep b\given c\) by (a). (The book's solution sums \(p(a,b,d\given c)=p(a\given c)p(b,d\given c)\) over \(d\), which is the same argument.)

(c) The same factorisation \(p(a,b,d,c)=g(a,c)h(b,d,c)\) reads, with \((c,d)\) as the conditioning variable, \(g'(a,(c,d))\,h(b,(c,d))\) where \(g'\) ignores \(d\); by (a), \(a\indep b\given(c,d)\). ∎

Testing a conditional independence by manipulating the sum and product rules is laborious. The point of the graph is that the independences can be read off it, by a criterion called d-separation (Pearl, 1988). The three examples below contain all the ideas.

8.2.1 Three example graphs

pp. 373–376 By (8.5), the three graphs of Figure 8.15 (top row) have the joint distributions

\[ \text{tail-to-tail } (a\leftarrow c\to b):\qquad p(a,b,c)=p(a\given c)\,p(b\given c)\,p(c), \tag{8.23} \] \[ \text{head-to-tail } (a\to c\to b):\qquad p(a,b,c)=p(a)\,p(c\given a)\,p(b\given c), \tag{8.26} \] \[ \text{head-to-head } (a\to c\leftarrow b):\qquad p(a,b,c)=p(a)\,p(b)\,p(c\given a,b). \tag{8.28} \]

The names describe how the two arrows of the path \(a - c - b\) meet at \(c\): at their tails, one head and one tail, or at their heads. Marginalising (8.23) over \(c\) gives

\[ p(a,b)=\sum_c p(a\given c)\,p(b\given c)\,p(c), \tag{8.24} \]

which in general is not \(p(a)p(b)\), so

\[ a\nindep b\given\varnothing; \tag{8.25} \]

the same holds for the head-to-tail graph,

\[ a\nindep b\given\varnothing, \tag{8.27} \]

whereas for the head-to-head graph \(\sum_c p(c\given a,b)=1\) gives \(p(a,b)=p(a)p(b)\):

\[ a\indep b\given\varnothing. \tag{8.29} \]

Proof, with numerical counterexamples

Tail-to-tail. (8.23) is of the form \(g(a,c)h(b,c)\) with \(g=p(a\given c)\), \(h=p(b\given c)p(c)\), so \(a\indep b\given c\) by Result 8.6(a). Directly: \(p(a,b\given c)\)\({}=p(a,b,c)/p(c)\)\({}=p(a\given c)p(b\given c)\) (p. 374). Counterexample to marginal independence: let \(c\in\{0,1\}\) with \(p(c=1)=\frac12\), and let \(a\) and \(b\) each copy \(c\) with probability 0.9: \(p(a=1\given c=1)=p(b=1\given c=1)=0.9\), \(p(a=1\given c=0)=p(b=1\given c=0)=0.1\). Then \(p(a=1)=p(b=1)=\frac12\), but \(p(a=1,b=1)\)\({}=\frac12(0.9^2+0.1^2)\)\({}=0.41\ne0.25\). A common cause makes its effects dependent.

Head-to-tail. (8.26) is \(g(a,c)h(b,c)\) with \(g=p(a)p(c\given a)\), \(h=p(b\given c)\), so \(a\indep b\given c\). (Equivalently, by Bayes' theorem \(p(a)p(c\given a)=p(c)p(a\given c)\), so \(p(a,b\given c)=p(a\given c)p(b\given c)\), as on p. 375.) Marginally, \(p(a,b)\)\({}=p(a)\sum_cp(c\given a)p(b\given c)\)\({}=p(a)p(b\given a)\), and \(p(b\given a)\) depends on \(a\) in general. Counterexample: \(p(a=1)=\frac12\), \(c\) copies \(a\) with probability 0.9 and \(b\) copies \(c\) with probability 0.9. Then \(p(b=1\given a=1)=0.9\cdot0.9+0.1\cdot0.1=0.82\) and \(p(b=1\given a=0)=0.18\), whereas independence would need both equal to \(p(b=1)=0.5\).

Head-to-head. Marginal independence was shown in (8.29). Given \(c\), \(p(a,b\given c)=p(a)p(b)p(c\given a,b)/p(c)\), and \(p(c\given a,b)\) need not split into a function of \((a,c)\) times a function of \((b,c)\). Counterexample: \(a,b\) independent fair bits and \(c=a\oplus b\) (exclusive or). Given \(c=0\), \((a,b)\) is \((0,0)\) or \((1,1)\) with probability \(\frac12\) each, so \(p(a=1\given c=0)=p(b=1\given c=0)=\frac12\) but \(p(a=1,b=1\given c=0)=\frac12\ne\frac14\). Knowing \(c\) and \(a\) determines \(b\). The fuel gauge below is a less extreme example. ∎

Graphical summary pp. 374–376. A path through a tail-to-tail or head-to-tail node is open when the node is unobserved and blocked when it is observed. A path through a head-to-head node is blocked when the node is unobserved and becomes open when it is observed. A node \(y\) is a descendant of \(x\) if there is a directed path from \(x\) to \(y\); observing a descendant of a head-to-head node also opens the path.

Proof

The joint is \(p(a)p(b)p(c\given a,b)p(d\given c)\). Summing over \(d\) and then \(c\) gives \(p(a,b)=p(a)p(b)\). Given \(d\),

\[ p(a,b\given d)=\frac{p(a)\,p(b)\sum_cp(c\given a,b)\,p(d\given c)}{p(d)}, \]

and the sum is an arbitrary-looking function of \((a,b,d)\). Counterexample: \(a,b\) fair independent bits, \(c=a\oplus b\), and \(d\) a noisy copy of \(c\), \(p(d=c\given c)=0.9\). Then \(p(a,b,d=0)=\frac14\cdot0.9\) if \(a=b\) and \(\frac14\cdot0.1\) otherwise, so \(p(d=0)=\frac12\), \(p(a=1\given d=0)=p(b=1\given d=0)=\frac12\), but \(p(a=1,b=1\given d=0)=0.45\ne0.25\). The report \(d\) carries information about \(c\), and that is enough to couple \(a\) and \(b\). ∎

Explaining away: the fuel gauge pp. 376–378, (8.30)–(8.33)

Battery \(B\) (charged 1, flat 0) and fuel tank \(F\) (full 1, empty 0) are independent a priori, \(p(B=1)=p(F=1)=0.9\), and both influence the gauge \(G\) (reads full 1, empty 0) through

The graph \(B\to G\leftarrow F\) is head-to-head at \(G\). Observing \(G=0\) makes an empty tank more likely; then learning that the battery is flat makes it less likely again, because the flat battery already explains the reading:

\[ p(G=0)=\sum_{B\in\{0,1\}}\sum_{F\in\{0,1\}}p(G=0\given B,F)\,p(B)\,p(F)=0.315, \tag{8.30} \] \[ p(G=0\given F=0)=\sum_{B\in\{0,1\}}p(G=0\given B,F=0)\,p(B)=0.81, \tag{8.31} \] \[ p(F=0\given G=0)=\frac{p(G=0\given F=0)\,p(F=0)}{p(G=0)}\simeq0.257, \tag{8.32} \] \[ p(F=0\given G=0,B=0)=\frac{p(G=0\given B=0,F=0)\,p(F=0)}{\sum_{F\in\{0,1\}}p(G=0\given B=0,F)\,p(F)}\simeq0.111. \tag{8.33} \]

Exercise 8.11 replaces the gauge by a driver's unreliable report of it, a descendant of \(G\); explaining away persists (solution).

8.2.2 D-separation

pp. 378–379 The general rule replaces the single middle node by every node on every path.

In Figure 8.22(a), with \(C=\{c\}\), the only path from \(a\) to \(b\) is \(a\to e\leftarrow f\to b\). It is not blocked at \(f\) (tail-to-tail but unobserved), nor at \(e\) (head-to-head, and its descendant \(c\) is observed). So \(a\indep b\given c\) does not follow from the graph. In Figure 8.22(b), with \(C=\{f\}\), the same path is blocked at \(f\) (tail-to-tail and observed), and also at \(e\) (head-to-head with neither \(e\) nor \(c\) observed), so \(a\indep b\given f\) for every distribution that factorises over the graph. With nothing observed, the path is blocked at \(e\) and \(a\indep b\given\varnothing\).

The book states that d-separation implies conditional independence for every factorising distribution and refers to Lauritzen (1996) for a proof (p. 373). It also describes the graph as a filter (p. 381, Figure 8.25): the set of distributions passed by the factorisation filter, \(\mathcal{DF}\), equals the set passed by the filter "satisfy every d-separation statement". Both claims are proved below; the proof is the main piece of theory missing from the chapter.

Proof of (a) and (b)

Write \(\an(S)\) for the set of nodes of \(S\) together with all their ancestors. The proof of (a) goes through an undirected graph and has three steps (Lauritzen et al., 1990).

Step 1: marginal on an ancestral set. Let \(H=\an(A\cup B\cup C)\). Then \(p(\mathbf{x}_H)=\prod_{k\in H}p(x_k\given\pa_k)\). Indeed, \(H\) contains the parents of its nodes. Among the nodes outside \(H\), take the last one \(v\) in a topological ordering. A child of \(v\) inside \(H\) would make \(v\) an ancestor of \(H\), hence a member of \(H\); a child outside \(H\) would come after \(v\). So \(v\) has no children, appears only in its own factor, and summing over \(x_v\) removes that factor (as in Result 8.2). Repeat until only \(H\) is left.

Step 2: an undirected factorisation. Let \(M\) be the moral graph of \(G\) restricted to \(H\): join every pair of parents of a common child by an undirected link, then drop all arrow heads (Section 8.3.4). Each factor \(p(x_k\given\pa_k)\) depends on \(\{k\}\cup\pa_k\), a fully connected set in \(M\). If \(C\) separates \(A\) from \(B\) in \(M\) (every path from \(A\) to \(B\) in \(M\) passes through \(C\)), then Result 8.12 (a three-line argument in Section 8.3.2, independent of this proof) gives \(A\indep B\given C\) under \(p(\mathbf{x}_H)\), and therefore under \(p\), since \(A,B,C\subseteq H\).

Step 3: d-separation in \(G\) implies separation in \(M\). We prove the contrapositive: a path in \(M\) from \(A\) to \(B\) avoiding \(C\) yields an active path in \(G\). Call a trail a sequence of nodes, each linked in \(G\) to the next, in which nodes may repeat; a trail is active if every non-collider occurrence is outside \(C\) and every collider occurrence is in \(\an(C)\) (that is, the node or one of its descendants is in \(C\)).

(i) From \(M\) to a trail. Let \(a=v_0 - v_1 - \dots - v_n=b\) be the path in \(M\), with no \(v_i\) in \(C\). Each link of \(M\) is either a link of \(G\) or a moral link between two parents of a child \(w\in H\); replace the latter by \(v_i\to w\leftarrow v_{i+1}\). This gives a trail in \(G\) whose non-collider occurrences are all among the \(v_i\) (so outside \(C\)) and whose colliders all lie in \(H=\an(A\cup B\cup C)\).

(ii) Removing bad colliders. Among all trails from \(A\) to \(B\) whose non-colliders avoid \(C\) and whose colliders lie in \(\an(A\cup B\cup C)\), choose one with the fewest collider occurrences outside \(\an(C)\). Suppose it has such a collider \(w\). Then \(w\in\an(A\cup B)\), so there is a directed path \(w\to\dots\to t\) with \(t\in A\cup B\), and no node of it is in \(C\) (otherwise \(w\in\an(C)\)). If \(t\in A\), start a new trail at \(t\), run backwards along this directed path to \(w\), then continue along the old trail from \(w\) to its end in \(B\). On the new piece every node, including \(w\), is a non-collider (the links run in one direction), and none is in \(C\); the rest of the trail keeps its old colliders minus \(w\). If \(t\in B\), keep the old trail from its start to \(w\) and then follow the directed path to \(t\). Either way there is one bad collider fewer, a contradiction. So the chosen trail is active.

(iii) From an active trail to an active path. If a node \(v\) occurs twice on an active trail, cut out the stretch between the two occurrences. The new occurrence of \(v\) keeps the link before the first occurrence and the link after the second. If \(v\in C\), both old occurrences were colliders (non-colliders avoid \(C\)), so both kept links point into \(v\): the new occurrence is a collider in \(C\subseteq\an(C)\). If \(v\notin C\) and the new occurrence is a non-collider, nothing is needed. Finally let \(v\notin C\) with the new occurrence a collider, so both kept links point into \(v\). If either old occurrence was a collider, \(v\in\an(C)\) and we are done. Otherwise the first old occurrence, entered by a link pointing into \(v\), was left by a link pointing away from \(v\); likewise the second was entered by a link pointing away from \(v\). So the cut-out stretch starts with \(v\to\cdot\) and ends with \(\cdot\leftarrow v\). Walking along it, the first link traversed against its arrow is preceded by a collider of the trail, which is reached from \(v\) by a directed path; that collider is in \(\an(C)\) because the trail is active, hence so is \(v\). In every case the shorter trail is still active. Repeating the cut, we end with an active path from \(A\) to \(B\): \(C\) does not d-separate \(A\) from \(B\).

Together: d-separation in \(G\) gives separation in \(M\) (Step 3), which gives \(A\indep B\given C\) (Steps 1 and 2). This proves (a).

(b) "If" is (a). For "only if", number the nodes topologically and let \(P_k=\{1,\dots,k-1\}\). Claim: \(\pa_k\) d-separates \(k\) from \(P_k\setminus\pa_k\). Take a path from \(k\) to \(u\in P_k\setminus\pa_k\). If its first link is \(j\to k\), then \(j\in\pa_k\), \(j\ne u\), and the link leaves \(j\) by its tail, so \(j\) is not head-to-head: the path is blocked at \(j\in\pa_k\). If its first link is \(k\to y_1\), follow the path \(k\to y_1, y_2,\dots,u\). Not all its links can point forwards, since \(u\) precedes \(k\) and so is not a descendant of \(k\). At the first link that points backwards, the node just before it is head-to-head and is a descendant of \(k\); neither it nor any of its descendants is in \(\pa_k\) (that would close a directed cycle). So the path is blocked there. Hence the claim. If \(p\) satisfies all d-separation statements, it satisfies these, so \(p(x_k\given\mathbf{x}_{P_k})=p(x_k\given\pa_k)\) for every \(k\), and \(p\in\mathcal{DF}\) by Result 8.2. ∎

Two remarks complete the picture. First, the fully connected DAG has no d-separation statements and \(\mathcal{DF}\) is everything; the empty graph lets through only fully factorised distributions. A fully factorised distribution passes every filter: \(\mathcal{DF}\) contains distributions with more independences than the graph shows. Second, d-separation can be tested in time linear in the size of the graph (Geiger, Verma and Pearl, 1990), which is what the demonstration does.

Parameters p. 379. Deterministic parameters (solid dots such as \(\alpha\), \(\sigma^2\) in Figure 8.5) behave like observed nodes. They have no parents, so every path through them is tail-to-tail there and blocked: they never affect d-separation.

Independent identically distributed data pp. 379–380. In the graph \(\mu\to x_n\), \(n=1,\dots,N\) (the book's Figure 8.23), the unique path between \(x_i\) and \(x_j\) is tail-to-tail at \(\mu\). Given \(\mu\) it is blocked, so

\[ p(\mathcal D\given\mu)=\prod_{n=1}^{N}p(x_n\given\mu); \tag{8.34} \]

with \(\mu\) unobserved the path is open and

\[ p(\mathcal D)=\int_{-\infty}^{\infty}p(\mathcal D\given\mu)\,p(\mu)\,\d\mu\ne\prod_{n=1}^{N}p(x_n). \tag{8.35} \]

Erratum. Some printings have 0 as the lower limit of the integral in (8.35); it should be \(-\infty\).

For example, with \(\mu\sim\N(\mu_0,\sigma_0^2)\) and \(x_n\given\mu\sim\N(\mu,\sigma^2)\), write \(x_n=\mu+\sigma\epsilon_n\): then \(\cov[x_i,x_j]=\var[\mu]=\sigma_0^2\) for \(i\ne j\), so \(p(\mathcal D)\)\({}=\N(\mathcal D\given\mu_0\mathbf 1,\sigma^2\mathbf I+\sigma_0^2\mathbf 1\mathbf 1^\T)\), which is not a product: each observation tells us something about \(\mu\) and hence about the next one. In the regression graph of Figure 8.7, the path from \(\widehat t\) to each \(t_n\) is tail-to-tail at \(\mathbf w\), so

\[ \widehat t\indep t_n\given\mathbf{w}, \tag{8.36} \]

which is why the training data can be discarded once the posterior over \(\mathbf w\) is known (Filling the gap 8.2).

Naive Bayes pp. 380–381, Figure 8.24

A class label \(\mathbf z\) (1-of-\(K\), prior \(p(\mathbf z\given\bm\mu)\)) is the single parent of every feature \(x_1,\dots,x_D\). Every path between \(x_i\) and \(x_j\) is tail-to-tail at \(\mathbf z\): the features are independent given the class but dependent marginally.

The Markov blanket pp. 382–383, Figure 8.26

What is the conditional distribution of one node given all the others? Using (8.5),

\[ p(x_i\given\mathbf{x}_{\{j\ne i\}})=\frac{p(x_1,\dots,x_D)}{\int p(x_1,\dots,x_D)\,\d x_i}=\frac{\prod_kp(x_k\given\pa_k)}{\int\prod_kp(x_k\given\pa_k)\,\d x_i}, \]

and every factor that does not contain \(x_i\) cancels.

Proof

The formula. A factor \(p(x_k\given\pa_k)\) contains \(x_i\) exactly when \(k=i\) or \(i\in\pa_k\) (i.e. \(k\in\mathrm{ch}_i\)). All other factors are constant in \(x_i\), can be taken out of the integral, and cancel between numerator and denominator. The remaining factors involve \(x_i\), \(\pa_i\), the children \(x_k\) and their parents \(\pa_k\), which are \(x_i\) and the co-parents.

D-separation (Exercise 8.9). Let \(C\) be the blanket and consider a path from \(i\) to a node \(u\) outside \(C\cup\{i\}\). (1) If it starts with \(j\to i\), \(j\) is a parent, in \(C\), and not head-to-head on the path (the link leaves \(j\) by its tail): blocked. (2) If it starts with \(i\to k\) and continues \(k\to\cdot\), then \(k\in C\) is head-to-tail: blocked. (3) If it starts \(i\to k\leftarrow j\), then \(j\) is a co-parent in \(C\); the path leaves \(j\) by a link that, at \(j\), meets \(j\to k\) tail-to-tail or head-to-tail, so it is blocked at \(j\) (\(j\ne u\) because \(u\notin C\)). Every path is blocked, so Result 8.9 gives \(x_i\indep\mathbf{x}_{\text{rest}}\given\mathbf{x}_C\).

Why the co-parents are needed. If a co-parent \(j\) (with common child \(k\)) is left out, the path \(i\to k\leftarrow j\) has an observed head-to-head node and is active; by Result 8.9(c) the dependence is present for generic tables. ∎

The Markov blanket is what Gibbs sampling needs (Chapter 11, Section 11.3): each update draws a node from the conditional above, which involves only a handful of factors.

8.3 Markov random fields

p. 383 A Markov random field (Markov network, undirected graphical model; Kindermann and Snell, 1980) has one node per variable or group of variables and undirected links. As for directed graphs, the graph specifies both a factorisation and a set of conditional independences; this time it is simpler to start with the independences.

8.3.1 Conditional independence properties

pp. 383–385 Removing the arrows removes the asymmetry between parents and children, and with it the head-to-head subtlety: in an undirected graph a path is blocked exactly when it passes through an observed node.

Proof

Global \(\Rightarrow\) local. Every path from \(i\) to a non-neighbour starts with a link to a neighbour, so \(\mathrm{ne}(i)\) separates \(i\) from all non-neighbours; apply (8.37).

Local \(\Rightarrow\) pairwise. If \(i\) and \(j\) are not linked, \(j\) is one of the non-neighbours, so \(x_i\indep(x_j,\mathbf{x}_R)\given\mathbf{x}_{\mathrm{ne}(i)}\), where \(R\) is the set of the other non-neighbours. Weak union (Result 8.6(c)) moves \(\mathbf{x}_R\) into the conditioning set: \(x_i\indep x_j\given\mathbf{x}_{\mathrm{ne}(i)\cup R}\), and \(\mathrm{ne}(i)\cup R\) is everything except \(i\) and \(j\). That is (8.38).

Positivity matters. Let \(x_1=x_2=x_3\) be the same fair bit, and take the graph with no links. Given any one variable the other two are constants, so every pairwise statement \(x_i\indep x_j\given x_k\) holds; but \(x_1\indep x_2\given\varnothing\) fails, so the global property fails. The distribution puts zero mass on six of the eight configurations. ∎

The book's Figure 8.27 shows three sets with every path from \(A\) to \(B\) passing through \(C\): then \(A\indep B\given C\) for every distribution of the graph; if some path avoids \(C\), there are distributions of the graph for which the independence fails. Compared with d-separation there is no explaining away.

8.3.2 Factorization properties

pp. 384–387 Which factorisation goes with separation? If \(x_i\) and \(x_j\) are not linked, (8.38) must hold, so no factor may contain both. This leads to cliques.

Restricting to maximal cliques loses nothing: a factor on a smaller clique can be multiplied into any maximal clique that contains it. The potentials need not be marginals or conditionals, which is why \(Z\) is needed (for a directed graph each factor is normalised and \(Z=1\) automatically). Computing \(Z\) for \(M\) discrete nodes with \(K\) states is a sum of \(K^M\) terms in the worst case. It is needed for learning the parameters of the potentials, but not for conditionals (a ratio of two marginals, in which \(Z\) cancels) nor for marginals of a few variables, which can be computed from the unnormalised product and normalised at the end (p. 386).

Proof

Let \(\widetilde A\) be the set of nodes outside \(C\) that can be reached from \(A\) by a path avoiding \(C\) (so \(A\subseteq\widetilde A\)), and \(\widetilde B\) the remaining nodes outside \(C\) (so \(B\subseteq\widetilde B\), by separation). There is no link between \(\widetilde A\) and \(\widetilde B\): such a link would make its endpoint in \(\widetilde B\) reachable from \(A\). A clique cannot contain a node of \(\widetilde A\) and a node of \(\widetilde B\), since these would have to be linked. So every factor is a function of \(\mathbf{x}_{\widetilde A\cup C}\) or of \(\mathbf{x}_{\widetilde B\cup C}\); grouping them, \(p\)\({}=g(\mathbf{x}_{\widetilde A},\mathbf{x}_C)\,h(\mathbf{x}_{\widetilde B},\mathbf{x}_C)\). By Result 8.6(a), \(\widetilde A\indep\widetilde B\given C\), and by decomposition (applied twice), \(A\indep B\given C\). ∎

The converse needs strictly positive potentials, and then the two descriptions coincide (p. 387).

Proof

(i)\(\Rightarrow\)(ii) is Result 8.12, and (ii)\(\Rightarrow\)(iii)\(\Rightarrow\)(iv) is Result 8.11. It remains to show (iv)\(\Rightarrow\)(i), the hard direction.

Möbius inversion. For functions \(\Phi,H\) on the subsets of a finite set \(V\): if \(H(S)\)\({}=\sum_{U\subseteq S}(-1)^{|S\setminus U|}\Phi(U)\) for all \(S\), then \(\Phi(S)=\sum_{U\subseteq S}H(U)\). Indeed,

\[ \sum_{U\subseteq S}H(U)=\sum_{U\subseteq S}\sum_{W\subseteq U}(-1)^{|U\setminus W|}\Phi(W)=\sum_{W\subseteq S}\Phi(W)\sum_{U:\,W\subseteq U\subseteq S}(-1)^{|U\setminus W|}=\sum_{W\subseteq S}\Phi(W)\,(1-1)^{|S\setminus W|}, \]

by the binomial theorem, and \((1-1)^n\) is 1 for \(n=0\) and 0 otherwise.

The canonical potentials. Fix a reference configuration \(\mathbf{x}^*\). For \(U\subseteq V\), let \((\mathbf{x}_U,\mathbf{x}^*_{V\setminus U})\) be the configuration that agrees with \(\mathbf{x}\) on \(U\) and with \(\mathbf{x}^*\) elsewhere, and define

\[ H_S(\mathbf{x}_S)=\sum_{U\subseteq S}(-1)^{|S\setminus U|}\ln p(\mathbf{x}_U,\mathbf{x}^*_{V\setminus U}), \]

which is finite (positivity) and depends on \(\mathbf{x}\) only through \(\mathbf{x}_S\). Möbius inversion with \(S=V\) gives \(\ln p(\mathbf{x})\)\({}=\sum_{S\subseteq V}H_S(\mathbf{x}_S)\).

Only cliques survive. Let \(S\) contain two nodes \(i,j\) that are not linked. Group the subsets \(U\subseteq S\) in fours, \(W\), \(W\cup\{i\}\), \(W\cup\{j\}\), \(W\cup\{i,j\}\) with \(W\subseteq S\setminus\{i,j\}\); their signs are \(+,-,-,+\) times \((-1)^{|S\setminus W|}\). Writing \(\mathbf z\) for the common values of all variables other than \(x_i,x_j\) in these four configurations, each group contributes \((-1)^{|S\setminus W|}\) times

\[ \ln\frac{p(x_i,x_j,\mathbf z)\;p(x_i^*,x_j^*,\mathbf z)}{p(x_i,x_j^*,\mathbf z)\;p(x_i^*,x_j,\mathbf z)}=\ln\frac{p(x_i\given\mathbf z)p(x_j\given\mathbf z)\;p(x_i^*\given\mathbf z)p(x_j^*\given\mathbf z)}{p(x_i\given\mathbf z)p(x_j^*\given\mathbf z)\;p(x_i^*\given\mathbf z)p(x_j\given\mathbf z)}=0, \]

using (8.38) in each term (the factors \(p(\mathbf z)\) cancel). Hence \(H_S\equiv0\) unless \(S\) is a clique (the empty set and single nodes count as cliques).

Assemble. \(p(\mathbf{x})\)\({}=\exp\{\sum_{S\text{ clique}}H_S(\mathbf{x}_S)\}\). Assign each clique to one maximal clique containing it and let \(\psi_C\) be the exponential of the sum of the \(H_S\) assigned to \(C\): this is (8.39) with positive potentials and \(Z=1\). ∎

p. 387 Strictly positive potentials can be written as exponentials,

\[ \psi_C(\mathbf{x}_C)=\exp\{-E(\mathbf{x}_C)\}, \tag{8.41} \]

where \(E(\mathbf{x}_C)\) is an energy function and \(p(\mathbf{x})\)\({}\propto\exp\{-\sum_CE(\mathbf{x}_C)\}\) is a Boltzmann distribution: energies add over cliques, and low total energy means high probability. (In statistical physics \(\exp\{-E/T\}\) with a temperature \(T\); here \(T=1\).) Unlike the conditionals of a directed graph, potentials have no probabilistic meaning, so one chooses them to say which local configurations are preferred; a configuration of high probability balances the possibly conflicting preferences of all cliques. The canonical potentials \(H_S\) above show that the decomposition into energies is not unique: one can move terms between a clique and its sub-cliques freely.

8.3.3 Illustration: Image de-noising

pp. 387–390 A binary image \(x_i\in\{-1,+1\}\), \(i=1,\dots,D\), is observed as \(y_i\in\{-1,+1\}\) after each pixel has been flipped independently with a small probability (Besag, 1974; Geman and Geman, 1984; Besag, 1986). Two kinds of knowledge help: \(y_i\) usually equals \(x_i\), and neighbouring \(x_i\) usually agree. The graph of the book's Figure 8.31 links each \(x_i\) to its observation \(y_i\) and to its four lattice neighbours; its cliques are pairs. Giving the pair \(\{x_i,y_i\}\) energy \(-\eta x_iy_i\), each neighbour pair \(\{x_i,x_j\}\) energy \(-\beta x_ix_j\) (\(\eta,\beta\gt0\)), and adding a bias \(hx_i\) per pixel gives the energy

\[ E(\mathbf{x},\mathbf{y})=h\sum_ix_i-\beta\sum_{\{i,j\}}x_ix_j-\eta\sum_ix_iy_i \tag{8.42} \]

(the middle sum over neighbouring pairs), and the joint distribution

\[ p(\mathbf{x},\mathbf{y})=\frac1Z\exp\{-E(\mathbf{x},\mathbf{y})\}. \tag{8.43} \]

Clamping \(\mathbf y\) to the observed image defines \(p(\mathbf{x}\given\mathbf{y})\), an Ising model; we want a configuration \(\mathbf{x}\) of high (ideally maximal) posterior probability.

Proof

The terms of (8.42) that contain \(x_j\) are \(hx_j\), \(-\beta x_jx_i\) for \(i\in\mathrm{ne}(j)\) and \(-\eta x_jy_j\); all other terms are the same for both values of \(x_j\) and cancel in the difference. Each of the three terms changes by its coefficient times \(+1-(-1)=2\), giving the formula. Choosing the value with lower energy (keeping the current value on a tie) can only lower \(E\) or leave it unchanged, and it lowers \(E\) strictly whenever \(x_j\) changes. There are finitely many configurations, so there can only be finitely many changes; once a full sweep changes nothing, no single flip lowers the energy: a local minimum of \(E\) (local maximum of \(p(\mathbf x\given\mathbf y)\)) with respect to single-pixel moves. It need not be the global minimum. ∎

With \(\beta=1\), \(\eta=2.1\), \(h=0\) (equal prior weight on both colours), ICM started from the noisy image gives the ICM restoration of Figure 8.30. With \(\beta=0\) the neighbours are disconnected and the most probable image is the noisy one (Exercise 8.14: with \(\beta=h=0\) the energy \(-\eta\sum_ix_iy_i\) is minimised term by term by \(x_i=y_i\)).

p. 390 The max-sum algorithm of Section 8.4.5 usually does better than ICM but is not exact on a lattice, which has loops. For this energy, however, the global maximum can be found exactly and efficiently by a minimum graph cut (Greig, Porteous and Seheult, 1989; Boykov, Veksler and Zabih, 2001; Kolmogorov and Zabih, 2004), as in the last panel of Figure 8.30.

8.3.4 Relation to directed graphs

pp. 390–393 For the directed chain of Figure 8.32(a),

\[ p(\mathbf{x})=p(x_1)\,p(x_2\given x_1)\,p(x_3\given x_2)\cdots p(x_N\given x_{N-1}), \tag{8.44} \]

and the undirected chain of Figure 8.32(b) has the maximal cliques \(\{x_{n-1},x_n\}\), so we want

\[ p(\mathbf{x})=\frac1Z\psi_{1,2}(x_1,x_2)\,\psi_{2,3}(x_2,x_3)\cdots\psi_{N-1,N}(x_{N-1},x_N). \tag{8.45} \]

Take \(\psi_{1,2}(x_1,x_2)=p(x_1)p(x_2\given x_1)\) and \(\psi_{n-1,n}(x_{n-1},x_n)=p(x_n\given x_{n-1})\) for \(n\ge3\); then \(Z=1\).

In general every conditional \(p(x_k\given\pa_k)\) must fit into some clique, so all parents of a node must be linked to each other. For the graph of Figure 8.33(a),

\[ p(\mathbf{x})=p(x_1)\,p(x_2)\,p(x_3)\,p(x_4\given x_1,x_2,x_3), \tag{8.46} \]

the factor \(p(x_4\given x_1,x_2,x_3)\) requires the clique \(\{x_1,x_2,x_3,x_4\}\): "marrying the parents" (moralisation) produces the fully connected moral graph of Figure 8.33(b), which displays none of the independences of (8.46) (for example \(x_1\indep x_2\given\varnothing\)).

Proof

Correctness. \(\{k\}\cup\pa_k\) is a clique of \(G^m\) (\(k\) is linked to each parent, and the parents to each other), so it lies in some maximal clique. The product of the potentials is the product of all conditionals, which is \(p\) and sums to one, so \(Z=1\). Result 8.12 gives the global Markov property.

Minimality. Suppose \(U\) misses a link \(i-j\) of \(G^m\). In \(G\), either \(i\) and \(j\) are linked, or they are parents of a common child \(k\). In the first case they are never d-separated; in the second the path \(i\to k\leftarrow j\) is active given all other nodes (its head-to-head node \(k\) is observed). Either way \(i\) and \(j\) are not d-separated by the set of all other nodes, so by Result 8.9(c) some \(p\in\mathcal{DF}(G)\) has \(x_i\nindep x_j\given\mathbf x_{\setminus\{i,j\}}\). But \(i\) and \(j\) are not linked in \(U\), so the pairwise property of \(U\), which follows from its global property (Result 8.11), requires that independence. Contradiction. ∎

Moralisation is the first step of the junction tree algorithm (Section 8.4.6). Going from undirected to directed graphs is rarer and harder because of the normalisation constraints. To compare what the two kinds of graph can express, the book uses the filter view again.

Proof

Adjacency. In a perfect map two nodes must be linked exactly when the distribution makes them dependent given every set of other variables. Undirected graphs: linked nodes are never separated, and non-linked nodes are separated by all the other nodes. Directed graphs: linked nodes are never d-separated, and if \(u\) precedes \(v\) in a topological order and they are not linked, \(\pa_v\) d-separates them (the claim in the proof of Result 8.9(b)).

(a) \(A\) and \(C\) are dependent given every subset of the other variables (nothing but \(A\indep B\) holds), and so are \(B\) and \(C\), so a perfect undirected map links \(A-C\) and \(B-C\). If it does not link \(A-B\), \(C\) separates them and the graph implies \(A\indep B\given C\), which \(p\) violates: not an I map. If it links \(A-B\), the graph is complete and shows no independence, but \(p\) has \(A\indep B\): not a D map.

(b) By the adjacency rule, a perfect DAG map has links exactly \(A-C\), \(C-B\), \(B-D\), \(D-A\). An acyclic orientation of a cycle cannot have all four links pointing the same way round, so at some node both cycle links point inwards. If this node is \(C\) (parents \(A\) and \(B\)), the path \(A\to C\leftarrow B\) is active given \(\{C,D\}\) (observed head-to-head node), so the DAG does not show \(A\indep B\given\{C,D\}\), which \(p\) satisfies: not a D map. If the node is \(D\), the same holds with \(D\) observed. If it is \(A\) or \(B\), the same argument applies to \(C\indep D\given\{A,B\}\). ∎

Graphs with both directed and undirected links (chain graphs; Lauritzen and Wermuth, 1989; Frydenberg, 1990) contain both classes, but there remain distributions without a perfect chain-graph map either (p. 393).

8.4 Inference in graphical models

pp. 393–394 Inference means computing the posterior distribution of some nodes when others are observed. The simplest case is Bayes' theorem itself (the book's Figure 8.37): with \(p(x,y)=p(x)p(y\given x)\) (graph \(x\to y\)) and \(y\) observed,

\[ p(y)=\sum_{x'}p(y\given x')\,p(x'), \tag{8.47} \] \[ p(x\given y)=\frac{p(y\given x)\,p(x)}{p(y)}, \tag{8.48} \]

so the same joint is now written \(p(y)p(x\given y)\), the graph \(y\to x\) with the arrow reversed. The rest of the section turns this into algorithms that pass local messages along the links of a graph. They are exact on trees; Chapters 10 and 11 deal with approximate inference.

8.4.1 Inference on a chain

pp. 394–398 Take the undirected chain of Figure 8.32(b) (a directed chain gives the same graph, with \(Z=1\)):

\[ p(\mathbf{x})=\frac1Z\psi_{1,2}(x_1,x_2)\,\psi_{2,3}(x_2,x_3)\cdots\psi_{N-1,N}(x_{N-1},x_N), \tag{8.49} \]

with \(N\) discrete nodes of \(K\) states, so each potential is a \(K\times K\) table and there are \((N-1)K^2\) numbers. The marginal of an interior node is

\[ p(x_n)=\sum_{x_1}\cdots\sum_{x_{n-1}}\sum_{x_{n+1}}\cdots\sum_{x_N}p(\mathbf{x}). \tag{8.50} \]

Done naively this needs the \(K^N\) values of the joint. Instead, notice that only \(\psi_{N-1,N}\) contains \(x_N\), so

\[ \sum_{x_N}\psi_{N-1,N}(x_{N-1},x_N) \tag{8.51} \]

can be done first, giving a function of \(x_{N-1}\), and so on from both ends:

\[ p(x_n)=\frac1Z\underbrace{\Bigg[\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\cdots\Big[\sum_{x_2}\psi_{2,3}(x_2,x_3)\Big[\sum_{x_1}\psi_{1,2}(x_1,x_2)\Big]\Big]\cdots\Bigg]}_{\mu_\alpha(x_n)}\;\underbrace{\Bigg[\sum_{x_{n+1}}\psi_{n,n+1}(x_n,x_{n+1})\cdots\Big[\sum_{x_N}\psi_{N-1,N}(x_{N-1},x_N)\Big]\cdots\Bigg]}_{\mu_\beta(x_n)}. \tag{8.52} \]

The only fact used is the distributive law

\[ ab+ac=a(b+c), \tag{8.53} \]

whose right side needs two operations instead of three. Hence

\[ p(x_n)=\frac1Z\,\mu_\alpha(x_n)\,\mu_\beta(x_n), \tag{8.54} \]

where the forward and backward messages satisfy

\[ \mu_\alpha(x_n)=\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\Big[\sum_{x_{n-2}}\cdots\Big]=\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\,\mu_\alpha(x_{n-1}), \tag{8.55} \] \[ \mu_\alpha(x_2)=\sum_{x_1}\psi_{1,2}(x_1,x_2), \tag{8.56} \] \[ \mu_\beta(x_n)=\sum_{x_{n+1}}\psi_{n,n+1}(x_n,x_{n+1})\Big[\sum_{x_{n+2}}\cdots\Big]=\sum_{x_{n+1}}\psi_{n,n+1}(x_n,x_{n+1})\,\mu_\beta(x_{n+1}). \tag{8.57} \]

Erratum. In some printings the indices and arguments of the potentials in (8.57) are ordered differently from (8.49) and the rest of the section; the form above, \(\psi_{n,n+1}(x_n,x_{n+1})\), is the corrected one.

Each message is a vector of \(K\) numbers and products of messages are taken elementwise. The outgoing message is the incoming one multiplied by the local potential and summed over the sending node's variable (the book's Figure 8.38). When the potentials come from a directed chain, these recursions are the Chapman-Kolmogorov equations of a Markov chain.

Proof

The messages. Define \(\mu_\alpha(x_n)\)\({}=\sum_{x_1,\dots,x_{n-1}}\prod_{m=1}^{n-1}\psi_{m,m+1}(x_m,x_{m+1})\) (the product of the potentials to the left of \(x_n\), summed over the variables to the left) and \(\mu_\beta(x_n)\)\({}=\sum_{x_{n+1},\dots,x_N}\prod_{m=n}^{N-1}\psi_{m,m+1}(x_m,x_{m+1})\). In the definition of \(\mu_\alpha(x_n)\) only the last factor \(\psi_{n-1,n}\) contains \(x_n\); pulling it out of the sums over \(x_1,\dots,x_{n-2}\) (distributive law) leaves exactly \(\mu_\alpha(x_{n-1})\): this is (8.55), and for \(n=2\) the empty product gives (8.56). The same argument from the right gives (8.57).

The marginal. In (8.50) the joint is \(\frac1Z\) times (left product, a function of \(x_1,\dots,x_n\)) times (right product, a function of \(x_n,\dots,x_N\)). With \(x_n\) fixed the two groups of summation variables are disjoint, so the sum of the product is the product of the sums (Result 8.19 below), which is (8.54). Summing (8.54) over \(x_n\) gives 1, hence \(Z=\sum_{x_n}\mu_\alpha\mu_\beta\), the same number at every \(n\). For (8.58) (Exercise 8.15) keep both \(x_{n-1}\) and \(x_n\) fixed: the joint splits into the left product up to \(x_{n-1}\), the single potential \(\psi_{n-1,n}\), and the right product from \(x_n\); summing the outer groups gives \(\mu_\alpha(x_{n-1})\psi_{n-1,n}\mu_\beta(x_n)/Z\).

Cost. One step of (8.55) computes \(K\) numbers, each a sum of \(K\) products: \(O(K^2)\). Reaching node \(n\) from both ends takes \(N-1\) steps: \(O(NK^2)\). Running the forward recursion from \(x_1\) to \(x_N\) and the backward one from \(x_N\) to \(x_1\) once, and storing all \(2(N-1)\) messages, gives every \(\mu_\alpha(x_n)\) and \(\mu_\beta(x_n)\), hence every marginal by (8.54) at \(O(K)\) extra cost each: \(O(NK^2)\) in total, twice the cost of one marginal. Repeating the single-marginal computation for each \(n\) would cost \(O(N^2K^2)\). Brute force evaluates \(K^N\) joint values of \(N-1\) factors each.

Directed chains. If \(\psi_{1,2}=p(x_1)p(x_2\given x_1)\) and \(\psi_{n-1,n}=p(x_n\given x_{n-1})\), then by induction \(\mu_\alpha(x_n)\)\({}=\sum_{x_{n-1}}p(x_n\given x_{n-1})p(x_{n-1})\)\({}=p(x_n)\) (Chapman-Kolmogorov) and \(\mu_\beta(x_n)\)\({}=\sum_{x_{n+1}}p(x_{n+1}\given x_n)\mu_\beta(x_{n+1})\)\({}=1\), so (8.54) holds with \(Z=1\).

Evidence. Observing \(x_m=\widehat x_m\) multiplies the joint by the indicator \(I(x_m,\widehat x_m)\), which can be absorbed into a potential containing \(x_m\). Every sum over \(x_m\) then has a single term. The recursions are unchanged, and the new normalising constant is \(Z\,p(\widehat x_m)\), so normalising (8.54) gives \(p(x_n\given\widehat x_m)\). ∎

Erratum. On p. 398 some printings give the cost of \(N\) separate runs as \(O(N^2M^2)\); it is \(O(N^2K^2)\).

The pairwise marginals (8.58) are exactly what the E step of EM needs when the potentials have parameters; Chapter 13 uses this for hidden Markov models (forward-backward algorithm). Exercises 8.16 and 8.17 treat an observed end node.

8.4.2 Trees

pp. 398–399 Message passing extends from chains to trees.

Moralising a directed tree adds no links (no node has two parents), so it becomes an undirected tree; conversely an undirected tree can be directed away from any chosen root (Exercise 8.18). Moralising a polytree marries co-parents and creates loops; the factor graph of the next section keeps it a tree.

8.4.3 Factor graphs

pp. 399–402 Both kinds of graph express a product of factors; a factor graph (Frey, 1998; Kschischang, Frey and Loeliger, 2001) draws the factors themselves. Write

\[ p(\mathbf{x})=\prod_{s}f_s(\mathbf{x}_s), \tag{8.59} \]

where each \(\mathbf{x}_s\) is a subset of the variables. The graph has a circle for each variable, a small square for each factor, and a link between \(f_s\) and every variable in \(\mathbf{x}_s\): it is bipartite (links only join nodes of opposite type). For example

\[ p(\mathbf{x})=f_a(x_1,x_2)\,f_b(x_1,x_2)\,f_c(x_2,x_3)\,f_d(x_3) \tag{8.60} \]

is drawn in Figure 8.40. Directed graphs are the special case where the factors are the conditionals \(p(x_k\given\pa_k)\), undirected graphs the case where they are clique potentials (with \(1/Z\) as a factor on the empty set). A factor graph can say more: in (8.60) the two factors on \((x_1,x_2)\), which an undirected graph would merge into one clique potential, stay separate.

Conversions (pp. 401–402). From an undirected graph: one factor node per maximal clique, with the clique potential as factor; other factor graphs give the same distribution if their factors multiply to the potentials (the book's Figure 8.41, whose caption should read \(f_b(x_2,x_3)\); see the errata). From a directed graph: one factor per conditional (Figure 8.42). A directed or undirected tree gives a tree factor graph; so does a polytree (Figure 8.43), and local cycles made by linked parents disappear inside a single factor (Figure 8.44). In the book's Figure 8.45, \(f_a(x_1,x_2)f_b(x_1,x_3)f_c(x_2,x_3)\) and \(f(x_1,x_2,x_3)\) have the same (complete) undirected graph, but the first restricts the distribution to pairwise interactions; it implies no conditional independence.

8.4.4 The sum-product algorithm

pp. 402–411 From now on the factor graph is a tree (it came from an undirected tree, a directed tree or a polytree) and the variables are discrete; for continuous variables sums become integrals, and for linear-Gaussian models the messages are Gaussians (the Kalman filter, Chapter 13). Belief propagation for directed graphs without loops (Pearl, 1988; Lauritzen and Spiegelhalter, 1988, for junction trees) is a special case. The goal is the marginal of a variable \(x\),

\[ p(x)=\sum_{\mathbf{x}\setminus x}p(\mathbf{x}), \tag{8.61} \]

and, with shared work, all the marginals at once. We assume first that nothing is observed and that \(p\) is normalised.

Proof

Components. If two neighbours \(u,u'\) of \(v\) were joined by a path avoiding \(v\), adding \(u-v-u'\) would close a loop. So different neighbours lie in different components. Every other node \(w\) is joined to \(v\) by a unique path, and the last node before \(v\) on it is the neighbour whose component contains \(w\).

Factors stay in their component. The variables of a factor \(f\) are its neighbours in the factor graph, so they lie in the component of \(f\), or are \(v\) itself.

(8.62), (8.65), (8.68). Apply this with \(v=x\): the factors split into groups, one per neighbouring factor \(f_s\), and the group of \(f_s\) depends only on \(x\) and \(X_s\). Then apply it inside the component of \(f_s\) with \(v=f_s\): removing \(f_s\) leaves one sub-component per variable \(x_m\), whose factors multiply to \(G_m(x_m,X_{sm})\). Finally apply it inside the sub-component of \(x_m\) with \(v=x_m\). ∎

Proof

Induction on \(m\). For \(m=2\), \(\sum_{X_1}\sum_{X_2}g_1(X_1)g_2(X_2)\)\({}=\sum_{X_1}g_1(X_1)\big[\sum_{X_2}g_2(X_2)\big]\) by (8.53), because \(g_1(X_1)\) is constant in the inner sum; the bracket is constant in the outer sum and comes out too. For the maximum use (8.90), \(\max(ab,ac)=a\max(b,c)\) for \(a\ge0\), in the same way: \(\max_{X_2}g_1(X_1)g_2(X_2)\)\({}=g_1(X_1)\max_{X_2}g_2(X_2)\) since \(g_1\ge0\), then the outer maximum of \(g_1(X_1)\) times a nonnegative constant is that constant times \(\max g_1\). The step from \(m-1\) to \(m\) groups \(X_1,\dots,X_{m-1}\) into one set. ∎

In words: a factor node multiplies its factor by the incoming messages on all other links and sums out every variable except the recipient (8.66); a variable node multiplies the incoming messages on all other links (8.69), so a variable node with two neighbours just passes messages through. Every message is a function of the variable on its link. A node can send along a link once it has received messages on all its other links.

Proof

Sides of a link. Cutting the link between neighbours \(u\) and \(v\) splits the tree in two (Result 8.18); call the part containing \(u\) the side of the directed link \(u\to v\), and let \(d(u\to v)\) be its number of nodes. If \(w\ne v\) is another neighbour of \(u\), the side of \(w\to u\) is strictly contained in the side of \(u\to v\), so \(d(w\to u)\lt d(u\to v)\).

Exactness. By induction on \(d\). If \(d(u\to v)=1\), \(u\) is a leaf and its message (8.70) or (8.71) is the subtree sum by Filling the gap 8.12. Otherwise the message on \(u\to v\) is computed by (8.66) or (8.69) from the messages on the links \(w\to u\), \(w\ne v\), which have smaller sides and are exact by the induction hypothesis; the derivations of (8.66) and (8.69) then show that the result is the subtree sum (8.64) or (8.67) for the side of \(u\to v\). Every message, in particular each \(\mu_{f_s\to x}\) used in (8.63), is therefore exact, whatever the order in which messages were computed.

Feasibility. Send the messages in increasing order of \(d\). The messages needed for \(u\to v\) are those on links \(w\to u\) with smaller \(d\), already sent. The inward pass of Algorithm 8.4 sends every link pointing towards the root, the outward pass every link pointing away; within each pass a node sends only after receiving from all its other neighbours, which is a special case of this ordering argument. (The book's own induction, Exercise 8.20: a tree grows by adding leaves one at a time; a new leaf can send first in the inward pass and receive last in the outward pass, without disturbing the schedule of the smaller tree.)

Count and root. Each link carries one message each way, \(2\times\)(number of links) messages in total, the cost of about two single-marginal computations; running the single-marginal algorithm separately for each of \(n\) variables would cost of order \(n\) times more. By the exactness argument each message is determined by its link and direction alone, so the root plays no role. ∎

Cost. A message from a factor with \(M+1\) discrete variables of \(K\) states sums over \(K^M\) configurations for each of \(K\) values: \(O(K^{M+1})\), exponential in the size of the factor but not in the size of the graph. A message from a variable with \(d\) neighbours costs \(O(dK)\).

Proof

(8.72). Cut the tree at \(f_s\) (Result 8.18): one component per neighbour \(x_i\), with factor product \(G_i(x_i,X_{si})\), and \(p(\mathbf x)\)\({}=f_s(\mathbf x_s)\prod_iG_i(x_i,X_{si})\). With \(\mathbf x_s\) fixed, sum over the disjoint sets \(X_{si}\) (Result 8.19): \(p(\mathbf x_s)\)\({}=f_s(\mathbf x_s)\prod_i\sum_{X_{si}}G_i\), and each sum is \(\mu_{x_i\to f_s}(x_i)\) by (8.67).

The identity. From (8.63) and (8.69), \(p(x)\)\({}=\mu_{f_s\to x}(x)\prod_{t\in\mathrm{ne}(x)\setminus f_s}\mu_{f_t\to x}(x)\)\({}=\mu_{f_s\to x}(x)\,\mu_{x\to f_s}(x)\). ∎

Substituting (8.69) into (8.66) eliminates the variable-to-factor messages: each factor multiplies the messages from the factors beyond its variables, multiplies by its own factor and sums (the book's Figure 8.50).

A worked example pp. 408–410, (8.73)–(8.86), Figures 8.51, 8.52

The factor graph of Figure 8.51 has the unnormalised joint

\[ \widetilde p(\mathbf{x})=f_a(x_1,x_2)\,f_b(x_2,x_3)\,f_c(x_2,x_4). \tag{8.73} \]

With \(x_3\) as root, \(x_1\) and \(x_4\) are leaves, and the inward pass sends

\[ \mu_{x_1\to f_a}(x_1)=1, \tag{8.74} \] \[ \mu_{f_a\to x_2}(x_2)=\sum_{x_1}f_a(x_1,x_2), \tag{8.75} \] \[ \mu_{x_4\to f_c}(x_4)=1, \tag{8.76} \] \[ \mu_{f_c\to x_2}(x_2)=\sum_{x_4}f_c(x_2,x_4), \tag{8.77} \] \[ \mu_{x_2\to f_b}(x_2)=\mu_{f_a\to x_2}(x_2)\,\mu_{f_c\to x_2}(x_2), \tag{8.78} \] \[ \mu_{f_b\to x_3}(x_3)=\sum_{x_2}f_b(x_2,x_3)\,\mu_{x_2\to f_b}(x_2); \tag{8.79} \]

the outward pass sends

\[ \mu_{x_3\to f_b}(x_3)=1, \tag{8.80} \] \[ \mu_{f_b\to x_2}(x_2)=\sum_{x_3}f_b(x_2,x_3), \tag{8.81} \] \[ \mu_{x_2\to f_a}(x_2)=\mu_{f_b\to x_2}(x_2)\,\mu_{f_c\to x_2}(x_2), \tag{8.82} \] \[ \mu_{f_a\to x_1}(x_1)=\sum_{x_2}f_a(x_1,x_2)\,\mu_{x_2\to f_a}(x_2), \tag{8.83} \] \[ \mu_{x_2\to f_c}(x_2)=\mu_{f_a\to x_2}(x_2)\,\mu_{f_b\to x_2}(x_2), \tag{8.84} \] \[ \mu_{f_c\to x_4}(x_4)=\sum_{x_2}f_c(x_2,x_4)\,\mu_{x_2\to f_c}(x_2). \tag{8.85} \]

Erratum. Some printings end (8.79) with "\(\mu_{x_2\to f_b}.\)" without the argument; it is \(\mu_{x_2\to f_b}(x_2)\).

The check on \(x_2\) is

\[ \widetilde p(x_2)=\mu_{f_a\to x_2}(x_2)\,\mu_{f_b\to x_2}(x_2)\,\mu_{f_c\to x_2}(x_2)=\Big[\sum_{x_1}f_a(x_1,x_2)\Big]\Big[\sum_{x_3}f_b(x_2,x_3)\Big]\Big[\sum_{x_4}f_c(x_2,x_4)\Big]=\sum_{x_1}\sum_{x_3}\sum_{x_4}\widetilde p(\mathbf{x}). \tag{8.86} \]

Erratum. In some printings the middle summation of the second line of (8.86) runs over \(x_2\); it is over \(x_3\).

Nothing above used discreteness: for continuous variables the sums are integrals (p. 410), and for linear-Gaussian models every message is a Gaussian (Section 13.3).

8.4.5 The max-sum algorithm

pp. 411–415 Two other tasks are to find a configuration of highest probability and that probability:

\[ \mathbf{x}^{\max}=\argmax_{\mathbf{x}}p(\mathbf{x}), \tag{8.87} \] \[ p(\mathbf{x}^{\max})=\max_{\mathbf{x}}p(\mathbf{x}). \tag{8.88} \]

Maximising each marginal separately answers a different question. In the book's Table 8.1, \(p(x,y)\) is 0.3 at \((0,0)\), 0.4 at \((1,0)\), 0.3 at \((0,1)\) and 0 at \((1,1)\). The joint is largest at \((1,0)\) (0.4), but the marginals \(p(x=0)=0.6\), \(p(y=0)=0.7\) pick \((0,0)\), whose joint probability is 0.3; Exercise 8.27 makes it 0. The same happens in the worked example above: the marginals pick \(x_1=0\), \(x_2=1\), \(x_3=1\), \(x_4=0\) with \(\widetilde p=9\), while the maximum is \(\widetilde p=18\) at \((1,1,1,0)\) (computed below).

To compute the maximum, write it as nested maximisations,

\[ \max_{\mathbf{x}}p(\mathbf{x})=\max_{x_1}\cdots\max_{x_M}p(\mathbf{x}), \tag{8.89} \]

and use the distributive law for the maximum,

\[ \max(ab,ac)=a\max(b,c)\qquad(a\ge0), \tag{8.90} \]

which holds because multiplying by \(a\ge0\) preserves order (for \(a\lt0\) it would reverse it; factors of graphical models are nonnegative). For the chain (8.49),

\[ \max_{\mathbf x}p(\mathbf x)=\frac1Z\max_{x_1}\cdots\max_{x_N}\big[\psi_{1,2}(x_1,x_2)\cdots\psi_{N-1,N}(x_{N-1},x_N)\big]=\frac1Z\max_{x_1}\Big[\max_{x_2}\Big[\psi_{1,2}(x_1,x_2)\Big[\cdots\max_{x_N}\psi_{N-1,N}(x_{N-1},x_N)\Big]\cdots\Big]\Big], \]

a backward pass of messages from \(x_N\) to \(x_1\).

Erratum. In some printings the second line of this unnumbered display (p. 412) is misprinted; the corrected form, given in the errata, is the one above.

Products of many probabilities underflow, so one works with logarithms. The logarithm is increasing, so

\[ \ln\Big(\max_{\mathbf{x}}p(\mathbf{x})\Big)=\max_{\mathbf{x}}\ln p(\mathbf{x}), \tag{8.91} \]

and the distributive law becomes

\[ \max(a+b,a+c)=a+\max(b,c), \tag{8.92} \]

now with no sign condition. Replacing sums by maxima and products by sums of logarithms in (8.66), (8.69), (8.70), (8.71) and (8.63) gives the max-sum messages

\[ \mu_{f\to x}(x)=\max_{x_1,\dots,x_M}\Big[\ln f(x,x_1,\dots,x_M)+\sum_{m\in\mathrm{ne}(f)\setminus x}\mu_{x_m\to f}(x_m)\Big], \tag{8.93} \] \[ \mu_{x\to f}(x)=\sum_{l\in\mathrm{ne}(x)\setminus f}\mu_{f_l\to x}(x), \tag{8.94} \]

with leaf messages

\[ \mu_{x\to f}(x)=0, \tag{8.95} \] \[ \mu_{f\to x}(x)=\ln f(x), \tag{8.96} \]

and, at the root,

\[ p^{\max}=\max_{x}\Big[\sum_{s\in\mathrm{ne}(x)}\mu_{f_s\to x}(x)\Big], \tag{8.97} \] \[ x^{\max}=\argmax_{x}\Big[\sum_{s\in\mathrm{ne}(x)}\mu_{f_s\to x}(x)\Big]. \tag{8.98} \]

Erratum. Some printings write \(\mathrm{ne}(f_s)\) under the sum in (8.93); it is \(\mathrm{ne}(f)\). Note also that (8.97) gives \(\ln p^{\max}\) (or \(\ln\) of the unnormalised maximum), not \(p^{\max}\) itself.

Recovering the configuration. It is tempting to send max-sum messages back out from the root and apply (8.98) at every node. If the maximiser is unique this works: the max-marginal of \(x_i\) equals \(\max p\) at \(x_i^{\max}\) and is strictly smaller elsewhere. With ties it can fail: if \(p\) is uniform on \(\{(0,0),(1,1)\}\), both max-marginals are flat, and choosing each variable's maximiser independently may return \((0,1)\), of probability zero. The cure is to remember, during the inward pass, which arguments achieved each maximum, and to trace them back (pp. 413–415). For a chain with root \(x_N\), the inward messages are

\[ \mu_{x_n\to f_{n,n+1}}(x_n)=\mu_{f_{n-1,n}\to x_n}(x_n),\qquad \mu_{f_{n-1,n}\to x_n}(x_n)=\max_{x_{n-1}}\big[\ln f_{n-1,n}(x_{n-1},x_n)+\mu_{x_{n-1}\to f_{n-1,n}}(x_{n-1})\big], \]

starting from

\[ \mu_{x_1\to f_{1,2}}(x_1)=0, \tag{8.99} \]

then

\[ x_N^{\max}=\argmax_{x_N}\big[\mu_{f_{N-1,N}\to x_N}(x_N)\big], \tag{8.100} \] \[ \phi(x_n)=\argmax_{x_{n-1}}\big[\ln f_{n-1,n}(x_{n-1},x_n)+\mu_{x_{n-1}\to f_{n-1,n}}(x_{n-1})\big], \tag{8.101} \] \[ x_{n-1}^{\max}=\phi(x_n^{\max}). \tag{8.102} \]

Erratum. In the unnumbered equation before (8.99) and in (8.101), some printings write \(\mu_{x_{n-1}\to f_{n-1,n}}(x_n)\); the argument is \(x_{n-1}\), as above.

Proof

Write \(m_n(x_n)=\mu_{f_{n-1,n}\to x_n}(x_n)\) and \(m_1\equiv0\). By (8.92) and induction, \(m_n(x_n)\)\({}=\max_{x_1,\dots,x_{n-1}}\sum_{k=1}^{n-1}\ln f_{k,k+1}(x_k,x_{k+1})\): the best log-score of the first \(n\) variables ending in state \(x_n\). Claim: for the back-tracked configuration, \(\sum_{k\lt n}\ln f_{k,k+1}(x_k^{\max},x_{k+1}^{\max})\)\({}=m_n(x_n^{\max})\) for every \(n\). For \(n=1\) both sides are 0. If it holds for \(n-1\), then by (8.101)–(8.102) \(x_{n-1}^{\max}=\phi(x_n^{\max})\) attains the maximum defining \(m_n(x_n^{\max})\), so \(m_n(x_n^{\max})\)\({}=\ln f_{n-1,n}(x_{n-1}^{\max},x_n^{\max})\)\({}+m_{n-1}(x_{n-1}^{\max})\), which is the claim for \(n\). At \(n=N\), \(m_N(x_N^{\max})\)\({}=\max_{x_N}m_N\)\({}=\max_{\mathbf x}\ln\widetilde p(\mathbf x)\) by (8.100). Ties never hurt, because each choice is consistent with the stored predecessor of the value actually chosen. On a tree the same induction runs over the subtrees, from the root outwards. ∎

ICM versus max-sum (p. 415). ICM passes a single value per update, max-sum a whole vector of \(K\) values per message. ICM is cheaper but may stop at a local optimum even on a tree; max-sum with back-tracking is exact on every tree.

8.4.6 Exact inference in general graphs

pp. 416–417 For graphs with loops the junction tree algorithm (Lauritzen and Spiegelhalter, 1988; Jordan, 2007) groups variables until the graph becomes a tree of clusters, and then runs sum-product on that tree.

Errata (p. 416). The text should read "A–C–B–D–A is chord-less and so a link should be added", "join tree" should be "junction tree", and the sentence beginning "If the tree is condensed" should be omitted.

8.4.7 Loopy belief propagation

pp. 417–418 When exact inference is too expensive, one may simply run the local updates (8.66), (8.69) on a graph with loops: loopy belief propagation (Frey and MacKay, 1998). Every message is initialised to the unit function, so every node can send at once. A flooding schedule sends all messages simultaneously at each step; a serial schedule one at a time. Following Kschischang et al. (2001), a node \(a\) has a message pending on its link to \(b\) if \(a\) has received a message on another link since it last sent to \(b\); only pending messages need to be sent, because any other message would repeat the previous one. After stopping, approximate marginals are the products (8.63) and (8.72) of the latest messages.

Proof

(a) Use the sides of links from Result 8.20 and induct on \(d(u\to v)\) to show that only finitely many messages are ever sent along \(u\to v\). If \(d(u\to v)=1\), \(u\) is a leaf with no other links, so after its first message it never receives anything that makes \(u\to v\) pending again. Otherwise, \(u\to v\) becomes pending only when \(u\) receives on some link \(w\to u\) with \(w\ne v\); by induction there are finitely many such receipts, and each makes at most one later message along \(u\to v\). Hence finitely many messages in total, and the schedule stops. When it stops nothing is pending, so the last message on each \(u\to v\) was computed after the last messages arrived on all the other links into \(u\), from those final messages. Induction on \(d\) again shows that the final messages are the exact ones (as in Result 8.20).

(b) Let \(n_1-n_2-\dots-n_k-n_1\) be a cycle, indices mod \(k\). Suppose that at some moment nothing is pending. Let \(s_i\) be the time at which \(n_i\) last sent to \(n_{i+1}\) (initial unit messages count as sent at time 0). Node \(n_i\) last received from \(n_{i-1}\) at time \(s_{i-1}\). Since \(n_i\) has nothing pending towards \(n_{i+1}\), it sent to \(n_{i+1}\) strictly after that receipt (a message sent in the same step could not use it): \(s_i\gt s_{i-1}\). Going round the cycle gives \(s_1\gt s_k\gt\dots\gt s_2\gt s_1\), a contradiction. ∎

So on loopy graphs one stops when the messages stop changing (or after a fixed number of steps). Convergence is not guaranteed, and the result is approximate even when it converges. Its fixed points are the stationary points of the Bethe free energy (Yedidia, Freeman and Weiss, 2005), and for a single loop the error can be analysed exactly (Weiss, 2000). Some state-of-the-art decoders of error-correcting codes are loopy belief propagation: turbo codes (Berrou et al., 1993; McEliece, MacKay and Cheng, 1998) and low-density parity-check codes (Gallager, 1962; MacKay and Neal, 1996; MacKay, 1999).

8.4.8 Learning the graph structure

p. 418 So far the graph was given. To learn it from data (Friedman and Koller, 2003) we need a space of structures and a score. A Bayesian puts a prior \(p(m)\) on graphs \(m\) and uses

\[ p(m\given\mathcal D)\propto p(m)\,p(\mathcal D\given m), \tag{8.103} \]

where the model evidence \(p(\mathcal D\given m)\) scores each structure; ideally predictions average over the posterior. Two difficulties: the evidence requires integrating over parameters (and latent variables), and the number of structures is enormous.

Proof

A source is a node without parents; every non-empty DAG has one (Result 8.1). Fix a set \(S\) of \(k\) nodes. The DAGs in which every node of \(S\) is a source are obtained, each exactly once, by choosing any DAG on the other \(n-k\) nodes (\(a(n-k)\) ways) and any set of links from \(S\) to the other nodes (\(2^{k(n-k)}\) ways); there are no links into \(S\), and links leaving sources cannot create cycles. By inclusion-exclusion over the set of sources, the number of DAGs with at least one source is \(\sum_{\varnothing\ne S}(-1)^{|S|+1}2^{|S|(n-|S|)}a(n-|S|)\), which is the formula after grouping the \(\binom nk\) sets of each size; and it equals \(a(n)\) since every DAG has a source. The values were computed from the recursion. Since \(a(n)\ge2^{n(n-1)/2}\) (every graph whose links all point from lower to higher labels is acyclic), \(\ln a(n)\) grows at least like \(n^2\). ∎

Exhaustive search is hopeless beyond a handful of nodes, and finding the highest-scoring DAG is NP-hard in general (Chickering, 1996); in practice one uses greedy local search, search over node orderings, or Markov chain Monte Carlo over structures (Friedman and Koller, 2003). Distinct DAGs can encode the same independences (for example \(a\to c\to b\), \(a\leftarrow c\leftarrow b\) and \(a\leftarrow c\to b\) all say exactly \(a\indep b\given c\)); data alone cannot distinguish them, and only the head-to-head structure \(a\to c\leftarrow b\) is identified.

Exercises

All 29 exercises of Chapter 8 (Bishop, 2006, pp. 418–422), restated in my own words, with complete solutions (hidden). Stars give the book's difficulty and "www" marks the exercises with official solutions. Several solutions are compact versions of the results above, which are linked for more detail.

1. Exercise 8.1 (★, www). By marginalising the variables in turn, show that (8.5) is normalised whenever each conditional distribution is.

   Solution

   Number the nodes topologically. The last node \(x_K\) has no children, so it appears only in \(p(x_K\given\pa_K)\), and \(\sum_{x_K}\prod_kp(x_k\given\pa_k)\)\({}=\prod_{k\lt K}p(x_k\given\pa_k)\cdot\sum_{x_K}p(x_K\given\pa_K)\)\({}=\prod_{k\lt K}p(x_k\given\pa_k)\). The remaining product has the same form on \(K-1\) nodes. After \(K-1\) steps we are left with \(\sum_{x_1}p(x_1)=1\). Details, and why the factors are then the conditionals of the joint: Result 8.2.

2. Exercise 8.2 (★, www). Show that if the nodes can be numbered so that no link goes to a lower-numbered node, the graph has no directed cycles.

   Solution

   Along a directed cycle \(k_1\to k_2\to\dots\to k_m\to k_1\) the numbers would strictly increase at every step and still return to \(k_1\): impossible. The converse (every DAG has such a numbering) is also proved in Result 8.1.

3. Exercise 8.3 (★★). For the joint distribution of Table 8.2 over binary \(a,b,c\), show that \(p(a,b)\ne p(a)p(b)\) but \(p(a,b\given c)=p(a\given c)p(b\given c)\) for \(c=0\) and \(c=1\).

   Solution

   Table 8.2: \(p(a,b,c)\) for \(abc=000,001,010,011,100,101,110,111\) is 0.192, 0.144, 0.048, 0.216, 0.192, 0.064, 0.048, 0.096.

   Marginally dependent. \(p(a{=}0)=0.6\), \(p(b{=}0)\)\({}=0.192+0.144+0.192+0.064\)\({}=0.592\), and \(p(a{=}0,b{=}0)=0.336\ne0.6\cdot0.592=0.3552\).

   Independent given \(c\). \(p(c{=}0)=0.48\): \(p(a,b\given c{=}0)\) is \(0.4,0.1,0.4,0.1\) for \(ab=00,01,10,11\), with \(p(a{=}0\given c{=}0)=0.5\) and \(p(b{=}0\given c{=}0)=0.8\); the products \(0.5\cdot0.8=0.4\), \(0.5\cdot0.2=0.1\), \(0.4\), \(0.1\) agree. \(p(c{=}1)=0.52\): \(p(a,b\given c{=}1)\) is \(\frac{0.144}{0.52},\frac{0.216}{0.52},\frac{0.064}{0.52},\frac{0.096}{0.52}\)\({}=\frac{18}{65},\frac{27}{65},\frac{8}{65},\frac{12}{65}\), with \(p(a{=}0\given c{=}1)=\frac{9}{13}\) and \(p(b{=}0\given c{=}1)=0.4=\frac25\); the products \(\frac9{13}\cdot\frac25=\frac{18}{65}\), \(\frac9{13}\cdot\frac35=\frac{27}{65}\), \(\frac4{13}\cdot\frac25=\frac8{65}\), \(\frac4{13}\cdot\frac35=\frac{12}{65}\) agree.

4. Exercise 8.4 (★★). For Table 8.2, compute \(p(a)\), \(p(b\given c)\) and \(p(c\given a)\), show that \(p(a,b,c)=p(a)p(c\given a)p(b\given c)\), and draw the graph.

   Solution

   \(p(a)=(0.6,0.4)\). \(p(c\given a)\): for \(a=0\), \(p(c{=}0)=(0.192+0.048)/0.6=0.4\), \(p(c{=}1)=0.6\); for \(a=1\), \(p(c{=}0)=(0.192+0.048)/0.4=0.6\), \(p(c{=}1)=0.4\). \(p(b\given c)\): for \(c=0\), \(p(b{=}0)=(0.192+0.192)/0.48=0.8\); for \(c=1\), \(p(b{=}0)=(0.144+0.064)/0.52=0.4\). Check all eight products, e.g. \(p(0,0,0)=0.6\cdot0.4\cdot0.8=0.192\), \(p(0,1,1)=0.6\cdot0.6\cdot0.6=0.216\), \(p(1,0,1)=0.4\cdot0.4\cdot0.4=0.064\), \(p(1,1,1)=0.4\cdot0.4\cdot0.6=0.096\) (all eight agree exactly). The graph is the head-to-tail chain \(a\to c\to b\), consistent with Exercise 8.3 (Result 8.7).

5. Exercise 8.5 (★, www). Draw the directed graphical model of the relevance vector machine, (7.79)–(7.80).

   Solution

   The model is \(p(\mathbf t\given\mathbf X,\mathbf w,\beta)\)\({}=\prod_{n=1}^{N}\N(t_n\given\mathbf w^\T\bm\phi(\mathbf x_n),\beta^{-1})\) and \(p(\mathbf w\given\bm\alpha)\)\({}=\prod_{i=1}^{M}\N(w_i\given0,\alpha_i^{-1})\). (In some printings (7.79) has \(\beta^{-1}\) in the conditioning set; the parameter is \(\beta\). This does not affect the graph.) Each weight \(w_i\) has its own precision \(\alpha_i\) (plate over \(i\)); each target \(t_n\) depends on all weights, on its input \(\mathbf x_n\) and on \(\beta\) (plate over \(n\)); \(\mathbf x_n\), \(\alpha_i\) and \(\beta\) are parameters (solid dots) and \(t_n\) is observed.

6. Exercise 8.6 (★). The noisy-OR conditional (Pearl, 1988) is

   \[ p(y=1\given x_1,\dots,x_M)=1-(1-\mu_0)\prod_{i=1}^{M}(1-\mu_i)^{x_i}, \tag{8.104} \]

   with \(0\le\mu_i\le1\) for \(i=0,\dots,M\). Show that it is a soft version of the logical OR, and discuss the interpretation of the \(\mu_i\).

   Solution

   A generative story. Let each active parent (\(x_i=1\)) independently switch \(y\) on with probability \(\mu_i\), and let a "leak" switch it on with probability \(\mu_0\) whatever the parents: \(z_0\sim\Bern(\mu_0)\), \(z_i\sim\Bern(\mu_ix_i)\), \(y=z_0\lor z_1\lor\dots\lor z_M\). Then \(y=0\) only if every \(z_i\) is 0, so \(p(y=0\given\mathbf x)\)\({}=(1-\mu_0)\prod_i(1-\mu_ix_i)\)\({}=(1-\mu_0)\prod_i(1-\mu_i)^{x_i}\) (for \(x_i\in\{0,1\}\)), which is (8.104).

   Soft OR. With \(\mu_0=0\) and all \(\mu_i=1\), \(p(y=1\given\mathbf x)\) is 0 if all \(x_i=0\) and 1 otherwise: the logical OR. In general \(p(y=1)\) increases with every additional active parent, as for an OR, but no single parent is decisive.

   Interpretation. \(\mu_i\) (\(i\ge1\)) is the probability that cause \(i\) on its own produces the effect, \(p(y=1\given x_i=1,\text{others }0)\) when \(\mu_0=0\); \(1-\mu_i\) is the probability that it is "inhibited". \(\mu_0\) is the probability of the effect when no listed cause is present (unmodelled causes). The table needs \(M+1\) parameters instead of \(2^M\), like (8.10) but with a different restriction: causes act independently through the probability of failure, so \(\ln p(y=0\given\mathbf x)\) is additive in the parents.

7. Exercise 8.7 (★★). Use (8.15) and (8.16) to derive the mean (8.17) and covariance (8.18) of the graph of Figure 8.14.

   Solution

   (8.15) gives \(\mu_1=b_1\), \(\mu_2=b_2+w_{21}b_1\), \(\mu_3=b_3+w_{32}\mu_2\). (8.16) for \(i\le j\), row by row: \(\Sigma_{11}=v_1\), \(\Sigma_{12}=w_{21}v_1\), \(\Sigma_{22}=w_{21}\Sigma_{12}+v_2\), \(\Sigma_{13}=w_{32}\Sigma_{12}\), \(\Sigma_{23}=w_{32}\Sigma_{22}\), \(\Sigma_{33}=w_{32}\Sigma_{23}+v_3\); the rest by symmetry. The full calculation, the warning that (8.16) holds only for \(i\le j\), and the precision matrix are in Filling the gap 8.5 and Result 8.5.

8. Exercise 8.8 (★, www). Show that \(a\indep b,c\given d\) implies \(a\indep b\given d\).

   Solution

   \(p(a,b,c\given d)=p(a\given d)p(b,c\given d)\) for every \(d\) with \(p(d)\gt0\). Summing over \(c\): \(p(a,b\given d)=p(a\given d)p(b\given d)\). See Result 8.6(b).

9. Exercise 8.9 (★, www). Use d-separation to show that a node is independent of all other nodes given its Markov blanket.

   Solution

   A path leaving \(x_i\) starts either through a parent (which is in the blanket and not head-to-head on the path: blocked), or through a child \(k\). If it continues from \(k\) to a child of \(k\), \(k\) is observed and head-to-tail: blocked. If it continues from \(k\) to another parent \(j\) of \(k\) (a co-parent, in the blanket), \(k\) is head-to-head and observed, so not blocked there, but \(j\) is observed and not head-to-head on the path (the link \(j\to k\) leaves \(j\) by its tail): blocked. So every path is blocked and Result 8.9 applies. Full version: Result 8.10.

10. Exercise 8.10 (★). In the graph of Figure 8.54 (\(a\to c\leftarrow b\), \(c\to d\)), show that \(a\indep b\given\varnothing\), and that in general \(a\nindep b\given d\).

    Solution

    Summing \(p(a)p(b)p(c\given a,b)p(d\given c)\) over \(d\) and then \(c\) gives \(p(a)p(b)\). Given \(d\), \(p(a,b\given d)\)\({}\propto p(a)p(b)\sum_cp(c\given a,b)p(d\given c)\), which need not factorise; with \(c=a\oplus b\) and \(d\) a 90%-reliable copy of \(c\), \(p(a=1,b=1\given d=0)\)\({}=0.45\)\({}\ne0.25\)\({}=p(a=1\given d=0)p(b=1\given d=0)\). See Result 8.8.

11. Exercise 8.11 (★★). In the fuel system of Figure 8.21, a driver reads the gauge and reports \(D\), with

    \[ p(D=1\given G=1)=0.9, \tag{8.105} \] \[ p(D=0\given G=0)=0.9. \tag{8.106} \]

    Given the report \(D=0\), find the probability that the tank is empty; then add the observation \(B=0\). Explain, and relate to Figure 8.54.

    Solution

    From Filling the gap 8.6, \(p(G=0)=0.315\) and \(p(G=0\given F=0)=0.81\). Sum over \(G\): \(p(D=0)=0.9\cdot0.315+0.1\cdot0.685=0.352\), \(p(D=0\given F=0)\)\({}=0.9\cdot0.81+0.1\cdot0.19\)\({}=0.748\), so

    \[ p(F=0\given D=0)=\frac{0.748\cdot0.1}{0.352}=\frac{17}{80}=0.2125. \]

    With the battery flat: \(p(D=0\given B=0,F=0)\)\({}=0.9\cdot0.9+0.1\cdot0.1\)\({}=0.82\) and \(p(D=0\given B=0,F=1)\)\({}=0.9\cdot0.8+0.1\cdot0.2\)\({}=0.74\); as in (8.33) \(p(B=0)\) cancels and

    \[ p(F=0\given D=0,B=0)=\frac{0.82\cdot0.1}{0.82\cdot0.1+0.74\cdot0.9}=\frac{0.082}{0.748}=\frac{41}{374}\approx0.110. \]

    The second value is lower: the flat battery explains away the "empty" report. This is Figure 8.54 with \(a=B\), \(b=F\), \(c=G\), \(d=D\): observing a descendant of the head-to-head node \(G\) makes \(B\) and \(F\) dependent (Result 8.8). Both probabilities are closer to the prior 0.1 than the values 0.257 and 0.111 obtained from the gauge itself, because the report is a noisy version of the gauge. (Exact rational arithmetic.)

12. Exercise 8.12 (★, www). Show that there are \(2^{M(M-1)/2}\) distinct undirected graphs on \(M\) labelled nodes, and draw the 8 for \(M=3\).

    Solution

    A graph is determined by which of the \(\binom M2=M(M-1)/2\) possible links are present (each unordered pair counted once), and each can be present or absent independently: \(2^{M(M-1)/2}\) graphs. For \(M=3\), with nodes \(1,2,3\): the empty graph; three graphs with one link (\(1-2\), \(1-3\) or \(2-3\)); three paths with two links (centred at 1, 2 or 3); and the triangle. Compare the number of DAGs in Result 8.24 (25 for \(M=3\)).

13. Exercise 8.13 (★). For ICM on the energy (8.42), write the energy difference between the two states of \(x_j\) with all other variables fixed, and show that it depends only on quantities local to \(x_j\).

    Solution

    Only \(hx_j\), \(-\beta x_j\sum_{i\in\mathrm{ne}(j)}x_i\) and \(-\eta x_jy_j\) involve \(x_j\), so \(E(x_j{=}{+}1)-E(x_j{=}{-}1)\)\({}=2h-2\beta\sum_{i\in\mathrm{ne}(j)}x_i-2\eta y_j\): it involves only the lattice neighbours of \(j\) and \(y_j\), i.e. the Markov blanket of \(x_j\). See Result 8.14.

    ▶ See it in a demo: ICM sweeps and the energy trace

14. Exercise 8.14 (★). With \(\beta=h=0\) in (8.42), show that the most probable \(\mathbf x\) is \(\mathbf x=\mathbf y\).

    Solution

    Then \(E=-\eta\sum_ix_iy_i\) is a sum of terms each involving one \(x_i\), so it is minimised term by term: \(-\eta x_iy_i\) is \(-\eta\) for \(x_i=y_i\) and \(+\eta\) otherwise, and \(\eta\gt0\). Hence \(x_i=y_i\) for all \(i\) is the unique minimiser of the energy, i.e. the unique maximiser of \(p(\mathbf x\given\mathbf y)\propto e^{-E}\). Without coupling, each pixel only sees its own observation.

    ▶ See it in a demo: no coupling, nothing restored

15. Exercise 8.15 (★★, www). Show that the joint distribution of two neighbouring nodes of the chain of Figure 8.38 is (8.58).

    Solution

    Sum the joint (8.49) over all variables except \(x_{n-1},x_n\). With these two fixed, the product splits into the potentials left of \(x_{n-1}\), the single potential \(\psi_{n-1,n}(x_{n-1},x_n)\), and the potentials right of \(x_n\); the left group involves the summation variables \(x_1,\dots,x_{n-2}\) only, the right group \(x_{n+1},\dots,x_N\) only. The sum of the product is the product of the sums (Result 8.19): \(\mu_\alpha(x_{n-1})\,\psi_{n-1,n}(x_{n-1},x_n)\,\mu_\beta(x_n)/Z\). See Result 8.17.

16. Exercise 8.16 (★★). Show how the chain algorithm of Section 8.4.1 computes \(p(x_n\given\widehat x_N)\) for all \(n\lt N\), and which messages change.

    Solution

    Clamp \(x_N=\widehat x_N\) by multiplying \(\psi_{N-1,N}\) by \(I(x_N,\widehat x_N)\). The forward messages \(\mu_\alpha(x_n)\), \(n\le N-1\), do not involve \(x_N\) and are unchanged. Every backward message changes: it starts from \(\mu_\beta(x_{N-1})\)\({}=\psi_{N-1,N}(x_{N-1},\widehat x_N)\) (the sum over \(x_N\) has one term) and then follows (8.57). Then \(p(x_n\given\widehat x_N)\)\({}=\mu_\alpha(x_n)\mu_\beta(x_n)/Z'\) with \(Z'\)\({}=\sum_{x_n}\mu_\alpha(x_n)\mu_\beta(x_n)\)\({}=Z\,p(\widehat x_N)\), the same for every \(n\). Cost: one new backward sweep, \(O(NK^2)\). For a directed chain the new backward messages are \(\mu_\beta(x_n)=p(\widehat x_N\given x_n)\) (Chapman-Kolmogorov backwards), so the formula is Bayes' theorem \(p(x_n\given\widehat x_N)\)\({}\propto p(x_n)p(\widehat x_N\given x_n)\).

    ▶ See it in a demo: observed variables and normalisation

17. Exercise 8.17 (★★). In the chain of Figure 8.38 with \(N=5\) and \(x_3,x_5\) observed, show by d-separation that \(x_2\indep x_5\given x_3\), and that the message-passing value of \(p(x_2\given x_3,x_5)\) does not depend on \(x_5\).

    Solution

    Separation. The only path from \(x_2\) to \(x_5\) passes through \(x_3\), which is observed (head-to-tail in the directed chain; any observed node blocks a path in the undirected chain). So \(x_2\indep x_5\given x_3\).

    Messages. With \(x_3,x_5\) clamped, \(\mu_\beta(x_4)=\psi_{4,5}(x_4,\widehat x_5)\), \(\mu_\beta(x_3)\)\({}=\sum_{x_4}\psi_{3,4}(x_3,x_4)\mu_\beta(x_4)\), evaluated only at \(x_3=\widehat x_3\), and \(\mu_\beta(x_2)\)\({}=\sum_{x_3}\psi_{2,3}(x_2,x_3)I(x_3,\widehat x_3)\mu_\beta(x_3)\)\({}=\psi_{2,3}(x_2,\widehat x_3)\,c(\widehat x_3,\widehat x_5)\), where the scalar \(c=\mu_\beta(\widehat x_3)\) is the only place \(\widehat x_5\) enters. Hence

    \[ p(x_2\given\widehat x_3,\widehat x_5)=\frac{\mu_\alpha(x_2)\,\psi_{2,3}(x_2,\widehat x_3)\,c}{\sum_{x_2'}\mu_\alpha(x_2')\,\psi_{2,3}(x_2',\widehat x_3)\,c}, \]

    and \(c\) cancels.

18. Exercise 8.18 (★★, www). Show that a directed-tree distribution can be written over the corresponding undirected tree, and that an undirected-tree distribution can be written, by normalising the potentials, as a directed tree. How many directed trees correspond to one undirected tree?

    Solution

    Directed to undirected. Each non-root node has one parent, so (8.5) is \(p(x_r)\prod_{k\ne r}p(x_k\given x_{\pa(k)})\), a product of functions of linked pairs. Take \(\psi_{\pa(k),k}=p(x_k\given x_{\pa(k)})\) and multiply \(p(x_r)\) into one potential containing the root, exactly as in (8.44)–(8.45). Then \(Z=1\). Moralisation adds nothing (no co-parents).

    Undirected to directed. Let \(p\propto\prod_{\text{links}}\psi_{ij}\), pick a root \(r\) and direct every link away from it. Remove leaves one at a time: for a leaf \(l\) with neighbour \(u\), set \(p(x_l\given x_u)=\psi_{ul}(x_u,x_l)/m(x_u)\) with \(m(x_u)=\sum_{x_l}\psi_{ul}(x_u,x_l)\), and multiply \(m(x_u)\) into another potential containing \(u\) (or keep it as a factor on \(u\) alone). The product is unchanged. When only \(r\) is left, its remaining factor, normalised, is \(p(x_r)\), and its normaliser is \(Z\). Now \(p=p(x_r)\prod_kp(x_k\given x_{\pa(k)})\), and these are the true conditionals by Result 8.2. (This is the inward pass of sum-product towards \(r\). If some \(m(x_u)=0\), that value of \(x_u\) has probability zero and \(p(x_l\given x_u)\) may be chosen arbitrarily.)

    Counting. In a directed tree the path from the root to any node follows the arrows (go back through the unique parents; this must end at the root), so the root determines every orientation. Each of the \(N\) nodes can be the root: \(N\) directed trees, all representing the same family of distributions.

19. Exercise 8.19 (★★). Apply the sum-product algorithm to the chain of Section 8.4.1 and recover (8.54), (8.55) and (8.57).

    Solution

    The factor graph of (8.49) has factors \(f_{n-1,n}=\psi_{n-1,n}\) (put \(1/Z\) aside) and variable nodes with two neighbours (one for the end nodes). The leaf \(x_1\) sends \(\mu_{x_1\to f_{1,2}}=1\) (8.70). A variable with two neighbours forwards what it receives (8.69): \(\mu_{x_{n-1}\to f_{n-1,n}}\)\({}=\mu_{f_{n-2,n-1}\to x_{n-1}}\). By (8.66),

    \[ \mu_{f_{n-1,n}\to x_n}(x_n)=\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\,\mu_{f_{n-2,n-1}\to x_{n-1}}(x_{n-1}). \]

    Writing \(\mu_\alpha(x_n)=\mu_{f_{n-1,n}\to x_n}(x_n)\) this is (8.55), and for \(n=2\) it is (8.56). In the same way \(\mu_\beta(x_n)=\mu_{f_{n,n+1}\to x_n}(x_n)\) satisfies (8.57) starting from \(\mu_{x_N\to f_{N-1,N}}=1\). Node \(x_n\) has the two neighbours \(f_{n-1,n}\), \(f_{n,n+1}\), so (8.63) gives \(\widetilde p(x_n)=\mu_\alpha(x_n)\mu_\beta(x_n)\), which is (8.54) after normalising.

    ▶ See it in a demo: forward and backward messages on a chain

20. Exercise 8.20 (★, www). Show by induction that, on a tree, the messages can be ordered (leaves to root, then root to leaves) so that every node has all the incoming messages it needs when it sends.

    Solution

    Induction on the number of nodes. A single node sends nothing. A tree with \(n+1\) nodes is a tree with \(n\) nodes plus a leaf \(l\) attached to a node \(u\) (remove any leaf). Inward pass: let \(l\) send first (it needs nothing), then follow the schedule of the smaller tree, in which \(u\) now also has \(l\)'s message before it sends towards the root. Outward pass: follow the smaller tree's schedule; when \(u\) has received from the root side it has everything needed to send to \(l\) last. A shorter argument orders the messages by the size of the sender's side of the link (Result 8.20).

21. Exercise 8.21 (★★, www). Show that the marginal over the variables \(\mathbf x_s\) of a factor \(f_s(\mathbf x_s)\) can be found after sum-product by (8.72).

    Solution

    Cut the tree at \(f_s\): \(p(\mathbf x)\)\({}=f_s(\mathbf x_s)\prod_{i\in\mathrm{ne}(f_s)}G_i(x_i,X_{si})\) with disjoint \(X_{si}\) (Result 8.18). Summing over all variables not in \(\mathbf x_s\), the sum of the product is the product of the sums (Result 8.19), and \(\sum_{X_{si}}G_i=\mu_{x_i\to f_s}(x_i)\) by (8.67); after both passes of sum-product all these messages are available. Hence (8.72). (Erratum: the exercise should refer to \(f_s(\mathbf x_s)\), not \(f_x(\mathbf x_s)\).) See Result 8.21.

22. Exercise 8.22 (★). In a tree-structured factor graph, let a subset \(S\) of the variables be connected through factor nodes. Show how to use sum-product to compute \(p(\mathbf x_S)\).

    Solution

    Let \(\mathcal F_S\) be the factors linked to at least two variables of \(S\). The nodes \(S\cup\mathcal F_S\) form a subtree (connected by assumption, loop-free because the whole graph is a tree). Cut every link leaving this subtree; each cut link leads into its own component (Result 8.18). Two kinds of cut link occur: \(x\in S\) to a factor \(g\notin\mathcal F_S\), whose component sums to \(\mu_{g\to x}(x)\); and \(f\in\mathcal F_S\) to a variable \(y\notin S\), whose component sums to \(\mu_{y\to f}(y)\). Each such \(y\) belongs to a single factor of the subtree, so its sum can be done locally:

    \[ p(\mathbf x_S)\propto\prod_{f\in\mathcal F_S}\Big[\sum_{\mathbf y_f}f(\mathbf x_f)\prod_{y\in\mathrm{ne}(f)\setminus S}\mu_{y\to f}(y)\Big]\prod_{x\in S}\ \prod_{g\in\mathrm{ne}(x)\setminus\mathcal F_S}\mu_{g\to x}(x), \]

    where \(\mathbf y_f\) are the variables of \(f\) outside \(S\). All messages come from one standard two-pass run; normalise at the end. For \(S=\{x\}\) this is (8.63), and for \(S=\mathbf x_s\) it is (8.72).

23. Exercise 8.23 (★★, www). Show that \(p(x_i)\) equals the product of the incoming and outgoing messages on any one link at \(x_i\).

    Solution

    By (8.63) and (8.69), \(p(x_i)\)\({}=\mu_{f_s\to x_i}(x_i)\prod_{t\in\mathrm{ne}(x_i)\setminus f_s}\mu_{f_t\to x_i}(x_i)\)\({}=\mu_{f_s\to x_i}(x_i)\,\mu_{x_i\to f_s}(x_i)\) for any \(f_s\in\mathrm{ne}(x_i)\). See Result 8.21.

24. Exercise 8.24 (★★). Show that, after sum-product on a tree, the marginal of the variables of a factor is (8.72).

    Solution

    This is Exercise 8.21 again. Another way to see it: the messages \(\mu_{x_i\to f_s}\) arriving at \(f_s\) are, by (8.67), the sums over everything beyond \(x_i\); the factor \(f_s\) is the only remaining piece of the joint. Multiplying them and not summing anything gives the joint of \(\mathbf x_s\) with everything else summed out. Numerical check on Figure 8.51: Filling the gap 8.14.

25. Exercise 8.25 (★★). For the graph of Figure 8.51 with root \(x_3\), check that the marginals of \(x_1\) and \(x_3\) are correct, and that (8.72) gives the correct \(p(x_1,x_2)\).

    Solution

    Using (8.83), (8.82), (8.81), (8.77):

    \[ \widetilde p(x_1)=\mu_{f_a\to x_1}(x_1)=\sum_{x_2}f_a(x_1,x_2)\,\mu_{f_b\to x_2}(x_2)\,\mu_{f_c\to x_2}(x_2)=\sum_{x_2}f_a(x_1,x_2)\sum_{x_3}f_b(x_2,x_3)\sum_{x_4}f_c(x_2,x_4)=\sum_{x_2,x_3,x_4}\widetilde p(\mathbf x). \]

    Using (8.79), (8.78), (8.75), (8.77):

    \[ \widetilde p(x_3)=\mu_{f_b\to x_3}(x_3)=\sum_{x_2}f_b(x_2,x_3)\,\mu_{f_a\to x_2}(x_2)\,\mu_{f_c\to x_2}(x_2)=\sum_{x_2}f_b(x_2,x_3)\sum_{x_1}f_a(x_1,x_2)\sum_{x_4}f_c(x_2,x_4)=\sum_{x_1,x_2,x_4}\widetilde p(\mathbf x). \]

    And by (8.72), with (8.74) and (8.82):

    \[ f_a(x_1,x_2)\,\mu_{x_1\to f_a}(x_1)\,\mu_{x_2\to f_a}(x_2)=f_a(x_1,x_2)\cdot1\cdot\sum_{x_3}f_b(x_2,x_3)\sum_{x_4}f_c(x_2,x_4)=\sum_{x_3,x_4}\widetilde p(\mathbf x). \]

    With numbers: Filling the gap 8.14 (\(\widetilde p(x_1)=(43,41)\), \(\widetilde p(x_3)=(36,48)\), \(\widetilde p(x_1,x_2)\) as computed there, all matching enumeration).

    ▶ See it in a demo: sum-product on Figure 8.51

26. Exercise 8.26 (★). Describe how to obtain \(p(x_a,x_b)\) for two variables that share no factor, by clamping one of them in turn to each of its values.

    Solution

    For each value \(k\) of \(x_a\): clamp \(x_a=k\) (an indicator factor), run sum-product, and read off the unnormalised marginal at \(x_b\), which is \(\widetilde p(x_b,x_a=k)=Z\,p(x_a=k,x_b)\) (Filling the gap 8.13). Doing this for all \(K_a\) values gives the whole table up to the constant \(Z\), which is its total sum (or comes from an unclamped run). Only the messages on the path from \(x_a\) towards \(x_b\) change with \(k\), so each extra run costs only that path. Equivalently, \(p(x_a,x_b)=p(x_a)\,p(x_b\given x_a)\), with \(p(x_b\given x_a=k)\) from the clamped run.

27. Exercise 8.27 (★★). Construct \(p(x,y)\) on \(\{0,1,2\}^2\) such that the maximisers \(\widehat x\) of \(p(x)\) and \(\widehat y\) of \(p(y)\) satisfy \(p(\widehat x,\widehat y)=0\).

    Solution

    Take (rows \(x=0,1,2\), columns \(y=0,1,2\))

    \[ p(x,y)=\begin{pmatrix}0&0.2&0.2\\0.2&0.05&0.05\\0.2&0.05&0.05\end{pmatrix}. \]

    It sums to 1. The marginals are \(p(x)=(0.4,0.3,0.3)\) and \(p(y)=(0.4,0.3,0.3)\), so \(\widehat x=\widehat y=0\), but \(p(0,0)=0\). The joint maximum is 0.2, attained at four configurations. The idea: put no mass on \((0,0)\) and give row 0 and column 0 more total mass than any other row or column, spread over cells that avoid \((0,0)\).

28. Exercise 8.28 (★★, www). Show that on a factor graph with a cycle there is always at least one pending message, however long the algorithm runs.

    Solution

    If nothing were pending, then around a cycle \(n_1-\dots-n_k-n_1\) each node \(n_i\) would have sent to \(n_{i+1}\) strictly after it last received from \(n_{i-1}\), i.e. \(s_i\gt s_{i-1}\) for the last sending times \(s_i\); going round the cycle gives \(s_1\gt s_1\). See Result 8.23(b). (The official solution's argument, that each message along the cycle creates a pending message on the next link, is the same idea.)

    ▶ See it in a demo: loopy belief propagation on a cycle

29. Exercise 8.29 (★★, www). Show that on a tree, after finitely many messages, nothing is pending.

    Solution

    Induct on the size of the sender's side of a link: a leaf sends at most once (it never receives on other links), and a link \(u\to v\) becomes pending only when \(u\) receives on one of its other links, which have smaller sides and, by induction, carry finitely many messages. So finitely many messages are sent in total, after which nothing is pending, and the final messages are the exact ones. See Result 8.23(a).

Demonstrations for this chapter

Each demonstration runs in the browser, with seeded random numbers so that a class sees the same pictures, and links back to these notes. The ▶ Demo boxes above open them already set to the case under discussion.

The Python code that draws every figure of this page, and checks the chapter's numbers (fuel gauge, sum-product and max-sum against enumeration, ICM and graph cuts), is code/ch08_graphical_models.py (see the code index).

References

1. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer, New York. Chapter 8, pp. 359–422 (and the official errata).
2. Berrou, C., Glavieux, A. and Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: turbo-codes. In Proceedings of ICC '93, IEEE International Conference on Communications, Vol. 2, 1064–1070. doi:10.1109/ICC.1993.397441.
3. Besag, J. (1974). Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society: Series B, 36(2), 192–225. doi:10.1111/j.2517-6161.1974.tb00999.x.
4. Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society: Series B, 48(3), 259–279. doi:10.1111/j.2517-6161.1986.tb01412.x.
5. Bodlaender, H. L. (1993). A tourist guide through treewidth. Acta Cybernetica, 11(1–2), 1–21.
6. Boykov, Y., Veksler, O. and Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11), 1222–1239. doi:10.1109/34.969114.
7. Chickering, D. M. (1996). Learning Bayesian networks is NP-complete. In D. Fisher and H.-J. Lenz (eds), Learning from Data: Artificial Intelligence and Statistics V, Lecture Notes in Statistics 112, 121–130. Springer. doi:10.1007/978-1-4612-2404-4_12.
8. Clifford, P. (1990). Markov random fields in statistics. In G. R. Grimmett and D. J. A. Welsh (eds), Disorder in Physical Systems: A Volume in Honour of John M. Hammersley, 19–32. Oxford University Press.
9. Cooper, G. F. (1990). The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42(2–3), 393–405. doi:10.1016/0004-3702(90)90060-D.
10. Cooper, G. F. and Herskovits, E. (1992). A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9(4), 309–347. doi:10.1007/BF00994110.
11. Cowell, R. G., Dawid, A. P., Lauritzen, S. L. and Spiegelhalter, D. J. (1999). Probabilistic Networks and Expert Systems. Springer, New York. doi:10.1007/b97670.
12. Dawid, A. P. (1979). Conditional independence in statistical theory. Journal of the Royal Statistical Society: Series B, 41(1), 1–15. doi:10.1111/j.2517-6161.1979.tb01052.x.
13. Dawid, A. P. (1980). Conditional independence for statistical operations. The Annals of Statistics, 8(3), 598–617. doi:10.1214/aos/1176345011.
14. Frey, B. J. (1998). Graphical Models for Machine Learning and Digital Communication. MIT Press, Cambridge, MA. doi:10.7551/mitpress/3348.001.0001.
15. Frey, B. J. and MacKay, D. J. C. (1998). A revolution: belief propagation in graphs with cycles. In M. I. Jordan, M. J. Kearns and S. A. Solla (eds), Advances in Neural Information Processing Systems, Vol. 10, 479–485. MIT Press.
16. Friedman, N. and Koller, D. (2003). Being Bayesian about network structure: a Bayesian approach to structure discovery in Bayesian networks. Machine Learning, 50(1–2), 95–125. doi:10.1023/A:1020249912095.
17. Frydenberg, M. (1990). The chain graph Markov property. Scandinavian Journal of Statistics, 17(4), 333–353.
18. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21–28. doi:10.1109/TIT.1962.1057683.
19. Geiger, D., Verma, T. and Pearl, J. (1990). Identifying independence in Bayesian networks. Networks, 20(5), 507–534. doi:10.1002/net.3230200504.
20. Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6(6), 721–741. doi:10.1109/TPAMI.1984.4767596.
21. Greig, D. M., Porteous, B. T. and Seheult, A. H. (1989). Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society: Series B, 51(2), 271–279. doi:10.1111/j.2517-6161.1989.tb01764.x.
22. Heckerman, D., Geiger, D. and Chickering, D. M. (1995). Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 20(3), 197–243. doi:10.1007/BF00994016.
23. Jordan, M. I. (2007). An Introduction to Probabilistic Graphical Models. In preparation (cited by Bishop).
24. Kindermann, R. and Snell, J. L. (1980). Markov Random Fields and Their Applications. Contemporary Mathematics 1. American Mathematical Society, Providence, RI. doi:10.1090/conm/001.
25. Kittler, J. and Föglein, J. (1984). Contextual classification of multispectral pixel data. Image and Vision Computing, 2(1), 13–29. doi:10.1016/0262-8856(84)90040-4.
26. Koller, D. and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA.
27. Kolmogorov, V. and Zabih, R. (2004). What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), 147–159. doi:10.1109/TPAMI.2004.1262177.
28. Kschischang, F. R., Frey, B. J. and Loeliger, H.-A. (2001). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2), 498–519. doi:10.1109/18.910572.
29. Lauritzen, S. L. (1996). Graphical Models. Oxford University Press. doi:10.1093/oso/9780198522195.001.0001.
30. Lauritzen, S. L., Dawid, A. P., Larsen, B. N. and Leimer, H.-G. (1990). Independence properties of directed Markov fields. Networks, 20(5), 491–505. doi:10.1002/net.3230200503.
31. 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–194. doi:10.1111/j.2517-6161.1988.tb01721.x.
32. Lauritzen, S. L. and Wermuth, N. (1989). Graphical models for associations between variables, some of which are qualitative and some quantitative. The Annals of Statistics, 17(1), 31–57. doi:10.1214/aos/1176347003.
33. MacKay, D. J. C. (1999). Good error-correcting codes based on very sparse matrices. IEEE Transactions on Information Theory, 45(2), 399–431. doi:10.1109/18.748992. (Bishop lists it as MacKay and Neal, 1999.)
34. MacKay, D. J. C. and Neal, R. M. (1996). Near Shannon limit performance of low density parity check codes. Electronics Letters, 32(18), 1645–1646. doi:10.1049/el:19961141.
35. McEliece, R. J., MacKay, D. J. C. and Cheng, J.-F. (1998). Turbo decoding as an instance of Pearl's "belief propagation" algorithm. IEEE Journal on Selected Areas in Communications, 16(2), 140–152. doi:10.1109/49.661103.
36. Meek, C. (1995). Strong completeness and faithfulness in Bayesian networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, 411–418. Morgan Kaufmann.
37. Moussouris, J. (1974). Gibbs and Markov random systems with constraints. Journal of Statistical Physics, 10(1), 11–33. doi:10.1007/BF01011714.
38. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA. doi:10.1016/C2009-0-27609-4.
39. Robinson, R. W. (1973). Counting labeled acyclic digraphs. In F. Harary (ed.), New Directions in the Theory of Graphs, 239–273. Academic Press, New York.
40. Roweis, S. and Ghahramani, Z. (1999). A unifying review of linear Gaussian models. Neural Computation, 11(2), 305–345. doi:10.1162/089976699300016674.
41. Weiss, Y. (2000). Correctness of local probability propagation in graphical models with loops. Neural Computation, 12(1), 1–41. doi:10.1162/089976600300015880.
42. Yedidia, J. S., Freeman, W. T. and Weiss, Y. (2005). Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory, 51(7), 2282–2312. doi:10.1109/TIT.2005.850085.

DOIs were checked against Crossref; works without a DOI on Crossref are listed without one. The numerical statements made in the text (fuel-gauge and driver probabilities in exact rational arithmetic, the sum-product and max-sum example against enumeration, loopy belief propagation on a four-cycle, the Moussouris example, the linear-Gaussian matrices, the DAG counts) come from short Python computations written for these notes; the figures come from the course code.