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.
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:
- Maximum Likelihood Estimation (MLE): Sum-product BP estimates gradients.
- 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.
- 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