HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Yuille, A. L. Search for Related Content PubMed PubMed Citation Articles by Yuille, A. L.

CCCP Algorithms to Minimize the Bethe and Kikuchi Free Energies: Convergent Alternatives to Belief Propagation

yuille{at}ski.org, Smith-Kettlewell Eye Research Institute, San Francisco, CA 94115, U.S.A.

This article introduces a class of discrete iterative algorithms that are provably convergent alternatives to belief propagation (BP) and generalized belief propagation (GBP). Our work builds on recent results by Yedidia, Freeman, and Weiss (2000), who showed that the fixed points of BP and GBP algorithms correspond to extrema of the Bethe and Kikuchi free energies, respectively. We obtain two algorithms by applying CCCP to the Bethe and Kikuchi free energies, respectively (CCCP is a procedure, introduced here, for obtaining discrete iterative algorithms by decomposing a cost function into a concave and a convex part). We implement our CCCP algorithms on two- and three-dimensional spin glasses and compare their results to BP and GBP. Our simulations show that the CCCP algorithms are stable and converge very quickly (the speed of CCCP is similar to that of BP and GBP). Unlike CCCP, BP will often not converge for these problems (GBP usually, but not always, converges). The results found by CCCP applied to the Bethe or Kikuchi free energies are equivalent, or slightly better than, those found by BP or GBP, respectively (when BP and GBP converge). Note that for these, and other problems, BP and GBP give very accurate results (see Yedidia et al., 2000), and failure to converge is their major error mode. Finally, we point out that our algorithms have a large range of inference and learning applications.

This article has been cited by other articles:

				P. Pakzad and V. Anantharam Estimation and Marginalization Using the Kikuchi Approximation Methods Neural Comput., August 1, 2005; 17(8): 1836 - 1873. [Abstract] [Full Text] [PDF]

				T. Heskes On the Uniqueness of Loopy Belief Propagation Fixed Points Neural Comput., November 1, 2004; 16(11): 2379 - 2413. [Abstract] [Full Text] [PDF]

				S. Ikeda, T. Tanaka, and S.-i. Amari Stochastic Reasoning, Free Energy, and Information Geometry Neural Comput., September 1, 2004; 16(9): 1779 - 1810. [Abstract] [Full Text] [PDF]

				M. Welling and Y. W. Teh Linear Response Algorithms for Approximate Inference in Graphical Models Neural Comput., January 1, 2004; 16(1): 197 - 221. [Abstract] [Full Text] [PDF]

				A. L. Yuille and A. Rangarajan The Concave-Convex Procedure Neural Comput., April 1, 2003; 15(4): 915 - 936. [Abstract] [Full Text] [PDF]