Pattern Recognition and Machine Learning

8.4. Inference in Graphical Models 401

x 1 x 2

x 3

(a)

x 1 x 2

x 3

f

(b)

x 1 x 2

x 3

fc

fa fb

(c)

Figure 8.42 (a) A directed graph with the factorizationp(x 1 )p(x 2 )p(x 3 |x 1 ,x 2 ). (b) A factor graph representing
the same distribution as the directed graph, whose factor satisfiesf(x 1 ,x 2 ,x 3 )=p(x 1 )p(x 2 )p(x 3 |x 1 ,x 2 ). (c)
A different factor graph representing the same distribution with factorsfa(x 1 )=p(x 1 ),fb(x 2 )=p(x 2 )and
fc(x 1 ,x 2 ,x 3 )=p(x 3 |x 1 ,x 2 ).

Factor graphs are said to bebipartitebecause they consist of two distinct kinds

of nodes, and all links go between nodes of opposite type. In general, factor graphs

can therefore always be drawn as two rows of nodes (variable nodes at the top and

factor nodes at the bottom) with links between the rows, as shown in the example in

Figure 8.40. In some situations, however, other ways of laying out the graph may

be more intuitive, for example when the factor graph is derived from a directed or

undirected graph, as we shall see.

If we are given a distribution that is expressed in terms of an undirected graph,

then we can readily convert it to a factor graph. To do this, we create variable nodes

corresponding to the nodes in the original undirected graph, and then create addi-

tional factor nodes corresponding to the maximal cliquesxs. The factorsfs(xs)are

then set equal to the clique potentials. Note that there may be several different factor

graphs that correspond to the same undirected graph. These concepts are illustrated

in Figure 8.41.

Similarly, to convert a directed graph to a factor graph, we simply create variable

nodes in the factor graph corresponding to the nodes of the directed graph, and then

create factor nodes corresponding to the conditional distributions, and then finally

add the appropriate links. Again, there can be multiple factor graphs all of which

correspond to the same directed graph. The conversion of a directed graph to a

factor graph is illustrated in Figure 8.42.

We have already noted the importance of tree-structured graphs for performing

efficient inference. If we take a directed or undirected tree and convert it into a factor

graph, then the result will again be a tree (in other words, the factor graph will have

no loops, and there will be one and only one path connecting any two nodes). In

the case of a directed polytree, conversion to an undirected graph results in loops

due to the moralization step, whereas conversion to a factor graph again results in a

tree, as illustrated in Figure 8.43. In fact, local cycles in a directed graph due to

links connecting parents of a node can be removed on conversion to a factor graph

by defining the appropriate factor function, as shown in Figure 8.44.

We have seen that multiple different factor graphs can represent the same di-

rected or undirected graph. This allows factor graphs to be more specific about the