Pseudolikelihood

Ratios hide the normalizer

Many models give every state a positive score and leave the probabilities unfinished. In the undirected models of this chapter, the score of a state is written , and the probability is . The number is the partition function, the sum of the scores of every state. It is the expensive part, because it visits every state.

Picture a bakery that scores every loaf for taste. The scores are not probabilities, since they do not add up to one. Turning a score into a share of the total needs the sum of all scores. Comparing two loaves needs no sum at all: divide one score by the other, and the total cancels.

Read the equation from left to right. Each probability is its unnormalized score multiplied by . The two factors sit in the numerator and the denominator of the ratio, so they cancel. What remains is a ratio of unnormalized scores. No sum over states appears, so the ratio can be computed even when cannot.

The demo uses a small model with three binary variables, so there are eight states. Each state is written as three digits, such as 110. The energy of a state is , where is a coupling and is a constant that is added to every energy. Since , the constant multiplies every score by the same factor.

Two things happen as the shift grows. The violet bars shrink, because every score is multiplied by . The teal bars do not move, because the same factor appears in and cancels. The ratio equals whatever the shift, so the ratio is the part of the model that does not depend on the normalizer.

The coupling does change the ratio, because it sets how strongly neighbouring variables prefer to agree.

Conditionals and the cost of marginalizing

A conditional is the distribution of some variables when the others are fixed. Split the variables of a state into three groups: holds the variables we want the distribution of, holds the variables we condition on, and holds the variables that are not in the query. Then

The top line is the joint probability of and . The bottom line is the probability of alone, which sums the joint over every value of and . This sum is called marginalizing out and . Again the cancels, because it appears once above and once below the fraction.

The sum is cheap when is a single variable and is empty. Then the sum has only as many terms as the variable has values. The cost grows when many variables must be summed out, and the log-likelihood of a whole vector needs exactly that. The chain rule of probability splits a vector into one factor per variable:

Each term after the first conditions on all earlier variables, so it sums out a set of up to variables. The book prints the last term without its logarithm. The chain rule needs the logarithm, so it is written here with one.

Computing needs evaluations of , one for each state. The pseudolikelihood of Section 3 needs evaluations. With 30 binary variables the exact count is about a billion, while the other count is 60. The rest of this page is about estimators that trade a little accuracy for this large saving.

The pseudolikelihood objective

The pseudolikelihood (Besag, 1975) replaces the chain rule by a sum of conditionals, one for each variable, each conditioned on all the others. Write for every variable except :

Each term is a conditional probability of one variable, so the ratio trick of Section 1 applies. Only takes its values in the denominator, and every other variable is fixed. The denominator sums over the values of alone. For a vector of variables with values each, the full objective therefore needs evaluations of , as the counting demo showed.

The book notes that this may look like an unprincipled shortcut. It cites Mase (1995) for the result that maximizing the pseudolikelihood gives a consistent estimate, which means the estimate approaches the true parameters as the data grow. The book also warns that with a finite data set the pseudolikelihood may behave differently from maximum likelihood. The next demo shows exactly that.

Over the 200 samples of ten points that we simulated for this page (seeds 0 to 199), 28 (14%, about one in seven) had lowest points more than 0.3 apart. With 1000 points the two lowest points were within 0.04 of each other in each of the 20 samples we checked (seeds 0 to 19), and the typical gap was about 0.01. This simulation is our own check, not a result printed in the book. The book's claim is the large-sample one, and this demo shows why a small sample can mislead.

Generalized pseudolikelihood

The pseudolikelihood conditions on everything except one variable. The generalized pseudolikelihood (Huang and Ogata, 2002) lets the learner choose the size of each conditioning group. Split the variables into sets for . Each set is conditioned on the rest:

The two extremes are the same two objectives as before. If there is one set holding every variable, the sum has one term and it is the exact log-likelihood. If there are sets, each holding one variable, the sum is the pseudolikelihood of Equation 18.20. Every grouping in between is a different approximation, and larger sets cost more to compute.

The book explains where this helps. In natural images, pixels far apart are only weakly correlated. Each set can then be a small window of neighbouring pixels, and the far-away pixels are left out of the conditioning.

With one set the gap is zero, and with six single-variable sets the gap is the pseudolikelihood gap. In between the gap is neither zero nor monotone. At coupling 1.2 the gap is -0.50 with six sets and -0.57 with five sets. Both objectives lie below the exact log-likelihood here, and the six-set objective is closer to it. The gap therefore does not improve steadily as the sets shrink, so the choice of sets is a modelling decision, and the book suggests choosing sets that capture the strongest correlations.

The negative phase hidden in the denominators

Maximum likelihood has an explicit negative phase, a term that pushes down the probability of model states. The pseudolikelihood has no such term, since it never computes . The book observes that it still has something like one: the denominators of each conditional suppress every state that differs from a training example in only one variable.

Here is the reason, written with each state's energy treated as a free number. (This derivation is added here and is not printed in the book.) Let be a training example and let be the state that differs from it in variable alone. The example appears in each of the three conditionals, and each conditional has in its denominator. The gradient of the objective with respect to the energy of a neighbour is

This number is positive. Gradient ascent therefore raises the energy of each neighbour, which lowers its probability. The energy of the training example itself has the opposite gradient, because its own score appears in every conditional.

The push grows with the unnormalized score of the neighbour, so the largest push goes to the most probable neighbour. That neighbour is the state the model is most likely to over-weight, so pushing it down is the useful signal. The training state's own energy moves the other way, so its probability rises.

What pseudolikelihood can and cannot do

The book gives a clear rule for choosing. Pseudolikelihood performs poorly when the task needs a good model of the whole joint distribution, such as density estimation or sampling. It can do better than maximum likelihood when the task needs only the conditionals used in training, such as filling in a few missing values.

Two more limits matter for deep models. First, the method cannot be combined with a variational lower bound on , because sits in a denominator. A lower bound on a denominator gives an upper bound on the whole ratio, and maximizing an upper bound is of no use. Deep Boltzmann machines are hard for this reason, while a single layer model or an approximate inference method that is not a lower bound can still be trained. Second, the cost per gradient step is higher than for stochastic maximum likelihood, since every conditional is computed. The book notes that the generalized form with one randomly chosen conditional per example (Goodfellow et al., 2013b) brings the cost back to that of stochastic maximum likelihood.

The book refers to Marlin and de Freitas (2011) for the theory of its asymptotic efficiency. Sort the four tasks below.

The lesson of the page is in the shape of the approximation. Each estimator removes the sum over states in its own way, and the price is paid in whatever the model can no longer represent well. Ask first which quantity the task needs, then ask which estimator provides it.

• The partition function cancels in every ratio of probabilities (Equation 18.17), so ratios of unnormalized scores need no sum over states.
• A conditional sums out only the variables in one group (Equation 18.18). The pseudolikelihood (Equation 18.20) replaces the chain rule with n single-variable conditionals, costing k × n evaluations instead of kⁿ.
• The generalized pseudolikelihood (Equation 18.21) groups the variables into m sets. One set gives the exact log-likelihood, and n single-variable sets give the pseudolikelihood.
• Each conditional's denominator pushes down the states that differ from a training example in one variable. The pseudolikelihood is consistent, but it is weak for sampling and density estimation, and it cannot use variational lower bounds.

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.3 (pages 615–617), 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.