Section 1
One variable at a time
How to use this pageClick the colored symbols. Clicking a symbol explains it and lights up the same symbol in the other equations. Commit to a guess before each reveal. Each demo shows the result once you have chosen.
x1, x2 the two variables
rho the correlation
sweep one pass of updates
p the target
Section 17.3 showed that a chain needs a transition whose stationary distribution is the target . Section 17.4 of the book calls Gibbs sampling a conceptually simple and effective way to build it. Pick one variable, sample it from its distribution given all its neighbours in the graph, and repeat. That update is called Gibbs sampling. The book also names the Metropolis-Hastings algorithm, which is widely used in other disciplines, but says that deep learning rarely uses anything other than Gibbs sampling.
A small picture helps. Think of a crowd on a long street, where each person moves only after looking at the people next to them. Nobody needs the whole crowd's positions at once, only the nearest neighbours. Each small move is simple, and together the moves explore the street.
Try it on the simplest case: two normal variables with unit spread and correlation . Predict first. The starting point is at the top left, where is about −2 and is about 2. Which path would a Gibbs chain trace when the correlation is high?
Pick a guess.
Update one coordinate at a time
path of the chainone standard deviation of the target
Challenge +8 XPLet the chain cross the line = 0 at least 20 times in at least 100 sweeps.
An update samples one coordinate from its conditional distribution, which the other coordinate fixes. For this pair the conditional is normal. This formula is added here and is not printed in the book. It is the standard result for two unit normal variables with correlation .
Click any coloured symbol to see what it means.
Click any coloured symbol to see what it means.
The conditional mean is , so is pulled towards times the current . The conditional spread is . When is near 1 the spread is tiny, and each update can only move a little.
NoteThe book does not write out this example. It describes Gibbs sampling in general, and the formulas above are added to make the demo concrete.
Section 2
Why correlation slows the chain
Section 17.5 of the book notes that a Gibbs chain mixes slowly when the variables are strongly tied together. If one variable can only change a little given the other, the chain can only move a little at a time. The figure in section 17.5 shows this with three pictures. This section gives you the same effect in numbers.
Predict first. The correlation is 0.95. Which description fits the path of the chain over many sweeps?
Pick a guess.
How far does the chain travel?
path of the chainone standard deviation of the target
Challenge +8 XPPick a correlation so that 200 sweeps travel less than 150 units in total, measured along both axes.
The readout adds up how far the chain moves on each sweep, measured as the sum of the changes in and . Compare a correlation of 0 with one of 0.95. With no correlation the chain jumps across the plane, and the total travel is large. With strong correlation the chain creeps along the diagonal, so the total travel is much smaller for the same number of sweeps.
NoteThe readout uses the same random numbers each time, so the picture is repeatable. Changing the correlation starts the chain again from the same point.
Section 3
Block Gibbs sampling
Single-variable updates are not the only option. The book says that several variables can be sampled at the same time, provided they are conditionally independent given all their neighbours. Updating such a group together is called block Gibbs sampling. The book's example is the restricted Boltzmann machine of section 16.7.1, where all hidden units are conditionally independent of each other given the visible units. All visible units can therefore be sampled in one block, and so can all hidden units.
The demo below uses a small graph in that shape: three visible units on the left and two hidden units on the right. Every visible unit is joined to every hidden unit. Predict first. Which pair cannot be updated together as one block?
Pick a guess.
Pick a block of units to update together
Click units to select them, then update the block.
selected unitunselected unit
Challenge +8 XPSelect three units that form a valid block, then update it.
Challenge +8 XPTry a block with a unit and one of its neighbours, and press update to see the readout explain why it is not allowed.
The rule behind the readout is short. Two units can share a block only when neither one is a neighbour of the other. Inside the graph, the conditional of a unit depends on its neighbours. If a neighbour is in the same block, its value is changing at the same time, so the conditional would use an out-of-date value.
- Gibbs sampling updates one variable at a time, each from its conditional distribution given all its neighbours.
- For two normal variables the conditional of one given the other is normal with mean and spread .
- A high correlation makes the conditional spread small, so the chain moves slowly and travels little in each sweep.
- Variables that are conditionally independent, such as all visible units of a restricted Boltzmann machine, can be updated together as one block.
Final quizCheck 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.4 (pages 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.