Restricted Boltzmann Machines

The three shapes at the top of this page are the ones the associative memory page stored, a T, an L and a cross, each drawn on a grid of twenty-five cells. That network held one weight for every pair of cells, and the shapes survived inside it as a table of which cells agreed with which. During recall, individual cell updates reduced or preserved the network’s energy until it settled. A stored shape could be recovered, but other stable patterns were also possible. Recall did not guarantee the nearest stored shape.

Here no cell is wired to any other cell. Every cell is wired instead to a short row of hidden units, the bars under the shapes in the playground, and the hidden units are wired to nothing but the cells. Click the T and two of the three bars stand up while the third stays down.

Click the L and a different pair stands. Each shape has become a short code over the hidden units, and nobody gave the machine that code. It arrived at one, because three hidden units were all it had to tell three shapes apart with.

Every model on this site before the memory page learned a mapping. Heights and weights went in, an answer came out, and the question the model could answer was always of the form what is the answer for this row. A model of a distribution answers a different question. Handed a grid, it says how plausible that grid is, and it has an opinion about all thirty-three million grids the twenty-five cells can make, though it was only ever shown three of them.

That is a strictly larger claim than a mapping, and it buys three things a mapping cannot. It can be asked about a grid it has never seen, and answer with a number rather than a refusal. It can be asked to produce a grid, since a distribution can be drawn from. And it can be asked to finish a grid, filling in the cells that are missing from the ones that are there, which is the same question a mapping answers only if you decided in advance which cells were the inputs.

A distribution over twenty-five cells has to say something about how the cells depend on one another, since the whole content of the three shapes is that certain cells are lit together. The obvious way to say it is the memory page’s way, a weight for every pair, and that is three hundred numbers for twenty-five cells and grows as the square of the grid.

The hidden units are the other way. Give the model a few extra switches nobody measured, wire every cell to every switch and no cell to any cell, and the cells become dependent on each other through the switches rather than directly.

So a hidden unit is a fact the machine invents about a grid. Nothing in the data says what it should mean, and after five hundred passes on these three shapes the first unit turns on for the T and the cross and off for the L, which is a fact about the shapes that was never written down anywhere.

The three shapes end up at three corners of a small cube, the T at 110, the L at 011 and the cross at 101, and that is the first description on this site that a model built for itself rather than being handed.

Write v for the twenty-five cells and h for the hidden units, both holding zeros and ones. Every joint state of the two gets an energy, which is the memory page’s energy with a second layer and a weight of its own for every unit, and the probability of a state falls off as its energy climbs.

E(v, h) = −Σᵢ aᵢ·vᵢ − Σⱼ bⱼ·hⱼ − Σᵢ Σⱼ vᵢ·wᵢⱼ·hⱼ
P(v, h) ∝ exp( −E(v, h) )

Read the three terms as three kinds of preference. The first says how much each cell likes being lit whatever else is happening, the second says the same for each hidden unit, and the third is the only term that ties the two layers together. A large positive weight between a cell and a unit means the pair likes being on together, and a large negative one means it does not.

The restriction is one sentence. No cell is joined to another cell and no hidden unit to another hidden unit, so the energy above contains no term in vᵢ·vₖ and none in hⱼ·hₗ. What that buys is not tidiness. Fix the cells and every hidden unit is left with nothing to consult but its own weighted sum of them, so no hidden unit’s decision depends on any other hidden unit’s, and the whole layer can be redrawn at once rather than one unit at a time.

On the memory page that was not so. Every cell there read the cells around it, so the cells had to be visited one at a time and the answer depended on the order they were visited in. Here a pass in each direction is a single piece of matrix arithmetic, and the twenty-five cells and three hidden units of this page could be twenty-five thousand and three thousand with no change to the method.

Because of the restriction, each hidden unit switches on independently of the others with the probability the sigmoid gives its own weighted sum, and each cell does the same given the hidden units. Those two lines are everything the machine ever does with a grid.

P(hⱼ = 1 | v) = σ( bⱼ + Σᵢ vᵢ·wᵢⱼ )
P(vᵢ = 1 | h) = σ( aᵢ + Σⱼ wᵢⱼ·hⱼ )

