The Convolution Operation

A smoothing filter for a noisy sensor

Picture a laser sensor that tracks a spaceship. It reports the position at every instant, but every reading carries some noise. The fix is to average several readings, giving recent readings more weight than old ones. Applying that weighted average at every moment gives a smooth estimate of the position:

Read the equation as a recipe. For each moment , take every past reading , multiply it by a weight that depends only on how old that reading is, and add up the results. The integral sign means the sum runs over all ages .

• Convolution is the name of this operation. Equation 9.2 writes it with an asterisk.
• Input: the signal , here the sensor readings.
• Kernel: the weighting function . Its argument is the age, .
• Feature map: the output , a smoothed version of the input.

A running class grade works the same way. If the last test counts double, the grade is a weighted average in which recent scores carry more weight. The laser estimate applies the same rule to a physical signal, at every moment.

The book sets two conditions for this example. The weights must form a probability density, so they add up to 1, or the output is not a weighted average. The weights must also be zero for negative ages, or the estimate would use readings from the future. Convolution itself is defined for any pair of functions for which the integral exists, and it is used for many purposes besides averaging.

The estimate trails the true track. A reading that is seconds old counts with weight that falls like . Its average age is seconds, and a track moving at speed is therefore estimated units behind. This derivation is added here and is not printed in the book. The exponential shape of the weights is a choice made for this demo.

A larger gives a shorter memory. The estimate reacts faster, but it averages fewer readings, so more noise gets through. Try the decay rate at 0.2 and at 4 and compare the two estimates by eye.

Discrete convolution as a sum

A sensor that reports once per second has whole-number times, so and take integer values. The integral of equation 9.1 becomes the sum of equation 9.3. This is the form that a computer uses.

In a computer the arrays are finite, so the sum has finitely many non-zero terms. The kernel is zero outside its stored entries. Each output value is one sum of products, and each product is a reading times a kernel entry. The kernel index runs backwards as the reading index runs forwards.

With the default numbers, the output at adds two products. Move to 3 to see three products add up. The kernel length sets how many products can appear in one sum: at most three here. Guess the output at a time you choose, press the check button, and compare with the readout. The full output has 8 values, which is 6 plus 3 minus 1.

Two dimensions and the kernel flip

An image is a grid, so the input becomes a two-dimensional array and the kernel becomes a small grid . The book calls arrays of this kind tensors. The two-dimensional sum is equation 9.4. Its output is the feature map at row and column .

Look at the kernel index . As the input row grows, the kernel row shrinks. The kernel is read backwards. This reversal is the flip, and it is what makes the operation commutative: equation 9.5 gives the same result with the roles of input and kernel exchanged.

The book notes that equation 9.5 is the easier form to implement, because the range of valid index values varies less. The commutative property is useful in proofs. In a neural network implementation it is rarely important, and convolution is usually combined with other functions that do not commute with it. The book states that the only reason to flip the kernel is to obtain this commutative property.

Most machine learning libraries skip the flip and compute equation 9.6, called cross-correlation. This text calls both operations convolution, and states which one it means when the flip matters. A learning algorithm finds the right kernel values in any case, so a kernel learned with the flip is stored upside down relative to one learned without it.

Figure 9.1 shows the operation without the flip. The input is a 3 by 4 grid with letters a to l, row by row. The kernel is 2 by 2, with the entries , , and . The figure keeps only the positions where the kernel lies entirely inside the input, the valid positions, so the output is 2 by 3. The figure reuses the letters , , and for kernel entries, so here x means a kernel entry and not the signal of Section 1.

Choose an output value to see its sum. With the flip off, the upper-left output is , the first formula of Figure 9.1. With the flip on, each input letter meets the kernel entry in the opposite corner, so the same letters appear in a different pairing.

Convolution as a sparse matrix

Discrete convolution can also be written as a matrix product. Stack the input as a column , and place the kernel in each row of a matrix at a different offset. The output column is then . The example below uses three kernel entries and six inputs, with the kernel in the order written. In that order the product is the cross-correlation of equation 9.6. Reversing the kernel gives the convolution of equation 9.4, which the demo further down can switch on. The example and this remark are added here and are not printed in the book.

The matrix has a regular pattern. Each row is the row above shifted one place to the right, so every diagonal holds one repeated value. A matrix with this property is called a Toeplitz matrix. The book states this for univariate convolution.

In two dimensions the book describes a doubly block circulant matrix. A circulant matrix wraps around at its edges, so that description fits convolution of a wrapped input. The valid convolution of Figure 9.1 does not wrap, so its matrix is only block Toeplitz. This remark is added here and is not printed in the book.

Most entries of the matrix are zero, because the kernel is much smaller than the input. Each row has non-zero entries, and there are rows. So the fraction of zeros is . This count is added here and is not printed in the book.

Any algorithm that works with matrix multiplication and does not depend on special matrix structure also works with convolution, without change. Practical convolutional networks use faster methods, but these are not required in theory.

Change the input length and the kernel length. The kernel cannot be longer than the input, so its slider stops at the input length. Each row has the same number of non-zero entries, and those entries sit on a diagonal band. Turn the flip on and check that the matrix still reproduces the sliding sum.

• Convolution slides a kernel along an input and adds the products. In one dimension this is equation 9.3, and in two dimensions it is equation 9.4.
• The flip reverses the kernel. Most libraries drop it and call the result convolution (eq. 9.6), and the learned kernel adapts either way.
• Convolution is a matrix product with a Toeplitz structure. For valid convolution the fraction of zero entries is 1 minus k over N, so the matrix is sparse when the kernel is small.

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.1 (pages 331–334), 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.