A Double-Loop Algorithm to Minimize the Bethe and Kikuchi Free Energies

A. L. Yuille

Smith-Kettlewell Eye Research Institute

Recent work (Yedidia, Freeman, Weiss 2000}) has shown that stable points of belief propagation (BP) algorithms (Pearl 1988} for graphs with loops correspond to extrema of the Bethe free energy (Domb 1972). These BP algorithms have been used to obtain good solutions to problems for which alternative algorithms fail to work (Freeman et al 1999, Frey 1998, McEliece et al 1998, Murphy et al 1999 . In this paper we first obtain the dual energy of the Bethe free energy which throws light on the BP algorithm. Next we introduce a discrete iterative algorithm which we prove is guaranteed to converge to a minimum of the Bethe free energy. We call this the double-loop algorithm because it contains an inner and an outer loop. It extends a class of mean field theory algorithms developed by (Kosowsky and Yuille 1994},and, in particular, (Rangarajan et al 1996). Moreover, the double-loop algorithm is formally very similar to BP which may help understand when BP converges. Finally, we extend all our results to the Kikuchi approximation which includes the Bethe free energy as a special case (Domb 1972). (Yedidia et al 2000 showed that a ``generalized belief propagation'' algorithm also has its fixed points at extrema of the Kikuchi free energy). We are able both to obtain a dual formulation for Kikuchi but also obtain a double-loop discrete iterative algorithm that is guaranteed to converge to a minimum of the Kikuchi free energy. It is anticipated that these double-loop algorithms will be useful for solving optimization problems in computer vision and other applications.

ps.gz gzipped postscript file