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.