Introduction
In probabilistic graphical models, the partition function ($Z$) is the fundamental normalization constant required to transform raw weights into valid probabilities. However, calculating $Z$ is notoriously difficult as it involves summing over a state space that grows exponentially with the number of variables. Traditional methods like Importance Sampling (IS) often fail in high-dimensional spaces because they rely on point-based samples; if the proposal distribution misses high-weight regions, the resulting estimates suffer from massive variance and error.
Importance Sampling over Sets (ISS) addresses this "needle in a haystack" problem by replacing individual sample points with entire subsets of states. By transforming the integration problem into a more manageable optimization task, ISS provides a scalable framework for estimating partition functions and learning models with up to a million variables.
The ISS Framework
Instead of sampling a single configuration $x$, the ISS algorithm samples a subset $S \subseteq \mathcal{X}$. The core methodology involves several key innovations:
- Set-Proposal Distributions: The algorithm utilizes strategies like Clamping (randomly fixing a subset of variables) and Parity Constraints (using randomized XOR hashing) to define large, representative subsets.
- The "Max" Trick: Summing over a massive set $S$ remains computationally expensive. ISS leverages the fact that the weight of the heaviest configuration (the mode) in a set can provide a rigorous lower bound for the partition function. This effectively converts an inference problem (summation) into an optimization problem (finding the maximum).
- Adaptive Sampling: ISS is iterative, using high-weight states discovered in early rounds to refine the proposal distribution and focus on the most important regions of the state space.
- Learning via Cutting Planes: For model training, ISS is integrated into a maximum likelihood framework. By treating ISS estimates as an optimization oracle, the authors employ a cutting-plane method to learn model parameters efficiently.
Experimental Evaluation
The authors evaluated ISS against standard baselines, including Belief Propagation (BP), Mean Field (MF), and naive Importance Sampling (IS), across several benchmarks such as Ising models from the 2011 Probabilistic Inference Challenge and massive attractive Ising grids.
As shown in Figure 1, ISS consistently outperforms traditional methods as coupling strength increases. While the accuracy of BP, MF, and IS degrades significantly in strongly coupled systems, ISS maintains a stable, low-error estimate.
Furthermore, ISS demonstrates remarkable scalability. In tests on Ising grids ranging from $10 \times 10$ to $1000 \times 1000$ (one million variables), ISS was the only method capable of handling the largest models within reasonable time constraints.
Key Insights and Discussion
- Variance Reduction: By considering exponentially large subsets, ISS is significantly more likely to capture high-probability regions than point-based sampling, leading to more stable estimates.
- Optimization as a Proxy: ISS leverages fast modern solvers (like Graph Cuts or CPLEX) to solve integration problems, allowing it to scale to models orders of magnitude larger than those accessible to BP or MF.
- Universal Guarantees: Linked to randomized hashing theory, ISS can provide constant-factor approximations for any weight function, regardless of structure, provided sufficient samples are taken.
Limitations
Despite its strengths, ISS depends on the efficiency of the underlying "MAP oracle." If finding the maximum weight in a subset is itself intractable, ISS performance will suffer. Additionally, the "max" trick provides a lower bound that may be loose if the distribution is "flat" rather than "peaky." Future work aims to extend this framework to latent variable models, such as full Restricted Boltzmann Machine (RBM) training.
Summary updated