Going up is reading a grid as a code, and going down is drawing a grid from a code. Running the two in turn is a walk over grids that, left alone for long enough, visits each grid as often as the machine believes it deserves, and that walk is the only handle anyone has on a distribution nobody can write down.

T score = 5 × 0.8 − 2 = 2
P(unit on | T) = sigmoid(2) ≈ 0.88

L score = 1 × 0.8 − 2 = −1.2
P(unit on | L) = sigmoid(−1.2) ≈ 0.23

It is worth seeing that the first line is forced rather than chosen, because the same argument is what fails the moment a wire is put inside a layer. Fix the cells and write zⱼ for hidden unit j’s own weighted sum. Everything in the energy that mentions the hidden units is then a sum of one term per unit, and each term involves only that unit.

zⱼ = bⱼ + Σᵢ vᵢ·wᵢⱼ
E(v, h) = −Σᵢ aᵢ·vᵢ − Σⱼ hⱼ·zⱼ

P(h | v) ∝ Πⱼ exp( hⱼ·zⱼ )
P(hⱼ = 1 | v) = exp(zⱼ) / ( 1 + exp(zⱼ) ) = σ(zⱼ)

Learning here is one rule applied to every wire separately, and the rule reads two numbers. Hold the cells at the shapes and count how often a wire’s two ends are on together. Then let the machine go for one step of its own, drawing hidden units from their probabilities and cells from those, and count the same thing again. Move the weight by the rate times the difference.

Δwᵢⱼ = rate · ( ⟨vᵢ·hⱼ⟩ at the data − ⟨vᵢ·hⱼ⟩ after the step )
Δaᵢ = rate · ( ⟨vᵢ⟩ at the data − ⟨vᵢ⟩ after the step )
Δbⱼ = rate · ( ⟨hⱼ⟩ at the data − ⟨hⱼ⟩ after the step )

The first count pushes up the plausibility of what the data actually shows. The second pushes down the plausibility of what the machine currently believes, whether or not the data agrees, and it is what stops the first count simply inflating every weight without bound. Where the two counts agree the wire stops moving, which is the machine saying that what it believes and what it was shown have become the same thing.

Twenty-five cells and three hidden units is a table of seventy-five wires, so the rule is easier to check on something smaller. Take two rows of four cells, both lit in the first two, both dark in the third, and differing in the fourth. Two hidden units, the same rate of 0.1, and the same starting weights drawn small so that every unit begins near a half for every row.

…

Cell 1 is on in both observed rows. The observed association with hidden unit 1 is therefore the average of that unit’s activation probabilities, about 0.5035. In the two reconstructed rows, cell 1 is off, so the reconstructed association is zero.

weight update = rate × (observed association − reconstructed association)
              ≈ 0.1 × (0.5035 − 0)
              ≈ 0.0504

The weight moves from about 0.0013 to about 0.0516 using the full-precision values. The same subtraction is performed for every connection.

The hidden units’ own weights barely move on this step, none of them by as much as a thousandth, and the reason is worth a sentence. Both counts for a hidden unit are averages of a probability that is still very near a half everywhere, because the weights started as noise, so the subtraction very nearly cancels. Breaking that near-cancellation is what the first stretch of any of these fits is spent on, and it is visible again in Part 4.

On the three shapes, the first connection has an observed association of about 0.4967 and a reconstructed association of about 0.1681. Apply the same update rule.

weight change ≈ 0.1 × (0.4967 − 0.1681) ≈ 0.03286
new weight ≈ 0.00126 + 0.03286 ≈ 0.03412

Every association lies between zero and one. Their difference therefore has magnitude at most one, so this update cannot change a weight by more than the learning rate.

The rule is not arbitrary. Differentiate the log likelihood of the data with respect to a weight and the answer really is a difference of two counts, the first taken with the cells held at the data and the second taken under the machine’s own distribution.

∂ ln P(v) / ∂wᵢⱼ = ⟨vᵢ·hⱼ⟩ at the data − ⟨vᵢ·hⱼ⟩ under the model

