Predictive Sparse Decomposition

Two ways to get a code

A sparse code is a code in which most entries are exactly zero. Section 13.4 of the book describes sparse coding, where the code for an input is not produced by a formula. It is the answer to a search problem: find the code that best explains the input while keeping most entries at zero. The search is written as Equation 13.18. The book calls the decoder matrix there, and this page calls it . The precision weight is set to 1, as the book typically does:

Every input needs its own search, so the encoder is slow. The alternative is a parametric encoder , a formula with a few weights that gives a code in one pass. It is fast, but it is only a guess. Predictive sparse decomposition (PSD) combines the two. It trains a fast encoder to predict the codes that the slow search would find, and it keeps the search during training.

Think of a tutor and a student. The tutor works each problem out slowly, step by step. The student learns from those worked answers until the student can guess the answer at once. In PSD the search is the tutor and is the student.

The demos use one input number and a two-number code, so the search can be seen on a screen. The decoder is () = + 0.6 , a row = (1, 0.6). The encoder guess is = (0.7 , 0.2 ), with the weights = (0.7, 0.2). Those numbers are chosen by hand for the toy and are not trained, except in Section 3, where the demo trains its own.

The search from the guess starts close to the answer, so it needs few steps. The search from zero starts far away and needs many. The step count is the cost of the search, and the guess is what makes the search cheap. This is the reason for PSD: the encoder is trained so that its guess is good enough to start the search near the answer.

The cost in Equation 14.19

PSD judges a code for one input with the cost below. The book writes it with the decoder , the encoder , and two strengths and that the user chooses. This page calls the sum :

The cost has three terms, and each one has a job.

• The reconstruction term asks the decoder to rebuild the input from the code.
• The sparsity term asks the code to have few nonzero entries. The book writes the same penalty as . Both mean the sum of the absolute values of the entries. Its size is set by .
• The agreement term keeps the code close to the encoder guess. Its strength is , and setting to zero removes the encoder from the search.

Two extremes make the roles clear. With and both zero, only the reconstruction term remains, and many codes rebuild the input equally well. The readout says so. With large, the best code moves toward the guess, and only the reconstruction term pulls it away.

The search for minimizes . The book only says that simple gradient descent can obtain reasonable codes in as few as ten steps. The sparsity term is harder for plain gradient descent, because the absolute value has a kink at zero. This demo uses a standard variant called a proximal gradient step. The kink remark and the step below are added here, not printed in the book. Each step moves along the negative gradient of the smooth part , the first and third terms together, and then pulls every entry toward zero by . The step is:

Here moves a number toward zero by the amount in the second slot and stops at zero. The step size is one over a bound on the curvature. The pull toward zero is what puts entries exactly at zero. Plain gradient descent on the same cost only gets close to zero and does not land on it.

The heat map is the cost for each pair of code entries, with the input fixed. Darker means lower cost. The sparsity penalty puts creases along the two axes, so the lowest point often sits exactly on an axis, where one entry is zero. Find the strength at which that first happens, then the strength at which the code is zero in every entry.

For the default input, the code is zero when reaches the value in this inequality. The inequality is added here from the optimality condition of the cost, and it is not printed in the book. The readout names the entries that are exactly zero, so you can check the threshold by hand.

Training by taking turns

Training minimizes the cost over the code and over the parameters, and the two minimizations alternate. The book states this as the training rule for sparse coding, and PSD follows the same pattern. Each round has two moves. First, the search finds the code for every training input, starting from the encoder guess. Second, the parameters move one step with the codes held fixed.

The search is cheap in this setting, because the guess already lies near the answer and the cost keeps the code near the guess. The book notes that simple gradient descent can reach reasonable codes in as few as ten steps. The demo uses ten steps per input.

The decoder needs one safeguard. Without a constraint, the decoder atoms can grow while the code shrinks. The reconstruction stays the same and the sparsity penalty falls, so the cost is lowered by a trick rather than by learning. The book makes this point for sparse coding in Chapter 8 (page 321, around Equation 8.38): most applications constrain the norms of the columns, to prevent the pathological solution with small codes and large weights. The columns of the decoder are called atoms. This demo builds the constraint in, by setting each atom with an angle . Each atom then has length one.

For the encoder weights, the gradient with the codes held fixed is:

PSD does not train a sparse coding model first and then fit the encoder to its codes. The book states that PSD regularizes the decoder so that the encoder can infer good code values. The two steps are linked, and the demo shows that link.

Each press first finds the codes with the current parameters, then takes one step on the parameters. The gap is the average squared distance between the encoder guess and the code the search found. Training works to shrink it, so the encoder predicts the search better over time. With at zero the encoder gets no signal from the agreement term, so the gap shrinks only a little, and only because the decoder moves.

Deployment, learned inference and stacking

The search is a training device. The book says that in practical PSD applications the iterative optimization is only used during training, and the parametric encoder computes the features when the model is deployed. Evaluating costs one pass, while the search needs many gradient steps per input.

The book calls this learned approximate inference. The encoder learns to approximate the result of the search. Section 19.5 develops the idea further. Chapter 19 gives a view in which PSD trains a directed sparse coding model by maximizing a lower bound on the log-likelihood. This page does not prove that result.

Because is a differentiable parametric function, PSD models can be stacked. The features of one layer become the input of the next, and the stack can initialize a deep network that is then trained with another criterion. The book reports that PSD has been used for object recognition in images and video and for audio.

The violet curve is what a deployed PSD model computes, in one pass. The teal curve is the refined code that training uses. The gap between the violet curve and the teal curve is what training shrinks, and the refinement steps show how far a few steps of search can carry the guess.

• Predictive sparse decomposition trains a fast parametric encoder to predict the codes that an iterative sparse search would find.
• Equation 14.19 has three terms: reconstruction, sparsity with strength , and agreement with the encoder with strength .
• Training alternates between the search for the codes and a step on the parameters, and the decoder needs a norm constraint so that the sparsity penalty cannot be dodged.
• At deployment only the encoder runs, so the model is cheap. PSD models can be stacked to initialize a deep network.

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 14.8 (pages 523–524), 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.