To Relieve Your Headache of Training an MRF, Take AdVIL

Chongxuan Li, Chao Du, Kun Xu, Max Welling, Jun Zhu, Bo Zhang

Abstract

We propose a black-box algorithm called Adversarial Variational Inference and Learning (AdVIL) to perform inference and learning on a general Markov random field (MRF). AdVIL employs two variational distributions to approximately infer the latent variables and estimate the partition function of an MRF, respectively. The two variational distributions provide an estimate of the negative log-likelihood of the MRF as a minimax optimization problem, which is solved by stochastic gradient descent. AdVIL is proven convergent under certain conditions. On one hand, compared with contrastive divergence, AdVIL requires a minimal assumption about the model structure and can deal with a broader family of MRFs. On the other hand, compared with existing black-box methods, AdVIL provides a tighter estimate of the log partition function and achieves much better empirical results.

Introduction

Markov Random Fields (MRFs) are powerful undirected graphical models used to capture complex dependencies in data. However, training them is notoriously difficult due to the intractable partition function—a global normalizing constant that ensures probabilities sum to one. Calculating this constant requires summing or integrating over every possible state of the system, which is computationally impossible for most real-world applications.

When latent (hidden) variables are introduced, the complexity doubles: one must approximate both the posterior of the hidden states and the partition function. Traditional methods like Contrastive Divergence (CD) are "white-box" approaches, requiring model-specific derivations. Conversely, recent "black-box" methods like NVIL often suffer from high variance and tend to underestimate the partition function in high-dimensional spaces, leading to unstable training and poor performance.

The AdVIL Framework

To address these challenges, we propose AdVIL, which utilizes a "double variational trick" to handle latent variables and the partition function simultaneously. The framework consists of three primary components:

  1. The Variational Encoder ($Q$): This network approximates the posterior distribution of the latent variables $h$ given observed data $v$, providing an upper bound on the model's "free energy."
  2. The Variational Decoder ($q$): This network acts as an approximate sampler for the MRF itself, providing a lower bound on the log partition function.
  3. Auxiliary Variables ($z$): To ensure the decoder is expressive enough to track complex MRFs, we introduce auxiliary variables $z$. This allows the decoder to capture intricate correlations that simpler distributions might miss.
The AdVIL architecture showing the variational encoder $Q$, the MRF model $P$, and the variational decoder $q$ with auxiliary variables $z$.

Training is framed as a minimax optimization problem. The model parameters and the encoder work together to minimize the objective, while the decoder works to maximize it, effectively tightening the bound on the partition function. This "black-box" nature allows users to define only the model's energy function, leaving the algorithm to handle optimization via stochastic gradient descent.

Empirical Evaluation and Results

We evaluated AdVIL across diverse benchmarks, including the UCI binary databases, Digits, and the Frey Faces dataset for continuous data. A key finding is the stability of AdVIL's "sandwich bound." By bounding the free energy from above and the partition function from below, AdVIL creates a stable training signal that prevents the divergence issues common in previous black-box methods.

Convergence of AdVIL's variational bounds for free energy, entropy, and the partition function over training iterations.

Key Findings:

  • Superior Accuracy: AdVIL consistently outperformed NVIL on UCI datasets. While NVIL often diverged, AdVIL remained stable and provided more accurate log-likelihood estimates.
  • Complexity Handling: In Deep Boltzmann Machines (DBMs), AdVIL outperformed traditional variational baselines, demonstrating its ability to handle multi-layer latent structures.
  • Generative Quality: On the Frey Faces dataset, AdVIL successfully learned meaningful facial filters and generated realistic samples, proving its efficacy on high-dimensional continuous data.
  • Theoretical Convergence: We provide formal proof that AdVIL converges to a stationary point of the evidence lower bound (ELBO), offering a theoretical safety net for practitioners.

Conclusion and Future Work

AdVIL offers a robust, black-box solution for training MRFs, relieving the "headache" of manual derivations and unstable partition function estimates. While it introduces some computational overhead—the decoder must be updated multiple times for every model update—the gains in stability and accuracy are significant. Future research will focus on accelerating the "inner loop" of decoder updates using advanced non-convex optimization techniques to make AdVIL even more practical for massive, high-dimensional datasets.

Summary updated

Abstract

We propose a black-box algorithm called {\it Adversarial Variational Inference and Learning} (AdVIL) to perform inference and learning on a general Markov random field (MRF). AdVIL employs two variational distributions to approximately infer the latent variables and estimate the partition function of an MRF, respectively. The two variational distributions provide an estimate of the negative log-likelihood of the MRF as a minimax optimization problem, which is solved by stochastic gradient descent. AdVIL is proven convergent under certain conditions. On one hand, compared with contrastive divergence, AdVIL requires a minimal assumption about the model structure and can deal with a broader family of MRFs. On the other hand, compared with existing black-box methods, AdVIL provides a tighter estimate of the log partition function and achieves much better empirical results.
BibTeX
@inproceedings{li2020relieve,
  author = {Chongxuan Li and Chao Du and Kun Xu and Max Welling and Jun Zhu and Bo Zhang},
  title = {{To Relieve Your Headache of Training an MRF, Take AdVIL}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=lZa9z3l6M55},
}
Figure