Difference between revisions of "Belief Propagation"

From Cohen Courses
Jump to navigationJump to search
Line 19: Line 19:
 
where as the partition function is:
 
where as the partition function is:
 
:<math> Z = \sum_{x_1...x_N} \prod_{(i,j \in E)} \chi_{i,j}(x_i,x_j)
 
:<math> Z = \sum_{x_1...x_N} \prod_{(i,j \in E)} \chi_{i,j}(x_i,x_j)
 +
Therefore, the two task here are:
 +
(1)compute the partition function
 +
(2)compute the marginals of <math>P(X_{i}=x)</math>
  
 
== Inference ==
 
== Inference ==

Revision as of 09:41, 27 September 2011

This is a method proposed by Judea Pearl, 1982: Reverend Bayes on inference engines: A distributed hierarchical approach, AAAI 1982.

Belief Propagation is a message passing inference method for statistical graphical models (e.g. Bayesian networks and Markov random fields). The basic idea is to compute the marginal distribution of unobserved nodes, based on the conditional distribution of observed nodes. There are two major cases:

  • When the graphical model is both a factor graph and a tree (no loops), the exact marginals can be obtained. This is also equivalent to dynamic programming and Viterbi.
  • Otherwise, loopy Belief Propagation will become an approximation inference algorithm.

Motivation: Marginals vs. Joint Maximizer

To compute marginals, we need to find:

where as to compute joint maximum likelihood, we need:

Unfortunately, for each random variable , it might have M possible states, so if we run search algorithms for all states, the complexity is , which is a computationally hard problem. As a result, we need to find better inference algorithms to solve the above problems.

Problem Formulation

In a generalized Markov random fields, the log-likelihood model can be formalized as the following equation:

where as the partition function is:

Inference