Abstract
Inference problems in graphical models are often approximated by casting them as constrained optimization problems. Message passing algorithms, such as belief propagation, have previously been suggested as methods for solving these optimization problems. However, there are few convergence guarantees for such algorithms, and the algorithms are therefore not guaranteed to solve the corresponding optimization problem. Here we present an oriented tree decomposition algorithm that is guaranteed to converge to the global optimum of the Tree-Reweighted (TRW) variational problem. Our algorithm performs local updates in the convex dual of the TRW problem - an unconstrained generalized geometric program. Primal updates, also local, correspond to oriented reparametrization operations that leave the distribution intact.
Introduction
Probabilistic inference—calculating marginal distributions or finding the most likely state in a graphical model—is a fundamental but NP-hard challenge. Variational methods address this by transforming inference into an optimization problem, typically minimizing a "free energy" function. While Belief Propagation (BP) is a popular heuristic for this, its underlying Bethe free energy is non-convex, leading to potential oscillations or convergence to local minima.
The Tree-Reweighted (TRW) framework was introduced to provide a convex alternative, ensuring a single global optimum. However, even with a convex objective, standard message-passing implementations like TRW-MP often fail to converge in practice, particularly in highly correlated systems. Practitioners often resort to "damping" (averaging successive messages), a heuristic that lacks strong theoretical guarantees. This paper introduces TRW-GP, a principled message-passing algorithm that is mathematically guaranteed to converge to the global optimum of the TRW objective.
Methodology: The TRW-GP Algorithm
The authors derive TRW-GP by reformulating the TRW objective through several key steps:
- Oriented Tree Decomposition: By treating trees as directed (oriented) rather than undirected, the system's entropy can be expressed as a sum of conditional entropies, which are concave functions.
- Decoupling and Dual Formulation: The authors decouple shared marginal variables by creating local copies and enforcing consistency through constraints. By applying Lagrange multipliers, they derive the convex dual of the optimization problem.
- Geometric Programming: The resulting dual is shown to be an unconstrained generalized geometric program. This structure allows for the derivation of local, parameter-free update rules similar to Generalized Iterative Scaling.
Unlike standard message passing, every update in TRW-GP is proven to monotonically improve the objective, ensuring stability without the need for external damping heuristics.
Experimental Evaluation
The algorithm was evaluated using synthetic 10x10 Ising model grids, a standard benchmark in statistical physics. The experiments varied the interaction strength ($\alpha_I$) to test the algorithms under increasingly difficult, highly correlated conditions.
Key Results
- Robust Convergence: TRW-GP converged in every test case, including high-interaction regimes where undamped TRW-MP failed entirely.
- Performance Trade-offs: In high-interaction scenarios, TRW-GP's convergence rate was competitive with carefully tuned damped TRW-MP. However, in lower-interaction regimes, standard message passing was sometimes faster, though TRW-GP remained the only method with a convergence guarantee.
Conclusion
TRW-GP addresses a significant gap in variational inference by providing a message-passing algorithm with a guaranteed path to the global optimum of the TRW free energy. By leveraging the stability of the unconstrained dual space and the mathematical properties of geometric programming, it offers a robust alternative to heuristic damping. Future work may involve extending this framework to higher-order interactions and applying similar dual-space techniques to MAP inference problems.
Summary updated