MAP Inference and Sparse Coding

The most likely hidden value

Chapter 19 mostly asks for the whole posterior . Sometimes you only need one answer: the single most likely value of the hidden variables. Call it . The book calls this maximum a posteriori inference, or MAP inference:

Think of a hiker lost in fog on a hill with two peaks. A MAP answer names the top of the higher peak. The posterior mean would instead average the two peaks, and might land in the valley between them. The demo below builds such a bimodal posterior from two bumps. Drag the sliders and watch where the top and the average move apart.

MAP inference computes the most likely exactly, but it returns only that one value. The posterior mean and the MAP value answer different questions. For one symmetric peak, such as a Gaussian, they coincide. For two peaks, they can lie far apart.

Point guesses and a loose bound

Section 19.1 showed that the bound is maximized over with the exact choice. A learning procedure based on maximizing the bound can instead use MAP inference to choose . The book restricts to a Dirac distribution, a spike of zero width at a single point :

A Dirac distribution is written with the Dirac delta function , as in equation 19.11. Because it has only one free value, , the bound reduces to maximizing the log probability with set to :

This is the same problem as MAP inference, equation 19.13 with the same answer:

The book describes the result as a procedure similar to EM. Infer by MAP inference, then update to increase (, ). MAP inference is usually not called approximate, because it computes the exact most likely value. It counts as approximate here because it does not give the optimal . The procedure is still coordinate ascent on the bound, as EM is.

The bound is then infinitely loose. The entropy of a Dirac distribution is minus infinity, so the bound sits far below of the data. A guess with some spread instead gives a finite entropy and a meaningful bound. The demo below measures the gap for a Gaussian guess centred on the MAP value, and shrinks its spread towards a point.

The gap is the KL divergence from the guess to the posterior, so a narrow guess has a large gap and a moderate spread gives the smallest gap. A guess that sits exactly on a peak still misses the other peak, which is why a single point cannot be a good approximation to a two-peaked posterior.

Sparse coding and its prior

MAP inference matters most in sparse coding, a linear factor model whose hidden units are encouraged to be zero. Each hidden unit has a Laplace prior with rate . The prior is sharply peaked at zero, so most units sit near zero for a typical input.

The visible vector is then a linear combination of the hidden units plus Gaussian noise. The book writes x on the left of equation 19.15 and v inside the Gaussian on the right. This page writes on both sides, the same visible vector used throughout the chapter:

Each column of is an atom, a direction in data space, and says how much of that atom is used. The prior pushes most hidden units towards zero, and sets the noise.

The posterior is hard to compute. Every two hidden units are co-parents of every visible unit, so observing connects every pair of hidden units, and all of them form one massive clique. If the model were Gaussian, these interactions could be handled through a covariance matrix. The sparse prior makes them non-Gaussian, so no such shortcut exists. Figure 19.2 of the book shows this for a binary sparse coding model with four hidden units. The book places it in its section on variational learning, where it explains why variable elimination does not help. The demo draws the same two graphs.

The joint graph on the left has no links between hidden units. The posterior graph on the right does, because observing creates a clique among the hidden units. This coupling is why computing the posterior exactly is hard.

The sparse coding objective

Exact maximum likelihood is out, because the log-likelihood and its gradient need . The book therefore learns with MAP inference, maximizing the bound defined by a Dirac distribution around the MAP estimate of . For sparse coding this becomes one objective over the codes and the dictionary . The first term rewards codes with small entries, which is the Laplace prior in disguise. The second term measures how badly the code reconstructs the data:

Read the two sums in turn. The first is the total size of all code entries. The second is the squared error of the reconstruction , summed over all data. Most applications also add weight decay or a constraint on the norms of the columns of . Without one, a tiny code paired with a huge dictionary lowers the first term, which the book calls the pathological solution.

The two sets of variables can be optimized in turn, and the book says both sub-problems are convex. For a fixed code, the dictionary problem is an ordinary linear regression. Minimizing over the codes needs specialized algorithms, such as feature-sign search. Jointly, the problem is usually not convex.

The demo below uses a single data point and two atoms, with the dictionary fixed. It minimizes the same objective over a two-unit code. Drag the data point and watch the code. Each unit is either used or pulled to exactly zero.

The code units are pulled towards zero by the first term, and the penalty is exactly what shrinks a code below the value that would reconstruct the data perfectly. This shrinkage is the price of sparsity. It also explains the answer above: one unit is used, but its weight is less than 1.

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 19.3 (pages 635–637), 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.