§17.5–17.5.2The Challenge of Mixing between Separated Modes · Tempering · Depth

§17.5 The challenge of mixing between separated modes

MCMC’s central weakness is slow mixing slow mixing When successive Markov-chain samples stay highly correlated and fail to visit modes in proportion to probability; the chain gets stuck in one mode instead of exploring. defined in ch. 17 — open in glossary . Ideally successive samples would be independent and visit regions of $\boldsymbol{x}$ in proportion to their probability. Instead — especially in high dimensions — they become strongly correlated. A Gibbs chain behaves like noisy hill-climbing on probability (noisy gradient descent on energy): it takes small steps that mostly lower the energy, so once it finds a mode mode (of a distribution) A region of high probability / low energy (e.g. a connected manifold of similar images) around which a Markov chain tends to random-walk. defined in ch. 17 — open in glossary (a region of low energy — say, a connected manifold of images of one object) it random-walks within that mode and only rarely escapes.

Whether it can escape is governed by the energy barrier energy barrier A region of low probability / high energy separating two modes; transitions across a high barrier are exponentially unlikely, causing slow mixing. defined in ch. 17 — open in glossary between modes: crossing a barrier of height $\Delta E$ is exponentially unlikely in $\Delta E$. When high- probability modes are separated by wide low-probability valleys — exactly the structure of a distribution with one manifold per class — the chain stays put far longer than it should. See all three regimes of the book’s figure 17.1, and use the temperature slider to break out of the trapped case:

The problem is sharpest for latent-variable models, where we alternate sampling $p(\boldsymbol{x}\mid\boldsymbol{h})$ and $p(\boldsymbol{h}\mid\boldsymbol{x})$. Good mixing wants $p(\boldsymbol{h}\mid \boldsymbol{x})$ to have high entropy (so $\boldsymbol{h}$ can wander); a useful representation wants $\boldsymbol{h}$ to carry high mutual information with $\boldsymbol{x}$ (so it pins $\boldsymbol{x}$ down). These pull in opposite directions — the sharper a Boltzmann machine’s learned distribution, the worse it mixes:

§17.5.1 Tempering to mix between modes

If the peaks are too sharp, flatten them. Energy-based models make this trivial: add an inverse-temperature $\beta$ to the energy.

Tempering tempering Flattening a distribution via p_β(x)∝exp(−βE(x)) with β<1 (β=1/temperature) so a chain can mix between modes more easily; e.g. tempered transitions, parallel tempering. defined in ch. 17 — open in glossary mixes between the modes of $p_1$ by drawing samples at $\beta < 1$, then relating them back to $\beta = 1$. Two schemes — tempered transitions and parallel tempering parallel tempering Running many chains at different temperatures simultaneously and stochastically swapping states, so high-temperature chains that mix freely feed the temperature-1 chain. defined in ch. 17 — open in glossary — differ in how the temperatures are arranged:

Tempering helps but has not cracked the problem: there are critical temperatures around which the temperature must be changed very slowly for tempering to work, which is expensive.

§17.5.2 Depth may help mixing

There is a structural fix hinted at by representation learning. If $p(\boldsymbol{h}\mid\boldsymbol{x})$ encodes $\boldsymbol{x}$ too precisely, sampling $p(\boldsymbol{x}\mid\boldsymbol{h})$ barely moves $\boldsymbol{x}$ and mixing fails. But make $\boldsymbol{h}$ a deep representation and the chain in $\boldsymbol{h}$-space can mix more easily: autoencoders and RBMs tend to produce a marginal over $\boldsymbol{h}$ that is more uniform and more unimodal than the data distribution over $\boldsymbol{x}$ — plausibly because minimizing reconstruction error while using all of representation space spreads the training examples out, well-separated, in $\boldsymbol{h}$-space. Bengio et al. (2013a) found that deeper stacks yield top-level marginals that are more spread out, with smaller gaps between the regions for different modes (classes), so Gibbs sampling in that higher space mixes faster between modes. How best to exploit this remains open.

Despite the mixing difficulty, Monte Carlo methods are often the best tool available — and they are the primary weapon against the intractable partition function of undirected models, the subject of chapter 18.