Abstract
This paper generalizes the Bethe free energy approximation to a broad class of pairwise entropy approximations defined by arbitrary "counting numbers." For attractive binary models, the author proves that finding the global minimum of the approximate free energy is a submodular optimization problem. This theoretical breakthrough enables a fully polynomial-time approximation scheme (FPTAS) to estimate the partition function to any desired accuracy, extending guarantees previously limited to the specific Bethe case.
Introduction: The Challenge of Inference
In graphical models, such as Markov Random Fields, two tasks are paramount: marginal inference (finding the probability of a subset of variables) and computing the partition function ($Z$). Both are NP-hard for general graphs. Belief Propagation (BP) is the standard heuristic for these tasks, aiming to minimize the Bethe free energy. However, BP often fails to converge or gets trapped in local minima because the objective function is typically non-convex, as shown in the complex energy landscapes of these models.
Theoretical Framework and Methodology
The paper moves beyond the standard Bethe approximation by considering a variational framework where the true entropy is replaced by an approximation $S_A$ using weighted singleton and pairwise terms. These weights, known as "counting numbers" ($c_i$ and $\rho_{ij}$), define a family of approximations that includes Tree-Reweighted (TRW) methods.
The Mesh Method and Derivative Bounds
To find the global minimum efficiently, the author introduces the "Mesh Method" (Algorithm 1). A critical component of this algorithm is Theorem 5, which provides a "sandwich inequality" for the first derivatives of the free energy. By bounding the partial derivatives, the algorithm can prune large regions of the marginal space that cannot contain the global minimum, significantly reducing the search space.
Submodularity in Attractive Models
The paper's most significant contribution is proving that for attractive models (where variables prefer similar states), the discrete optimization over the remaining mesh is submodular. Submodularity is the discrete analogue of convexity, allowing for polynomial-time global optimization. This result is "universal" in that it applies to any valid set of counting numbers, not just the Bethe approximation.
Key Insights and Results
The research yields several important conclusions:
- FPTAS for General Approximations: A Fully Polynomial-Time Approximation Scheme is now available for the log-partition function of any attractive binary pairwise model, regardless of the specific counting numbers chosen.
- The Polytope Effect: The paper highlights a beneficial interaction between entropy approximation and the "local polytope" relaxation. In frustrated cycles, the errors from these two approximations can cancel each other out, often making the Bethe approximation more accurate than more computationally expensive alternatives.
- Bethe vs. TRW: While TRW approximations are convex and thus easier to optimize directly, the Bethe approximation's tendency to benefit from error cancellation often leads to superior performance in practice.
Conclusion
By bridging the gap between specific heuristics like BP and general variational approximations, this work provides a robust theoretical foundation for inference in graphical models. The extension of submodularity guarantees to a wide family of counting numbers opens new avenues for designing efficient, accurate approximation schemes for complex probabilistic systems.
Summary updated