Inference and Approximate Inference

What inference asks

A probabilistic model is useful because it can answer questions. Given a set of medical tests, we can ask what disease a patient might have. The book calls these questions inference: predicting some variables from others, or giving a distribution over some variables once the values of others are known. In a latent variable model, one such question asks for the features that describe the observed variables.

The distribution over the hidden variables once the visible ones are known is the posterior, . The medical case has the same structure. Let the hidden bit be 1 when a patient is ill, and let the visible bit be 1 when the test is positive. Three numbers describe the test. The chance of illness is . The sensitivity is the chance of a positive test when a patient is ill. The specificity is the chance of a negative test when a patient is healthy.

The readout is Bayes rule, the rule that turns a prior into a posterior. Bayes rule with the three numbers gives the formula below. This form is derived for this page from the definition of a conditional probability, and is not printed in the book.

The denominator is the chance of a positive test at all. It adds the true positives to the false positives, and the false positives come mostly from the large healthy group. That is why an accurate test can still give a posterior near 8% when the illness is rare.

The identity behind maximum likelihood

We often train a model with maximum likelihood, which pushes up , the log of the probability of the training data. The book states the identity that links this quantity to the posterior as (16.9):

The book says that we often want in order to implement a learning rule. The right side of the identity is an expectation under that posterior. An expectation is a weighted average, where each value counts in proportion to its probability. The identity is easier to trust once you see why each term works. For any value of the hidden variables, the posterior is the joint divided by the probability of the visible data. The logarithm turns that into a short derivation, which the book does not print:

Every term inside the expectation therefore equals . The average of a constant is that constant under any distribution, so the identity holds for the posterior and for any other distribution over the hidden variables. The log here is the natural logarithm, so the unit is the nat, and one nat is about 1.44 bits.

The demo shows the same number three ways. Each term has the value of , and the posterior-weighted average of the two terms is that value too. Because the identity holds for every setting, maximum likelihood can be written as a sum over the posterior, and computing the posterior is the difficult step.

Why exact inference is hard

Inference is hard for most interesting deep models, even when a graph keeps the number of parameters small. The book says that computing the marginal probability of a general graphical model is #P-hard. The marginal probability of a variable is its chance after the other variables are summed out. The class #P is a relative of NP. An NP problem asks whether a solution exists, and finds one if it does. A #P problem asks how many solutions there are. The book adds that the graphs used in deep learning are usually not restrictive enough for efficient inference, and that NP-hard graphs commonly arise in real-world scenarios.

The book builds a worst-case example from 3-SAT, a satisfiability problem in which each clause is an OR of three literals and every clause must be true. Put a uniform distribution over the Boolean variables. Add one binary latent variable per clause that reports whether that clause is satisfied, and a reduction tree of latent variables whose root reports whether all clauses are satisfied. The marginal probability at the root is then the fraction of assignments that satisfy the formula, so computing it exactly means counting solutions.

The demo uses three variables, so the 8 assignments can be checked one by one. Each clause below is false on exactly one of the 8 assignments. Tick clauses and count the assignments that satisfy all of the ticked ones.

The count is exact here because the table has only 8 rows. A formula over 100 binary variables has rows, which is far beyond any direct count. This is why the book turns to approximate inference, which trades exactness for a tractable computation.

Guessing the posterior

The book’s answer to hard inference is approximate inference. In deep learning this usually means variational inference: approximate the true posterior with a distribution that is as close to it as possible. For one hidden bit, the guess is the single number , the chance that = 1 under the guess. Chapter 19 of the book covers these techniques in depth.

The expectation in (16.9), taken under the guess, gives a lower bound on . The book does not print the exact identity, so here is the derivation for this page. The difference between the true value and the bound equals the KL divergence from the guess to the posterior:

The difference is the gap. A KL divergence measures how far one distribution is from another, and it is never negative, so the bound never exceeds , and the gap is zero only when the guess equals the posterior. The demo fixes the model: the hidden bit is 1 with chance 0.3, and the visible bit is 1 with chance 0.2 when the hidden bit is 0 and 0.9 when it is 1. The exact posterior is then 0.66.

• Inference asks for the posterior , or for features such as . Exact answers are hard for most deep models.
• The identity (16.9) holds because each term inside the expectation equals , which is measured in nats.
• The count of satisfying assignments of a 3-SAT formula is #P-hard in general. Exact counting for 8 assignments is trivial, and the cost doubles with every extra variable.
• A variational guess gives a lower bound. The gap below is a KL divergence, so it is zero only when the guess is the posterior.

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 16.6 (pages 584–585), 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.