Abstract
We examine the effect of clamping variables for approximate inference in undirected graphical models with pairwise relationships and discrete variables. For any number of variable labels, we demonstrate that clamping and summing approximate sub-partition functions can lead only to a decrease in the partition function estimate for TRW, and an increase for the naive mean field method, in each case guaranteeing an improvement in the approximation and bound. We next focus on binary variables, add the Bethe approximation to consideration and examine ways to choose good variables to clamp, introducing new methods. We show the importance of identifying highly frustrated cycles, and of checking the singleton entropy of a variable. We explore the value of our methods by empirical analysis and draw lessons to guide practitioners.
Introduction
In undirected graphical models, such as Markov Random Fields, computing the partition function $Z$ is a fundamental yet computationally daunting task. As a normalizing constant for probability distributions, $Z$ is essential for inference, but its exact calculation is NP-hard for most non-trivial topologies. Consequently, researchers often turn to variational approximations. Two prominent methods are the Tree-Reweighted (TRW) belief propagation, which provides an upper bound on $\log Z$, and the Naive Mean Field (MF) method, which provides a lower bound.
"Clamping" (or conditioning) is a strategy to refine these approximations. By fixing a variable to each of its possible states, solving the resulting sub-problems, and summing their approximate partition functions, one intuitively expects a better overall estimate. While this intuition is widely held, formal guarantees have been limited. This paper provides the first general theoretical proofs that clamping always improves TRW and MF bounds and introduces novel heuristics for selecting the most impactful variables to clamp.
Theoretical Guarantees
The core theoretical contribution of this work is establishing that clamping is mathematically guaranteed to tighten the bounds for both TRW and MF in any pairwise discrete model. Specifically:
- Theorem 2 (TRW): Clamping any variable and summing the approximate sub-partition functions is guaranteed to decrease (or leave unchanged) the TRW upper bound.
- Theorem 4 (MF): Clamping any variable and summing the approximate sub-partition functions is guaranteed to increase (or leave unchanged) the MF lower bound.
These results hold for any number of variable labels, providing a solid foundation for using clamping as a general-purpose refinement technique. From a geometric perspective, clamping in TRW can be viewed as tightening the local polytope relaxation, bringing the approximation closer to the true marginal polytope.
Heuristics for Variable Selection
Since clamping $k$ variables requires solving $L^k$ sub-problems (where $L$ is the number of labels), selecting the "best" variables is critical for efficiency. The authors propose several innovative heuristics:
Stripping to the Core
Approximation errors in TRW and MF primarily originate from cycles in the graph; trees are solved exactly. The "Stripping to the Core" heuristic involves iteratively pruning nodes with degree 1 until only the cyclic "core" remains. This allows selection heuristics to focus on the parts of the graph where clamping will yield the most significant error reduction.
Frustrated Cycle Search
The authors identify "frustrated cycles"—cycles with an odd number of repulsive (negative) edges—as major sources of error for Bethe and TRW approximations. They introduce heuristics like frustCycles and strongCycles to find variables involved in these problematic structures.
TRW Entropy (TRE)
A variable's singleton entropy indicates how "fixed" it already is by its own potentials. If a variable is nearly deterministic, clamping it provides little benefit. The TRE heuristic weights other selection criteria by the variable's singleton entropy to prioritize variables with high uncertainty.
Empirical Evaluation and Results
The methods were tested on various synthetic models, including toroidal grids, random 4-regular graphs, and complete graphs ($K_{10}, K_{15}$), featuring both attractive and mixed potentials.
The experiments confirmed that the new frustCycles and TRE-augmented heuristics consistently outperform traditional methods like maxW (maximum edge weight). Notably, the authors found that for dense, mixed models with strong frustration, Mean Field can be more accurate than the Bethe approximation, as Bethe's error can grow unbounded while MF's remains constrained.
Furthermore, while clamping increases the number of sub-problems, it often simplifies the optimization landscape for each sub-problem, leading to faster convergence. In some cases, the total runtime for a clamped problem was lower than for the original unclamped problem.
Conclusion
This work provides both the theoretical justification and practical tools for using clamping to improve variational inference. By proving guaranteed improvements for TRW and MF and introducing heuristics that target the structural sources of approximation error, the authors offer a robust framework for practitioners. Future work includes extending these guarantees to the Bethe approximation for mixed models and optimizing heuristic search for massive-scale graphs.
Summary updated