Belief Propagation (BP)
Belief Propagation (BP) is a message-passing algorithm on a tree-structured graphical model. Its only operation is to send messages along edges, typically from the leaves toward a chosen root, in order to compute a posterior or marginal distribution.
1. Message Structure
A message sent from node $j$ to node $i$ is a vector indexed by the possible states of $x_i$:
$$m_{j \to i}(x_i) = \sum_{x_j} \psi_{ij}(x_i, x_j)\,\psi_j(x_j)\,\prod_{k \in \mathrm{neighbors}(j)\setminus i} m_{k \to j}(x_j)$$The summand is the product of:
- the edge potential $\psi_{ij}(x_i, x_j)$
- the node potential $\psi_j(x_j)$
- all incoming messages to $j$ from neighbors other than $i$
2. Leaf Node Case
If $j$ is a leaf node, then it has no other incoming neighbors, so the product term disappears:
$$m_{j \to i}(x_i) = \sum_{x_j} \psi_{ij}(x_i, x_j)\,\psi_j(x_j)$$This is the edge potential combined with the node potential.
3. Observed Node Case
If node $j$ is observed with fixed value $x_j=\bar{x}_j$, then there is no summation. The message becomes:
$$m_{j \to i}(x_i) = \psi_{ij}(x_i,\bar{x}_j)\,\psi_j(\bar{x}_j)$$Thus observation collapses the variable to its observed state.
4. Root Posterior
After the root node receives messages from all its neighbors, its unnormalized posterior is
$$\tilde{p}(x_{\mathrm{root}}) = \psi_{\mathrm{root}}(x_{\mathrm{root}})\,\prod_{\text{all neighbors } j} m_{j \to \mathrm{root}}(x_{\mathrm{root}})$$To obtain the normalized posterior, divide by the sum over all root states:
$$p(x_{\mathrm{root}}) = \frac{\tilde{p}(x_{\mathrm{root}})}{\sum_{x_{\mathrm{root}}} \tilde{p}(x_{\mathrm{root}})}$$5. Interpretation
Each message summarizes all information from one subtree into a function of the receiving node’s state. BP therefore propagates local evidence through the tree until the target posterior can be computed at the root.