(Professor Venkat Anantharam)

California MICRO, (DARPA) F30602-00-2-0538, (NSF) SBR-9873086, and (ONR/MURI) N00014-1-0637

It was shown recently in [1] that the well known belief propagation algorithms for posterior probability evaluation can be viewed as algorithms that aim to minimize certain approximations to the variational free energy in a statistical physics context. Specifically, the fixed points of belief propagation algorithms are shown to coincide with the stationary points of Bethe's approximate free energy subject to certain consistency constraints. Bethe's approximation is known to be a special case of a more general class of approximations called Kikuchi free energy approximations. A more general class of belief propagation algorithms was thus introduced which corresponds to algorithms that aim to minimize a general Kikuchi approximate free energy.

In this reseach we develop and extend this general method of approximation. Specifically, given an arbitrary collection of regions, i.e., proper subsets of a set of state variables, and a collection of functions of the configuration of state variables over these regions, we define a general constrained minimization problem corresponding to the general Kikuchi approximation whose stationary points approximate marginals over these regions of the product function, and we specify a general class of local message-passing algorithms along the edges of a graphical representation of the collection of Kikuchi regions, which attempt to solve that problem (see [2]). We have also developed a suitable minimal graphical representation of the collection of regions (see [3]). Iterative message-passing algorithms on the graph we construct involve fewest message updates at each iteration. We have proven that exactness of Kikuchi approximation of marginals depends directly on this graph being cycle-free, and we have conditions for convexity of the Kikuchi function based on the properties of the minimal graph of regions.

- [1]
- J. S. Yedidia, W. T. Freeman, and Y. Weiss,
*Bethe Free Energy, Kikuchi Approximations, and Belief Propagation Algorithms,*Mitsubishi Electric Research Laboratories Technical Report No. MERL TR2001-16, May 2001. - [2]
- P. Pakzad and V. Anantharam, "Belief Propagation and Statistical Physics,"
*Proc. CISS Conf.,*Princeton University, March 2002. - [3]
- P. Pakzad and V. Anantharam, "Minimal Graphical Representation of Kikuchi Regions,"
*Proc. Allerton Conf.,*Monticello, IL, October 2002.

Edit this abstract