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 m arginal probabili ties at each unit, using an analytic expres sion. Next, we update the marginal proba bilities , by following the negative gradient of the Bethe free energy. Both steps are guar anteed 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 con firm that when belief propagation converges it usually finds identical solutions as our be lief optimization method. The stable nature of belief optimization makes it ideally suited for learning graphical models from data. Belief propagation (BP) is an efficient local message passing protocol for exact inference on trees (Pearl, 1988) . Applying the same rules to graphs with cycles, named loopy BP, has proven a successful strategy for approximate inference (Murphy et a!., 1999). In par ticular, it was shown that the ce lebrated method of "turbo decoding" is equivalent to loopy BP on an ap propriate graphical model (M cEliece et a!., 1998), (Frey and MacKay, 1997) . Other applications can be found in image analysis (Freeman and Pasztor, 1998) , (Frey, 1999 ). An important drawback of loopy BP is that it can eas ily fail to converge (e.g. it may get stuck in limit cy- An attractive feature of loopy BP is the fact that it performs local computations to find a solution which is approximately optimal globally. Solutions to the Bethe approximation can be underst ood as mean field solutions, in that pairs of nodes are interacting with a mean field generated from the rest of the system. Since this must be tr ue for any pair of nodes, this leads to consistency equations equivalent to the BP updates. Yet another way of deriving the BP equations is through the "cav ity method", where one computes the effect of taking one node and its connections out of the system (Opper and Winther, 2000). The problem with a set of consistency equations is that they are not guaranteed to converge. A more sta ble approach is to minimize an objective function if there exists one. Since we know that BP converges to the stationary points of the Bethe free energy, it seems natural to derive an algorithm which minimizes it directly. This is precisely the approach taken in this paper. Progress can be made especially for binary net works, since they allow a convenient parameterization which avoids the usual need for Lagrange multipliers. Moreover, in the binary case we can find an analytic expression for the correlations p(s; = 1, Sj = 1) in terms of the marginals p(si = 1) and p(sj = 1). This result can be used to formulate gradient descent or fixed point updates for the marginals in terms of the neighbouring marginals and the connecting weights.
An important contribution REF showed that the Bethe free energy of a binary pairwise MRF may be considered as a function only of the singleton marginals, however this connection was provided without convergence results.
Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation
ArXiv
ArXiv
Computer Science Mathematics