# Belief Propagation

Belief Propagation (BP) is a message passing inference method for statistical graphical models (e.g. Bayesian networks and Markov random fields). The basic idea is to compute the marginal distribution of unobserved nodes, based on the conditional distribution of observed nodes. There are two major cases:

• When the graphical model is both a factor graph and a tree (no loops), the exact marginals can be obtained. This is also equivalent to dynamic programming and Viterbi.
• Otherwise, loopy Belief Propagation will become an approximation inference algorithm.

## Motivation: Marginals vs. Joint Maximizer

To compute marginals, we need to find:

${\displaystyle P(x_{1}),P(x_{2}),P(x_{3}),...,P(x_{N})}$

where as to compute joint maximum likelihood, we need:

${\displaystyle {\underset {x_{1},x_{2},x_{3},...,x_{N}}{\operatorname {argmax} }}\ P(x_{1},x_{2},x_{3},...,x_{N}).}$

Unfortunately, for each random variable ${\displaystyle X_{i}}$, it might have M possible states, so if we run search algorithms for all states, the complexity is ${\displaystyle O(M^{N})}$, which is a computationally hard problem. As a result, we need to find better inference algorithms to solve the above problems.

## Problem Formulation

In a generalized Markov random fields (MRFs), the marginals of the log-likelihood model can be formalized as the following equation:

${\displaystyle P(X_{i}=x)={\frac {1}{Z}}\sum _{x_{1},...x_{N}}\Phi (x_{i},x)\prod _{(i,j\in E)}\chi _{i,j}(x_{i},x_{j})}$

here ${\displaystyle \Phi (x_{i},x)}$ is a binary function, where as the above partition function is:

${\displaystyle Z=\sum _{x_{1}...x_{N}}\prod _{(i,j\in E)}\chi _{i,j}(x_{i},x_{j})}$

Therefore, the two tasks here are: (1)compute the marginals of ${\displaystyle P(X_{i}=x)}$. (2)compute the partition function.

## The Belief Propagation Algorithm

In this example, we first show a simple case where the graph is a tree, then we also show the general form of BP messages. Assume we have the following tree-structured MRF, and we pick ${\displaystyle \mathbf {Z} }$ as the root node (technically, you can choose any node).

(1) In the first step, we compute the partition function by sending messages from leaves to the top of the tree. The message passing process can be recognized as bottom-up dynamic programming as well. For example, to compute the possible value of ${\displaystyle G}$ in message ${\displaystyle m_{A,G}(G)}$ from node A to node G, we can calculate

${\displaystyle m_{A,G}(G)=\sum _{x_{A}}\Phi _{A,G}(x_{A},x_{G})}$

following the same method above, we can also calculate ${\displaystyle m_{D,G}(G)}$ and ${\displaystyle m_{M,P}(P)}$. Next, we can calculate

${\displaystyle m_{G,Z}(Z)=\sum _{x_{G}}\Phi _{G,Z}(x_{G},x_{Z})m_{A,G}(G)m_{D,G}(G)}$
${\displaystyle m_{P,Z}(Z)=\sum _{x_{P}}\Phi _{P,Z}(x_{P},x_{Z})m_{M,P}(P)}$

and the partition function will become

${\displaystyle Z=\sum _{x_{Z}}m_{G,Z}(Z)m_{P,Z}(Z)}$

If we define ${\displaystyle Neighbor(i)}$ to be the set of neighbors of ${\displaystyle i}$, the general form of the message can be defined as

${\displaystyle m_{i,j}(i)=\sum _{x_{i}}\Phi _{i,j}(x_{i},x_{j})\prod _{n\in Neighbor(i),n\neq j}m_{n,i}(x_{i})}$

when ${\displaystyle Neighbor(i)={j}}$, then

${\displaystyle m_{i,j}(j)=\sum _{x_{i}}\Phi _{i,j}(x_{i},x_{j})}$

(2) In the second step, we compute marginals by sending top-down messages through out the tree MRF, using the same definition as above.

${\displaystyle m_{i,j}(i)=\sum _{x_{i}}\Phi _{i,j}(x_{i},x_{j})\prod _{n\in Neighbor(i)}m_{n,i}(x_{i})}$

for example, when calculating the downward message from Z to G, we can compute:

${\displaystyle m_{Z,G}(G)=\sum _{x_{Z}}\Phi _{Z,G}(x_{Z},x_{G})m_{P,Z}(Z)}$

we then do the same to compute all the downward messages. After we obtain all the bottom-up and top-down messages, we then can easily compute the marginals. For example, if we want to compute ${\displaystyle P(x_{G}=\epsilon )}$, we can

${\displaystyle P(x_{G}=\epsilon )={\frac {1}{Z}}m_{A,G}(\epsilon )m_{D,G}(\epsilon )m_{Z,G}(\epsilon )}$

the general form of above calculation can be expressed as

${\displaystyle P(X_{i}=x)={\frac {1}{Z}}\prod _{j\in Neighbor(i)}m_{i,j}(x)}$

## Some Reflections

(1) If we use Bayesian networks to represent hidden Markov models (HMMs), then the BP algorithm would be the forward-backward algorithm.

(2) In terms of computational complexity, if we are working on a pair-wise MRF, the complexity can be dropped from ${\displaystyle O(M^{N})}$ to ${\displaystyle O(M^{2})}$.

(3) Some people describe BP as Sum-Product method to estimate marginals. There is a variant called Max-Product to estimate the maximum probability. The general definition of message updates stays the same, but the ${\displaystyle \sum _{x_{i}}\Phi _{i,j}(x_{i},x_{j})}$ will be replaced by ${\displaystyle \max _{x_{i}}\Phi _{i,j}(x_{i},x_{j})}$