Stochastic Maximum Likelihood and Contrastive Divergence

The cost of burning in

Maximum likelihood for an undirected model needs the negative phase, an expectation under the model. The direct way to get it is to run a Markov chain from random values each time the gradient is needed. Burn-in is the number of steps a chain needs before its states look like samples from the model.

Algorithm 18.1 does exactly that. Each gradient step draws a fresh minibatch of training examples, starts the chains from random values, runs Gibbs steps on every chain, and subtracts the average gradient at the final states.

The negative phase is the gradient of the log partition function. Equation 18.15 of the book writes it as an expectation under the model. Restated with this page's symbols:

The cost is in step 5. Every gradient step pays for Gibbs steps on each of the chains, and the chains have to forget their random starts before they say anything useful about the model. The book calls the procedure computationally infeasible. The rest of the section explains how each of the other algorithms approximates the same negative phase more cheaply, and what it pays for that saving.

The chains here are Metropolis random walks rather than Gibbs samplers. Each step proposes a move of size at most = 1 and accepts it with the usual rule. The histograms use 24 bins, and is half the sum of the absolute differences between a chain histogram and the model's bin probabilities. It is a number between 0 and 1, where 0 is a perfect match. The book does not define this distance, and it is used here only to measure how close the strips are.

The random starts begin at and fall to about 0.2. Only 41 of the 400 chains change side in 200 steps, so the share of chains on the right stays near 0.49, while the model has 0.30 there. The chains need to find the right mode weights, and that is what burn-in costs. The model samples begin close to the answer, so their distance stays between 0.04 and 0.12 at every step. Those values are the sampling noise of 400 chains.

Contrastive divergence starts at the data

The fix is to start the chains from a distribution close to the model, so that burn-in takes fewer steps. Contrastive divergence, or CD, starts each chain at a training example. Those examples are already samples from the data distribution, so they cost nothing. This is Algorithm 18.2 with steps, written CD-.

Each algorithm turns that expectation into a minibatch estimate. The estimate has two averages, one over the data and one over the chain samples. This combined form is added here. It summarizes lines 3 and 6 of Algorithms 18.1 to 18.3, and the three algorithms differ only in how they choose the chain samples in the second average:

The book explains the early behaviour this way. At first the data distribution is not close to the model, so the negative phase is not very accurate. The positive phase can still raise the model's probability of the data. After the positive phase has had time to act, the model is closer to the data, and the negative phase becomes accurate.

Spurious modes

Here is the failure that the book illustrates in its Figure 18.2. The model has a spurious mode: a bump where the model has probability but the data do not. A chain that starts at the data cannot reach a far-away mode in a few steps, so the negative phase does not push down that bump in a short run. Its probability stays too high, and the model wastes part of its probability mass there.

Watch the orange bars at the spurious bump. They are about 4% of the samples at 20 steps and reach 10% only near 56 steps, and they are still about 20% at 200 steps, short of the model's 25%. The chains move by small steps, so their route from the data to the far mode is long. As the book's text says, CD fails to suppress spurious modes unless is very large.

The book adds several remarks, which are summarized here in plain terms. CD gives a biased estimate: Carreira-Perpiñan and Hinton (2005) showed experimentally that for RBMs and fully visible Boltzmann machines it converges to different points than maximum likelihood, and Bengio and Delalleau (2009) showed that CD discards the smallest terms of the correct MCMC gradient. CD suits shallow models such as RBMs, which can be stacked to start deeper models. It does little for deep models directly, because the hidden units are not in the data, so a chain would still need burn-in over them.

CD also resembles autoencoder training. It penalizes a model whose chains change the input quickly when the input comes from the data, which is why the earliest layers of a stack copy more information upwards. The book calls this a useful side effect rather than a principled design. Finally, Sutskever and Tieleman (2010) showed that the CD update is not the gradient of any function. That allows CD to cycle in principle, but the book reports that this is not a serious problem in practice.

Stochastic maximum likelihood keeps the chains

Stochastic maximum likelihood, or SML, is also known as persistent contrastive divergence, PCD. It was discovered first in statistics and then again in deep learning. The idea is to stop restarting the chains. The chains from the previous gradient step are kept, and each gradient step only runs more steps on them.

