Bishop C.M. Pattern Recognition and Machine Learning (2006) (811375), страница 93
Текст из файла (страница 93)
Note carefully thestructure of the message passing equation. The outgoing message µα (xn ) in (8.55)is obtained by multiplying the incoming message µα (xn−1 ) by the local potentialinvolving the node variable and the outgoing variable and then summing over thenode variable.Similarly, the message µβ (xn ) can be evaluated recursively by starting withnode xN and using⎡⎤µβ (xn ) =ψn+1,n (xn+1 , xn ) ⎣···⎦xn+1=xn+2ψn+1,n (xn+1 , xn )µβ (xn+1 ).(8.57)xn+1This recursive message passing is illustrated in Figure 8.38. The normalization constant Z is easily evaluated by summing the right-hand side of (8.54) over all statesof xn , an operation that requires only O(K) computation.Graphs of the form shown in Figure 8.38 are called Markov chains, and thecorresponding message passing equations represent an example of the ChapmanKolmogorov equations for Markov processes (Papoulis, 1984).3988.
GRAPHICAL MODELSExercise 8.15Chapter 9Now suppose we wish to evaluate the marginals p(xn ) for every node n ∈{1, . . . , N } in the chain. Simply applying the above procedure separately for eachnode will have computational cost that is O(N 2 M 2 ). However, such an approachwould be very wasteful of computation. For instance, to find p(x1 ) we need to propagate a message µβ (·) from node xN back to node x2 . Similarly, to evaluate p(x2 )we need to propagate a messages µβ (·) from node xN back to node x3 .
This willinvolve much duplicated computation because most of the messages will be identicalin the two cases.Suppose instead we first launch a message µβ (xN −1 ) starting from node xNand propagate corresponding messages all the way back to node x1 , and suppose wesimilarly launch a message µα (x2 ) starting from node x1 and propagate the corresponding messages all the way forward to node xN . Provided we store all of theintermediate messages along the way, then any node can evaluate its marginal simply by applying (8.54). The computational cost is only twice that for finding themarginal of a single node, rather than N times as much. Observe that a messagehas passed once in each direction across each link in the graph.
Note also that thenormalization constant Z need be evaluated only once, using any convenient node.If some of the nodes in the graph are observed, then the corresponding variablesare simply clamped to their observed values and there is no summation. To seexn canthis, note that the effect of clamping a variable xn to an observed value be expressed by multiplying the joint distribution by (one or more copies of) anxn ), which takes the value 1 when xn = xn and the valueadditional function I(xn , 0 otherwise. One such function can then be absorbed into each of the potentials thatxn .contain xn . Summations over xn then contain only one term in which xn = Now suppose we wish to calculate the joint distribution p(xn−1 , xn ) for twoneighbouring nodes on the chain. This is similar to the evaluation of the marginalfor a single node, except that there are now two variables that are not summed out.A few moments thought will show that the required joint distribution can be writtenin the form1(8.58)p(xn−1 , xn ) = µα (xn−1 )ψn−1,n (xn−1 , xn )µβ (xn ).ZThus we can obtain the joint distributions over all of the sets of variables in eachof the potentials directly once we have completed the message passing required toobtain the marginals.This is a useful result because in practice we may wish to use parametric formsfor the clique potentials, or equivalently for the conditional distributions if we startedfrom a directed graph.
In order to learn the parameters of these potentials in situations where not all of the variables are observed, we can employ the EM algorithm,and it turns out that the local joint distributions of the cliques, conditioned on anyobserved data, is precisely what is needed in the E step. We shall consider someexamples of this in detail in Chapter 13.8.4.2 TreesWe have seen that exact inference on a graph comprising a chain of nodes can beperformed efficiently in time that is linear in the number of nodes, using an algorithm3998.4.
Inference in Graphical ModelsFigure 8.39 Examples of treestructured graphs, showing (a) anundirected tree, (b) a directed tree,and (c) a directed polytree.(a)Exercise 8.18(b)(c)that can be interpreted in terms of messages passed along the chain. More generally,inference can be performed efficiently using local message passing on a broaderclass of graphs called trees. In particular, we shall shortly generalize the messagepassing formalism derived above for chains to give the sum-product algorithm, whichprovides an efficient framework for exact inference in tree-structured graphs.In the case of an undirected graph, a tree is defined as a graph in which thereis one, and only one, path between any pair of nodes.
Such graphs therefore do nothave loops. In the case of directed graphs, a tree is defined such that there is a singlenode, called the root, which has no parents, and all other nodes have one parent. Ifwe convert a directed tree into an undirected graph, we see that the moralization stepwill not add any links as all nodes have at most one parent, and as a consequence thecorresponding moralized graph will be an undirected tree.
Examples of undirectedand directed trees are shown in Figure 8.39(a) and 8.39(b). Note that a distributionrepresented as a directed tree can easily be converted into one represented by anundirected tree, and vice versa.If there are nodes in a directed graph that have more than one parent, but there isstill only one path (ignoring the direction of the arrows) between any two nodes, thenthe graph is a called a polytree, as illustrated in Figure 8.39(c). Such a graph willhave more than one node with the property of having no parents, and furthermore,the corresponding moralized undirected graph will have loops.8.4.3 Factor graphsThe sum-product algorithm that we derive in the next section is applicable toundirected and directed trees and to polytrees.
It can be cast in a particularly simpleand general form if we first introduce a new graphical construction called a factorgraph (Frey, 1998; Kschischnang et al., 2001).Both directed and undirected graphs allow a global function of several variables to be expressed as a product of factors over subsets of those variables.
Factorgraphs make this decomposition explicit by introducing additional nodes for the factors themselves in addition to the nodes representing the variables. They also allowus to be more explicit about the details of the factorization, as we shall see.Let us write the joint distribution over a set of variables in the form of a productof factorsfs (xs )(8.59)p(x) =swhere xs denotes a subset of the variables. For convenience, we shall denote the4008. GRAPHICAL MODELSFigure 8.40x1Example of a factor graph, which correspondsto the factorization (8.60).x2fafbx3fcfdindividual variables by xi , however, as in earlier discussions, these can comprisegroups of variables (such as vectors or matrices). Each factor fs is a function of acorresponding set of variables xs .Directed graphs, whose factorization is defined by (8.5), represent special casesof (8.59) in which the factors fs (xs ) are local conditional distributions.
Similarly,undirected graphs, given by (8.39), are a special case in which the factors are potential functions over the maximal cliques (the normalizing coefficient 1/Z can beviewed as a factor defined over the empty set of variables).In a factor graph, there is a node (depicted as usual by a circle) for every variablein the distribution, as was the case for directed and undirected graphs. There are alsoadditional nodes (depicted by small squares) for each factor fs (xs ) in the joint distribution.
Finally, there are undirected links connecting each factor node to all of thevariables nodes on which that factor depends. Consider, for example, a distributionthat is expressed in terms of the factorizationp(x) = fa (x1 , x2 )fb (x1 , x2 )fc (x2 , x3 )fd (x3 ).(8.60)This can be expressed by the factor graph shown in Figure 8.40. Note that there aretwo factors fa (x1 , x2 ) and fb (x1 , x2 ) that are defined over the same set of variables.In an undirected graph, the product of two such factors would simply be lumpedtogether into the same clique potential.
Similarly, fc (x2 , x3 ) and fd (x3 ) could becombined into a single potential over x2 and x3 . The factor graph, however, keepssuch factors explicit and so is able to convey more detailed information about theunderlying factorization.x1x2x1x2fx1x2fafbx3(a)x3(b)x3(c)Figure 8.41 (a) An undirected graph with a single clique potential ψ(x1 , x2 , x3 ). (b) A factor graph with factorf (x1 , x2 , x3 ) = ψ(x1 , x2 , x3 ) representing the same distribution as the undirected graph. (c) A different factorgraph representing the same distribution, whose factors satisfy fa (x1 , x2 , x3 )fb (x1 , x2 ) = ψ(x1 , x2 , x3 ).4018.4. Inference in Graphical Modelsx1x2x1x2x1fx2fcfax3(a)fbx3(b)x3(c)Figure 8.42 (a) A directed graph with the factorization p(x1 )p(x2 )p(x3 |x1 , x2 ). (b) A factor graph representingthe same distribution as the directed graph, whose factor satisfies f (x1 , x2 , x3 ) = p(x1 )p(x2 )p(x3 |x1 , x2 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
