Convolution

Theory

A fully connected layer on a 100 by 100 colour image has 30000 inputs. With 100 hidden neurons that is three million parameters in the first layer alone, and none of them know that pixel \((3, 4)\) is next to pixel \((3, 5)\).

A convolutional layer fixes both problems at once: each output combines only neighbouring pixels, and the same few weights are used everywhere.

The idea

We take a small filter, for example 3 by 3, and slide it over the image. At each position we compute a weighted sum of the pixels under the filter, add a bias, and apply an activation function.

Move the output pixel slider. The window slides over the input, and each output pixel is the weighted sum of the nine pixels under it (the bias is 0), followed by a relu. Padding adds a border of zeros, stride 2 makes the window jump two pixels. The output width is the number of places the window fits.

The same filter is used at every position. This is where the saving comes from. A 3 by 3 filter has 9 weights and 1 bias, no matter how large the image is.

It also builds in an assumption. A feature that is useful in the top left corner is useful in the bottom right corner too. For images this is usually right. A shifted image gives the same feature map, shifted by the same amount: the layer is equivariant to translations.

One filter on an MNIST digit, followed by a relu. The output is large where the image looks like the filter (dark: a positive weight, light: a negative one); the box marks the largest value. “A piece of the digit” is a 5 by 5 patch cut from the digit itself. Shift the digit: the feature map moves with it and its largest value stays the same, while a dense neuron with one weight per pixel responds less and less.

Volumes

An image has three channels, red, green and blue. So the input is a volume of width, height and depth 3. Any input with several features at every position is a volume in the same way: a microscopy image with one channel per fluorescent marker, or the output of a convolutional layer, which has one channel per filter.

A filter has the same depth as its input: one 3 by 3 slice per channel. At each position every slice computes a weighted sum of its own channel, and the output pixel is the sum of these, plus a bias. A 3 by 3 filter on a 3 channel input has \(3 \times 3 \times 3 = 27\) weights and 1 bias.

One filter on an input with one, two or three channels. The channels are stacked into a volume, and so are the slices of the filter, into a 3 by 3 by \(c\) box. The window covers the same place in every channel, each slice weights its own channel, and the sums are added into one output pixel.

A layer has several filters. Each filter produces one output channel, so a layer with \(k\) filters produces an output volume of depth \(k\). The next layer reads these \(k\) channels as the first one reads red, green and blue.

Size arithmetic

Given an input of width \(n\), a filter of size \(f\), stride \(s\) and padding \(p\), the output width is

\[ \left\lfloor \frac{n + 2p - f}{s} \right\rfloor + 1 . \]

Stride is how far the filter moves between positions. Stride 1 moves one pixel, stride 2 moves two and halves the output size.

Padding adds a border of zeros around the input, so that the filter can also be centred on the edge pixels. With \(p = (f-1)/2\) and stride 1 the output has the same size as the input.

Parameter count

A layer with \(k\) filters of size \(f \times f\) on an input of depth \(c\) has

\[ k \left( f^2 c + 1 \right) \]

parameters. Note that this does not depend on the width or the height of the image. This is why convolutional networks can handle large images.

Pooling

A pooling layer reduces the width and the height. Max pooling with a 2 by 2 window takes the largest of every four values, which halves both dimensions.

It has no parameters. It makes the representation smaller and slightly invariant to small shifts: the output stays the same instead of moving.

A typical architecture

A convolutional network alternates convolution and pooling, so that the volume gets thinner and deeper as we go. At the end the volume is flattened and passed to one or two fully connected layers, and then to the output layer.

The early layers learn edges and simple textures. The later layers learn parts and objects. This is not something we programmed. It comes out of the training.