TL;DR
This paper extends previous work showing that the Bethe partition function provides a lower bound for certain graphical models. The authors demonstrate how to transform non-log-supermodular models into equivalent log-supermodular ones, thereby proving that the Bethe approximation is a lower bound for a broader class of models, including the ferromagnetic Potts model and weighted graph homomorphism problems. This work is significant because it expands the applicability of theoretical guarantees for the Bethe approximation, a crucial tool in statistical inference.
What Problem Does This Paper Address?
The core problem this paper tackles is understanding the relationship between the true partition function of a graphical model and its approximation using the Bethe partition function. Computing the exact partition function for arbitrary graphical models is NP-hard. The Bethe partition function, derived from statistical physics and related to the belief propagation algorithm, is a popular approximation. However, it's not always clear whether the Bethe approximation is an upper or lower bound for the true partition function. Previous work established that for binary, log-supermodular graphical models, the Bethe partition function is always a lower bound. This paper aims to generalize this crucial lower bound guarantee to models that are not necessarily binary or log-supermodular.
Methods
The paper's central methodological contribution lies in transforming models that are not inherently log-supermodular into equivalent log-supermodular models. This is achieved through various techniques:
- Variable Switching: For certain models, changing the state space of some variables (e.g., mapping $x_i$ to $1-x_i$) can convert a log-submodular function into a log-supermodular one. This is particularly useful for bipartite graphs.
- Equivalence to Log-Supermodular Models: The authors show that the partition functions of several complex models (like the ferromagnetic Potts model and weighted graph homomorphisms) can be equivalently formulated as the partition functions of log-supermodular graphical models, often over different factor graphs or state spaces. This equivalence is key, as it allows the application of existing theorems for log-supermodular models.
- Graph Covers and Combinatorial Characterization: The paper leverages Vontobel's (2013) combinatorial characterization of the Bethe partition function, which relates it to averages over graph covers. By proving bounds on the partition functions of individual graph covers of the transformed log-supermodular models, they can then bound the Bethe partition function of the original model.
- Theorem 3.4 (Correlation Inequality): This theorem is a crucial tool for proving inequalities between products of functions and sums of functions, particularly when dealing with log-supermodular functions.
Datasets
Not discussed in the paper. The paper focuses on theoretical results and general classes of graphical models rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Log-Supermodularity is "Recognizable": The paper echoes Lovász's sentiment that log-supermodularity, while not a "deep" property, can be "difficult to recognize." The core insight is that many seemingly non-log-supermodular models can be transformed into equivalent log-supermodular ones, revealing hidden structure.
- Equivalence is the Key: The ability to show that the partition function of a complex model is exactly equal to the partition function of a log-supermodular model is the linchpin. This allows the theoretical guarantees of log-supermodularity to be applied indirectly.
- Generalizing Lower Bounds: The paper successfully extends the Bethe partition function's lower bound guarantee beyond binary and strictly log-supermodular models to important classes like the ferromagnetic Potts model and weighted graph homomorphisms. This broadens the applicability of theoretical guarantees for belief propagation.
- Beyond Simple Variable Swaps: While variable switching is useful, the paper demonstrates that more sophisticated transformations are sometimes needed to reveal the underlying log-supermodularity.
Key Results
The paper establishes that for several classes of graphical models, the Bethe partition function provides a provably tighter lower bound than the naive mean-field approximation. Specifically:
- Ferromagnetic Potts Model (with uniform external field): The Bethe partition function is shown to be a lower bound for the true partition function.
- Generalizations of Potts Models: This includes certain weight enumerators of linear codes and models defined on matroids.
- Weighted Graph Homomorphisms: For models where the potential matrix is of the form $\Gamma = aa^T + bb^T$, the Bethe partition function is a lower bound.
Limitations and Future Work
- Arbitrary External Fields: The paper explicitly notes that the lower bound guarantee for the ferromagnetic Potts model does not hold for arbitrary external fields, providing a counterexample. This suggests that the structure of external fields is critical.
- Computational Intractability: While the paper proves theoretical bounds, computing the partition function of log-supermodular models is generally intractable. The focus is on the theoretical relationship between the Bethe approximation and the true partition function, not on efficient computation for these specific models.
- Future Directions: The paper's approach of transforming models into log-supermodular equivalents suggests that further exploration of such transformations could yield more general theoretical guarantees for the Bethe approximation across a wider range of graphical models. Investigating the precise conditions under which these transformations are possible and how they relate to the structure of the original model would be a natural next step.
Summary updated