TL;DR
This paper introduces a novel method for computing lower bounds on the log partition function of Markov Random Fields (MRFs) by leveraging a "reversed Jensen's inequality" with negative weights on spanning trees. This new approach unifies and extends existing methods like Tree-Reweighted Belief Propagation (TRBP) and mean field approximations, offering a more flexible framework for approximate inference and learning.
What Problem Does This Paper Address?
A fundamental challenge in probabilistic graphical models, particularly MRFs with cyclic dependencies, is computing the log partition function. This value is crucial for tasks like learning model parameters from data. For tree-structured graphs, this is efficient, but for general graphs, it becomes computationally intractable (exponential in graph treewidth). Existing methods offer either upper bounds (like TRBP) or lower bounds (like mean field), but TRBP's optimization is convex while mean field's is often non-convex, and they are typically viewed as separate. The paper aims to bridge this gap by developing a unified framework that provides guaranteed lower bounds and connects these seemingly disparate approaches.
Methods
The core contribution is the introduction of a "negative Tree Reweighted Belief Propagation" (negTRBP) algorithm. This method uses a reversed Jensen's inequality, allowing for a linear combination of spanning trees with negative weights. This contrasts with standard TRBP, which uses positive weights and Jensen's inequality to derive upper bounds.
Key aspects of the method include:
- Reversed Jensen's Inequality: This mathematical tool is central to deriving the lower bound. It allows for the use of negative weights on spanning trees, which is crucial for obtaining a lower bound.
- Negative Weights: Unlike TRBP, which uses a convex combination of spanning trees (positive weights), negTRBP employs a combination that can include negative weights. This shifts the guarantee from an upper bound to a lower bound.
- Non-Convex Optimization: The optimization problem for finding the best weights in negTRBP is non-convex. The paper proposes message-passing algorithms to find local optima, similar to loopy belief propagation.
- Generalization of Mean Field: The paper demonstrates that naive and structured mean field approximations are limiting cases of their proposed framework. This provides a theoretical connection between these methods.
- Message Passing Algorithm: A fixed-point message-passing algorithm is derived to optimize the bound. This algorithm is shown to be robust and can be used to find local maxima of the objective function.
- Weight Optimization: The paper also proposes a method to optimize the weights, including a heuristic for selecting the "positive tree" (which acts as a bridge between subdomains of negative weights) using the Chow-Liu algorithm.
Datasets
Not discussed in the paper. The experiments are conducted on synthetic Ising models.
Key Insights and Ideas
- Unified Framework for Bounds: The paper elegantly unifies upper and lower bound methods for the log partition function by showing they arise from the same underlying structure but differ in the sign of the weights used for spanning trees.
- Negative Weights Unlock Lower Bounds: The key insight is that by using a reversed Jensen's inequality and allowing negative weights on spanning trees, one can derive guaranteed lower bounds, complementing existing upper bound techniques.
- Mean Field as a Limiting Case: Demonstrating that mean field methods are a special case of negTRBP provides a powerful theoretical link and explains why mean field is a lower bound.
- Non-Convexity as a Feature, Not Just a Bug: While non-convex optimization is often a challenge, the paper shows how to leverage it to find tighter lower bounds, and that local optima can be meaningful.
- Adaptive Structure Selection: The ability to adaptively choose the "positive tree" structure during optimization allows the algorithm to improve its bounds by focusing on the most relevant dependencies.
Key Results
- Significant Improvement over Naive Mean Field: Experiments on Ising models show that negTRBP provides a substantial improvement over naive mean field, typically achieving about twice the accuracy in terms of the lower bound.
- Tighter Bounds with Adaptive Structure: Updating the choice of the positive tree using a Chow-Liu heuristic significantly tightens the lower bound, demonstrating the benefit of adaptive structure selection.
- Theoretical Connection: The paper establishes that structured mean field with v-acyclic subgraphs is a limiting case of their negative TRBP algorithm.
Limitations and Future Work
- Combinatorial Optimization of Positive Tree: The paper acknowledges that finding the optimal positive tree structure is a challenging combinatorial problem, and the proposed heuristic is a practical approach rather than a guaranteed optimal solution.
- Non-Convexity and Local Optima: While the paper provides algorithms to find local optima, the inherent non-convexity means that finding the global optimum is difficult. Multiple restarts might be necessary.
- Further Tightening of Bounds: The authors suggest that exploring ways to further tighten the bounds remains an open question.
- Relationship to b-acyclic Structured Mean Field: The connection to b-acyclic structured mean field is mentioned as an area for future exploration.
- Understanding Saddle Points: The paper notes that stationary points in negTRBP can correspond to saddle points of the approximate free energy, suggesting further theoretical analysis is needed.
Summary updated