Concavity of reweighted Kikuchi approximation

Po-Ling Loh, Andre WibisonoNeurIPS 2014 · OpenReview

Overview

Estimating the log partition function is a fundamental but computationally intractable (NP-hard) task in probabilistic graphical models, which are widely used in computer vision, statistical physics, and machine learning. This value is essential for normalizing distributions and performing accurate inference.

To bypass this computational wall, researchers often rely on variational approximations. The most famous is the Bethe approximation (closely linked to Loopy Belief Propagation), but it frequently fails to converge or gets trapped in local optima because its underlying energy function is not concave. The Kikuchi approximation is a more powerful generalization that analyzes larger "regions" of a graph, yet it suffers from identical stability and optimization issues.

This paper provides a rigorous theoretical foundation for the reweighted Kikuchi approximation. By establishing the first necessary and sufficient conditions for the objective function to be concave, the authors ensure that message-passing algorithms can efficiently find a global optimum rather than getting stuck in local minima.

Methodology: Reweighting for Concavity

The authors tackle the challenge of making these approximations "well-behaved" by introducing a reweighted version of the Kikuchi approximation. Their approach involves:

  1. Variational Framework: Treating the log partition function estimation as a maximization problem over a "region graph."
  2. Weight Assignment: Introducing arbitrary weights ($\rho$) for individual terms in the Kikuchi entropy expansion.
  3. Concavity Analysis: Deriving strict conditions on these weights based on the structure of the region graph (ancestors, forebears, and neighbors) to guarantee that the objective function is strictly concave.
  4. Algorithm Design: Proposing a reweighted sum-product algorithm—a message-passing scheme specifically designed to optimize this reweighted objective. They prove that if this algorithm converges, it is guaranteed to reach the unique global optimum.

Key Theoretical Insights

  • The Geometry of Concavity: For the Bethe case (a two-layer region graph), the "region of concavity" is exactly the convex hull of indicator vectors for single-cycle forests (subgraphs where each connected component has at most one cycle).
  • Necessity vs. Sufficiency: While previous work established some sufficient conditions for concavity, this paper proves that for Bethe approximations, their conditions are also necessary. Stepping outside this "polytope of concavity" guarantees the function will lose its concavity.
  • Better than Spanning Forests: The authors demonstrate that the region of concavity for the reweighted Bethe approximation is larger than the previously studied "spanning forest polytope." This affords more flexibility in choosing weights, leading to tighter approximations of the true log partition function.

Experimental Results

The theoretical findings were evaluated using synthetic experiments on the pairwise Ising model. The authors tested two specific graph topologies: Complete Graphs ($K_n$, where every node connects to all others) and Toroidal Grids ($T_n$, a grid where edges wrap around). They evaluated both "Attractive" models (neighbors prefer the same state) and "Mixed" models (random interactions).

Simulation results across various graph topologies ($K_n, T_n$) and interaction types.

As illustrated in the experimental results above, the simulations validate the theoretical boundaries:

  • Stability within Boundaries: As long as the weights remained within the calculated "concavity region" ($\rho \le \rho_{cycle}$, marked by the red vertical lines), the algorithm was stable and converged reliably.
  • Instability Outside Boundaries: Once the weights moved outside the theoretical concavity boundaries, "point clouds" appeared. These scattered points indicate a failure to converge or the presence of multiple local optima.
  • Improved Accuracy: The reweighted Kikuchi approach generally provided a better approximation of the true log partition function ($A(\gamma)$) compared to standard unweighted versions or versions restricted to simpler spanning forest weights.

Limitations and Future Directions

While this paper establishes a strong theoretical baseline, a few limitations remain. Currently, the concavity conditions depend entirely on the graph structure and the weights, ignoring the actual values of the potentials (the interaction strength between nodes). In practice, very weak interactions might allow for concavity even if the graph structure is complex.

Furthermore, while the paper defines the safe region for weights, it does not prescribe a universal method for selecting the absolute optimal weights within that region to maximize accuracy. Finally, as the complexity of the region graph grows quickly for higher-order Kikuchi approximations, future work could explore automated ways to select the best regions to balance accuracy and computational cost.

Summary updated

Abstract

We analyze a reweighted version of the Kikuchi approximation for estimating the log partition function of a product distribution defined over a region graph. We establish sufficient conditions for the concavity of our reweighted objective function in terms of weight assignments in the Kikuchi expansion, and show that a reweighted version of the sum product algorithm applied to the Kikuchi region graph will produce global optima of the Kikuchi approximation whenever the algorithm converges. When the region graph has two layers, corresponding to a Bethe approximation, we show that our sufficient conditions for concavity are also necessary. Finally, we provide an explicit characterization of the polytope of concavity in terms of the cycle structure of the region graph. We conclude with simulations that demonstrate the advantages of the reweighted Kikuchi approach.
BibTeX
@inproceedings{loh2014concavity,
  author = {Po-Ling Loh and Andre Wibisono},
  title = {{Concavity of reweighted Kikuchi approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=H1EvzKbOZS},
}
Figure