Back-Propagation through Random Operations

A sample is not a function

Training follows gradients, and gradients need a formula to differentiate. Many generative models contain a step where a random number generator produces a value. A random draw is not a formula, so the chain of derivatives seems to break there.

Think of a vending machine that drops a random candy. Each press gives a different candy, so the machine has no single output to differentiate. The trick in this chapter is to move the randomness to the side. The random part becomes an input that you do not train, and the machine becomes a fixed, smooth function of its settings.

The answer depends on what you hold fixed. A draw is random, but one particular draw is a definite number. If you keep the random number that produced it and change , the sample moves by a definite amount. The next two sections make that precise.

Reparametrizing a Gaussian

Sampling from a Gaussian looks like a single random event. The book rewrites it as an ordinary formula with an extra input. Draw a noise value from the standard normal (mean 0, spread 1), then compute the sample from it:

The mean shifts every sample by the same amount. The spread stretches the noise. The noise does not depend on or , so you can change them and still use the same . That is the whole idea: the parameters act on a fixed noise value, and the result is a deterministic function of the parameters.

Because the sample is now a formula, its derivatives exist. (These two derivatives are added here and are not printed in the book.) Changing by a small amount moves the sample by the same amount, so the derivative with respect to is 1. Changing moves the sample by times the change, so the derivative with respect to is itself.

Move the spread and watch each sample travel along its own line. The sample built from the noise value farthest from zero moves the most when the spread changes. The noise values stay the same while you move the controls, so each row is one fixed random draw seen through different parameters.

Any distribution as a function of noise

The Gaussian example generalizes. Any distribution with parameters can be written as a sample that comes from a function of a noise value :

Read the second line as a recipe. Draw the noise from a fixed, simple distribution. Feed it, together with the parameters , into . The output has the distribution you wanted. The derivative of with respect to then follows from ordinary back-propagation through .

Two conditions keep the trick valid. The parameters must not depend on , and must not depend on . The function must be continuous and differentiable, which in turn means must be continuous. The book notes that this technique is often called the reparametrization trick, stochastic back-propagation or perturbation analysis.

A second example, added here and not printed in the book, shows how far the recipe reaches. The exponential distribution with rate can be sampled by drawing a uniform noise value on (0, 1) and computing . This works because the formula is the inverse of the cumulative distribution, the running total of probability from 0 up to 1, applied to a uniform value. Differentiating gives , which is a formula you can use directly in training.

The bars are 2000 samples built from the uniform noise. The black curve is the exact density, and the bars follow it. Move the rate and watch the whole picture stretch, while the marked sample keeps its noise value and slides along the axis.

Discrete samples and step functions

Now let the output be discrete, for example a yes or no decision. The same recipe still applies, but the function must now be a step: it jumps from one value to another as the parameters cross a threshold.

The toy for this section and the next is a Bernoulli sample: a yes or no value that equals 1 with chance and 0 otherwise. The chance depends on the parameter through , an S-shaped curve called the logistic function. It rises from 0 to 1 as grows.

A step function has zero slope everywhere except at its jumps, and the jumps have no slope at all. So the derivative of a cost on a discrete sample carries no information for training. The book names this as the large problem for discrete outputs.

The sample follows the step curve. It switches only at the point where the probability passes the noise value. The expected value is a smooth curve, and its slope is at each point. A training signal based on the expected value exists, while a signal based on one sample is zero almost everywhere. The next section shows how REINFORCE recovers the slope from samples.

REINFORCE estimates the gradient

The book gives a family of estimators for this problem, called REINFORCE after its author Williams (1992). The idea is to differentiate the expected cost, which is smooth, and then to estimate that derivative by averaging over samples. The derivation takes four lines.

Equation 20.60 uses one assumption: the cost does not refer to directly. The book notes that this assumption can be relaxed. The next step uses the derivative rule for the logarithm, , which the book states in the text beside Equation 20.61. The left-hand side, , is called the score on this page. It measures how the log-probability of a sample changes when the parameters move.

The sum over all is replaced by an average over samples drawn from . The right-hand side is the estimate, which this page writes as . It is unbiased: if you repeat the sampling many times and average the estimates, the average equals the true gradient. is the cost of each sample.

In the toy of section 4, the cost is , so the true expected cost is and its true derivative is . (This toy is added here and is not printed in the book.)

At one sample the estimate is either 0 or , so the histogram has two bars. As grows, the average spreads less and the histogram narrows around the true gradient. The spread falls in proportion to 1 over the square root of , so four times as many samples halves it.

Baselines reduce the variance

The plain estimator is unbiased, but it is noisy. Its variance, the average squared distance of an estimate from the true gradient, can be large. The book reduces it with a baseline, a number that is subtracted from the cost before the score is applied. Any baseline that does not depend on the sample leaves the expected value unchanged, because the expectation of the score is zero:

Equations 20.63 to 20.65 show that the average of the score is zero, which is why a constant shift changes nothing in expectation. Equations 20.66 and 20.67 subtract that zero from the estimate. The book uses the same argument to show that a baseline that depends on does not bias the estimate either.

The toy of section 5 makes this concrete. (The estimator with a baseline, its mean and its variance in this toy are added here and are not printed in the book.) Per sample, the estimate is . Its mean is for every , and its variance is

Watch the two bars move. For a fixed , the mean stays on the dashed line for every baseline, while the spread changes. The curve below the bars shows the variance against the baseline. It is a parabola, and it has a lowest point.

The optimal baseline and variance normalization

The variance in section 6 depends on the baseline, so it is natural to ask which baseline gives the least variance. The book answers with a formula for each element of . The optimal baseline for element is:

In practice the book does not compute this expectation by hand. The baseline is estimated by adding extra outputs to the network and training them with a mean squared error. The targets are the two expectations inside the fraction, measured on the samples. The gradient estimate then uses the baseline in the form of Equation 20.69:

The book also cites Mnih and Gregor (2014), who used a single shared output for all elements of . That output is trained on the cost itself, so the baseline approximates the expected cost. A second heuristic from the same work divides the centred cost by a moving estimate of its standard deviation. The book calls this variance normalization. It acts like an adaptive learning rate that keeps the size of the update steady while the cost changes during training.

In the one-parameter toy, the optimal baseline has a clean form. (This simplification is added here and is not printed in the book.) Equation 20.68 gives , which is a function of through . The demo below compares the optimal baseline with the two fixed choices.

In this toy the optimal baseline removes all of the variance. That is a feature of a binary sample with one parameter. The book does not claim that the optimal baseline removes the variance in general, so do not read this toy as a measure of the gain for a network. The lesson to keep is the design rule: subtract a number that does not depend on the sample, and the estimate keeps its mean while its spread can fall. The expected cost is a choice that can also make the spread larger. Move to the right-hand end of its range, and the expected-cost bar rises far above the bar for no baseline.

• A sample from a distribution with parameters becomes a deterministic function of noise , so back-propagation works (Equations 20.54 to 20.57).
• For a Gaussian, the reparametrization gives the derivatives 1 with respect to and with respect to .
• For discrete samples the derivative of the sample is zero almost everywhere, so the book uses REINFORCE on the smooth expected cost (Equations 20.58 to 20.62).
• REINFORCE is unbiased, but noisy. Averaging over samples shrinks the spread in proportion to 1 over the square root of .
• A baseline that does not depend on the sample keeps the mean and can reduce the variance. The optimal baseline is given by Equation 20.68, and variance normalization is a practical heuristic for scaling the update.

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 20.9 (pages 687–692), 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.