Belief Propagation in Conditional RBMs for Structured Prediction

Wei Ping, Alexander Ihler

Abstract

Restricted Boltzmann machines (RBMs) and their conditional counterparts (CRBMs) are versatile models for structured prediction, but their training has traditionally relied on Contrastive Divergence (CD) due to the perceived inefficiency and instability of Belief Propagation (BP). This paper introduces a matrix-based implementation of BP for CRBMs that scales to large-scale problems. We demonstrate that BP-based training, in both maximum likelihood and max-margin settings, significantly outperforms state-of-the-art CD methods in tasks like image denoising and completion.

Introduction

Training RBMs is challenging because the partition function is mathematically intractable. While Contrastive Divergence (CD) using Gibbs sampling is the standard approximation, it faces difficulties in Conditional RBMs (CRBMs). In CRBMs, the model predicts an output $y$ given input features $x$. Using Persistent CD (PCD) becomes computationally prohibitive as each unique input requires maintaining a separate Markov chain.

Historically, Belief Propagation (BP) was dismissed for being slow and prone to non-convergence in dense bipartite graphs like RBMs. This work revitalizes BP by providing a highly efficient matrix-based implementation and showing that the "high signal" from observed features in CRBMs actually aids BP convergence.

Comparison of (a) standard RBM and (b) Conditional RBM architectures.

Efficient Matrix-Based Belief Propagation

The core contribution is a reformulation of BP updates—specifically sum-product and mixed-product BP—into matrix operations. By avoiding node-by-node loops and leveraging optimized linear algebra libraries, the authors achieved a 600x speedup over standard factor graph libraries like libDAI. This efficiency allows BP to be used as a routine inference step during training.

The method is applied in two learning frameworks:

  1. Maximum Likelihood Estimation (MLE): Sum-product BP estimates gradients.
  2. Marginal Structured SVM (MSSVM): Mixed-product BP handles max-margin learning with latent variables.

Experimental Evaluation

The approach was tested on MNIST and Caltech101 Silhouettes for structured prediction tasks such as image denoising and completion.

Key Findings

  • Superior Accuracy: MLE-BP consistently outperformed CD variants. On MNIST with 20% noise, MLE-BP reached a 3.69% error rate, surpassing CD-10's 3.99%.
  • Robustness to Occlusion: BP-based methods are notably more robust when large portions of the input are missing. As shown in the test error comparison, MLE-BP maintains lower test error across various occlusion levels compared to CD-10.
Test error comparison between MLE-BP and CD-10 across different occlusion levels on MNIST.
  • Practical Training Tips:
    • Matching Inference: It is critical to use the same inference method at test time as was used during training. Mixing methods leads to poor results.
  • Dynamic Iterations: The authors recommend increasing BP iterations linearly with epochs, as convergence becomes harder as weights grow.

Conclusion

This work demonstrates that Belief Propagation is not only viable but superior to sampling-based methods for training Conditional RBMs. The proposed matrix-based implementation overcomes previous speed barriers, while the conditional nature of the task mitigates convergence issues. Future work includes extending these techniques to Deep Boltzmann Machines and GPU implementations.

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