Abstract
Information projections are the key building block of variational inference algorithms and are used to approximate a target probabilistic model by projecting it onto a family of tractable distributions. In general, there is no guarantee on the quality of the approximation obtained. To overcome this issue, we introduce a new class of random projections to reduce the dimensionality and hence the complexity of the original model. In the spirit of random projections, the projection preserves (with high probability) key properties of the target distribution. We show that information projections can be combined with random projections to obtain provable guarantees on the quality of the approximation obtained, regardless of the complexity of the original model. We demonstrate empirically that augmenting mean field with a random projection step dramatically improves partition function and marginal probability estimates, both on synthetic and real world data.
Introduction
A fundamental challenge in probabilistic machine learning is the computation of the partition function ($Z$), the normalization constant required to transform raw model scores into valid probabilities. For complex graphical models, such as Ising models or Deep Belief Networks, calculating $Z$ is #P-hard, necessitating the use of approximate inference techniques.
Variational Inference (VI) is a popular approach that approximates a complex target distribution $p$ by finding the "closest" distribution within a simpler, tractable family (e.g., fully factored Mean Field distributions). While computationally efficient, standard VI lacks theoretical guarantees; the resulting lower bound on the partition function can be arbitrarily loose, with no mechanism to assess the approximation's quality in practice.
The MFRP Framework
To address these limitations, we introduce Mean Field with Random Projections (MFRP). This method bridges the gap between theoretical computer science and variational inference by incorporating random XOR constraints—a form of universal hashing—into the inference process.
The MFRP workflow involves three key steps:
- Random Projection: We apply sets of random linear constraints (parity checks) to the original model. These constraints effectively "subsample" the state space in a statistically predictable manner.
- Constrained Optimization: We perform Mean Field inference on these simplified, constrained models using a coordinate-wise ascent algorithm tailored for hard parity constraints.
- Aggregation: The results from multiple projected models are aggregated (typically using the median) to recover a provably tight estimate of the original partition function.
By reducing the complexity of the distribution before projection, random projections ensure that the target distribution becomes "closer" to the simple families used in VI, leading to significantly tighter bounds.
Experimental Evaluation
We evaluated MFRP on two primary benchmarks:
- Ising Models: Synthetic $n \times n$ binary grids with random interactions, serving as a standard testbed for inference algorithms.
- Restricted Boltzmann Machines (RBMs): Generative neural networks trained on the MNIST dataset of handwritten digits.
Results and Discussion
MFRP demonstrates substantial improvements over standard variational techniques in both accuracy and theoretical robustness.
Provable Tightness and Accuracy
The most striking result is the magnitude of improvement in partition function estimation. On large Ising grids, MFRP provides lower bounds that are hundreds of orders of magnitude tighter than those from standard Mean Field. Crucially, we prove that MFRP provides a constant-factor approximation (specifically, a 32-approximation) with high probability, regardless of the model's underlying complexity.
Qualitative Improvements
On MNIST-trained RBMs, MFRP's superior marginal probability estimates translate to clearer digit reconstructions. While standard Mean Field often produces blurry averages, MFRP captures the multi-modal nature of the data more effectively.
Scalability
Despite the overhead of managing XOR constraints, MFRP remains computationally practical. The runtime scales linearly with the number of variables, ensuring it can be applied to large-scale machine learning problems.
Conclusion
MFRP represents a significant step forward in providing reliable approximate inference. By combining the strengths of random projections and information projections, we can obtain provably tight bounds on the partition function. Future work includes extending this framework to more sophisticated variational families, such as the Bethe approximation, and addressing the non-convexity of the underlying optimization problem to further improve global convergence.
Summary updated