Belief propagation - Citizendia

Belief propagation, also known as the sum-product algorithm, is an iterative algorithm for computing marginals of functions on a graphical model most commonly used in artificial intelligence and information theory. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation In Probability theory, given two jointly distributed Random variables X and Y, the marginal distribution of X is simply the Probability In Probability theory, Statistics, and Machine learning, a graphical model (GM is a graph that represents independencies among Random variables Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information. Judea Pearl in 1982^[1] formulated this algorithm on trees, and Kim and Pearl (in 1983)^[2] on polytrees. Judea Pearl is a Computer scientist and Philosopher, best known for developing the probabilistic approach to Artificial intelligence, in Pearl (1988)^[3] has then suggested this algorithm as an approximation for general (loopy) network. It is an efficient inference algorithm on trees and has demonstrated empirical success in numerous applications including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability. In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path. In Information theory, a low-density parity-check code (LDPC code is an Error correcting code, a method of transmitting a message over a noisy transmission In Electrical engineering and Digital communications, turbo codes (originally in French Turbocodes) are a class of high-performance error correction In Thermodynamics, the term thermodynamic free energy refers to the amount of work that can be extracted from a System, and is helpful in Engineering It is commonly used in pairwise Markov random fields (which have a maximum clique size of 2), Bayesian networks, and factor graphs. A Markov network, or Markov random field, is a model of the (full Joint probability distribution of a set \mathcal{X} of Random variables In Graph theory, a clique in an Undirected graph G is a set of vertices V such that for every two vertices in V there exists an edge connecting A Bayesian network (or a belief network) is a Probabilistic graphical model that represents a set of Variables and their probabilistic independencies In Mathematics, a factor graph is an XF- Bipartite graph where X=\{X_1X_2\dotsX_n\} is a set of variables and F=\{f_1f_2\dotsf_m\}

Recall that the marginal distribution of a single random variable $X i$ is simply the summation of a joint distribution over all variables except $X i$ , and let $\mathbf{x}$ be an assignment of all variables in the joint distribution:

$P(x_i) = \sum_{\mathbf{x}: X_i=x_i} P(\mathbf{x}).$

For the purposes of explaining this algorithm, consider the marginal function, which is simply an unnormalized marginal distribution with a generic global function $g(\mathbf{x})$ :

$z(x_i) = \sum_{\mathbf{x}: X_i=x_i} g(\mathbf{x}).$

1 Exact algorithm for trees
2 Approximate algorithm for general graphs
3 Related algorithm and complexity issues
4 Relation to free energy
5 Generalized belief propagation (GBP)
6 References

Exact algorithm for trees

This algorithm functions by passing positive real vector valued messages across edges in a graphical model. In Probability theory, given two jointly distributed Random variables X and Y, the marginal distribution of X is simply the Probability A random variable is a rigorously defined mathematical entity used mainly to describe Chance and Probability in a mathematical way In the study of Probability, given two Random variables X and Y, the joint distribution of X and Y is the distribution The concept of a normalizing constant arises in Probability theory and a variety of other areas of Mathematics. In Mathematics, the real numbers may be described informally in several different ways More precisely, in trees: a vertex sends a message to an adjacent vertex if (a) it has received messages from all of its other adjacent vertices and (b) hasn't already sent one. In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path. For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out Adjacent is an adjective meaning contiguous, adjoining or abutting. Adjacent is an adjective meaning contiguous, adjoining or abutting. So in the first iteration, the algorithm sends messages from all leaf nodes to each of the lone vertices adjacent to those respective leaves and continues sending messages in this manner until all messages have been sent exactly once, hence explaining the term propagation. In Computer science, a leaf node or external node is a node of a Tree data structure that has zero Child nodes Often leaf nodes are It is easily proven that all messages will be sent (there are twice the number of edges of them). Upon termination, the marginal of a variable is simply the product of the incoming messages of all its adjacent vertices. A simple proof of this fact, though somewhat messy, can be done by mathematical induction. Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that

The message definitions will be described in the factor graph setting, as the algorithms for other graphical models are nearly identical. In Mathematics, a factor graph is an XF- Bipartite graph where X=\{X_1X_2\dotsX_n\} is a set of variables and F=\{f_1f_2\dotsf_m\} In Probability theory, Statistics, and Machine learning, a graphical model (GM is a graph that represents independencies among Random variables Since factor graphs have variable and factor nodes, there are two types of messages to define:

A variable message is a real-valued function that is a message sent from a variable to a factor, and defined as

$X_n\rightarrow f_m(x_n) = \prod_{f_i\in N(X_n)\setminus \{f_m\}} f_i\rightarrow X_n(x_n).$

A factor message is a real-valued function that is a message sent from a factor to a variable, and defined as

$f_m\rightarrow X_n(x_n) = \sum_{\mathbf{x_m}:X_n=x_n} f_m(\mathbf{x_m}) \prod_{X_i\in N(f_m)\setminus \{X_n\}} X_i\rightarrow f_m(x_i),$

where $N (u)$ is defined as the set of neighbours (adjacent vertices in a graph) of a vertex $u$ . In Mathematics, a factor graph is an XF- Bipartite graph where X=\{X_1X_2\dotsX_n\} is a set of variables and F=\{f_1f_2\dotsf_m\} The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function In Mathematics and Computer science, a graph is the basic object of study in Graph theory. $\mathbf{x_m}$ is an assignment to the vertices affecting $f m$ (i. e. vertices in $N (f m)$ ).

As mentioned in the description of the algorithm, the marginal of $X i$ can be computed in the following manner:

$z(x_i) = \prod_{f_j\in N(X_i)} f_j\rightarrow X_i(x_i).$

One can also compute the marginal of a factor $f j$ , equivalently, the marginal of the subset of variables $X j$ in the following manner:

$z(\mathbf{x_j}) = f_j(\mathbf{x_j})\prod_{X_i\in N(f_j)} X_i\rightarrow f_j(x_i).$

Approximate algorithm for general graphs

Curiously, nearly the same algorithm is used in general graphs. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. The algorithm is then sometimes called "loopy" belief propagation, because graphs typically contain cycles, or loops. Cycle in Graph theory and Computer science has several meanings A closed walk with repeated vertices allowed The procedure must be adjusted slightly because graphs might not contain any leaves. Instead, one initializes all variable messages to 1 and uses the same message definitions above, updating all messages at every iteration (although messages coming from known leaves or tree-structured subgraphs may no longer need updating after sufficient iterations). It is easy to show that in a tree, the message definitions of this modified procedure will converge to the set of message definitions given above within a number of iterations equal to the diameter of the tree. Geometry, a diameter of a Circle is any straight Line segment that passes through the center of the circle and whose Endpoints are on the

The precise conditions under which loopy belief propagation will converge are still not well understood; it is known that graphs containing a single loop will converge to a correct solution. ^[4] Several sufficient (but not necessary) conditions for convergence of loopy belief propagation to a unique fixed point exist. ^[5] There exist graphs which will fail to converge, or which will oscillate between multiple states over repeated iterations. Techniques like EXIT charts can provide an approximate visualisation of the progress of belief propagation and an approximate test for convergence. An Extrinsic information transfer chart, commonly called an EXIT chart, is a technique to aid the construction of good iteratively-decoded Error-correcting codes

There are other approximate methods for marginalization including variational methods and Monte Carlo methods. The variational method is in Quantum mechanics, one way of finding approximations to the lowest energy eigenstate or Ground state, and some excited states Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results

One method of exact marginalization in general graphs is called the junction tree algorithm, which is simply belief propagation on a modified graph guaranteed to be a tree. The junction tree algorithm is a method used in Machine learning for Exact marginalization in general graphs In essence it entails performing Belief The basic premise is to eliminate cycles by clustering them into single nodes.

Related algorithm and complexity issues

A similar algorithm is commonly referred to as the Viterbi algorithm, but also known as the max-product or min-sum algorithm, which solves the related problem of maximization, or most probable explanation. The Viterbi algorithm is a Dynamic programming Algorithm for finding the most likely sequence of hidden states &ndash called the Viterbi path Instead of attempting to solve the marginal, the goal here is to find the values $\mathbf{x}$ that maximises the global function (i. e. most probable values in a probabilistic setting), and it can be defined using the arg max:

$\arg\max_{\mathbf{x}} g(\mathbf{x}).$

An algorithm that solves this problem is nearly identical to belief propagation, with the sums replaced by maxima in the definitions. In Mathematics, arg max (or argmax) stands for the argument of the maximum, that is to say the value of the given argument for which the value

It is worth noting that inference problems like marginalization and maximization are NP-hard to solve exactly and approximately (at least for relative error) in a graphical model. Inference is the act or process of deriving a Conclusion based solely on what one already knows NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems In the mathematical field of Numerical analysis, the approximation error in some data is the discrepancy between an exact value and some approximation to it More precisely, the marginalization problem defined above is #P-complete and maximization is NP-complete. #P, pronounced "sharp P" or "number P" is a complexity class in Computational complexity theory. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties

Relation to free energy

The sum-product algorithm is related to the calculation of free energy in thermodynamics. In Thermodynamics, the term thermodynamic free energy refers to the amount of work that can be extracted from a System, and is helpful in Engineering In Physics, thermodynamics (from the Greek θερμη therme meaning " Heat " and δυναμις dynamis meaning " A probability distribution

$P(\mathbf{X}) = \frac{1}{Z} \prod_{f_j} f_j(x_j)$

(as per the factor graph representation) can be viewed as a measure of the internal energy present in a system, computed as

$E(\mathbf{X}) = \log \prod_{f_j} f_j(x_j).$

The free energy of the system is then

$F = U - H = \sum_{\mathbf{X}} P(\mathbf{X}) E(\mathbf{X}) + \sum_{\mathbf{X}} P(\mathbf{X}) \log P(\mathbf{X}).$

It can then be shown that the points of convergence of the sum-product algorithm represent the points where the free energy in such a system is minimized. In Thermodynamics, the internal energy of a Thermodynamic system, or a body with well-defined boundaries, denoted by U, or sometimes Similarly, it can be shown that a fixed point of the iterative belief propagation algorithm in graphs with cycles is a stationary point of a free energy approximation.

Generalized belief propagation (GBP)

Belief propagation algorithms are normally presented as messages update equations on a factor graph, involving messages between variable nodes and their neighboring factor nodes and vice versa. Considering messages between regions in a graph is one way of generalizing the belief propagation algorithm. There are several ways of defining the set of regions in a graph that can exchange messages. One method uses ideas introduced by Kikuchi in the physics literature, and is known as Kikuchi's cluster variation method.

Improvements in the performance of belief propagation algorithms are also achievable by breaking the replicas symmetry in the distributions of the fields (messages). This generalization leads to a new kind of algorithm called Survey Propagation (SP), which have proved to be very efficient in NP-complete problems like satisfiability and graph coloring. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties In Graph theory, graph coloring is a special case of Graph labeling; it is an assignment of labels traditionally called "colors" to elements of a

The cluster variational method and the survey propagation algorithms are two different improvements to belief propagation. The name generalized survey propagation (GSP) is waiting to be assigned to the algorithm that merges both generalizations.

References

Frey, Brendan (1998). Graphical Models for Machine Learning and Digital Communication. MIT Press
David J.C. MacKay (2003). Exact Marginalization in Graphs. In David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, pp. 334–340. Cambridge: Cambridge University Press.
Mackenzie, Dana (2005). Communication Speed Nears Terminal Velocity New Scientist. 9 July 2005. Issue 2507 (Registration required)
Yedidia, J. S. and Freeman, W. T. and Weiss, Y. Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, vol. 51(7), pp. 2282-2312, July 2005.
Yedidia, J. S. ; Freeman, W. T. ; Weiss, Y. , Understanding Belief Propagation and Its Generalizations, Exploring Artificial Intelligence in the New Millennium, ISBN 1558608117, Chap. 8, pp. 239-236, January 2003 (Science & Technology Books)
Graphical models, Chapter 8 of Pattern Recognition and Machine Learning by Christopher M. Bishop
Koch, Volker M. (2007). A Factor Graph Approach to Model-Based Signal Separation --- A tutorial-style dissertation

^ Pearl, J. (1982) Reverend Bayes on inference engines: A distributed hierarchical approach. Proceedings American Association of Artificial Intelligence National Conference on AI, Pittsburgh, PA, 133--136.
^ Kim, J. H. and Pearl, J. , (1983) A computational model for combined causal and diagnostic reasoning in inference systems, Proceedings IJCAI-83, Karlsruhe, Germany, 190--193.
^ Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Revised Second Printing) San Francisco, CA: Morgan Kaufmann.
^ Y. Weiss. Correctness of Local Probability Propagation in Graphical Models with Loops. Neural Computation, 2000.
^ J. Mooij & H. Kappen. Sufficient Conditions for Convergence of the Sum–Product Algorithm. IEEE Transactions on Information Theory 53(12):4422-4437, 2007

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents