Efficient Convolution Algorithms

The big picture

Convolution can be cheap or expensive, and the cost depends on the route that the computer takes, not only on the answer. Think of two routes to the same station. One is a long walk through every street, and the other is a short route through a transfer. Both arrive at the same place, but one takes far fewer steps.

Modern convolutional networks often contain more than one million units, so powerful parallel implementations are essential. The book adds that, in many cases, speed also comes from choosing a suitable convolution algorithm.

The book describes two routes of this kind. The first applies to separable kernels, which can be replaced by a sequence of one-dimensional convolutions. The second is the Fourier route, which turns the convolution into a pointwise product. The book says that the Fourier route can be faster for some problem sizes, and that not every convolution can be written as a separable one.

The cost of a naive -dimensional kernel with width is written in the book as for runtime and for the storage of the parameters. The demo below counts the entries directly. Before you move a slider, make a guess.

The naive kernel stores entries. A separable kernel stores numbers. The ratio grows quickly with the number of axes, because the naive count multiplies by at every new axis, while the separable count only adds at each axis.

Separable kernels

A kernel is separable when it is the outer product of one vector per axis. The book states that a separable convolution can be computed as a composition of one-dimensional convolutions with each of these vectors. The result is the same as one convolution with the full kernel, and it is significantly faster. The kernel also takes fewer parameters to store.

For a two-dimensional kernel the rule is simple to write down. The entry at row and column is the product of the -th entry of and the -th entry of . This derivation is added here and is not printed in the book:

The kernel in the demo has nine entries, but it is fully determined by six numbers. The naive method uses nine stored values, and the separable method stores six. Not every convolution can be written this way, and a kernel that is not separable has no such pair of vectors.

The Fourier route

The book states that convolution is equivalent to converting the input and the kernel to the frequency domain with a Fourier transform, multiplying the two signals point by point, and converting back with an inverse Fourier transform. For some problem sizes this route is faster than the naive sum. The book does not give the operation counts for this route in this section.

In symbols, the route reads as below. This derivation is added here and is not printed in the book. It writes the book's description with the transform , where the product is taken point by point.

This caveat is added here and is not printed in the book. When no padding is used, the Fourier route computes a circular convolution, in which the kernel wraps around the end of the signal. The wrapped values can change the first places of the output. In the demo only place 1 changes. Zero padding of both signals to the full output length removes the wrap, and the two routes agree.

Choosing the cheapest method

The ratio of the naive cost to the separable cost is divided by . This derivation is added here and is not printed in the book. Because the saving grows with the width, the separable method is most useful for wide kernels with several axes, as long as the kernel is in fact separable.

The demo below lets you compare the two costs for any width and number of axes. The challenge asks for the smallest width at which the saving is at least tenfold for three axes.

The book says that not every convolution can be separated, and that devising faster or approximate methods is an active area of research. The methods in this section are exact, but the research direction also includes approximate ones. The book adds that techniques which improve the efficiency of only forward propagation are useful, because in the commercial setting it is typical to devote more resources to deployment than to training.

What to take away

• A naive -dimensional kernel of width needs entries, and a separable one needs numbers.
• A separable kernel is the outer product of one vector per axis, and it is applied as a sequence of one-dimensional convolutions.
• The Fourier route turns the convolution into a point-by-point product. The zero padding that avoids wrap-around is added here and is not printed in the book.
• The methods are exact, but they pay off only for some kernel shapes and problem sizes, so the choice of method depends on the problem.

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.8 (pages 362), 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.