Random or Unsupervised Features

Why the features are the costly part

Picture a bakery. The oven takes most of the time. Icing a finished sponge takes a minute. If you want to compare ten icings, you bake the sponge once and reuse it. You do not bake ten sponges from scratch.

The book makes the same point about convolutional networks. Most of the work sits in the layers that compute features, and the output layer is relatively inexpensive, because pooling has already shrunk the number of features that reach it. Each gradient step of supervised training needs a complete forward pass and a complete backward pass through the whole network. The oven runs again on every step.

Two plans follow from that split. The full plan retrains every layer on every step. The frozen plan computes the feature layers once, stores their output, and trains only the classifier layer at the top. The demo counts work in toy units, so that the two plans can be compared. The counts are a model you can check by hand, not a measurement of a real machine.

Count one unit for one layer applied to one example in one direction. With examples in each gradient step, steps and layers, the full plan costs

The frozen plan runs the feature layers forward once over examples, then trains only the classifier with the same number of steps:

The ratio of the two costs is the number to watch:

(These counts are added here and are not printed in the book.) The classifier steps always cost the fraction of the full run, so a deeper network makes the frozen plan relatively cheaper. The feature pass costs the same whatever the number of steps, so its share falls as the steps grow. Predict first, then check your prediction in the demo.

Watch the ratio as you move the two sliders. The layers set the floor, and the steps shrink the rest.

You can also see the trade in the bakery picture. The frozen feature layers cost a single pass over the data, and afterwards many classifiers can be tried at little cost.

The book adds one consequence. Once the features are fixed, extracting them for the whole training set gives a new training set for the top layer alone. If the top layer is logistic regression or an SVM, learning it is then typically a convex problem. A convex problem has one bowl-shaped bottom, so gradient methods cannot get stuck in a worse valley.

Kernels from clustering patches

The book names three ways to get convolution kernels without supervised training:

1. Random. Set every weight of the kernel at random.
2. Hand-designed. Set each kernel to detect edges at a chosen orientation or scale.
3. Learned with an unsupervised criterion. The book’s example is Coates et al. (2011), who apply k-means clustering to small image patches and then use each learned centroid as a convolution kernel.

A patch is a small square of pixels, written . Here a patch has 25 numbers, a 5 by 5 square. A centroid is the average of the patches assigned to it, so it has the same 25 numbers, and it can be drawn as a 5 by 5 kernel. That is why a centroid can serve as a kernel.

K-means works like sorting a box of socks into piles by shade, then labeling each pile with the average shade of its socks. It alternates two moves. The assignment move sends each patch to its nearest centroid. The update move moves each centroid to the mean of the patches sent to it. The quantity it reduces is the mean squared distance , with patches and centroids:

(This objective is added here and is not printed in the book.) Each patch contributes the squared distance to its closest centroid, and is the average over all patches. Each assignment move and each update move can only lower or leave it unchanged.

The patches in the demo are synthetic. Each one is a noisy grating, a stripe pattern at a random angle and phase, drawn with a seeded generator. They stand in for the natural image patches that Coates et al. used. Any kernels you see are a property of this toy data, not a result from the book.

Press One step and watch the kernels. Early steps change a lot, and later steps change less. The chart shows falling with each step. The orange stripes are positive weights and the violet stripes are negative weights, so a kernel made of parallel stripes has a grating-shaped weight pattern.

Random filters and pooling

The book reports that random filters often work surprisingly well in convolutional networks, citing Jarrett et al. (2009), Saxe et al. (2011) and others. Saxe et al. (2011) showed that a layer made of convolution followed by pooling becomes frequency selective and translation invariant even when its weights are random.

Pooling summarizes a window of responses with a single number. Here the number is the largest response in the window, which is max pooling. Translation invariance means that a pattern moved to a new place still produces the same pooled value. The toy below is one-dimensional, a single row of numbers, so that the arithmetic fits on the screen. The same idea holds in two dimensions.

The toy uses a random kernel of five numbers, a bump of three values, a ReLU, and max pooling over windows of four responses. In symbols, the raw response at position is

(This toy is added here and is not printed in the book.) The rectified response is , and the pooled value of window is

Here is the position of the bump. The demo moves it by shifting the input row, so it appears in no equation. The window holds the responses from position to position . Five windows of four cover responses 0 to 19, so the last two of the 22 responses are dropped.

Move the bump one step at a time. The raw response moves with it, one position per step, so the picture changes. The largest pooled value does not change. The bump and the kernel are the same, so the responses are the same numbers shifted along the row, and pooling reports their largest value wherever it sits. The one exception is the right border. When the bump reaches position 20, its peak falls into the two responses that the windows do not cover, and the largest pooled value drops.

The book attributes translation invariance to this kind of layer (Saxe et al., 2011). The toy shows where it comes from: the pooled value keeps the peak and drops its exact place.

Choosing architectures cheaply

The book describes a practical way to choose an architecture. Train only the classifier on top of frozen features for each candidate, compare the candidates, then take the best of them and train the whole architecture with the expensive method. The screening step costs little because it never runs the full backward pass through the feature layers.

Greedy layer-wise pretraining is the intermediate route. Train one layer in isolation, extract its features once, then train the next layer on those features. The book names the convolutional deep belief network of Lee et al. (2009) as a canonical example. It goes one step further by training a model of a small patch, as Coates et al. (2011) do with k-means, and then using that model’s parameters as the kernels of a convolutional layer. The book notes that this makes it possible to train a convolutional network without ever running convolution during training. Very large models can then be trained, and the high computational cost falls only at inference time. It was popular from about 2007 to 2013, when labeled datasets were small and computing power was more limited. Today most convolutional networks are trained purely with supervision.

The book also warns that the benefits are hard to separate. Unsupervised pretraining may regularize the model, or it may allow much larger architectures to be trained, because the learning rule is cheaper.

The demo fixes 6 layers and 10,000 examples, and it uses the same toy units as Section 1. Each candidate gets its own feature pass, because each architecture has different features. The screening plan trains the classifier of every candidate on frozen features, then trains only the best candidate fully. The two plans, in symbols, are:

(These plan costs are added here and are not printed in the book.) The screening plan spends , and the plan that trains every candidate fully spends . Dividing one by the other gives

So more candidates make screening relatively cheaper, and the frozen cost per candidate sets the floor. The readout counts computation only. It does not say that the best candidate after screening is the best after full training, which the book does not promise.

• Supervised training with gradient descent runs the whole network forward and backward on every step. The output layer is cheap because pooling has shrunk its inputs.
• Kernels can come from random weights, from hand design, or from an unsupervised criterion. Coates et al. (2011) cluster patches with k-means and use each centroid as a kernel.
• Convolution followed by pooling can already be translation invariant with random weights, as Saxe et al. (2011) show. Max pooling keeps the largest response in a window and forgets its exact place.
• Classifier-only training on frozen features is a cheap way to compare architectures. Only the best one then needs the full, expensive training.
• The book is careful: it is hard to tell whether unsupervised pretraining helps by regularizing the model or by making large models affordable.

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 9.9 (pages 363–364), 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.