Markov Chain Monte Carlo Methods

Why a chain can help

Sampling is easy when you can draw from the formula directly. Many models in deep learning cannot be sampled that way. An energy-based model writes its probability as . The energy is low where the state is likely and high where it is not. The constant that makes the probabilities add to one is hard to compute, so a direct sampler is usually out of reach.

A Markov chain avoids that constant. It starts in any state and makes small random moves. Each move compares two states, and the comparison uses a ratio in which the constant cancels. Over many moves the state starts to look like a draw from .

Picture a walker on six stepping stones who prefers the low ones. Predict where the walker spends most of its time when the stones get higher towards the right, then run the demo.

Pick a guess.

The rule is simple. Propose one step to the left or to the right. Always accept a move to lower energy. Accept a move to higher energy with probability , where is the rise in energy from the current stone to the proposed one. This is a special case of the Metropolis-Hastings algorithm, which section 17.4 names. The demo uses it to show the idea, and the book does not write it out here.

The walker never computes . Every decision uses the ratio of two weights, and the constant cancels. That is why a chain works when the constant is out of reach.

A chain as a transition matrix

Number the states 1, 2, 3 and so on. Keep track of the chain with a vector that holds one probability per state. The book describes a chain by its transition , the probability that a random update moves the state from to . Updating the distribution of many chains running in parallel uses one transition matrix , whose entries are .

Equation 17.17 says that entry is the probability of state under . The next equation is the rule for one update.

Each state collects probability from every state that can move to it. Writing the same rule with the matrix gives equations 17.19 and 17.20.

Each column of is a probability distribution, so the columns add to one. Such a matrix is called stochastic. Repeating the update t times means multiplying by the matrix t times.

The demo uses a ring of four states. The chain starts in state 1. With the stay probability it stays where it is. Otherwise it moves to one of its two neighbours, each with probability . The bars show after steps.

Pick a guess, then set the stay probability to 0 and the steps to 10 to check.

The stationary distribution and eigenvalues

Write the chain's distribution in terms of the eigenvalues of . The matrix can be split into eigenvectors and eigenvalues , and each eigenvalue is raised to the power .

Every eigenvalue other than 1 shrinks towards zero as grows, so the distribution settles. The eigenvalue 1 survives. The distribution that stays put is called the stationary distribution, or equilibrium distribution.

The stationary distribution is an eigenvector of with eigenvalue 1. Once the chain reaches it, further updates leave the distribution unchanged, even though each individual state keeps moving. The book adds that the Perron-Frobenius theorem guarantees that the largest eigenvalue is 1 when some power of the chain has a non-zero probability of every transition.

The demo below uses the same ring. Its eigenvalues are 1, , and . The error after steps is the largest gap between and the uniform distribution. The error shrinks at the rate set by the second largest eigenvalue in size.

The book adds that the stationary distribution is a fixed point of the update: is the expectation over states drawn from of the transition.

For a discrete state the expectation is a sum, and for a continuous state it is an integral. The same fixed-point idea covers both cases.

Burn-in, mixing time and many chains

A chain starts from an arbitrary state. The early steps, before the distribution has settled, are called burn-in. The number of steps needed to reach the stationary distribution is the mixing time. The book states that this number is hard to know in advance, and that testing whether a chain has reached equilibrium is also hard. In practice one runs the chain for a long enough time and checks heuristically, for example by inspecting samples or measuring how correlated successive samples are.

Successive samples from one chain are highly correlated. One remedy is to keep only every th sample. Another is to run several chains in parallel, one per desired sample. The book notes that practitioners often use a number of chains similar to the minibatch size, and that a commonly used number is 100. The demo below uses 200 chains, all starting in state 1.

Total variation, a measure added here and not used in the book, is the largest difference between the probabilities of two distributions over any set of states. Here it is half the sum of the absolute gaps to the uniform distribution. The readout shows that number, so you can see how close the chains are to equilibrium.

• A Markov chain makes random moves, and each move uses only a ratio of probabilities, so an unknown normalising constant cancels.
• The distribution after steps is raised to the power times the starting distribution (17.21).
• The stationary distribution satisfies = (17.23), and eigenvalues of size below 1 make the chain forget its start.
• The second largest eigenvalue in size controls how fast the chain mixes. Burn-in discards the early steps, and parallel chains give independent samples at once.

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.3 (pages 595–599), 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.