To Relieve Your Headache of Training an MRF, Take AdVIL

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

Training Markov Random Fields (MRFs) has long been a notorious "headache" in machine learning. Between intractable partition functions and the struggle of dealing with latent variables, researchers often find themselves reaching for model-specific hacks. At ICLR 2020, a team from Tsinghua University and the University of Amsterdam proposed a new prescription: AdVIL (Adversarial Variational Inference and Learning).

TL;DR

AdVIL is a "black-box" algorithm that simplifies training general Markov Random Fields by framing the problem as a minimax (adversarial) game. By using two separate neural networks to approximate latent variables and the global normalizing constant, it provides a tighter, more stable estimate of the model's likelihood than previous black-box methods.

What Problem Does This Paper Address?

Markov Random Fields (MRFs) are powerful undirected graphical models used in everything from computer vision to language processing. However, they suffer from two major computational bottlenecks:

  1. Inference: If the model has latent (hidden) variables, calculating their posterior distribution is usually impossible.
  2. Learning: MRFs are defined by an energy function, but to turn that energy into a probability, you must divide by a "partition function" ($Z$)—an integral over all possible states that is almost always intractable.

Traditional methods like Contrastive Divergence (CD) rely on Gibbs sampling, which is slow and requires a deep understanding of the specific model structure to implement. A more recent "black-box" approach called NVIL attempted to solve this using variational bounds, but it often suffers from high variance and tends to underestimate the partition function, leading to poor performance on complex data.

Methods

The authors introduce a "double variational trick" to tackle both the positive and negative phases of MRF training simultaneously:

  • The Variational Encoder ($Q$): A neural network that approximates the posterior of latent variables. This provides an upper bound on the "free energy" (the positive phase of training).
  • The Variational Decoder ($q$): A second network that acts as an approximate sampler for the MRF. This provides a lower bound on the log-partition function (the negative phase).
Graphical representation of the variational encoder Q, the MRF model P, and the variational decoder q.

By combining these, the authors reformulate the Negative Log-Likelihood (NLL) as a minimax optimization problem, similar to a Generative Adversarial Network (GAN). In this game, the model parameters and the encoder try to minimize the objective, while the decoder (the "adversary") tries to maximize it by providing the tightest possible estimate of the partition function.

To ensure the decoder is flexible enough to match complex MRFs, the authors also introduce an auxiliary variable ($z$) and a third variational distribution ($r$) to approximate the decoder's entropy, ensuring the "adversary" remains competitive throughout training.

Datasets

The authors evaluated AdVIL across several generative modeling tasks:

  • Digits: A standard small-scale image dataset.
  • UCI Binary Databases: Eight diverse datasets including Adult, Connect4, DNA, Mushrooms, NIPS-0-12, Ocr-letters, and RCV1.
  • Frey Faces: A dataset of continuous face images used to test Gaussian Restricted Boltzmann Machines (GRBMs).

Key Insights and Ideas

  • The Adversarial Connection: The paper elegantly shows that the classic "contrastive free energy" objective can be viewed as an adversarial game between an inference network and a sampling network.
  • Black-Box Flexibility: Unlike CD, AdVIL doesn't care about the specific structure of your MRF. As long as you can define an energy function, AdVIL can (theoretically) train it without model-specific derivations.
  • Stability through Bounds: By using a lower bound for the log-partition function, AdVIL avoids the catastrophic underestimation issues that plagued NVIL, leading to much more stable convergence.
Training curves demonstrating the tightness of the variational bounds for free energy and the partition function over iterations.
  • Theoretical Convergence: The authors provide a formal proof that AdVIL converges to a stationary point of the evidence lower bound (ELBO) under certain conditions, providing a mathematical safety net for the adversarial training process.

Key Results

  • Outperforming NVIL: In Restricted Boltzmann Machine (RBM) experiments across all eight UCI datasets, AdVIL consistently achieved better log-likelihood results than NVIL, often by a significant margin.
  • Handling Intractability: On Deep Boltzmann Machines (DBMs)—where standard CD is not applicable because the latent variables are too complex—AdVIL outperformed Variational Contrastive Divergence (VCD).
  • Visual Quality: On the Frey Faces dataset, the filters learned by AdVIL-trained models showed clear, diverse facial prototypes, and the model was able to generate realistic samples through efficient ancestral sampling.

Limitations and Future Work

While AdVIL is a significant step forward, the authors note a few remaining "aches":

  • Computational Cost: The inner loop of the minimax game (updating the decoder) can be expensive. In their DBM experiments, AdVIL was roughly ten times slower than the VCD baseline.
  • High-Dimensional Scaling: While AdVIL handles UCI-scale data well, the authors acknowledge that training MRFs on very high-dimensional data (like high-res images) remains an open challenge.
  • Optimization Sensitivity: Like GANs, the performance of AdVIL can be sensitive to hyperparameters, such as the number of decoder updates per model update ($K_1$).

In summary, AdVIL offers a principled, black-box alternative to traditional MRF training, proving that a little bit of adversarial competition can go a long way in solving some of the oldest headaches in probabilistic modeling.

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