The reason this works is that the model changes slowly. If each step is small, the samples from the previous model are very close to fair samples from the current model, so a chain that starts from them needs little burn-in. A persistent chain can also keep wandering, so it has time to find every mode. That makes SML much more resistant to spurious modes than CD. Because every state of the chain is stored, SML can also start both the visible and the hidden units, which lets it train deep models efficiently.

The demo below shows the persistence effect on the model of Figure 18.2. It keeps 50 chains and advances them by one step per iteration. The restarted chains do what CD does: each iteration they start from fresh data points. Both kinds of chain run with the same proposal width, which is set to 2.5 here. That width makes the far mode reachable within a few hundred steps, so the comparison is visible. It is a toy setting chosen for the demo.

The two readouts are the fraction of all chain steps taken at x above 0 so far. Persistent chains climb as they explore, and the restarted chains stay near the data. The model itself holds 25% there. The persistent chains have not reached that value after 200 iterations in this run, which is an honest limit of a short run.

Where SML is fragile

SML is vulnerable when the stochastic gradient moves the model faster than the chains can mix. That happens when is too small or is too large. No formal test is known for whether the chains mix between steps. The book's subjective sign of trouble is that the negative-phase samples vary more across gradient steps than across chains. For example, a model of MNIST digits might sample only 7s on one step, push that mode down strongly, and then sample only 9s on the next. The permissible range of and is highly problem-dependent.

Two cautions matter when you evaluate an SML model. First, its persistent samples were shaped by several recent versions of the model, so they can make the model look more capable than it is. Evaluation should draw samples from a fresh chain started at random. Second, the book reports that SML gave the best test-set log-likelihood for an RBM among the criteria it compared (Marlin et al., 2010), and the best classification accuracy when the hidden units served as features for an SVM. Berglund and Raiko (2013) found that CD has lower variance than exact sampling, because it uses the same training points in both phases, while SML has higher variance.

Fast persistent contrastive divergence

The chains can also be sped up by changing the parameterization rather than the sampler. Fast PCD, or FPCD (Tieleman and Hinton, 2009), writes each parameter as the sum of a slow copy and a fast copy:

The two copies are added element-wise to give the parameters used by the model. The model therefore has twice as many parameters as before. The fast copy is trained with a much larger learning rate than the slow copy , so it can respond quickly to the negative phase and push the chain to new regions. Its effect only lasts while the fast weights are free to change.

The book also applies significant weight decay to the fast weights. We write its coefficient as . It pulls the fast weights towards small values, so they take on large values only briefly, long enough to move the chain between modes. The demo below runs that arithmetic on a single parameter under a constant push. It does not measure how the chain mixes, so it shows the parameter dynamics only.

Under a constant push of size 1 the slow copy grows by per step, so it is a straight line. The fast copy rises quickly towards its limit , and the readout shows how close it is after steps. A small decay keeps the fast copy large for longer, and a large decay keeps it small. The demo shows exactly this trade-off, with no claim about the chain itself.

Choosing between the methods

The three algorithms differ in where the chains start and how long they run. Their costs per gradient step are the same, Gibbs updates. What differs is how many steps the chains need to be useful. Naive MCMC needs a long burn-in from random values. CD starts at the data, which is cheap, but misses far modes. SML keeps the chains, so they explore, but it can fall behind if the model moves too fast.

All three algorithms estimate the same negative phase, the gradient of the log partition function, . They differ only in where the chains start and how long they run, so each one trades accuracy against cost in its own way.

Because these methods estimate only the gradient of , the positive phase can use any other method for . The book notes that the positive phase can then use methods that give only a lower bound on the unnormalized log-probability, and the MCMC negative phase is simply added to that gradient.

Match each property to the algorithm that the book associates with it. Each answer is checked at once.

• Algorithm 18.1 starts every chain at random and pays for a long burn-in at every gradient step.
• Contrastive divergence starts chains at the data, which is cheap, but chains do not reach far modes, so spurious modes persist.
• SML keeps the chains across gradient steps. Small steps keep the model's samples close to fair, so the chains can explore, but SML fails when the learning rate is too large for the number of Gibbs steps.
• FPCD adds a fast copy of each parameter with a larger learning rate and weight decay. It changes the parameters, not the sampler.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 18.2 (pages 607–614), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.