Joint Training Deep Boltzmann Machines for Classification
Authors: Ian Goodfellow, Aaron Courville, Yoshua Bengio
ICLR 2013

Abstract: We introduce a new method for training deep Boltzmann machines jointly. Prior methods require an initial learning pass that trains the deep Boltzmann machine greedily, one layer at a time, or do not perform well on classification tasks. In our approach, we train all layers of the DBM simultaneously, using a novel inpainting-based objective function that facilitates second order optimization and line searches.

Joint Training of Deep Boltzmann Machines for
Classiﬁcation
Ian J. Goodfellow Aaron Courville
Universit´e de Montr´eal
Yoshua Bengio
Abstract
We introduce a new method for training deep Boltzmann machines jointly. Prior
methods of training DBMs require an initial learning pass that trains the model
greedily, one layer at a time, or do not perform well on classiﬁcation tasks. In
our approach, we train all layers of the DBM simultaneously, using a novel train-
ing procedure called multi-prediction training. The resulting model can either be
interpreted as a single generative model trained to maximize a variational approx-
imation to the generalized pseudolikelihood, or as a family of recurrent networks
that share parameters and may be approximately averaged together using a novel
technique we call the multi-inference trick. We show that our approach performs
competitively for classiﬁcation and outperforms previous methods in terms of ac-
curacy of approximate inference and classiﬁcation with missing inputs.
1 Deep Boltzmann machines
A deep Boltzmann machine (Salakhutdinov and Hinton, 2009) is a probabilistic model consisting
of many layers of random variables, most of which are latent. Typically, a DBM contains a set
of D input features v that are called the visible units because they are always observed during
both training and evaluation. The DBM is usually applied to classiﬁcation problems and thus often
represents the class label with a one-of- k code in the form of a discrete-valued label unit y. y is
observed (on examples for which it is available) during training. The DBM also contains several
latent variables that are never observed. These hidden units are usually organized into Llayers h(i)
of size Ni,i = 1,...,L , with each unit in a layer conditionally independent of the other units in
the layer given the neighboring layers. These conditional independence properties allow fast Gibbs
sampling because an entire layer of units can be sampled at a time. Likewise, mean ﬁeld inference
with ﬁxed point equations is fast because each ﬁxed point equation gives a solution to roughly half
of the variational parameters. Inference proceeds by alternating between updating all of the even
numbered layers and updating all of the odd numbered layers.
A DBM deﬁnes a probability distribution by exponentiating and normalizing an energy function
P(v,h,y ) = 1
Z exp (−E(v,h,y ))
where
Z =
∑
v′,h′,y′
exp (−E(v′,h′,y′)) .
Z, the partition function, is intractable, due to the summation over all possible states. Maximum
likelihood learning requires computing the gradient of log Z. Fortunately, the gradient can be esti-
mated using an MCMC procedure (Younes, 1999; Tieleman, 2008). Block Gibbs sampling of the
layers makes this procedure efﬁcient.
The structure of the interactions in hdetermines whether further approximations are necessary. In
the pathological case where every element of his conditionally independent of the others given the
1
arXiv:1301.3568v3  [stat.ML]  1 May 2013
c)b)a)
Figure 1: The training procedure employed by Salakhutdinov and Hinton (2009) on MNIST. a) An
RBM comprising vand h(1) is trained to maximize the log likelihood of vusing CD. Next, another
RBM is trained with CD, using yand samples of h(1) conditioned on vas observed data, and h(2)
as hidden units. b) The two RBMs are stitched together to form one DBM over v, h(1), h(2), and
y. This DBM is trained to maximize the log likelihood of vand yusing PCD. c) yis deleted from
the model. An extra MLP is built on top of vand the mean ﬁeld expectations of h(1) and h(2). The
parameters of the DBM are frozen, and the parameters of the MLP are initialized based on the DBM
parameters, then trained via nonlinear conjugate gradient descent to predict yfrom vand the mean
ﬁeld features.
visible units, the DBM is simply an RBM andlog Zis the only intractable term of the log likelihood.
In the general case, interactions between different elements of h render the posterior P(h |v,y)
intractable. Salakhutdinov and Hinton (2009) overcome this by maximizing the lower bound on the
log likelihood given by the mean ﬁeld approximation to the posterior rather than maximizing the log
likelihood itself. Again, block mean ﬁeld inference over the layers makes this procedure efﬁcient.
An interesting property of the DBM is that the training procedure thus involvesfeedback connections
between the layers. Consider the simple DBM consisting entirely of binary-valued units, with the
energy function
E(v,h) =−vT W(1)h(1) −h(1)T W(2)h(2).
Approximate inference in this model involves repeatedly applying two ﬁxed-point update equations
to solve for the mean ﬁeld approximation to the posterior. Essentially it involves running a recurrent
net in order to obtain approximate expectations of the latent variables.
Beyond their theoretical appeal as a deep model that admits simultaneous training of all components
using a generative cost, DBMs have achieved excellent performance in practice. When they were
ﬁrst introduced, DBMs set the state of the art on the permutation-invariant 1 version of the MNIST
handwritten digit recognition task at 0.95%.
Recently, new techniques were used in conjunction with DBM pretraining to set a new state of the
art of 0.79% test error (Hinton et al., 2012).
2 The joint training problem
Unfortunately, it is not possible to train a deep Boltzmann machine using only the variational bound
and approximate gradient described above. See (Goodfellow et al., 2013) for an example of a DBM
that has failed to learn using the naive training algorithm. Salakhutdinov and Hinton (2009) found
that for CD / PCD to work, the DBM must be initialized by training one layer at a time. After each
layer is trained as an RBM, the RBMs can be modiﬁed slightly, assembled into a DBM, and the
DBM may be trained with PCD learning rule described above. In order to achieve good classiﬁcation
results, an MLP designed speciﬁcally to predict yfrom vmust be trained on top of the DBM model.
Simply running mean ﬁeld inference to predict ygiven vin the DBM model does not work nearly
1By permutation-invariant, we mean that permuting all of the input pixels prior to learning the network
should not cause a change in performance, so using synthetic image distortions or convolution to engineer
knowledge about the structure of the images into the system is not allowed.
2
as well. See ﬁgure 1 for a graphical description of the training procedure used by Salakhutdinov and
Hinton (2009).
In this paper, we propose a method that enables the deep Boltzmann machine to be jointly trained,
and to achieve excellent performance as a classiﬁer without an additional classiﬁcation-speciﬁc ex-
tension of the model. The standard approach requires trainingL+2 different models usingL+2 dif-
ferent objective functions, and does not yield a single model that excels at answering all queries. Our
approach requires training only one model with only one objective function, and the resulting model
outperforms previous approaches at answering all kinds of queries (classiﬁcation, classiﬁcation with
missing inputs, predicting arbitrary subsets of variables given arbitrary subsets of variables).
3 Motivation
There are numerous reasons to prefer a single-model, single-training stage approach to deep Boltz-
mann machine learning:
1. Optimization As a greedy optimization procedure, layerwise training may be suboptimal.
Small-scale experimental work has demonstrated this to be the case for deep belief net-
works (Arnold and Ollivier, 2012).
In general, for layerwise training to be optimal, the training procedure for each layer must
take into account the inﬂuence that the deeper layers will provide. The standard training
layerwise procedure simply does not attempt to be optimal.
The procedures used by Le Roux and Bengio (2008); Arnold and Ollivier (2012) make
an optimistic assumption that the deeper layers will be able to implement the best possi-
ble prior on the current layer’s hidden units. This approach is not immediately applica-
ble to Boltzmann machines because it is speciﬁed in terms of learning the parameters of
P(h(i−1)|h(i)) assuming that the parameters of the P(h(i)) will be set optimally later. In a
DBM the symmetrical nature of the interactions between units means that these two distri-
butions share parameters, so it is not possible to set the parameters of the one distribution,
leave them ﬁxed for the remainder of learning, and then set the parameters of the other
distribution. Moreover, model architectures incorporating design features such as sparse
connections, pooling, or factored multilinear interactions make it difﬁcult to predict how
best to structure one layer’s hidden units in order for the next layer to make good use of
them.
2. Probabilistic modeling Using multiple models and having some models specialized for
exactly one task (like predicting yfrom v) loses some of the beneﬁt of probabilistic mod-
eling. If we have one model that excels at all tasks, we can use inference in this model to
answer arbitrary queries, perform classiﬁcation with missing inputs, and so on.
3. Simplicity Needing to implement multiple models and training stages makes the cost of
developing software with DBMs greater, and makes using them more cumbersome. Beyond
the practical considerations, it can be difﬁcult to monitor training and tell what kind of
results during layerwise DBM pretraining will correspond to good classiﬁcation accuracy
later. Our joint training procedure allows the user to monitor the model’s ability of interest
(usually ability to classify ygiven v) from the very start of training.
4 Multi-Prediction Training
Our proposed approach is to directly train the DBM to be good at solving all possible variational
inference problems. We call this multi-prediction training because the procedure involves training
the model to predict any subset of variables given the complement of that subset of variables.
Speciﬁcally, we use stochastic gradient descent on the multi-prediction (MP) objective function
J(v,θ) =−
∑
i
log Q∗
v−Si
(vSi)
3
Figure 2: Graphical description of multi-prediction training. During MP training, we sample ex-
amples (v,y) from the training set. For each example, we choose one subset of variables (uniformly
at random) to serve as the input to an inference problem, and use the complement of this subset
as targets for training. We then run mean ﬁeld inference and backpropagate the prediction error
through the entire computational graph of the inference process. Here, we depict the process for
three different examples, one example per row. We use black circles to indicate observed data and
blue circles to indicate prediction targets. The green arrows show the ﬂow of computation through
the mean ﬁeld graph. Each column indicates another time step in the mean ﬁeld inference algorithm.
Dotted lines indicate quantities that are not used for this instantiation of the problem, but would be
used if we ran another iteration of mean ﬁeld. Here, we show only one iteration of mean ﬁeld. To
work well, MP training should be run with 5-10 iterations of mean ﬁeld.
4
Figure 3: Mean ﬁeld inference applied to MNIST digits. The ﬁrst column shows the true digits. The
second column shows pixels of the digits to be masked out, with red pixels indicating the region to
be witheld from the input to the DBM. Yellow-boxed rows show input pixels. Green-boxed rows
represent the class variables. The subsequent columns show the DBM incrementally predicting the
missing variables, with each column being one iteration of mean ﬁeld. On rows where the green-
boxed class variable was masked out, the uncertainty over the class is represented by displaying a
weighted average of templates for the 10 different classes.
where Sis a sequence of subsets of the possible indices of vand
Q∗
v−Si
(vSi,h) =argminQDKL (Q(vSi,h)∥P(vSi,h |v−Si)) .
In other words, the criterion for a single example vis a sum of several terms, with term imeasuring
the model’s ability to predict a subset of the inputs,vSi, given the remainder of the inputs, v−Si.
During SGD training, we sample minibatches of values of v and Si. Sampling an Si uniformly
simply requires sampling one bit (1 with probability 0.5) for each variable, to determine whether
that variable should be an input to the inference procedure or a prediction target.
In this paper, Qis constrained to be factorial, though one could design model families for which it
makes sense to use richer structure in Q. In order to accomplish the minimization, we instantiate
a recurrent net that repreatedly runs the mean ﬁeld ﬁxed point equations, and backpropagrate the
gradient of J through the entire recurrent net.
See Fig. 2 for a graphical description of this training procedure, and Fig. 3 for an example of the
inference procedure run on MNIST digits.
5 The Multi-Inference Trick
Mean ﬁeld inference can be expensive due to needing to run the ﬁxed point equations several times
in order to reach convergence. In order to reduce this computational expense, it is possible to train
using fewer mean ﬁeld iterations than required to reach convergence. In this case, we are no longer
necessarily minimizing J as written, but rather doing partial training of a large number of ﬁxed-
iteration recurrent nets that solve related problems.
We can approximately take the geometric mean over all predicted distributionsQand renormalize in
order to combine the predictions of all of these recurrent nets. This way, imperfections in the training
procedure are averaged out, and we are able to solve inference tasks even if the corresponding
recurrent net was never sampled during MP training.
5
Mean Field Iteration
Multi-Inference Iteration
+ =
Step 1 Step 2Previous State + Reconstruction
Step 1 Step 2Previous State
Figure 4: Graphical description of the multi-inference trick . Consider the problem of estimating
y given v. A mean ﬁeld iteration consists of ﬁrst applying a mean ﬁeld update to h(1) and y, then
applying one to h(2). When using the multi-inference trick, we start the iteration by ﬁrst computing
ras the mean ﬁeld update vwould receive if it were not observed. We then use 0.5(r+ v) in place
of vand run a regular mean ﬁeld iteration.
Figure 5: Here we use MP training on MNIST with only 5 mean ﬁeld iterations, for a set of hyper-
paramters where 10 mean ﬁeld iterations are necessary to get good convergence. The classiﬁcation
error rate for mean ﬁeld quits improving after about 150 epochs of training, but the multi-inference
trick allows us to extract more information from the model. The model continues improving at
multi-inference for 100 epochs after its performance at mean ﬁeld inference has stagnated.
6
In order to approximate this average efﬁciently, we simply take the geometric mean at each step of
inference, instead of attempting to take the correct geometric mean of the entire inference process.
This is the same type of approximation used to take the average over several MLP predictions when
using dropout (Hinton et al., 2012). Here, the averaging rule is slightly different. In dropout, the dif-
ferent MLPs we average over either include or exclude diferent each variable. To take the geometric
mean over a unithj that receives input fromvi, we average together the contributionviWij from the
model that contains vi and the contribution 0 from the model that does not. The ﬁnal contribution
from vi is 0.5viWij so the dropout model averaging rule is to run an MLP with the weights divided
by 2.
For the multi-inference trick, each model we are averaging over solves a different inference problem.
In half the problems, vi is observed, and constributes viWij to hj’s total input. In the other half of
the problems, vi is inferred. If we represent the mean ﬁeld estimate of vi with ri, then in this case
that unit contributes riWij to hj’s total input. To run multi-inference, we thus replace references to
vwith 0.5(v+ r), where ris updated at each mean ﬁeld iteration.
The main reason this approach is effective is that it gives a good way to incorporate information
from many recurrent nets trained in slightly different ways. However, it can also be understand as
including an input denoising step built into the inference.
See Fig. 4 for a graphical depiction of the method, and Fig. 5 for an example of it in action.
6 Justiﬁcation and advantages
In the case where we run the recurrent net for predicting Q to convergence, the multi-prediction
training algorithm follows the gradient of the objective function J. This can be viewed as a mean
ﬁeld approximation to the generalized pseudolikelihood.
While both pseudolikelihood and likelihood are asymptotically consistent estimators, their behavior
in the limited data case is different. Maximum likelihood should be better if the overall goal is
to draw realistic samples from the model, but generalized pseudolikelihood can often be better for
training a model to answer queries conditioning on sets similar to the Si used during training.
Note that our variational approximation is not quite the same as the way variational approximations
are usually applied. We use variational inference to ensure that the distributions we shape using
backprop are as close as possible to the true conditionals. This is different from the usual approach
to variational learning, whereQis used to deﬁne a lower bound on the log likelihood and variational
inference is used to make the bound as tight as possible.
In the case where the recurrent net is not trained to convergence, there is an alternate way to justify
MP training. Rather than doing variational learning on a single probabilistic model, the MP proce-
dure trains a family of recurrent nets to solve related prediction problems by running for some ﬁxed
number of iterations. Each recurrent net is trained only a subset of the data (and most recurrent nets
are never trained at all, but only work because they share parameters with the others). In this case,
the multi-inference trick allows us to justify MP training as approximately training an ensemble of
recurrent nets using bagging.
Stoyanov et al. (2011) have observed that a similar training strategy is useful because it trains the
model to work well with the inference approximations it will be evaluated with at test time. We
ﬁnd these properties to be useful as well. The choice of this type of variational learning combined
with the underlying generalized pseudolikelihood objective makes an MP-DBM very well suited for
solving approximate inference problems but not very well suited for sampling.
Our primary design consideration when developing multi-prediction training was ensuring that the
learning rule was state-free. PCD training uses persistent Markov chains to estimate the gradient.
These Markov chains are used to approximately sample from the model, and only sample from ap-
proximately the right distribution if the model parameters evolve slowly. The MP training rule does
not make any reference to earlier training steps, and can be computed with no burn in. This means
that the accuracy of the MP gradient is not dependent on properties of the training algorithm such as
the learning rate–properties which can easily break PCD for many choices of the hyperparameters.
7
Figure 6: During cross-validation, MP training consistently performs better at classiﬁcation than
either centering or centering with the special negative phase.
Another beneﬁt of MP is that it is easy to obtain an unbiased estimate of the MP objective from
a small number of samples of v and i. This is in contrast to the log likelihood, which requires
estimating the log partition function. The best known method for doing so is AIS, which is relatively
expensive (Neal, 2001). Cheap estimates of the objective function enable early stopping based on
the MP-objective (though we generally use early stopping based on classiﬁcation accuracy) and
optimization based on line searches (though we do not explore that possibility in this paper).
7 Regularization
In order to obtain good generalization performance, Salakhutdinov and Hinton (2009) regularized
both the weights and the activations of the network.
Salakhutdinov and Hinton (2009) regularize the weights using an L2 penalty. We ﬁnd that for joint
training, it is critically important not to do this. When the second layer weights are not trained well
enough for them to be useful for modeling the data, the weight decay term will drive them to become
very small, and they will never have an opportunity to recover. It is much better to use constraints
on the norms of the columns of the weight vectors, as advocated by Hinton et al. (2012).
Salakhutdinov and Hinton (2009) regularize the activities of the hidden units with a somewhat com-
plicated sparsity penalty. See http://www.mit.edu/˜rsalakhu/DBM.html for details.
We use max(|Eh∼Q(h)[h] −t|−λ,0) and backpropagate this through the entire inference graph. t
and λare hyperparameters.
8 Related work: centering
Montavon and M¨uller (2012) showed that reparameterizing the DBM to improve the condition num-
ber of the Hessian results in succesful generative training without a greedy layerwise pretraining
step. However, this method has never been shown to have good classiﬁcation performance, possibly
because the reparameterization makes the features never be zero from the point of view of the ﬁnal
classiﬁer.
We evaluate its classiﬁcation performance in more detail in this work. We consider two methods
of PCD training. In one, we use Rao-Blackwellization of the negative phase particles to reduce the
variance of the negative phase. In the other variant, we use a special negative phase that Salakhutdi-
nov and Hinton (2009) found useful. This negative phase uses a small amount of mean ﬁeld, which
reduces the variance further but introduces some bias, and has better symmetry with the positive
phase. See http://www.mit.edu/˜rsalakhu/DBM.html for details.
8
Figure 7: When classifying with missing inputs, the MP-DBM outperforms the other DBMs for
most amounts of missing inputs.
Figure 8: When using approximate inference to resolve general queries, the standard DBM, cen-
tered DBM, and MP-DBM all perform about the same when asked to predict a small number of
variables. For larger queries, the MP-DBM performs the best.
9
9 MNIST experiments
In order to compare MP training and centering to standard DBM performance, we cross-validated
each of the new methods by running 25 training experiments for each of three conditions: centered
DBMs, centered DBMs with the special negative phase (“Centering+”), and MP training. For these
experiments we did not use the multi-inference trick.
All three conditions visited exactly the same set of 25 hyperparameter values for the momentum
schedule, sparsity regularization hyperparameters, weight and bias initialization hyperparameters,
weight norm constraint values, and number of mean ﬁeld iterations. The centered DBMs also re-
quired one additional hyperparameter, the number of Gibbs steps to run for PCD.
We used different values of the learning rate for the different conditions, because the different con-
ditions require different ranges of learning rate to perform well.
We use the same size of model, minibatch and negative chain collection as Salakhutdinov and Hinton
(2009), with 500 hidden units in the ﬁrst layer, 1,000 hidden units in the second, 100 examples per
minibatch, and 100 negative chains.
See Fig. 6 for the results of cross-validation. On the validation set, MP training consistently per-
forms better and is much less sensitive to hyperparameters than the other methods. This is likely
because the state-free nature of the learning rule makes it perform better with settings of the learn-
ing rate and momentum schedule that result in the model distribution changing too fast for a method
based on Markov chains to keep up.
When we ﬁne-tune the best model, the best “Centering+” DBM obtains a classiﬁcation error of 1.22
% on the test set. The best MP-DBM obtains a classiﬁcation error of 0.99 %. This compares to 0.95
% obtained by Salakhutdinov and Hinton (2009).
If instead of adding an MLP to the model to do ﬁne tuning, we simply train a larger MP-DBM with
twice as many hidden units in each layer, and apply the multi-inference trick, we obtain a slightly
better classiﬁcation error rate of 0.91 %. In other words, we are able to classify better using a single
large DBM and a generic inference procedure, rather than using a DBM followed by an entirely
separate MLP model specalized for classiﬁcation.
The original DBM was motivated primarily as a generative model with a high AIS score and as a
classiﬁer. Here we explore some more uses of the DBM as a generative model. First, we evaluate
the use of the DBM to classify in the presence of missing inputs. See Fig. 7 for details. We ﬁnd
that for most amounts of missing inputs, the MP-DBM classiﬁes better than the standard DBM or
the best centering DBM. We also explored the ability of the DBM to resolve queries about random
subsets of variables. See Fig. 8 for details. Again, we ﬁnd that the MP-DBM outperforms the other
DBMs.
10 Conclusion
This paper has demonstrated that MP training and the multi-inference trick provide a means of train-
ing a single model, with a single stage of training, that matches the performance of standard DBMs
but still works as a general probabilistic model, capable of handling missing inputs and answering
general queries. In future work, we hope to obtain state of the art performance by combining MP
training with dropout, and also to apply this method to other datasets.
References
Arnold, L. and Ollivier, Y . (2012). Layer-wise learning of deep generative models. Technical report,
arXiv:1212.1524.
Goodfellow, I. J., Courville, A., and Bengio, Y . (2013). Scaling up spike-and-slab models for unsu-
pervised feature learning. IEEE, special issue on deep learning. (To appear).
Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. (2012). Im-
proving neural networks by preventing co-adaptation of feature detectors. Technical report,
arXiv:1207.0580.
10
Le Roux, N. and Bengio, Y . (2008). Representational power of restricted Boltzmann machines and
deep belief networks. Neural Computation, 20(6), 1631–1649.
Montavon, G. and M ¨uller, K.-R. (2012). Learning feature hierarchies with cented deep Boltzmann
machines. CoRR, abs/1203.4416.
Neal, R. M. (2001). Annealed importance sampling. Statistics and Computing, 11(2), 125–139.
Salakhutdinov, R. and Hinton, G. (2009). Deep Boltzmann machines. In Proceedings of the Twelfth
International Conference on Artiﬁcial Intelligence and Statistics (AISTATS 2009), volume 8.
Stoyanov, V ., Ropson, A., and Eisner, J. (2011). Empirical risk minimization of graphical model
parameters given approximate inference, decoding, and model structure. In Proceedings of the
14th International Conference on Artiﬁcial Intelligence and Statistics (AISTATS) , volume 15 of
JMLR Workshop and Conference Proceedings, pages 725–733, Fort Lauderdale. Supplementary
material (4 pages) also available.
Tieleman, T. (2008). Training restricted Boltzmann machines using approximations to the likelihood
gradient. In W. W. Cohen, A. McCallum, and S. T. Roweis, editors, ICML 2008, pages 1064–
1071. ACM.
Younes, L. (1999). On the convergence of Markovian stochastic algorithms with rapidly decreasing
ergodicity rates. Stochastics and Stochastic Reports, 65(3), 177–228.
11