The first count is cheap, since the data is right there. The second is not. Counting under the machine’s own distribution means running the up-and-down walk of step 6 until it has forgotten where it started, and how long that takes is not knowable in advance, which makes the true gradient intractable rather than merely slow. What is done instead is to start the walk at the data and stop it after a single alternation, and use whatever it has arrived at.

That last row is the part that is easy to misread. Most approximations on this site get better with more data. This one does not, because what is wrong with it is where the walk was stopped, and no amount of data changes where the walk was stopped. Running more alternations before reading the second count reduces the error and never removes it.

A fit stops either when it has used up its passes or when nothing moved. The second condition needs reading carefully, because on every other page of this site a walk that stops moving has arrived somewhere. Here it means the weights stopped moving and nothing more, since nothing was ever climbing a likelihood, and the four-cell set gives the cleanest possible demonstration of the difference.

On the three shapes the opposite happens. At five hundred passes and a constant rate the fit has not settled and reports so, because the drawing keeps the counts jittering, and that is the ordinary case rather than a failed one. A rate that decays towards zero would make it report itself settled for the trivial reason that the steps had become too small to see.

A reconstruction is the two lines of step 6 run once each. Push a grid up to the hidden units, read what they say, and push that back down to the cells, and what comes out is one probability per cell rather than a grid of noughts and ones. That is the shaded grid in the playground, each cell darkened by the probability the machine gives it.

The important part is what is not consulted on the way back down. The cells the probe held are gone by then. All the return journey has is the code the hidden units settled on, and on these three shapes that code is three numbers. So a reconstruction is not a repair of the grid you handed in. It is a fresh drawing of whatever grid that code describes.

Take the T with the same five cells flipped that the memory page’s first scramble flips, and put it through machines that have learned for different lengths of time. Every grid below is a separate fit from the same starting weights, so the fit at ten passes really is the first ten passes of the fit at five hundred.

The shape of that fall is the thing to look at, because it is not the shape a gradient descent produces. For the first hundred and fifty passes the answer barely moves, eighteen of the twenty-five cells landing on the undamaged T and the gap staying above 0.15, and at a hundred and fifty it is briefly worse at seventeen.

Then it collapses, twenty-four cells at two hundred passes, all twenty-five at three hundred with a gap of 0.0380, and 0.0061 by five hundred. A run cut short at a hundred and fifty passes would have reported a machine that had learned nothing while it was most of the way to learning everything.

What happened at five hundred is that the damaged grid read as 110, which is the T’s own code, and the return journey then drew a T. The stem cell the damage switched off comes back near 0.9 and the four cells it switched on come back below a tenth. Nothing rolled downhill into a stored copy, since there is no stored copy anywhere in the machine; the twenty-five cells were summarised as three numbers on the way up, and what came down was drawn from those three numbers with the probe no longer in the picture.

The damaged T is a grid the machine never saw, but it is near one it did. Press the second button on the ladder above and the probe becomes a square, an outline the machine was never given and which is not a damaged copy of anything it was. This is where a distribution and a store of originals part company.

After five hundred passes the square comes back with seventeen of twenty-five cells rounding to the square itself and a gap of 0.2263, which is to say it is not rebuilt. What it reads as is 010, and that is not any of the three stored codes. Only the second hidden unit rises, which is the unit the L raises, so what returns is the L’s stem and foot at probabilities between 0.4 and 0.8, the rest of the square’s top row hanging around 0.45, and the square’s side walls below a tenth.

The machine has described the square as most of an L, because most of an L is the nearest thing in its account of the world.

The number under the sliders in the playground is the mean squared gap between the three shapes and what comes back from them, and it is the only cheap thing to watch during a fit. It is not what is being minimised. Nothing on this page minimises anything, as step 11 laid out, and this number is not even the quantity the biased step is a biased step towards.

On the three shapes at three hidden units it falls from 0.2437 after one pass to 0.0057 after five hundred, and no single shape ends above 0.01. A quarter is roughly what a machine that answers half for every cell scores, since each cell is then half away from a nought or a one, which is why the number starts there.

