Sparse Coding

A linear decoder with a sparse prior

Sparse coding is a linear factor model. It uses a linear decoder plus noise to reconstruct the observation, as in Equation 13.2, and it adds a prior that puts most of its mass near zero. The book is explicit about the noise. Each observation is the decoded code plus Gaussian noise with isotropic precision :

The prior is chosen to have sharp peaks at zero. The common choices are the factorised Laplace, Cauchy and Student-t distributions. The Laplace prior, parametrised by the sparsity weight , is

and the Student-t prior is

The Laplace prior is a double-sided exponential. Its scale is , so a larger gives a sharper peak. The predict step below compares it with a Gaussian of the same variance.

The two peaks are always in the same proportion. The Laplace peak is and the Gaussian peak with the same variance is smaller by a fixed factor. The demo reports that factor, which does not change as moves. The variance of the Laplace prior is

This variance formula is added here for the demo and is not printed in the book.

Inference as a lasso problem

For PCA and factor analysis the encoder is a weight matrix. In sparse coding the encoder is instead an optimisation problem. It asks for the single most probable code:

Combining the prior and the likelihood and dropping terms that do not depend on the code gives the lasso problem, a least squares fit with an L1 penalty:

The L1 norm, the sum of the absolute values of the code, pulls many entries exactly to zero, so the solution is sparse. The book treats as a hyperparameter and sets it to 1 in practice, since its role is shared with . The demo below solves this problem for two-dimensional observations and three dictionary atoms, using a fixed number of proximal gradient steps. Each step moves the code along the gradient of the squared error and then applies a soft threshold, which shrinks every entry towards zero by a fixed amount.

When the penalty is small, several atoms share the reconstruction. As the penalty grows, the code moves to a single atom and the other entries become exactly zero. The inferred code is exactly sparse because the soft threshold in the solver sets small entries to zero.

The book weighs this choice. The optimisation encoder has no generalisation error of its own. For the usual convex inference problems it finds the optimal code for any input, including unusual inputs that a learned encoder might mishandle. The cost is time, because every code needs an iterative algorithm. It is also hard to back-propagate through, which makes it difficult to pretrain with an unsupervised criterion and then fine-tune with a supervised one. The book reports that sparse coding features generalise better than the features of a parametric encoder for object recognition (Coates and Ng, 2011).

Learning the dictionary by alternation

Some approaches learn only the dictionary of features and never build an explicit or . Such a dictionary is learned by the same alternation, which is what this section describes.

Sparse coding is trained by alternating two steps. The encoding step solves Equation 13.18 for every training example, with the dictionary fixed. The decoder step then changes the dictionary to reconstruct the data better, with the codes fixed. The book calls this alternation a principled approximation to maximum likelihood, which section 19.3 develops.

The demo's decoder step is a least squares fit followed by rescaling each atom to unit length. The rescaling is needed. Without it the dictionary can grow while the codes shrink, which lowers the L1 penalty without improving the reconstruction. The demo below starts from a fixed dictionary and runs the alternation on 60 observations drawn near two directions.

The total loss is the sum over observations of the penalised reconstruction cost in Equation 13.18, with the weight fixed at 0.3. Each atom moves towards the direction of the observations it reconstructs. After a few steps the two atoms settle near the two directions in the data, and the loss stops changing.

Sparse codes versus sparse samples

The book shows this with Figure 13.2, which is taken from Goodfellow et al. (2013d). It displays samples from a spike and slab sparse coding model trained on MNIST digits. The samples do not resemble digits, while the learned weight vectors look like pen strokes and sometimes whole digits. The page does not reproduce the figure.

The book notes that sparse coding often produces poor samples, even when the features are useful. Each feature may be learned well, but the factorial prior on the code includes random subsets of features in each sample, so the samples are often poor. The generative model is not especially sparse. Only the feature extractor is. Samples from a Laplace prior are almost surely nonzero, because the probability that an entry is exactly zero is zero.

The contrast is the point. The samples have no exact zeros, as the prior implies. The inferred codes for the same kind of data have many. The encoder is sparse because the optimisation sets small entries to zero, and the generative model is not. The book takes this as motivation for deeper models.

Summary

• Sparse coding is a linear factor model with Gaussian noise, Equation 13.12, and a sharply peaked prior on the code, such as the Laplace or Student-t prior (Equations 13.13 and 13.14).
• Inference is an optimisation problem, the lasso in Equation 13.18. The L1 penalty gives an exactly sparse code.
• Training alternates between encoding the data and fitting the decoder, since maximum likelihood is intractable.
• The non-parametric encoder has no generalisation error in the encoder itself, but it is slower than a feedforward encoder and is hard to back-propagate through, which makes pretraining difficult.
• Samples are often poor, because the factorial prior includes random subsets of features in each sample. The encoder is sparse, but the generative model is not.

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 13.4 (pages 496–499), 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.