belief propagation
In plain wordsA way for a network of uncertain quantities to reach conclusions by having each node pass short messages to its neighbors about what it currently believes, until the beliefs settle down.
An algorithm that computes marginal probabilities, or the most probable joint assignment, in a probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together. by passing local messages between neighboring nodes. Each node (or factor) repeatedly sends each neighbor a message summarizing the evidence it has received from the rest of the graph, and a variable's belief — its estimated marginal distribution — is the normalized product of its incoming messages. The sum-product form computes marginals; the max-product (or min-sum) form computes the most probable joint assignment, with the Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination. as a special case. On graphs without cycles belief propagation is exact after two sweeps, and the junction-tree algorithm extends exactness to any graph by clustering variables, at a cost exponential in cluster size. On graphs with cycles, 'loopy' belief propagation is approximate and may not converge, yet it often works well: it decodes the turbo and low-density parity-check codes of modern telecommunications and is used in stereo vision and error-correcting inference.
Origin
Introduced by Judea Pearl in 1982 for tree-structured Bayesian networksBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence. and extended to polytrees (singly connected networks) with Jin Kim in 1983. In 1998 Robert McEliece, David MacKay and Jung-Fu Cheng showed that turbo decoding is loopy belief propagation, and Robert Gallager's 1963 decoder for low-density parity-check codes was recognized as an earlier instance.
Related
- probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together.
- Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence.
- Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which.
- Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination.
- variational inferencevariational inference, n.: A way of approximating a hard-to-compute probability distribution by picking the closest match from a simpler family of distributions, turning a hard problem of adding up every possibility into an optimization problem.
- Judea PearlJudea Pearl, prop. n.: An Israeli-American computer scientist who gave AI the mathematics for reasoning under uncertainty and, later, for telling cause and effect apart from mere correlation.
Sources
- Pearl, J. (1982). Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach. Proceedings of AAAI-82, 133–136.
- Kschischang, F. R., Frey, B. J. & Loeliger, H.-A. (2001). Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory 47(2), 498–519.
Mentioned in
Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence., inference engineinference engine, n.: The part of an AI system that does the working-out: in older AI, the program that applies rules to facts; in today's AI, the software that runs a trained model to produce answers., probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together., Markov logic networkMarkov logic network, n.: A way of combining logical rules with probabilities, so that a rule like 'friends usually like the same music' can sometimes be broken, with each rule given a weight saying how strongly it holds., Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which.