Belief Propagation Article Index for
Belief 		Shopping
Belief 		Shopping
Propagation 		Website Links For
Belief 		 

Information About

Belief Propagation
  CATEGORIES ABOUT BELIEF PROPAGATION
   
algorithms
   
graph theory
   
coding theory
   
probability theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Pearl (1988)Pearl, J. (1988) ''Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference'' (Revised Second Printing) San Francisco, CA: Morgan Kaufmann. has suggested this algorithm
as an approximation for general (loopy) network. It is an efficient inference algorithm on Tree s and has demonstrated empirical success in numerous applications including Low-density Parity-check Codes , Turbo Codes , Free Energy approximation, and Satisfiability . It is commonly used in pairwise Markov Random Field s (MRFs with a maximum Clique size of 2), Bayesian Networks , and Factor Graph s.

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}).


EXACT ALGORITHM FOR TREES


This algorithm functions by passing 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. So in the first iteration, the algorithm will send messages from all Leaf Node s to the lone vertex adjacent to its respective leaf and continues sending messages in this manner until all messages have been sent exactly once, hence explaining the term propagation. 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 .

The message definitions will be described in the Factor Graph setting, as the algorithms for other Graphical Model s are nearly identical. Since Factor Graph s 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 ightarrow f_m(x_n) = \prod_{f_i\in N(X_n)\setminus \{f_m\}} f_i ightarrow 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 ightarrow 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 ightarrow f_m(x_i),

where N(u) is defined as the set of neighbours (adjacent vertices in a Graph ) of a vertex u. \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 ightarrow 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 ightarrow f_j(x_i).


APPROXIMATE ALGORITHM FOR GENERAL GRAPHS


Curiously, nearly the same algorithm is used in general Graph s. The algorithm is then sometimes called "loopy" belief propagation, because graphs typically contain Cycle s, or loops. 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.

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. Y. Weiss. ''Correctness of Local Probability Propagation in Graphical Models with Loops''. Neural Computation, 2000. In the general case, no guarantees exist, and there exist graphs which will fail to converge, or which will oscillate between multiple states over repeated iterations.

There are other approximate methods for marginalization including Variational Method s and Monte Carlo Method s.

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 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. 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.

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. More precisely, the marginalization problem defined above is #P -complete and maximization is NP-complete .


RELATION TO FREE ENERGY


The sum-product algorithm is related to the calculation of Free Energy in Thermodynamics . A probability distribution

:P(\mathbf{X}) = rac{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. 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 .

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