5.3 Belief Propagation (the Sum-Product Algorithm)

To see this, we begin with an example, computing $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{5}}|\hat{x}_{4})$ in the tree in Fig. 5.2a. Using variable elimination and the ordering $\mathcal{I}=\{2,1,4,3\}$, we obtain

We could implement this in code as

It is easy to see that, in this example, the intermediate tables omega* all have at most two ways, and the intermediate tables m* all have one way.

Does this hold generally for VE on trees? Yes, it does, as long as we let the target node be the root of a(n undirected) tree, and then eliminate recursively from leaves to root. (Fig. 5.2b shows the undirected tree for our example, with root at top.) Since the graph is a tree, the maximal clique size is two, and correspondingly each potential function⁴⁴ 4 In a directed tree, these potential functions are conditional probabilities; in an undirected tree, they are arbitrary. references at most⁵⁵ 5 It can reference fewer: the node that was originally the root of the directed tree will have a singleton rather than pairwise potential. two variables. Eliminating a leaf variable therefore yields a one-way⁶⁶ 6 Or zero-way; see previous. table. Broadcast multiplying this table onto the parent’s potential function does not increase its dimensionality (number of ways), since the child’s table, after marginalization, references only the parent’s variable, which is already represented in the parent’s potential function. Once all of the parent’s children have been eliminated in this way, the (former) parent is itself a leaf of the tree, with an updated potential (i.e., table) that makes reference only to (at most) itself and its parent. So the argument generalizes to the whole tree.

We anticipated above that we would be able to interpret such a run of VE as an operation on the tree. Since every intermediate table m* is computed by marginalizing a child out of a pairwise potential over parent and child, we will think of it as a message passed from child to parent. For the example just discussed, these messages are shown in red in Fig. 5.2b. (We could just as well have used the original tree, Fig. 5.2a, but Fig. 5.2b makes the leaves-to-root order of message passing more perspicuous.)

The computation of any message can be summarized as: once a node $j$ has received messages $m_{kj}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}})$ from all of its children—i.e.,⁷⁷ 7 “The neighbors of $j$, excluding $i$.” for all $k\in\mathcal{N}(j)\setminus i$—it can compute

where the $\psi$ functions are the potential functions on the corresponding undirected graph. Note that for directed trees, the singleton potentials are

and the pairwise potentials are

That the message must take the form of Eq. 5.10 follows from the fact, familiar from the Section 5.2, that the sum over $\hat{x}_{j}$ will not “push in” any farther than the potentials that reference it. Since, by hypothesis, neither ${\hat{X}}_{j}$ nor its parent ${\hat{X}}_{i}$ have been eliminated yet, the (original) potentials $\psi({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}})$ and $\psi({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}},{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{i}})$ must be among these. Since the graph is a tree, the only other potentials that can reference ${\hat{X}}_{j}$ must be its children, which by hypothesis have already been eliminated, and therefore have sent their messages $m_{kj}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}})$.

By variable elimination, the final elimination leaves us with the desired marginal (possibly unnormalized), $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{i}},\bm{x})$, with ${\hat{X}}_{i}$ the last (uneliminated) node, and $\bm{x}$ the vector of all the observations. We can also say that it leaves us with whatever has not been eliminated, namely the messages into ${\hat{X}}_{i}$ and (possibly) a singleton potential $\psi({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{i}})$. (Note that we are not left with any pairwise potentials $\psi({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{i}},{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{j}})$ for any of the children ${\hat{X}}_{j}$ of ${\hat{X}}_{i}$, because these potentials reference those children, and will therefore have been marginalized into messages.) Therefore the target probability is

For unobserved directed graphs, the proportionality constant will be 1, but for undirected graphs or graphs with observations, the right-hand side will be unnormalized.

Mapping variable elimination on a tree onto message passing is neat, but we would like to go further and use this to develop a protocol for computation re-use. To see how to take this last step, consider (as above) computing a different posterior distribution, say, $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{1}}|\hat{x}_{4})$. We will begin again with a run of VE, this time with the elimination ordering $\mathcal{I}=\{5,4,3,2\}$:

It should be clear that this series of computations can be written in terms of Eq. 5.10 if we root the tree at ${\hat{X}}_{1}$ (rather than ${\hat{X}}_{5}$), and again pass messages recursively from leaf to root. The resulting message paths are shown in purple in Fig. 5.2b.

Notice that some of the (purple) message paths used to compute $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{1}}|\hat{x}_{4})$ are the same as some of the (red) message paths used to compute $\hat{p}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}x_{5}}|\hat{x}_{4})$—namely, any pair of red and purple paths in Fig. 5.2b that start from the same leaf. (In this example, such paths are only one edge long, but in general they could be longer). This suggests some immediate computational savings. But we can save more. We have just seen that any singleton marginal (or conditional) can be computed efficiently by treating the corresponding node in the graph as the root of a tree, and then eliminating recursively from leaves to root. Let us call this a collection for the target node. Now, if we have an arrow in both directions on every edge of the tree (Fig. 5.2c)—if we have passed a message in both directions—then we can construct collections for any node in the graph. (You should convince yourself that this is the case.)

Is it possible to compute efficiently all the messages in Fig. 5.2c, i.e. all the messages on the tree? Yes: We have already seen how to compute the red messages: a recursive collection of messages from leaves to root. The green messages, for their part, can be computed by a recursive distribution of messages from root to leaves, using the same message formula, Eq. 5.10. Note that in this case, the expression $k\in\mathcal{N}(j)\setminus i$ means “all neighbors of $j$ other than $i$, to which the message is sent” (rather than “all children…”). Thus, at twice the cost of VE, belief propagation^††margin: belief propagation can compute all the singleton marginals. (Pseudo-code for the entire algorithm is shown in Algorithm LABEL:alg:BP.)

For concreteness, we make this explicit for the example we have been working with. In code, we would have (picking up where we left off)

It is a simple exercise^††margin: Exercise LABEL:ex: to show that Eq. 5.11 turns all these messages (including those from the inward pass) into the singleton marginals.

Finally, although we have described the message passing in belief propagation as a two-stage algorithm—collection from leaves to root, followed by distribution from root to leaves—it can be more succinctly summarized in one line:

Message-passing protocol: A node can pass a message to a neighbor once it has received messages from all its other neighbors.

To see that this is more general than the collection-distribution implementation of Algorithm LABEL:alg:BP, consider that it can also be implemented asynchronously…..