Source-linked AI summary
Conditional Restricted Boltzmann Machines for Structured Output Prediction
Volodymyr Mnih, Hugo Larochelle, Geoffrey E. Hinton
TL;DR
Structured output prediction with conditional RBMs has seen little work, and standard Contrastive Divergence may not train these models well. The paper proposes separate algorithms for limited- and high-variability output spaces; the authors report better performance than alternatives in the settings each algorithm targets.
Problem
Method
The paper proposes semantic-hashing-based exact inference for limited output variability and perceptron-like training for high-dimensional, highly variable outputs.
Source: §1 · pp. 1–2Results
The proposed algorithms perform better than alternative methods in their appropriate regimes, and CD-PercLoss yields 20% lower error on deleted Occluded MNIST pixels than models trained with CD.
Source: §6.2.1 · p. 7, §7 · p. 8Takeaways & Limitations
The paper concludes that two training algorithms can outperform alternatives across the distinct structured-output regimes they target.
Source: §7 · p. 8Contrastive Divergence can produce a small training objective when its Gibbs chain mixes slowly, without guaranteeing good predictions.
Source: §5 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
Structured output prediction with RBMs has received little attention, especially when output interactions lack simplifying structure and the number of possible configurations is large. The paper proposes different CRBM learning algorithms for low- and high-variability output spaces.
1 Introduction
- Structured output prediction without simple interaction assumptions includes multi-label classification and image labeling.Multi-label examples may belong to several classes, while image labeling assigns labels to pixels or regions.Source: §1 · p. 1
- For large output spaces, exact gradients are intractable, and prior CRBM training relied on Contrastive Divergence.The passage says existing improved RBM algorithms for large output spaces do not apply to CRBMs.Source: §1 · p. 1
- For limited output variability, semantic hashing identifies a small set of likely outputs, enabling exact inference under the CRBM energy function.Multi-label classification is given as an example of this setting.Source: §1 · pp. 1–2
- For high-dimensional, highly variable outputs such as denoising and image labeling, the paper proposes perceptron-like CRBM training.The authors report that CD-based training fails to find a good denoising solution while perceptron-based training succeeds.Source: §1 · p. 2
2 Training RBMs
The section reviews RBM energy-based modeling and learning, then explains Contrastive Divergence and persistent-chain alternatives. It notes that persistent-chain methods do not transfer to conditional RBMs.
2.1 Restricted Boltzmann Machines
- An RBM defines a distribution over visible variables v and hidden variables h, with an energy function parameterized by their pairwise weights and biases.The visible distribution is obtained by marginalizing over hidden variables.Source: §2.1 · p. 2
- RBM learning uses negative log-likelihood gradients whose model-distribution expectation is intractable except for the smallest models.The positive gradient is tractable, while the negative gradient can be estimated with MCMC; fully equilibrated Gibbs chains are impractical for each update.Source: §2.1 · p. 2
2.2 Contrastive Divergence
- Contrastive Divergence approximates the negative gradient using samples from a short Gibbs chain initialized at a training vector.The method approximately minimizes a Contrastive Divergence objective.Source: §2.2 · p. 2
2.3 Persistent Contrastive Divergence
- Persistent Contrastive Divergence maintains one Gibbs chain across updates to improve negative-gradient estimates, but persistent-chain algorithms do not apply to conditional RBMs.The section states that the conditioning vector generally yields a distinct model distribution for each training case, preventing use of a single persistent chain.Source: §2.3 · p. 3
3 Training Conditional RBMs
A CRBM conditions an RBM on an input and is generally trained by minimizing negative conditional log-likelihood. The section describes why persistent chains are impractical across training cases and relates the proposed approaches to contrastive-set methods.
3 Training Conditional RBMs
- A CRBM models p(v|u) by using u to set increments to the visible and hidden biases of an RBM.The paper notes that its proposed algorithms can also train other energy-based models with computable free energy, with Gibbs sampling additionally required for CD-PercLoss.Source: §3 · p. 3
- Training generally minimizes negative conditional log-likelihood, whose gradient is intractable in general but can be approximated with block Gibbs sampling.The positive gradient remains tractable because the conditional distributions factor over visible and hidden variables.Source: §3 · p. 3
- Persistent-chain training is inefficient for CRBMs because each conditioning vector generally has a unique model distribution, and revisited chains can be far from stationarity after weight changes.Maintaining a separate persistent chain per training case is described as feasible only on very small datasets.Source: §3 · p. 3
- The proposed approaches share similarities with Contrastive Constraint Generation, while CD-PercLoss generates contrastive examples online and can scale to large datasets.The passage describes CCG as a batch algorithm maintaining a contrastive set for each case, generated by inference.Source: §3 · pp. 3–4
4 Making Predictions with Conditional RBMs
CRBM prediction generally requires approximate inference because conditional marginals and the full conditional mode are intractable. The section discusses mean-field inference and loopy belief propagation as message-passing approaches.
4 Making Predictions with Conditional RBMs
- Conditional prediction may seek marginal modes or the full conditional mode, both of which are generally intractable and require approximation.The target quantities are p(v_i|u) or p(v|u).Source: §4 · p. 4
- Mean-field is a fast message-passing method that approximates the full conditional by factorizing it into conditional marginals.It finds marginals that provide the best approximation of the true conditional distribution.Source: §4 · p. 4
- Loopy belief propagation tends to approximate conditional marginals better than mean-field, but is slower and practical only for relatively small output dimensionality and hidden layers.Source: §4 · p. 4
5 Suitability of CD Training
The section argues that CD may not suit conditional RBMs: its loss can be small when a slow, data-started Gibbs chain stays near the observed output, without guaranteeing good predictions. Unlike nonconditional RBMs, conditional models cannot rely on reconstruction because prediction-time access is only to the conditioning vector.
5 Suitability of CD Training
- CD can be viewed as lowering data free energy and raising the kth Gibbs-state free energy, while updates ignore changes to the chain induced by new parameters.The kth state is generated using the old parameters θold.Source: §5 · p. 4
- CD may be unsuitable for conditional RBMs because slow mixing can keep negative samples near the data, making the loss small without guaranteeing good predictions.The concern is especially relevant when the chain starts at the data and k is small.Source: §5 · p. 4
- Reconstructing the observed output can support representations in nonconditional RBMs, but does not suffice for conditional prediction because only u is available at test time.A chain that stays near v may still leave h informative for reconstructing v in the nonconditional setting.Source: §5 · p. 4
6 Two Algorithms for Structured Output Prediction with CRBMs
The paper proposes two CRBM training alternatives for structured prediction, selected according to whether the output configurations are sufficiently well covered by training data or highly variable.
6.1 Structured Output Prediction when Output Variability is Limited
- When training data covers likely targets, restricting outputs to observed configurations makes exact enumeration possible if the candidate set is small.This addresses settings where output variability is limited; enumerating a large observed set remains slow.Source: §6.1 · pp. 4–5, Spectral Hashing · p. 5
Spectral Hashing
- Spectral hashing builds input-specific candidate sets without searching the training set; radius-1 codes require n+1 hash-map accesses.The hash map associates codes with training targets, and duplicate output configurations are filtered when candidate sets are merged.Source: Spectral Hashing · p. 5
Training and Inference
- HashCRBM trains by exact gradient descent over V(u), but marginal-mode inference can produce outputs outside that candidate set.Alternatively, prediction can select the candidate in V(u) with the lowest free energy.Source: Training and Inference · pp. 5–6
6.1.1 Experiments with HashCRBM
- HashCRBM is consistently among the best multi-label models, with a particularly large improvement over all methods on Scene.The experiments report average test errors across Yeast, Scene, MTurk, and MajMin.Source: Table 1 · p. 6, §6.1.1 · p. 6
Minimizing the Generalized Perceptron Loss
- Generalized perceptron loss targets predictions directly, raising predicted-output free energy and lowering data free energy; training uses Gibbs search, while test prediction uses mean field.When exact minimization is intractable, the loss uses the free energy of the model’s prediction in place of the minimum free energy.Source: Minimizing the Generalized Perceptron… · pp. 6–7
6.2.1 Experiments
- On occluded MNIST, CD-PercLoss beats alternatives by a wider margin, with 20% lower changed-pixel error than CD; on corrupted MNIST, it slightly outperforms others.Corrupted MNIST flips 10% of binary pixels; occluded MNIST zeros a random 8 by 8 patch. CD-1 and CD-10 fail to reconstruct most digits, while CD-PercLoss cleans up most.Source: §6.2.1 · pp. 7–8, Table 2 · p. 8
7 Conclusions and Future Work
The proposed CRBM algorithms perform better than alternatives in the regimes for which they are appropriate. The conclusion links CD’s reduced usefulness for CRBMs to their generally less multimodal conditional distributions and outlines a structured-output max-margin extension as future work.
7 Conclusions and Future Work
- The two proposed algorithms perform better than alternative methods in the regimes for which they are appropriate.CD-PercLoss starts its chain at a random state, making it more like the original Boltzmann-machine learning procedure than contrastive divergence.Source: §7 · p. 8
- Because CRBM conditional joint distributions are generally less multimodal than RBM joint distributions, CD’s advantages can diminish until it is no longer effective.For RBMs, CD’s data-started chains can help sample modes and balance sampling error from small mini-batches.Source: §7 · p. 8
- Future work could extend CD-PercLoss to structured-output max-margin learning with loss-margin scaling, loss-augmented inference, and L2 regularization.The paper also proposes adapting HashCRBM similarly.Source: §7 · p. 8