Belief Propagation in Conditional RBMs for Structured Prediction

Wei Ping, Alexander Ihler

Abstract

Restricted Boltzmann machines (RBMs) and conditional RBMs (CRBMs) are popular models for a wide range of applications. In previous work, learning on such models has been dominated by contrastive divergence (CD) and its variants. Belief propagation (BP) algorithms are believed to be slow for structured prediction on conditional RBMs and not as good as CD when applied in learning. In this work, we present a matrix-based implementation of belief propagation algorithms on CRBMs, which is easily scalable to tens of thousands of visible and hidden units. We demonstrate that, in both maximum likelihood and max-margin learning, training conditional RBMs with BP as the inference routine can provide significantly better results than current state-of-the-art CD methods on structured prediction problems.

Introduction

Restricted Boltzmann Machines (RBMs) and their conditional counterparts (CRBMs) are powerful undirected graphical models used to capture complex dependencies in data. However, training these models is notoriously difficult because they involve an "intractable partition function"—a normalization constant that is computationally impossible to calculate exactly for large-scale models.

Traditionally, researchers have relied on Contrastive Divergence (CD), which uses a few steps of MCMC sampling to approximate the gradient. While CD works well for generative RBMs, it often struggles with Conditional RBMs used in structured prediction (where the goal is to predict an output $v$ given an input $x$). In these cases, the distributions become "peaked" and multimodal, making sampling-based methods slow to converge or inaccurately capture the distribution. Belief Propagation (BP), a deterministic alternative, was previously dismissed as being too slow for the dense, fully-connected graphs found in RBMs.

Architectural comparison of standard RBM and Conditional RBM (CRBM).

Matrix-based Belief Propagation

The authors provide two major contributions to make BP viable for CRBMs:

  1. Matrix-based BP Implementation: Instead of standard graph-based implementations, the authors reformulated BP message-passing equations into compact matrix operations. This allows the algorithm to leverage highly optimized BLAS libraries and GPU acceleration, achieving speeds roughly 600x faster than traditional libraries like libDAI.
  2. Learning Frameworks: They integrated this efficient BP into two learning paradigms: MLE-BP (Maximum Likelihood Estimation using sum-product BP) and MSSVM (Marginal Structured SVM using "mixed-product" BP).

A key insight is the "High Signal" advantage: while BP often fails to converge in generative RBMs, the presence of observed features $x$ in CRBMs provides a stabilizing signal that makes BP much more reliable.

Experimental Results

The researchers evaluated their approach on benchmarks for structured prediction, including MNIST (image denoising and completion) and Caltech101 Silhouettes.

Performance Comparison

In almost all tests, MLE-BP and MSSVM outperformed state-of-the-art CD methods (CD-1, CD-10, and Persistent CD). For example, on occluded MNIST ($12 \times 12$), MLE-BP achieved a 3.117% error rate, compared to 3.483% for the best CD variant.

Test error comparison between MLE-BP and CD-10 across various levels of image occlusion.

As shown in the figure above, MLE-BP maintains a lower test error than CD-10 across various levels of image occlusion, proving it captures the underlying structure of the data more effectively than sampling-based approximations.

Efficiency and Scalability

On a standard laptop, 10 iterations of matrix-based BP on a model with 1,000 visible and 500 hidden units took only 0.5 seconds. This efficiency allows for practical training of large-scale models that were previously considered out of reach for BP.

Conclusion

This paper challenges the long-held belief that BP is unsuitable for RBM training. By introducing a highly optimized implementation and demonstrating its effectiveness in conditional settings, the authors show that BP-based learning significantly outperforms standard CD methods for structured prediction tasks. Future work will explore applying these techniques to deeper architectures like Deep Boltzmann Machines.

Summary updated

Abstract

Restricted Boltzmann machines (RBMs) and conditional RBMs (CRBMs) are popular models for a wide range of applications. In previous work, learning on such models has been dominated by contrastive divergence (CD) and its variants. Belief propagation (BP) algorithms are believed to be slow for structured prediction on conditional RBMs (e.g., Mnih et al. [2011]), and not as good as CD when applied in learning (e.g., Larochelle et al. [2012]). In this work, we present a matrix-based implementation of belief propagation algorithms on CRBMs, which is easily scalable to tens of thousands of visible and hidden units. We demonstrate that, in both maximum likelihood and max-margin learning, training conditional RBMs with BP as the inference routine can provide significantly better results than current state-of-the-art CD methods on structured prediction problems. We also include practical guidelines on training CRBMs with BP, and some insights on the interaction of learning and inference algorithms for CRBMs.
BibTeX
@inproceedings{ping2017belief,
  author = {Wei Ping and Alexander Ihler},
  title = {{Belief Propagation in Conditional RBMs for Structured Prediction}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=lno6u9GVwV},
}
Figure