Bishop C.M. Pattern Recognition and Machine Learning (2006) (811375), страница 95
Текст из файла (страница 95)
Thus to evaluate the message sent by a variable node to an adjacentfactor node along the connecting link, we simply take the product of the incomingmessages along all of the other links. Note that any variable node that has onlytwo neighbours performs no computation but simply passes messages through unchanged. Also, we note that a variable node can send a message to a factor nodeonce it has received incoming messages from all other neighbouring factor nodes.Recall that our goal is to calculate the marginal for variable node x, and that thismarginal is given by the product of incoming messages along all of the links arrivingat that node.
Each of these messages can be computed recursively in terms of othermessages. In order to start this recursion, we can view the node x as the root of thetree and begin at the leaf nodes. From the definition (8.69), we see that if a leaf nodeis a variable node, then the message that it sends along its one and only link is givenby(8.70)µx→f (x) = 1as illustrated in Figure 8.49(a). Similarly, if the leaf node is a factor node, we seefrom (8.66) that the message sent should take the formµf →x (x) = f (x)Figure 8.49The sum-product algorithmbegins with messages sentby the leaf nodes, which depend on whether the leafnode is (a) a variable node,or (b) a factor node.µf →x (x) = f (x)µx→f (x) = 1xf(a)(8.71)xf(b)8.4. Inference in Graphical ModelsExercise 8.20407as illustrated in Figure 8.49(b).At this point, it is worth pausing to summarize the particular version of the sumproduct algorithm obtained so far for evaluating the marginal p(x).
We start byviewing the variable node x as the root of the factor graph and initiating messagesat the leaves of the graph using (8.70) and (8.71). The message passing steps (8.66)and (8.69) are then applied recursively until messages have been propagated alongevery link, and the root node has received messages from all of its neighbours. Eachnode can send a message towards the root once it has received messages from allof its other neighbours. Once the root node has received messages from all of itsneighbours, the required marginal can be evaluated using (8.63). We shall illustratethis process shortly.To see that each node will always receive enough messages to be able to send outa message, we can use a simple inductive argument as follows.
Clearly, for a graphcomprising a variable root node connected directly to several factor leaf nodes, thealgorithm trivially involves sending messages of the form (8.71) directly from theleaves to the root. Now imagine building up a general graph by adding nodes one ata time, and suppose that for some particular graph we have a valid algorithm. Whenone more (variable or factor) node is added, it can be connected only by a singlelink because the overall graph must remain a tree, and so the new node will be a leafnode. It therefore sends a message to the node to which it is linked, which in turnwill therefore receive all the messages it requires in order to send its own messagetowards the root, and so again we have a valid algorithm, thereby completing theproof.Now suppose we wish to find the marginals for every variable node in the graph.This could be done by simply running the above algorithm afresh for each such node.However, this would be very wasteful as many of the required computations wouldbe repeated.
We can obtain a much more efficient procedure by ‘overlaying’ thesemultiple message passing algorithms to obtain the general sum-product algorithmas follows. Arbitrarily pick any (variable or factor) node and designate it as theroot. Propagate messages from the leaves to the root as before. At this point, theroot node will have received messages from all of its neighbours. It can thereforesend out messages to all of its neighbours. These in turn will then have receivedmessages from all of their neighbours and so can send out messages along the linksgoing away from the root, and so on. In this way, messages are passed outwardsfrom the root all the way to the leaves.
By now, a message will have passed inboth directions across every link in the graph, and every node will have receiveda message from all of its neighbours. Again a simple inductive argument can beused to verify the validity of this message passing protocol. Because every variablenode will have received messages from all of its neighbours, we can readily calculatethe marginal distribution for every variable in the graph.
The number of messagesthat have to be computed is given by twice the number of links in the graph andso involves only twice the computation involved in finding a single marginal. Bycomparison, if we had run the sum-product algorithm separately for each node, theamount of computation would grow quadratically with the size of the graph. Notethat this algorithm is in fact independent of which node was designated as the root,4088. GRAPHICAL MODELSFigure 8.50Exercise 8.21The sum-product algorithm can be viewedpurely in terms of messages sent out by factornodes to other factor nodes.
In this example,the outgoing message shown by the blue arrowis obtained by taking the product of all the incoming messages shown by green arrows, multiplying by the factor fs , and marginalizing overthe variables x1 and x2 .x1x3x2fsand indeed the notion of one node having a special status was introduced only as aconvenient way to explain the message passing protocol.Next suppose we wish to find the marginal distributions p(xs ) associated withthe sets of variables belonging to each of the factors. By a similar argument to thatused above, it is easy to see that the marginal associated with a factor is given by theproduct of messages arriving at the factor node and the local factor at that nodeµxi →fs (xi )(8.72)p(xs ) = fs (xs )i∈ne(fs )in complete analogy with the marginals at the variable nodes. If the factors areparameterized functions and we wish to learn the values of the parameters usingthe EM algorithm, then these marginals are precisely the quantities we will need tocalculate in the E step, as we shall see in detail when we discuss the hidden Markovmodel in Chapter 13.The message sent by a variable node to a factor node, as we have seen, is simplythe product of the incoming messages on other links.
We can if we wish view thesum-product algorithm in a slightly different form by eliminating messages fromvariable nodes to factor nodes and simply considering messages that are sent out byfactor nodes. This is most easily seen by considering the example in Figure 8.50.So far, we have rather neglected the issue of normalization. If the factor graphwas derived from a directed graph, then the joint distribution is already correctly normalized, and so the marginals obtained by the sum-product algorithm will similarlybe normalized correctly.
However, if we started from an undirected graph, then ingeneral there will be an unknown normalization coefficient 1/Z. As with the simplechain example of Figure 8.38, this is easily handled by working with an unnormalp(x) of the joint distribution, where p(x) = p(x)/Z. We first run theized version sum-product algorithm to find the corresponding unnormalized marginals p(xi ). Thecoefficient 1/Z is then easily obtained by normalizing any one of these marginals,and this is computationally efficient because the normalization is done over a singlevariable rather than over the entire set of variables as would be required to normalizep(x) directly.At this point, it may be helpful to consider a simple example to illustrate theoperation of the sum-product algorithm. Figure 8.51 shows a simple 4-node factor8.4.
Inference in Graphical ModelsFigure 8.51x1A simple factor graph used to illustrate thesum-product algorithm.x2409x3fafbfcx4graph whose unnormalized joint distribution is given byp(x) = fa (x1 , x2 )fb (x2 , x3 )fc (x2 , x4 ).(8.73)In order to apply the sum-product algorithm to this graph, let us designate node x3as the root, in which case there are two leaf nodes x1 and x4 . Starting with the leafnodes, we then have the following sequence of six messagesµx1 →fa (x1 ) = 1fa (x1 , x2 )µfa →x2 (x2 ) =(8.74)(8.75)x1µx4 →fc (x4 ) = 1fc (x2 , x4 )µfc →x2 (x2 ) =(8.76)(8.77)x4µx2 →fb (x2 ) = µfa →x2 (x2 )µfc →x2 (x2 )fb (x2 , x3 )µx2 →fb .µfb →x3 (x3 ) =(8.78)(8.79)x2The direction of flow of these messages is illustrated in Figure 8.52.
Once this message propagation is complete, we can then propagate messages from the root nodeout to the leaf nodes, and these are given byµx3 →fb (x3 ) = 1fb (x2 , x3 )µfb →x2 (x2 ) =(8.80)(8.81)x3µx2 →fa (x2 ) = µfb →x2 (x2 )µfc →x2 (x2 )fa (x1 , x2 )µx2 →fa (x2 )µfa →x1 (x1 ) =(8.82)(8.83)x2µx2 →fc (x2 ) = µfa →x2 (x2 )µfb →x2 (x2 )fc (x2 , x4 )µx2 →fc (x2 ).µfc →x4 (x4 ) =x2(8.84)(8.85)4108. GRAPHICAL MODELSx1x2x3x1x2x4x4(a)(b)x3Figure 8.52 Flow of messages for the sum-product algorithm applied to the example graph in Figure 8.51.
(a)From the leaf nodes x1 and x4 towards the root node x3 . (b) From the root node towards the leaf nodes.One message has now passed in each direction across each link, and we can nowevaluate the marginals. As a simple check, let us verify that the marginal p(x2 ) isgiven by the correct expression. Using (8.63) and substituting for the messages usingthe above results, we havep(x2 ) = µfa →x2 (x2 )µfb →x2 (x2 )µfc →x2 (x2 ) fa (x1 , x2 )fb (x2 , x3 )fc (x2 , x4 )=x1==x1x2x4x1x3x4x3x4fa (x1 , x2 )fb (x2 , x3 )fc (x2 , x4 )p(x)(8.86)as required.So far, we have assumed that all of the variables in the graph are hidden.
In mostpractical applications, a subset of the variables will be observed, and we wish to calculate posterior distributions conditioned on these observations. Observed nodes areeasily handled within the sum-product algorithm as follows. Suppose we partition xinto hidden variables h and observed variables v, and that the observedvalue of v. Then we simply multiply the joint distribution p(x) by i I(vi , vi ),is denoted vwhere I(v, v ) = 1 if v = v and I(v, v ) = 0 otherwise. This product corresponds) and hence is an unnormalized version of p(h|v = v). By runto p(h, v = vning the sum-product algorithm, we can efficiently calculate the posterior marginalsp(hi |v = v) up to a normalization coefficient whose value can be found efficientlyusing a local computation. Any summations over variables in v then collapse into asingle term.We have assumed throughout this section that we are dealing with discrete variables.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
