Abstract: Conditional Restricted Boltzmann Machines (CRBMs) are rich probabilistic models that have recently been applied to a wide range of problems, including collaborative filtering, classification, and modeling motion capture data. While much progress has been made in training non-conditional RBMs, these algorithms are not applicable to conditional models and there has been almost no work on training and generating predictions from conditional RBMs for structured output problems. We first argue that standard Contrastive Divergence-based learning may not be suitable for training CRBMs. We then identify two distinct types of structured output prediction problems and propose an improved learning algorithm for each. The first problem type is one where the output space has arbitrary structure but the set of likely output configurations is relatively small, such as in multi-label classification. The second problem is one where the output space is arbitrarily structured but where the output space variability is much greater, such as in image denoising or pixel labeling. We show that the new learning algorithms can work much better than Contrastive Divergence on both types of problems.
Introduction
Structured output prediction involves predicting a set of variables with complex internal dependencies, such as labeling every pixel in an image or assigning multiple tags to a song. Conditional Restricted Boltzmann Machines (CRBMs) are powerful probabilistic models for these tasks. However, training them effectively for structured prediction remains a significant challenge.
The standard approach for training RBMs is Contrastive Divergence (CD), which was designed for unsupervised learning. In CD, a Markov chain starts at a data point and runs for a few steps to "reconstruct" the data. The authors argue that for conditional tasks (predicting $v$ given $u$), simple reconstruction is insufficient. A model might excel at reconstructing a noisy image if it has access to it, yet fail to predict a clean version from noisy input alone. Furthermore, techniques like Persistent CD (PCD) are mathematically incompatible with CRBMs because the model's distribution changes with every unique input $u$.
Proposed Methods
The paper introduces two novel training algorithms tailored to different output space characteristics:
1. HashCRBM (Limited Output Variability)
In tasks like multi-label classification, the number of possible label combinations is exponential, but the number of likely combinations is often small. HashCRBM uses Spectral Hashing to quickly retrieve a small set of candidate outputs from the training data that are "near" the current input. By restricting the model to this small set, the authors can perform exact gradient descent on the conditional likelihood, bypassing the need for noisy approximations like CD.
2. CD-PercLoss (High-Dimensional Outputs)
For tasks like image denoising where the output space is vast, the authors propose CD-PercLoss. Unlike standard CD, which starts a Gibbs chain at the ground-truth data, CD-PercLoss starts from a neutral or informed initialization to find the model's current "best guess" (prediction $\hat{v}$). The model is then updated to lower the energy of the true data and raise the energy of the prediction, directly penalizing incorrect predictions.
Experimental Results
The methods were evaluated on multi-label classification (Yeast, Scene, MTurk, MajMin) and image denoising using two variants of the MNIST database: Corrupted MNIST (10% noise) and Occluded MNIST (8x8 patch deleted).
As shown in the results for the Occluded MNIST dataset, standard CD-1 and CD-10 training performed poorly, even falling behind simple logistic regression on occluded pixels. In contrast, CD-PercLoss achieved a significantly lower error rate, successfully learning to "fill in" missing structures by capturing global dependencies. For multi-label tasks, HashCRBM consistently ranked among the top performers, showing particularly strong gains on the Scene dataset compared to standard CRBMs and CRFs.
Conclusion
This work demonstrates that moving beyond simple reconstruction to focus on predictive performance is crucial for training CRBMs in structured output settings. By addressing the "mixing trap" of standard CD, the proposed HashCRBM and CD-PercLoss algorithms provide more robust frameworks for complex prediction tasks. Future work includes exploring max-margin versions of these algorithms and incorporating additional regularization techniques to further improve generalization.
Summary updated