The Challenge of Mixing between Separated Modes

Slow mixing between modes

Section 17.4 gave a chain that moves one variable at a time. This section shows the weak point of such chains. The book calls it the challenge of mixing. Samples from one chain become very correlated, and the chain can stay in one region of the distribution, called a mode, for a long time before it finds another.

The book describes the chain as a kind of noisy hill climbing on the energy. It takes small steps that tend to lower the energy, and it only rarely climbs a high wall. Moving from one mode to another requires crossing the energy barrier between them. The height of that barrier controls how often the crossing happens.

The book gives a small example. Take two binary variables and , each equal to −1 or +1, with the energy that the book uses for this example. A large positive says that and should have the same sign. Predict how often changes sign when is large.

Pick a guess.

The book's conditional probability is written . With written as above and both variables equal to ±1, the two weights differ by a factor of , so the conditional is . This page uses . This correction is made here and is not printed in the book.

When is large the conditional saturates near 1. Updating given then almost always copies the sign of , and updating given almost always copies . Neither step can flip the pair from one mode to the other, because each step is locked to the other variable.

Modes a chain cannot cross

Figure 17.1 of the book shows three Gibbs chains. The first samples two independent normal variables, and it mixes well. The second samples two strongly correlated normal variables, and the chain moves only a little at a time. The third samples a mixture of two separated normal blobs that are not lined up with the axes. The chain stays near its starting blob for a long time. The three panels below are rebuilt for this page with our own distributions. Predict first. With the two blobs far apart, what does the third chain do over 500 sweeps?

Pick a guess.

The mixture panel uses an exact Gibbs update. Given one coordinate, the other coordinate comes from a mix of the two blobs, with weights set by how close the fixed coordinate is to each blob. Moving across the gap between blobs needs both coordinates to change sign together, and each single update cannot do that while the other coordinate is fixed in its blob. That is why the switches become rare as the blobs move apart.

Tempering to mix between modes

The book's first remedy changes the target. An energy-based model can carry an extra parameter that sets how sharply peaked it is. The book writes the usual model as and the tempered family as:

The parameter is the reciprocal of a temperature. At equal to 1 the model is the one we want. When falls below 1 the peaks flatten and the valleys rise, so the chain can cross between modes more easily. As goes to 0 the distribution, for discrete states, becomes uniform. The book's phrase for this strategy is tempering.

Predict first. The demo below uses an energy with two wells, a right well a little deeper than the left. At equal to 1, what happens to the share of probability in the right well as is lowered?

Pick a guess.

The book notes two ways to use this idea. Tempered transitions run the chain briefly at a higher temperature so that it mixes between modes, then return to the temperature of interest. Parallel tempering runs several chains at different temperatures together and swaps states between them, so that a state that has crossed at a high temperature can move into a chain at the target temperature. The book adds that tempering has not yet allowed a strong advance on complex energy-based models. One reason it gives is that there are critical temperatures where the schedule must change very slowly.

Depth may help mixing

Latent variables offer a second route. Suppose a model has a hidden variable and a visible variable . The book notes that if the hidden representation encodes the visible variable too well, then sampling from changes very little, and the chain mixes poorly. The book's remedy is a deeper representation in which the chain in the hidden space mixes more easily.

To see the effect, the demo uses a simple version. The visible variable is −1 or +1 with equal chance. The hidden value is equal to plus noise of size . A small means encodes precisely. Gibbs sampling alternates between the two. This conditional is added here and is not printed in the book. It follows from the two normal densities.

Predict first. The noise is 0.2, so the hidden value encodes the visible variable very precisely. How often does change sign over 1000 steps?

Pick a guess.

The book is careful about what this shows. Deep models often give a hidden representation whose distribution is more spread out and more uniform than the data, and training an RBM in a higher-level hidden space let Gibbs sampling mix faster between categories. The book adds that it remains unclear how to exploit this to train and sample deep generative models better.

Monte Carlo methods remain useful despite the difficulty of mixing. The book calls them often the best tool available, and they are the main tool for the intractable partition function of undirected models, which section 18 discusses.

• Mixing is the hard part of MCMC. Samples become correlated, and a chain can stay in one mode much longer than it should.
• An energy barrier between modes controls how often a chain crosses. Gibbs sampling struggles when each update is locked to a neighbour that sits in the same mode.
• Tempering with below 1 flattens the peaks so chains cross more easily, and parallel tempering swaps states between temperatures.
• When a hidden representation encodes the visible variable too precisely, the chain changes little. A deeper representation can mix more easily.

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 17.5 (pages 599–604), 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.