Bishop C.M. Pattern Recognition and Machine Learning (2006) (811375), страница 94
Текст из файла (страница 94)
(c)A different factor graph representing the same distribution with factors fa (x1 ) = p(x1 ), fb (x2 ) = p(x2 ) andfc (x1 , x2 , x3 ) = p(x3 |x1 , x2 ).Factor graphs are said to be bipartite because they consist of two distinct kindsof nodes, and all links go between nodes of opposite type. In general, factor graphscan therefore always be drawn as two rows of nodes (variable nodes at the top andfactor nodes at the bottom) with links between the rows, as shown in the example inFigure 8.40.
In some situations, however, other ways of laying out the graph maybe more intuitive, for example when the factor graph is derived from a directed orundirected 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 nodescorresponding to the nodes in the original undirected graph, and then create additional factor nodes corresponding to the maximal cliques xs . The factors fs (xs ) arethen set equal to the clique potentials.
Note that there may be several different factorgraphs that correspond to the same undirected graph. These concepts are illustratedin Figure 8.41.Similarly, to convert a directed graph to a factor graph, we simply create variablenodes in the factor graph corresponding to the nodes of the directed graph, and thencreate factor nodes corresponding to the conditional distributions, and then finallyadd the appropriate links.
Again, there can be multiple factor graphs all of whichcorrespond to the same directed graph. The conversion of a directed graph to afactor graph is illustrated in Figure 8.42.We have already noted the importance of tree-structured graphs for performingefficient inference. If we take a directed or undirected tree and convert it into a factorgraph, then the result will again be a tree (in other words, the factor graph will haveno loops, and there will be one and only one path connecting any two nodes). Inthe case of a directed polytree, conversion to an undirected graph results in loopsdue to the moralization step, whereas conversion to a factor graph again results in atree, as illustrated in Figure 8.43.
In fact, local cycles in a directed graph due tolinks connecting parents of a node can be removed on conversion to a factor graphby defining the appropriate factor function, as shown in Figure 8.44.We have seen that multiple different factor graphs can represent the same directed or undirected graph. This allows factor graphs to be more specific about the4028. GRAPHICAL MODELS(a)(b)(c)Figure 8.43 (a) A directed polytree. (b) The result of converting the polytree into an undirected graph showingthe creation of loops. (c) The result of converting the polytree into a factor graph, which retains the tree structure.precise form of the factorization. Figure 8.45 shows an example of a fully connectedundirected graph along with two different factor graphs.
In (b), the joint distribution is given by a general form p(x) = f (x1 , x2 , x3 ), whereas in (c), it is givenby the more specific factorization p(x) = fa (x1 , x2 )fb (x1 , x3 )fc (x2 , x3 ). It shouldbe emphasized that the factorization in (c) does not correspond to any conditionalindependence properties.8.4.4 The sum-product algorithmSection 13.3Figure 8.44We shall now make use of the factor graph framework to derive a powerful classof efficient, exact inference algorithms that are applicable to tree-structured graphs.Here we shall focus on the problem of evaluating local marginals over nodes orsubsets of nodes, which will lead us to the sum-product algorithm. Later we shallmodify the technique to allow the most probable state to be found, giving rise to themax-sum algorithm.Also we shall suppose that all of the variables in the model are discrete, andso marginalization corresponds to performing sums.
The framework, however, isequally applicable to linear-Gaussian models in which case marginalization involvesintegration, and we shall consider an example of this in detail when we discuss lineardynamical systems.(a) A fragment of a directed graph having a local cycle. (b) Conversionto a fragment of a factorgraph having a tree structure, in which f (x1 , x2 , x3 ) =p(x1 )p(x2 |x1 )p(x3 |x1 , x2 ).x1x2x1x2f (x1 , x2 , x3 )x3(a)x3(b)4038.4.
Inference in Graphical Modelsx1x2x1x2x1f (x1 , x2 , x3 )x3(a)x2fafbfcx3x3(b)(c)Figure 8.45 (a) A fully connected undirected graph. (b) and (c) Two factor graphs each of which correspondsto the undirected graph in (a).There is an algorithm for exact inference on directed graphs without loops knownas belief propagation (Pearl, 1988; Lauritzen and Spiegelhalter, 1988), and is equivalent to a special case of the sum-product algorithm. Here we shall consider only thesum-product algorithm because it is simpler to derive and to apply, as well as beingmore general.We shall assume that the original graph is an undirected tree or a directed tree orpolytree, so that the corresponding factor graph has a tree structure.
We first convertthe original graph into a factor graph so that we can deal with both directed andundirected models using the same framework. Our goal is to exploit the structure ofthe graph to achieve two things: (i) to obtain an efficient, exact inference algorithmfor finding marginals; (ii) in situations where several marginals are required to allowcomputations to be shared efficiently.We begin by considering the problem of finding the marginal p(x) for particular variable node x.
For the moment, we shall suppose that all of the variablesare hidden. Later we shall see how to modify the algorithm to incorporate evidencecorresponding to observed variables. By definition, the marginal is obtained by summing the joint distribution over all variables except x so thatp(x)(8.61)p(x) =x\xwhere x \ x denotes the set of variables in x with variable x omitted.
The idea isto substitute for p(x) using the factor graph expression (8.59) and then interchangesummations and products in order to obtain an efficient algorithm. Consider thefragment of graph shown in Figure 8.46 in which we see that the tree structure ofthe graph allows us to partition the factors in the joint distribution into groups, withone group associated with each of the factor nodes that is a neighbour of the variablenode x. We see that the joint distribution can be written as a product of the formFs (x, Xs )(8.62)p(x) =s∈ne(x)ne(x) denotes the set of factor nodes that are neighbours of x, and Xs denotes theset of all variables in the subtree connected to the variable node x via the factor node8.
GRAPHICAL MODELSFigure 8.46A fragment of a factor graph illustrating theevaluation of the marginal p(x).µfs →x (x)Fs (x, Xs )404fsxfs , and Fs (x, Xs ) represents the product of all the factors in the group associatedwith factor fs .Substituting (8.62) into (8.61) and interchanging the sums and products, we obtain Fs (x, Xs )p(x) =s∈ne(x)=Xsµfs →x (x).(8.63)s∈ne(x)Here we have introduced a set of functions µfs →x (x), defined byµfs →x (x) ≡Fs (x, Xs )(8.64)Xswhich can be viewed as messages from the factor nodes fs to the variable node x.We see that the required marginal p(x) is given by the product of all the incomingmessages arriving at node x.In order to evaluate these messages, we again turn to Figure 8.46 and note thateach factor Fs (x, Xs ) is described by a factor (sub-)graph and so can itself be factorized.
In particular, we can writeFs (x, Xs ) = fs (x, x1 , . . . , xM )G1 (x1 , Xs1 ) . . . GM (xM , XsM )(8.65)where, for convenience, we have denoted the variables associated with factor fx , inaddition to x, by x1 , . . . , xM . This factorization is illustrated in Figure 8.47. Notethat the set of variables {x, x1 , . . . , xM } is the set of variables on which the factorfs depends, and so it can also be denoted xs , using the notation of (8.59).Substituting (8.65) into (8.64) we obtain µfs →x (x) =...fs (x, x1 , . .
. , xM )Gm (xm , Xsm )x1=x1xM...xMm∈ne(fs )\xfs (x, x1 , . . . , xM )m∈ne(fs )\xXxmµxm →fs (xm )(8.66)8.4. Inference in Graphical ModelsFigure 8.47405xMIllustration of the factorization of the subgraph associated with factor node fs .µxM →fs (xM )fsµfs →x (x)xxmGm (xm , Xsm )where ne(fs ) denotes the set of variable nodes that are neighbours of the factor nodefs , and ne(fs ) \ x denotes the same set but with node x removed. Here we havedefined the following messages from variable nodes to factor nodesµxm →fs (xm ) ≡Gm (xm , Xsm ).(8.67)XsmWe have therefore introduced two distinct kinds of message, those that go from factornodes to variable nodes denoted µf →x (x), and those that go from variable nodes tofactor nodes denoted µx→f (x).
In each case, we see that messages passed along alink are always a function of the variable associated with the variable node that linkconnects to.The result (8.66) says that to evaluate the message sent by a factor node to a variable node along the link connecting them, take the product of the incoming messagesalong all other links coming into the factor node, multiply by the factor associatedwith that node, and then marginalize over all of the variables associated with theincoming messages. This is illustrated in Figure 8.47. It is important to note thata factor node can send a message to a variable node once it has received incomingmessages from all other neighbouring variable nodes.Finally, we derive an expression for evaluating the messages from variable nodesto factor nodes, again by making use of the (sub-)graph factorization.
From Figure 8.48, we see that term Gm (xm , Xsm ) associated with node xm is given by aproduct of terms Fl (xm , Xml ) each associated with one of the factor nodes fl that islinked to node xm (excluding node fs ), so thatGm (xm , Xsm ) =Fl (xm , Xml )(8.68)l∈ne(xm )\fswhere the product is taken over all neighbours of node xm except for node fs . Notethat each of the factors Fl (xm , Xml ) represents a subtree of the original graph ofprecisely the same kind as introduced in (8.62). Substituting (8.68) into (8.67), we4068. GRAPHICAL MODELSFigure 8.48Illustration of the evaluation of the message sent by avariable node to an adjacent factor node.fLfsxmflFl (xm , Xml )then obtainµxm →fs (xm ) =l∈ne(xm )\fs= Fl (xm , Xml )Xmlµfl →xm (xm )(8.69)l∈ne(xm )\fswhere we have used the definition (8.64) of the messages passed from factor nodes tovariable nodes.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