The quantity that compares two grids is the energy of Part 2 with the hidden layer summed out rather than sampled, which the restriction makes possible in closed form. It is called the free energy, and lower means the machine finds the grid more plausible.

F(v) = −Σᵢ aᵢ·vᵢ − Σⱼ ln( 1 + exp( bⱼ + Σᵢ vᵢ·wᵢⱼ ) )

A probability would be exp(−F) divided by the same quantity summed over every grid, and that sum runs over all thirty-three million grids here and over every possible image in general. Nobody computes it. So a single free energy on its own means nothing at all, and only differences between them carry information, which is why every readout on this page puts a grid’s score beside another grid’s.

P(v) = exp( −F(v) ) / Σᵤ exp( −F(u) )

So the question is what the ranking looks like once the machine has learned. Five grids go to one fit on the three shapes at three hidden units after five hundred passes, and each one is drawn beside what comes back from it.

…

The ordering runs the way it should and the spacing is the informative part. The T scores −24.50, and the L and cross −24.78 and −23.88 beside it. The T with five cells flipped scores −11.82, less than half as deep, which says the machine has learned that a T has a full top row and a stem and that a T with holes in it fits that worse. Thirteen cells scattered at random score −3.71, the square −0.77, and the T with every cell reversed +2.06, above the line entirely.

Two honest qualifications go with that. The square scores worse than the random scatter, so the ranking is not a ranking of how shape-like a grid looks; it is a ranking of how well a grid fits the account the machine built, and a square disagrees with that account more sharply than a scatter does.

And the ordering has to be earned. At one pass all five grids score within a tenth of one another, and the damaged T is actually below one of the stored shapes; the probe only rises above every stored shape from about a hundred passes on.

The closed form is worth deriving once, because it is the only place on the page where the restriction pays off in a way that looks like algebra rather than like speed.

Σₕ exp( −E(v, h) ) = exp( Σᵢ aᵢ·vᵢ ) · Πⱼ ( 1 + exp(zⱼ) )
F(v) = −ln Σₕ exp( −E(v, h) ) = −Σᵢ aᵢ·vᵢ − Σⱼ ln( 1 + exp(zⱼ) )

Set every weight to zero and the sum inside each logarithm vanishes, so every term is ln 2, and the free energy of any grid at all is minus the number of hidden units times ln 2. With three hidden units that is a number you can work out on paper.

F = −3 · ln 2 = −3 · 0.6931 = −2.0794

A fit cannot start from zero weights, because units with identical weights compute identical functions and stay identical forever, so it starts from small noise with a spread of 0.01 and both sets of unit weights at zero. The hollow bars in the playground are that starting point, observed by running a single pass at a rate of zero, which adds nothing to what the seed drew.

They come out at −2.08 for the T and −2.10 for the L and the cross, and the damaged probe at −2.07, each within the noise in those starting weights of the hand figure.

The width of the hidden layer is given rather than learned, so it has to be chosen, and the honest way to choose it is to measure. Every bar below is a fresh fit on the same three shapes from the same starting seed for the same five hundred passes, differing only in how many hidden units it was allowed.

…

One unit cannot do the job at all. It reads every one of the three shapes as 1, so all three have the same code, and since the code is all the return journey has, all three come back as the same grey average, with the gap at 0.1700 and none of the three rebuilt. Two units give three different codes, which is enough to tell three shapes apart, and the gap falls to 0.0351 with two of the three coming back cell for cell. Three units reach 0.0057 and all three shapes.

The reason two units suffice for the codes is that they are simultaneous switches rather than alternatives, so two units offer four codes and not two, and three offer eight. That is also why the three shapes end up at 110, 011 and 101, three different pairs out of three, rather than each shape claiming one unit for itself.

The textbook expectation is that the gap falls as the width grows, and on this fixture it does not. Five units score 0.0165, which is worse than four at 0.0042 and worse than three at 0.0057, and then six recovers to 0.0052 and seven reaches 0.0024 before eight goes back up to 0.0030. I looked for the monotone curve and it is not there.

