Abstract: Computing the partition function $Z$ of a discrete graphical model is a fundamental inference challenge. Since this is computationally intractable, variational approximations are often used in practice. This paper introduces Gauged Mini-Bucket Elimination (WMBE-G), a framework that leverages gauge transformations to systematically tighten upper bounds on the partition function.
Introduction
In discrete graphical models, such as Markov Random Fields or Ising models, the partition function $Z$ is the normalization constant that turns raw scores into probabilities. Computing $Z$ is fundamental for tasks like model selection and calculating likelihoods, but it is also computationally "intractable" (#P-hard). Because we cannot compute $Z$ exactly for large models, we rely on variational inference to find approximations. While methods like Tree-Reweighted Belief Propagation (TRBP) provide guaranteed upper bounds, these bounds often have a significant "gap" from the true value. This paper, presented at AISTATS 2018, introduces a method to systematically tighten these bounds using a flexible mathematical framework called gauge transformations.
Methodology: Gauged Mini-Bucket Elimination
The proposed WMBE-G algorithm builds on two main pillars:
- Weighted Mini-Bucket Elimination (WMBE): A standard technique that approximates the exact variable elimination process. It uses Hölder’s inequality to "split" large computations into smaller, manageable "mini-buckets," resulting in a guaranteed upper bound on $Z$.
- Gauge Transformations (GT): These are linear transformations applied to the local factors of a graphical model. Crucially, these transformations are "Z-invariant"—they change the local representation of the model but leave the global partition function $Z$ exactly the same.
The innovation of WMBE-G is the realization that while $Z$ stays the same under a gauge transformation, the WMBE bound does not. By searching for the "best" gauges using a specialized gradient-descent solver, the algorithm can squeeze the WMBE bound until it is much closer to the true value of $Z$. The authors prove that gauge transformations are a strictly larger family of transformations than standard reparameterization; for instance, in symmetric models like Ising models without a magnetic field, reparameterization cannot improve the WMBE bound at all, whereas gauges can improve it significantly.
Experimental Evaluation
The authors evaluated WMBE-G against several baselines, including standard MBE and TRBP, using three types of models:
- Ising Models: $10 \times 10$ grid graphs with "spin glass" interactions (mixed positive and negative correlations).
- 3-Regular Forney-style GMs: Synthetic models designed to have high induced width, making them particularly difficult for standard elimination algorithms.
- UAI Linkage Dataset: A suite of real-world benchmarks from the UAI 2014 Inference Competition, based on genetic linkage analysis.
Key Results
In almost all tests, WMBE-G (especially when jointly optimizing gauges and Hölder weights) provided significantly tighter upper bounds than standard WMBE, TRBP, or Mini-Bucket Elimination.
As shown in the experimental results, the gap between WMBE-G and other methods widened as "interaction strength" ($T$) increased, demonstrating its effectiveness on "hard" instances where traditional methods struggle. Furthermore, the results suggest that optimizing the gauges is often more critical for accuracy than optimizing the Hölder weights alone. By using a specialized solver that alternates between updating gauges and factor values, the method scales better to large instances than previous gauge-variational approaches.
Conclusion
WMBE-G provides a powerful new tool for estimating the partition function by allowing for local flexibility—even allowing factors to take on "invalid" values—to reach a tighter global bound. While the current implementation relies on pre-defined elimination orders, future work integrating the optimization of these orders with gauge transformations could lead to even more precise inference results.
Summary updated