Sparse Representations

Sparse parameters and sparse representations

Think of a recipe that uses a few spices from a large rack. There are two ways to make a recipe sparse. You can use a short list of ingredients, or you can keep a long list and let most amounts be zero. The book draws the same distinction for linear regression. Weight decay penalizes the parameters directly. A different strategy places a penalty on the activations, so that most units are zero for a given input. That indirectly penalizes the parameters in a complicated way.

The book's first form has a sparse matrix of parameters. Most of its entries are zero, so the model is sparse in its parameters (equation 7.46).

The second form has a dense matrix and a sparse vector that stands for the input . The representation is sparse, while the parameters are not (equation 7.47). The numbers in both equations are the book's own, and the demo below uses the second one.

Predict first. How many ways are there to choose two columns out of six?

The target is built from only two columns of , so most of the columns are not needed. Choose columns, then read how close the best fit comes. The search is small enough to try every pair by hand.

Penalties on the activations

To get a sparse representation, add a penalty on it to the loss. The book writes the regularized loss with a weight that is zero or larger, and a penalty on the representation:

Larger means more regularization. An L1 penalty on the elements of the representation, , induces representational sparsity, in the same way that an L1 penalty on the parameters induces sparse parameters. The book also mentions a penalty from a Student-t prior (Olshausen and Field, 1996; Bergstra, 2011) and KL divergence penalties (Larochelle and Bengio, 2008), which suit representations whose elements lie on the unit interval.

The added derivation below is not printed in the book. For a single unit with unpenalized value , the best activation under an L1 penalty minimizes a one-variable objective:

The minimizer is a soft threshold. It shrinks the value towards zero by and cuts it at zero. Under an L2 penalty, the term times the square of the unit replaces the absolute value. The same steps give a result that is only shrunk and never reaches zero:

Predict first. For a small input, which penalty can set an activation to exactly zero?

Move the penalty up past the size of the input. The L1 activation drops to exactly zero, while the L2 activation only shrinks.

Hard sparsity with OMP-k

Other methods set the sparsity directly, with a hard constraint on the number of nonzero activations. The book's example is orthogonal matching pursuit (Pati et al., 1993). It encodes an input with a representation that solves a constrained problem, where the constraint counts the nonzero entries of :

The book says the problem can be solved efficiently when is orthogonal, and that the method is often called OMP-k, where is the number of nonzero features. It also reports that OMP-1 can be a very effective feature extractor for deep architectures (Coates and Ng, 2011).

The added comparison below is not printed in the book. It sets to 1, 2 or 3 on a small dictionary that is not from the book. The brute-force search tries every set of columns of that size. The greedy steps of OMP add one column at a time, the one that best matches the current residual.

Predict first. As grows from 1 to 3, what happens to the residual of the best brute-force choice?

Average activation and the summary

A gentler route is to control the average activation over the training examples rather than each example. The book notes that some work regularizes the average activation across several examples to be near a target value, such as a vector with 0.01 for each entry (Lee et al., 2008; Goodfellow et al., 2009). With examples, the average of each unit is:

The added demo below uses three hidden units with sigmoid activations, on forty inputs spread evenly between minus one and one. Each unit has a bias that moves its average activation. The penalty is the sum of squared gaps between each average and the target .

Predict first. Starting from a bias of zero, what does a more negative bias do to a unit's average activation?

The sigmoid of a very negative input is close to zero, so a negative bias pulls the average down. The target is a number between zero and one, and the penalty is zero only when every average equals it.

• Sparse parameters and sparse representations are different things, although both are called sparsity.
• An L1 penalty on the activations, added to the loss with a weight, produces exact zeros in the representation.
• OMP-k enforces a hard limit on the number of nonzero features, and a brute-force search shows what the best limited code can do.
• A penalty on the average activation over the examples keeps each unit near a small target, without setting any single example to zero.

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 7.10 (pages 254–256), 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.