Belief propagation passes local messages between factors or neighboring variables to compute marginal distributions or maximizing assignments. On a tree, two directed messages per edge give exact results in time linear in the number of vertices when state spaces are fixed.
The sum-product form of belief propagation sums over eliminated states in each message. On a tree it computes exact normalization constants and marginal distributions.
The max-product form of belief propagation replaces summation by maximization. On a tree, storing maximizing states while passing messages and then backtracking gives an exact maximum a posteriori estimate.
Articles by others on the same topic
Belief propagation (BP) is an algorithm used for performing inference on graphical models, particularly in the context of probabilistic graphical models such as Bayesian networks and Markov random fields. Its primary purpose is to compute marginal distributions of a subset of variables given some observed data. ### Key Concepts: 1. **Graphical Models**: These represent relationships among variables using graphs where nodes represent random variables and edges represent probabilistic dependencies.