Two things are going on and they are worth keeping apart. Above three units the width is no longer the constraint, so what the numbers move with is which starting weights were drawn and which way the drawing sent the chain, and the next step measures that effect on its own. It comes to a spread of 0.0157 across six seeds at a fixed width of three, which is larger than the 0.0141 the whole sweep from three units to eight covers at a fixed seed.

And the gap is not the objective anyway, so a machine that scores 0.0024 has not been shown to have a better account of the shapes than one scoring 0.0057; it has been shown to pass them through more faithfully, which a wide enough layer can do without describing anything.

Every fit on this page starts from small random weights and draws a coin for every unit at every pass, so a seed decides quite a lot. The clean way to find out how much is to fit the same shapes six times under six seeds, and then fit the first one a second time.

…

Two fits under one seed agree to the last bit, the largest gap between any two matching weights coming out at exactly 0.0, and their gaps on the shapes are the same number. Two fits under different seeds hold weights 5.25 apart, which is larger than most of the weights themselves. So the seed fixes the machine completely and nothing else about the setup does.

What survives is the job getting done. Every one of the six seeds gives the three shapes three different codes, and the gap on the shapes runs from 0.0057 to 0.0215 across them, a spread of 0.0157, so the worst seed is about four times the best and all six have learned to tell the shapes apart.

What does not survive is which unit stands for what. Under the first seed the T reads as 110 and under the second it reads as 011, and neither is more correct. The units have no names and no order, so a machine that has swapped two of them is the same machine wearing different labels, and anything downstream that read unit 1 as though it meant something across fits would be reading a fact about the seed.

Both models on the last two pages have now been given the same three shapes, so they can be put side by side on the same five grids. The memory stores a list and recall is a fall into the nearest entry; this machine stores nothing of the kind and answers by asking what plausible grid its description of the probe would draw.

…

Read the middle and right columns down. The memory answers every one of the five grids with one of the three shapes, cell for cell, or one of them inverted, because those are the only things it can answer with. The machine answers with probabilities, and on three of the five those probabilities round to a stored shape and on two of them they round to no shape at all.

The square is where they part most clearly. The memory falls into the L exactly, while the machine gives back a grid that is mostly the L with the rest of the square’s top row hanging around a half and nothing else of the square surviving, and nobody stored that grid.

There is one difference between the two that is not a matter of degree, and the table above measures it in a single column. The memory’s energy is a sum over pairs of cells of a weight times both their values, so reversing every cell flips two signs in every term and leaves the term unchanged. A stored shape and its exact opposite therefore have identical energies, and the opposite is a resting state whether anyone wanted it or not.

Here they do not. Across the five grids the memory’s largest difference between a grid and its reversal is exactly 0.0, and the machine’s is 26.57. The T scores −24.50 and its reversal +2.06, while under the memory both score −11.20. The reason is that the cells run from nought to one rather than from minus one to one, so a cell contributes to the score when it is lit and contributes nothing when it is dark, and each cell has a weight of its own that a reversal reads the wrong way round.

Very little of this method is forced, so a description that does not state its choices cannot be reproduced. The list below is what has to be said, and beside each is what was chosen for the machine behind this page.

Here is the list of edges the page claims to handle, with what each one should do. Underneath it is the same list run against the machine behind this page when you loaded it, so the two can be read against each other rather than taken on trust.

…

The boundary checks reflect different mathematical requirements. For the binary-unit formulation, values must lie in the supported range. The implementation also accepts fractional values in that range as mean activations, which allows gray pixels to be supplied without pretending they are sampled binary states.

Shape and configuration checks occur before fitting. Unknown settings are rejected so a caller cannot silently run a default configuration instead of the one intended.

Some unusual inputs remain valid. A single pattern can define an empirical distribution. A column that is always zero need not cause division by a feature spread. More hidden units than visible units are also permitted, although the resulting hidden representation is wider than its input.

Two rows are worth stating plainly rather than arguing with. A rate of zero is accepted, and the walk then stops after a single pass calling itself settled, which is correct under the definition in step 12 and would mislead anyone who read settled as finished. And a probe with its cells given in a different order is accepted and answers identically, because cells are matched by name rather than by position, which is a promise worth having and one that hides a reordering bug rather than catching it.