# Greedy Training of Deep Belief Networks

I try to understand the justification of Greedy Training for Deep Belief Networks. I read the tutorial at http://deeplearning.net/tutorial/DBN.html and various papers of Hinton,Bengio and other authors but I have difficulty at a particular location. The tutorial in the link gives the following explanation:

Now, I am perfectly fine with the lower bound explanation since I am somewhat used to it from EM and Variational Inference algorithms. What disturbs me is the maximizing the log likelihood part (in the given page the log part has been omitted, as a result of error I think): $$\mathbb{E}_{Q(h^{(1)}|x)}\log p(h^{(1)}) = \sum_h Q(h^{(1)}|x)\log p(h^{(1)})$$.

I can see that maximizing $\log p(h^{(1)})$ corresponds to training a RBM with parameters $W^{(2)}$. But we need to maximize over the expectation of the data vectors $h^{(1)}$ with respect to the posterior $Q(h^{(1)}|x)$. This should be intractable since the space of all $h^{(1)}$ may be exponentially large. Is what we are actually doing is to sample a dataset $h^{(1)}_1,h^{(1)}_2,\dots,h^{(1)}_N$ from $Q(h^{(1)}|x)$ and to maximize then the unbiased Monte Carlo estimate:

$$\dfrac{1}{N}\sum_{i=1}^N\log p(h^{(1)}_i) \approx \sum_h Q(h^{(1)}|x)\log p(h^{(1)})$$?

All resources say that we need to train a second layer RBM with the sampled data from the first RBM's hidden layer, driven by the original training data. I think this corresponds to the Monte Carlo approximation I gave above. Is that right? If not, how is that expectation handled when training the second layer RBM?