Belief Optimization for Binary Networks: A Stable Alternative to Loopy
  Belief Propagation
  We present a novel inference algorithm for arbitrary, binary, undirected
graphs. Unlike loopy belief propagation, which iterates fixed point equations,
we directly descend on the Bethe free energy. The algorithm consists of two
phases, first we update the pairwise probabilities, given the marginal
probabilities at each unit,using an analytic expression. Next, we update the
marginal probabilities, given the pairwise probabilities by following the
negative gradient of the Bethe free energy. Both steps are guaranteed to
decrease the Bethe free energy, and since it is lower bounded, the algorithm is
guaranteed to converge to a local minimum. We also show that the Bethe free
energy is equal to the TAP free energy up to second order in the weights. In
experiments we confirm that when belief propagation converges it usually finds
identical solutions as our belief optimization method. However, in cases where
belief propagation fails to converge, belief optimization continues to converge
to reasonable beliefs. The stable nature of belief optimization makes it
ideally suited for learning graphical models from data.
