Motivation

A stencil that slides over the input

Think of a stencil, a card with a window cut in it. You lay the card over a row of squares, read the few squares showing through, then slide the card one square along and read again. The card never changes. It is the same card at every position, and it shows only a small part of the row at a time.

Convolution works this way. A small kernel is applied at every position of the input, and each application reads only a few neighboring entries. Section 9.1 defined the operation. This section explains why a neural network would want it. The book names three ideas: sparse interactions, parameter sharing and equivariant representations. Convolution also handles inputs of different sizes.

The demo below uses a three-entry kernel, . Its output compares the center entry with its two neighbors, so it is a second difference. It is zero on a straight line and large where the values bend, such as at a peak. Slide the window and watch which entries it reads.

The output at each window position is one sum over the three entries that the window covers. The same three weights are used at every position. That reuse is the subject of Section 3.

Sparse connections and receptive fields

A traditional layer multiplies the whole input by a full matrix. Every output unit then depends on every input unit. A convolutional layer keeps only a few connections per output. The kernel is smaller than the input, so each output unit depends on a small patch.

Counting the parameters makes the difference concrete. With inputs and outputs, a full matrix needs parameters and takes time proportional to that number per example. If each output keeps only connections, the count drops to . The book notes that can be several orders of magnitude smaller than while the model still performs well.

A unit reached through several layers can still see most of the input. The region of the input that influences one unit is its receptive field. Each extra convolutional layer widens it. The demo stacks valid convolutions of width with layers and lets you click a unit. It rebuilds the ideas of Figures 9.2 to 9.4 in one picture.

Click a unit in the top layer to see its receptive field, or click an input to see the units it influences. Each unit in one layer connects to neighbors below it. Deeper units reach further, and the book notes that pooling and strided convolution make this effect stronger.

Parameter sharing

Parameter sharing means that one parameter is used in more than one place in the model. In a traditional layer each weight is multiplied by one input and then never used again. In a convolutional layer every kernel entry is used at every position of the input, except perhaps some boundary positions, depending on how the edges are handled. The book calls this tied weights: the weight applied to one input is the same weight applied elsewhere.

Figure 9.5 of the book shows this. The top diagram uses the central entry of a three-entry kernel at every input location, so one parameter serves all of them. The bottom diagram is a fully connected layer, where the central weight is used once. Sharing leaves the runtime of forward propagation at , but the storage falls to parameters. The book calls convolution dramatically more efficient in memory and in statistical efficiency for this reason.

Because the same kernel is applied everywhere, the same layer works on inputs of any length. The output gets longer or shorter. Each shared kernel entry is used once per output position, so the number of uses grows with the input.

The bars use a logarithmic scale, so the gaps between them are factors. Set the input length to a few hundred and watch the fully connected count grow with the square. The shared count depends only on the kernel width. The third slider changes the input length for the shared layer alone and shows how many output values it produces.

Edge detection and the cost of convolution

Figure 9.6 of the book is an example with a real photograph. Each pixel is replaced by its value minus the value of its left neighbor. Where the brightness changes from left to right, the result is large, so this kernel marks vertical edges. The book uses this example to show what a two-entry kernel can detect.

This formula is added here and is not printed in the book. It is the same kernel of width two, written as a difference. The demo below uses a generated picture of rectangles, because the book's photograph is not reproduced here.

The output loses one column, because the first column has no left neighbor. The book makes the same point about its 320-pixel photograph: the output is 319 pixels wide. Flat regions come out near zero, and only the boundaries of the shapes survive.

Counting the work

The book gives the cost of this operation on a 320 by 280 image, once as a convolution and once as a full matrix product. The kernel has two entries, so each output pixel needs two multiplications and one addition, three operations in all. The equivalent full matrix has about eight billion entries. The demo below computes the same figures for any image size. Set the sliders to the book's size to match its numbers.

The convolution uses operations. A full matrix with one row per output pixel and one column per input pixel has entries, and the book's straightforward matrix multiplication does about twice that many floating point operations. Only of the entries are non-zero. The book also notes that most entries are zero. If only the non-zero entries are stored, matrix multiplication needs the same number of operations as convolution, but the matrix still holds entries, which is 178,640 for the book's image. The ratio in the readout is computed from the operation counts.

Equivariance to translation

A function is equivariant to a transformation when transforming the input and then applying the function gives the same result as applying the function and then transforming the output. Here is a transformation, such as a shift, and is the layer:

Convolution is equivariant to translation. If shifts every pixel one place to the right, applying the shift and then the convolution gives the same answer as convolving and then shifting the output. If an event moves later in a time series, its representation in the output moves later by the same amount. If an object moves in an image, its map of features moves the same distance.

The book gives a reason to share parameters. A feature such as an edge appears at many places, so one detector is useful everywhere. The book also gives the opposite case. For images cropped to a face, the top of the face and the bottom of the face need different detectors, so one set of shared detectors across the whole image would not suit them.

The readout compares two routes: convolve and then shift, or shift and then convolve. They agree, because a circular input has no edge where the shift could leave a gap. The book states that convolution is not naturally equivariant to other changes, such as scaling or rotation of an image, so other mechanisms are needed for those. It also notes that some data types cannot be fed to a fixed-shape matrix at all, and convolution handles some of them; Section 9.7 covers these.

• Convolution connects each output to a small patch of the input, so the number of connections, and the parameters of the local layer, is instead of .
• The same kernel is reused at every position, so the storage falls to parameters and the same layer handles inputs of any length.
• Shifting the input shifts the output by the same amount. Convolution is equivariant to translation, but not naturally to scaling or rotation.

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.2 (pages 335–338), 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.