Peer review:
[Review]:
This breaking-news paper proposes a new method to jointly train the layers of a DBM. DBM are usually 'pre-trained' in a layer-wise manner using RBMs, a conceivably suboptimal procedure. Here the authors propose to use a deterministic criterion that basically turns the DBM into a RNN. This RNN is trained with a loss that resembles that one of denoising auto-encoders (some inputs at random are missing and the task is to predict their values from the observed ones).

The view of a DBM as special kind of RNN is not new and the inpainting criterion is not new either, however their combination is. I am very curious to see whether this will work because it may introduce a new way to train RNNs that can possibly work well for image related tasks. I am not too excited about seeing this as a way to improve DBMs as a probabilistic model, but that's just my personal opinion.  
Overall this work can be moderately original and of good quality.

Pros
-- clear motivation
-- interesting model
-- good potential to improve DBM/RNN training
-- honest writing about method and its limitation (I really like this and it is so much unlike most of the work presented in the literature). Admitting current limitations of the work and being explicit about what is implemented helps the field making faster progress and becoming less obscure to outsiders. 

Cons
-- at this stage this work seems preliminary
--  formulation is unclear

More detailed comments:
The notation is a bit confusing: what's the difference between Q^*_i and Q^*? Is the KL divergence correct? I would expect something like:
KL(DBM probability of (v_{S_i} | v_{-S_i}) || empirical probability of ( v_{S_i} | v_{-S_i}) ). I do not understand why P(h | v_{-S_i}) shows up there.

It would be nice to relate this method to denoising autoencoders. In my understanding this is the analogous for RNN-kind of networks.

Doesn't CG make the training procedure more prone to overfitting on the minibatch? How many steps are executed?

Important details are missing. Saying that error rate on MNIST is X% does not mean much if the size of the network is not given.

Overall, this is a good breaking news paper.