Restricted Boltzmann Machines - Understanding contrastive divergence vs. ML learning I've read many articles about RBMs as well as Hinton's original paper about the CD algorithm (at least roughly), but I still don't get the big picture. I understand CD conceptually and I've already implemented it in code. I've also understood that CD is used, because the "original", "naive" algorithm to learn (?) RBMs, which is through maximum likelihood, is intractable. However I don't understand ...


*

*... how maximum likelihood with RBMs even works. Can someone give me a very concrete, illustrative example on how to apply ML learning for RBMs and why it is intractable? I didn't get that concept at all. Are there even any training examples involved?

*... how contrastive divergence is better in terms of complexity than ML learning. I've seen a lot of equations about conditional- and joint probability etc., but can someone give me a clear comparison (in terms of probability) between the two techniques?


You'd really help me, because I'm struggling with understanding the theory and motivation behind RBMs for days now. All resources I've found are pretty hard to understand for people with only basic knowledge in probability theory.
 A: Let me use Hinton's own writing to answer this question:

The CD learning procedure is based on ignoring derivatives that come from later steps in the Markov chain (Hinton, Osindero and Teh, 2006), so it tends to approximate maximum likelihood learning better when the mixing is fast. The ignored derivatives are then small for the following reason: When a Markov chain is very close to its stationary distribution, the best parameters for modeling samples from the chain are very close to its current parameters.

Hinton, A Practical Guide to Training Restricted Boltzmann Machines, 2010
So let's follow the "white rabbit":

[W]e can compute the derivatives of the log probability of the data. Let us start by computing the derivative for a generative weight, $\omega^{0,0}_{i,j}$, from a unit $j$ in [hidden] layer $H_0$ to unit $i$ in [visible] layer $V_0$ (see Figure 3). In a logistic belief net, the maximum likelihood learning
  rule for a single data vector [and layer!], $\vec{v}^0$, is $$\frac{\delta \log p(\vec{v}^0)}{\delta \omega^{0,0}_{i,j}} = \langle{ \vec{h}^0_j ( \vec{v}^0_i - \hat{\vec{v}}^0_i ) \rangle}$$ where ⟨·⟩ denotes an average over the sampled states and $\vec{v}^0_i$ is the probability that unit $i$ would be turned on if the visible vector was stochastically reconstructed from the sampled hidden states.

From Section 2.1 and Formula 2.2 in
Hinton et al., A Fast Learning Algorithm for Deep Belief Nets, 2006
Note that the super-script numbers represent layers in your DBN, so for a RBM, you just can "ignore" them.
Next, Hinton goes on to expand the ML rule over all layers of the DBN. But check out Figure 4, as that depicts how you would then use alternative Gibbs sampling (in theory: to infitinty!) on your Markov chain to optimize a [single] "RBM" layer. In a nutshell, it simply depicts making the angle-bracketed estimate with your MCMC sampler, up to infinity. He also gives us the probabilistic interpretation of ML learning your RBM:

Maximizing the log probability of the data is exactly the same as minimizing the Kullback-Leibler divergence, $KL(P^0||P^\infty_\theta)$, between the distribution of the data, $P^0$, and the equilibrium distribution defined by the model, $P^\infty_\theta$. In contrastive divergence learning (Hinton, 2002), we run the Markov chain for only $n$ full steps before measuring the second correlation.

However, then:

An empirical investigation of the relationship between the maximum likelihood and the contrastive divergence learning rules can be found in Carreira-Perpinan and Hinton (2005).

Bad luck, another redirection to fully resolve all your questions; Yet, we at least already understand how the ML approach will work for our RBM (Bullet 1). One question in that bullet, though, was "I didn't get that concept at all. Are there even any training examples involved?".
I am not sure I fully understand what you are asking for, but yes, of course, you initialize your visible units according to the training data, just like with the CD method (yet, that seems almost to trivial an question/answer?).
So next, let us dive into the answers for Bullet 2:

Maximum-likelihood (ML) learning of Markov random fields is challenging because it requires estimates of averages that have an exponential number of terms. Markov chain Monte Carlo methods typically take a long time to converge on unbiased estimates, but Hinton (2002) showed that if the Markov chain is only run for a few steps, the learning can still work well and it approximately minimizes a different function called "contrastive divergence" (CD).

And:

Fast CD learning can therefore be used to get close to an ML solution and slow ML learning can then be used to fine-tune the CD solution.

From the abstract of
Carreira-Perpinan and Hinton, On contrastive divergence learning, 2005
Luckily, the introduction spells out what you might have already guessed from our understanding of the ML approach above:

However, [ML learning with MCMC] is typically very slow, since running the Markov chain to equilibrium can require a very large number of steps, and no foolproof method exists to determine whether equilibrium has been reached. A further disadvantage is the large variance of the estimated gradient.

So all that is left to answer is "can someone give me a clear comparison (in terms of probability) between the two techniques?" (I believe/hope). Luckily, this, too, is answered immediately in the introduction of that paper:

ML learning minimises the Kullback-Leibler divergence $$KL(p_0||p_\infty) = \sum_x{p_0(\vec{x})\log\frac{p_o(\vec{x})}{p(\vec{x};\vec{W})}}$$ CD learning approximately follows the gradient of the difference of two divergences (Hinton, 2002): $$CD_n = KL(p_0||p_\infty) - KL(p_n||p_\infty)$$ In CD learning, we start the Markov chain at the data distribution $p_0$ and run the chain for a small number $n$ of steps (e.g. $n = 1$). This greatly reduces both the computation per gradient step and the variance of the estimated gradient, and experiments show that it results in good parameter estimates (Hinton, 2002).

I believe this has answered all questions, and for any further details, I strongly recommend studying the cited work. Hinton's work is always so refreshingly clear!
ADDENDUM: So to put it quite blatantly, this whole work is a very elaborate, academic way of showing that running a "1-step MCMC" on our RBM is not really significantly worse than running to "infinity" (or, more likely, some kind of convergence), while it makes finding the weights of a RBM/DBN tractable, and therefore this simplification "deserved" a new name ("CD learning" as opposed to "ML learning").
A: Thank you very much for your effort, @fnl! Although I couldn't follow all of your points (probably because I'm quite a beginner), your answer gave me some clarity.
Could you point out the problem again in terms of energy? I came across the following equation several times and one drawback of the ML method is that the denominator requires to sum over all possible combinations of visible and hidden states, which is exponentially complex, right?
$$
\arg \max_\theta \log p(v | \theta) = \log \frac{\sum_{h} e^{-E(v,h)}}{\sum_{v', h'}e^{-E(v',h')}} = \log \sum_{h} e^{-E(v,h)} - \log {\sum_{v', h'}}e^{-E(v',h')}
$$
However, I haven't completely understood, how the energy-related formulation fits into the whole problem. Also, I remember a quote (I believe by Hinton in one of his Coursera videos) which was like (in reference to the above equation) 

The gradient of the first sum is easy to comute, while the gradient of
  the second is not. It could be approximated when having samples, but
  even sampling is hard, so we also need to approximate them.

So does the "first" approximation mean to repeatedly run the Markov chain and the "second" approximaton to perform Gibbs sampling?
