Exactness of Belief Propagation for Some Graphical Models with Loops

Details Exactness of Belief Propagation for Some Graphical Models with Loops Exactness of Belief Propagation for Some Graphical Models with Loops

2008-01-02

arxiv.org/abs/0801.0341v4

J. Stat. Mech. (2008) P10016

Physics

Condensed Matter

Statistical Mechanics

12 pages, 1 figure, submitted to JSTAT

Scientific paper

10.1088/1742-5468/2008/10/P10016

It is well known that an arbitrary graphical model of statistical inference defined on a tree, i.e. on a graph without loops, is solved exactly and efficiently by an iterative Belief Propagation (BP) algorithm convergent to unique minimum of the so-called Bethe free energy functional. For a general graphical model on a loopy graph the functional may show multiple minima, the iterative BP algorithm may converge to one of the minima or may not converge at all, and the global minimum of the Bethe free energy functional is not guaranteed to correspond to the optimal Maximum-Likelihood (ML) solution in the zero-temperature limit. However, there are exceptions to this general rule, discussed in \cite{05KW} and \cite{08BSS} in two different contexts, where zero-temperature version of the BP algorithm finds ML solution for special models on graphs with loops. These two models share a key feature: their ML solutions can be found by an efficient Linear Programming (LP) algorithm with a Totally-Uni-Modular (TUM) matrix of constraints. Generalizing the two models we consider a class of graphical models reducible in the zero temperature limit to LP with TUM constraints. Assuming that a gedanken algorithm, g-BP, funding the global minimum of the Bethe free energy is available we show that in the limit of zero temperature g-BP outputs the ML solution. Our consideration is based on equivalence established between gapless Linear Programming (LP) relaxation of the graphical model in the $T\to 0$ limit and respective LP version of the Bethe-Free energy minimization.

Affiliated with

Also associated with

No associations

Rating

Exactness of Belief Propagation for Some Graphical Models with Loops does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exactness of Belief Propagation for Some Graphical Models with Loops, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exactness of Belief Propagation for Some Graphical Models with Loops will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495790