Belief propagation

Not to be confused with Belief revision.

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 (or variable), conditional on any observed nodes (or variables). 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.[1]

The algorithm was first proposed by Judea Pearl in 1982,[2] who formulated it as an exact inference algorithm on trees, later extended to polytrees.[3] While the algorithm is not exact on general graphs, it has been shown to be a useful approximate algorithm.[4]

  1. ^ Cite error: The named reference Sat was invoked but never defined (see the help page).
  2. ^ Pearl, Judea (1982). "Reverend Bayes on inference engines: A distributed hierarchical approach" (PDF). Proceedings of the Second National Conference on Artificial Intelligence. AAAI-82: Pittsburgh, PA. Menlo Park, California: AAAI Press. pp. 133–136. Retrieved 28 March 2009.
  3. ^ Kim, Jin H.; Pearl, Judea (1983). "A computational model for combined causal and diagnostic reasoning in inference systems" (PDF). Proceedings of the Eighth International Joint Conference on Artificial Intelligence. IJCAI-83: Karlsruhe, Germany. Vol. 1. pp. 190–193. Retrieved 20 March 2016.
  4. ^ Pearl, Judea (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (2nd ed.). San Francisco, CA: Morgan Kaufmann. ISBN 978-1-55860-479-7.