Belief Propagation

The belief is the estimated marginal probability of an event.

Let’s start with the first method for belief propagation, that is called the Sum-Product Messages

We can use a family of algorithm called belief propagation on graphs in order to do inference. In particular, we can do exact inference for graphs that are trees, and approximate inference for general graphs.

NOTE: The partition function $Z$ is used to normalize the probabilities, and it’s needed in order to compute the marginal probability, and so do the inference. The problem is that the partition function has many terms inside, and so it’s not efficient at all. We can do better.

Sum-Product Algorithm

When a node $A$ is sending the message to one of it’s neighbour $B$, it will send all the messages that $A$ neighbours have sent to it, excluding $B$, because $B$ already has that information.

$$m_{s\to t}\left(x_t\right):=\sum _{x_s}\left({\varphi }_{st}\left(x_s,x_t\right)\prod _{u\in \text{ neighbors }(s)\backslash t}{m}_{u\to s}\left(x_s\right)\right)$$

When computing the actual beliefs $A$ includes all its neighbour.

$$b_t(x_t)\alpha \prod _{s\in \text{neighbours}(t)}{m}_{s\to t}(x_t)$$

$x_t$ is the vector associated to the node $t$. todo

Usually this method is implemented in a message update algorithm called loopy belief propagation, which is guaranteed to converge to correct marginals probabilities for each node, but it’s expensive.

A more efficient algorithm is the collect and distribute schedule. It works in the following way:

1. Collect all the messages that are going towards the root, and compute the figurative parents of the nodes that are sending those messages.
2. The root collects all the messages, and distribute the information back to the leaves. This algorithm, like loopy belief propagation is guaranteed to converge to marginals, but it’s way more efficient, since it takes a single update per message in order to converge (we traverse each edge just once to traverse, and once to distribute).

The guarantees are not so nice in non-trees structures. Note that if the graph is not a tree, we can choose any node as the root.

Collect and Distribute is the same as Forward-Backward algorithm in Bayes Networks.

Max-Sum algorithm

Similarly to the sum-product algorithm, we can use the max-sum algorithm in order to do inference for the MAP (Maximum a Posteriori).

---

tags: graph-theory - probability-theory resources:

• Belief Propagation - YouTube
• https://cvg.cit.tum.de/_media/teaching/ss2017/pgmcv/in2329-08_bp.pdf