TL;DR
This paper introduces a novel "relax-and-round" algorithm for efficiently finding approximate maximum a posteriori (MAP) configurations in Restricted Boltzmann Machines (RBMs). By leveraging semidefinite programming relaxations and randomized rounding, their method achieves competitive or superior results compared to existing sampling techniques, particularly in challenging scenarios with local optima.
What Problem Does This Paper Address?
Finding the most probable configuration (MAP) in a Markov Random Field (MRF), especially for complex models like Restricted Boltzmann Machines (RBMs), is a computationally hard problem (NP-hard). Traditional methods often involve exact inference, which is intractable for large models, or sampling-based approaches like Gibbs sampling that can get stuck in local optima. This paper aims to bridge this gap by developing an efficient approximate inference algorithm that can find high-probability configurations, even when standard sampling methods struggle. They also explore using this sampler for estimating the log-partition function, another challenging inference task.
Methods
The core of the paper is the randomized relax-and-round (rrr-MAP) algorithm. It starts by formulating the MAP inference problem as an Integer Quadratic Program (IQP). This IQP is then relaxed into a continuous optimization problem. The authors explore a spectrum of relaxations:
- Quadratic Program (QP) Relaxation: A simpler, linear-sized relaxation that is efficient but can be non-convex.
- Semidefinite Program (SDP) Relaxation: A convex relaxation that guarantees a global optimum for the relaxed problem but is computationally expensive due to its quadratic number of variables.
- Low-Rank Relaxations (LRPk): A family of intermediate relaxations that interpolate between the QP and SDP. These problems are generally non-convex and are solved using projected gradient descent to find stationary points.
Once a solution X is obtained from one of these relaxations, the randomized rounding step comes into play. A random vector g is drawn from the unit sphere, and the rows of X are projected onto g. The sign of these projections then forms the sampled configuration x. This process is repeated to generate multiple samples, and the one with the highest score is taken as the approximate MAP configuration.
Datasets
The paper evaluates their methods on RBMs trained on:
- MNIST: Using weights from a pre-trained RBM on the MNIST dataset (originally in {0,1} domain, adapted to {-1,1}).
- Random: RBMs with parameters (weights and biases) sampled independently from a standard Gaussian distribution.
- Hard: A specially constructed RBM designed to create deep local energy minima, intended to challenge Gibbs samplers.
Key Insights and Ideas
- Bridging the QP and SDP Gap: The introduction of LRPk relaxations offers a flexible trade-off between computational cost and the quality of the relaxation, allowing for more scalable approximate inference than full SDPs.
- Randomized Rounding as a Powerful Sampler: The rrr-MAP algorithm, by sampling from the solution of the relaxation, can effectively explore the configuration space and find near-MAP states, even in the presence of challenging local optima that trap traditional Gibbs samplers.
- RBMs as a Testbed: While the techniques are general to MRFs, RBMs provide a well-motivated and computationally tractable setting to demonstrate the effectiveness of their approach, especially due to their bipartite structure.
- Challenges in Log-Partition Function Estimation: The paper highlights that simply sampling near-MAP configurations doesn't automatically lead to accurate log-partition function estimates, suggesting that more sophisticated importance sampling strategies are needed for this specific task.
Key Results
- MAP Inference: The rrr-MAP sampler (using LRP2 relaxation) achieved comparable or better RBM scores (a measure of configuration quality) than annealed Gibbs sampling and even outperformed it on a "hard" RBM designed to trap Gibbs samplers.
- Comparison with Exact Solvers: For small instances, the rrr-MAP sampler provided scores close to those obtained by the Gurobi IQP solver, which finds the exact MAP solution, within a significantly shorter execution time.
- Log-Partition Function Estimation: While rrr-MAP sampling provided a lower bound for the log-partition function, its direct use for estimation via importance sampling was found to be less effective than standard annealed importance sampling, though still comparable in quality.
Limitations and Future Work
- Non-Convexity of LRPk: The LRPk relaxations are generally non-convex, meaning the optimization might find only a local optimum, not necessarily the global optimum of the relaxed problem. The paper relies on finding stationary points via projected gradient descent.
- Log-Partition Function Estimation: The authors acknowledge that their direct application of rrr-MAP for log-partition function estimation was not as effective as hoped, indicating a need for further research to improve its utility for this task.
- General MRFs: While the techniques are applicable to general MRFs, the paper focuses on RBMs. Further exploration of their performance on other types of MRFs, especially those where Gibbs sampling is less efficient, is suggested as future work.
Summary updated