Belief propagation, also known as sum-product message passing is a message passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. Belief propagation is commonly used in artificial intelligence and information theory and has demonstrated empirical success in numerous applications including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability.
The algorithm was first proposed by Judea Pearl in 1982, who formulated this algorithm on trees, and was later extended to polytrees. It has since been shown to be a useful approximate algorithm on general graphs.
If X=(Xv) is a set of discrete random variables with a joint mass function p, the marginal distribution of a single Xi is simply the summation of p over all other variables:
However this quickly becomes computationally prohibitive: if there are 100 binary variables, then one needs to sum over 299 ≈ 6.338 × 1029 possible values. By exploiting the graphical structure, belief propagation allows the marginals to be computed much more efficiently.
Read more about Belief Propagation: Description of The Sum-product Algorithm, Related Algorithm and Complexity Issues, Relation To Free Energy, Generalized Belief Propagation (GBP), Gaussian Belief Propagation (GaBP)
Famous quotes containing the word belief:
“We black women must forgive black men for not protecting us against slavery, racism, white men, our confusion, their doubts. And black men must forgive black women for our own sometimes dubious choices, divided loyalties, and lack of belief in their possibilities. Only when our sons and our daughters know that forgiveness is real, existent, and that those who love them practice it, can they form bonds as men and women that really can save and change our community.”
—Marita Golden, educator, author. Saving Our Sons, p. 188, Doubleday (1995)