The Log-Likelihood Gradient

The partition function

An undirected model scores every state with a positive number , the unnormalized probability. The scores do not have to add up to 1. To get a probability, the model divides every score by one shared number , the partition function:

The partition function is the total of all the scores. It is a sum over every state, or an integral for continuous states:

Think of as the weight of each sweet in a jar and as the weight of the whole jar. The probability of picking a sweet is its weight divided by the total. Nothing about the sweets changes when you weigh the jar, but you need the total to turn weights into probabilities.

The trouble is that the sum has one term for every state. A model of 100 binary variables has 2¹⁰⁰ states. This chapter is about training and evaluating models for which that sum cannot be computed. Some models avoid the sum by design, and chapter 20 covers them.

Each state gets a bar whose height is . Raise one score and the total rises, so every other bar shrinks a little. That shared division is the whole job of the partition function.

Positive and negative phases

Training by maximum likelihood means raising the log-likelihood of the training examples. Its gradient with respect to the parameters has two parts, as Equation 18.4 shows:

The first part is the gradient of the unnormalized log-probability. It is the positive phase, because it pushes up the scores of the examples in the data. The second part, the gradient of , is the negative phase. It enters with a minus sign, so each update lowers Z, the total that every probability is divided by. Section 3 shows that this term is an average over states that the model itself generates, so the negative phase lowers the scores of those states.

For most undirected models of interest the negative phase is difficult. Models with no latent variables, or with few interactions between latent variables, typically have an easy positive phase. The quintessential example of a model with an easy positive phase and a hard negative phase is the restricted Boltzmann machine, whose hidden units are independent of each other given the visible units. This chapter focuses on the hard negative phase. Models with hard positive phases, which have complicated interactions among hidden variables, are covered in chapter 19.

The demo uses four states with a model and a small data set with frequencies 2, 5, 8 and 5. The positive phase is the average state in the data, which is 1.80 and never changes. The negative phase is the average state under the model, and it does change. The gradient is the difference. When the model average is below 1.80 the gradient is positive, and raising the parameter helps.

Look at the readout at large values. The model average approaches 3 but never passes it, so the gradient stays negative once the parameter passes its best value. The best value is where the two phases are equal.

Deriving the gradient of log Z

Only the negative phase needs new work. Here is the derivation of , one line at a time. Press Next line to reveal each step and its reason.

The steps are short. Equation 18.6 is the chain rule for the logarithm. Equation 18.7 replaces the gradient of by the gradient of its sum (Equation 18.3). Equation 18.9 writes each score as an exponential of its logarithm, Equation 18.10 applies the chain rule to that exponential, and Equation 18.11 cancels the logarithm against the exponential. Equation 18.12 uses to turn the scores into probabilities. The last step, 18.13, rewrites the sum as an average under the model. That is the meaning of the subscript : the states are drawn from the model.

The derivative and the sum can swap places in Equation 18.14, which is the Leibniz rule for differentiation under the integral sign. It holds under regularity conditions. The book states them for integrals: the unnormalized distribution must be integrable for every value of , its gradient must exist for almost every , and a single integrable function must bound the gradient. Most machine learning models satisfy them.

(The conditions above are the ones the book states. The swap from Equation 18.7 to 18.8 is a different case: it moves a gradient through a finite sum, which is always allowed because the gradient of a sum is the sum of the gradients. This point is added here.)

Estimating the negative phase by sampling

Equation 18.13 turns the negative phase into an average. The average is over states drawn from the model, so the negative phase is the expected value of under . Putting it together gives the identity that the book calls the basis for Monte Carlo methods:

The right side is an expectation, which we can estimate by drawing samples. If the samples are fair draws from the model, their average of is an unbiased estimate of the negative phase. That is much cheaper than summing over every state, because each sample costs one evaluation of and its gradient.

The catch is in the word fair. Drawing fair samples from an undirected model is itself hard, and it usually needs Markov chain Monte Carlo methods (chapter 17). The next demo uses samples of a small model, which are easy to draw, to show how the estimate settles as the number of samples grows.

The model has four states, the same as in Section 1, at the fixed parameter . The exact value of is 2.0846, which you can check from the four probabilities. The demo draws 2000 states with a seeded generator, so each sample count always gives the same answer and you can compare runs. In this seeded run the first ten readings are off by as much as 0.4, and after fifty samples the running average stays within about 0.12 of the exact value.

Two points carry over to larger models. The estimate is unbiased, so its average over many runs is the true value. Its typical error shrinks as the number of samples grows, roughly with the square root of the count. Small counts can still be far off, as the first few readings show.

Pushing up on data and down on samples

The two phases have a simple physical reading. The positive phase raises the unnormalized probability at the training examples. The negative phase lowers it at states that the model itself generates. Figure 18.1 of the book shows this with two bumps in one dimension. Here is a rebuild in which you move the model's two bumps.

Many deep learning models define the unnormalized probability through an energy function :

This is equation 16.7 of the book. A low energy means a high unnormalized probability. In that language, the positive phase pushes down the energy of training examples, and the negative phase pushes up the energy of samples drawn from the model.

The book draws the data as green dots. Here the data is a smooth curve of a similar shape: a fixed mixture of a tall bump on the left and a low bump on the right. The model is a mixture of two bumps whose centres and , weight and spread you control. The up arrows sit where the data is, and the positive phase raises the model there. The down arrows sit where the model puts its mass, and the negative phase lowers it there.

When the model overlaps the data, the up arrows and down arrows land in the same places and cancel on average. That is the point where the gradient is zero and training stops. The book calls the negative phase a possible account of dreaming, where the brain lowers the probability of its own fantasies. The book notes that neuroscience experiments have not proven this view, so treat it as an analogy here.

The book calls samples from the model fantasy particles or hallucinations. They are points the model believes in strongly, and the book takes them to be the model's incorrect beliefs about the world. The negative phase lowers their probability. Keep the two arrows in mind when the next chapters approximate the negative phase.

• The log-likelihood gradient splits into a positive phase, the gradient of log p̃ at the data, and a negative phase, the gradient of log Z (Equation 18.4).
• Z is a sum over all states, which is why the negative phase is hard for most undirected models.
• The negative phase equals an expectation under the model (Equation 18.15), so it can be estimated by averaging samples from the model.
• In a sampled estimate, more samples give a better answer, but the error is random and falls only slowly.

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 18.1 (pages 605–607), 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.