21 Convolutional Neural Networks

So far, we’ve considered feed-forward fully connected neural networks. But a great advantage of neural networks is that we can customize their design: layers can be chosen based on our knowledge of the data and its structure. While feed-forward networks have universality properties and in principle could fit anything if we try hard enough, encoding structure into the network can help achieve better performance more quickly, with more reasonable amounts of data.

Some data is naturally structured as a grid. The grid may be one-dimensional, such as a time series or discretized function; two-dimensional, such as an image; or three-dimensional, like a video. Instead of a fully connected layer that takes every pixel in the image or video as an input to every node, we might want to impose local structure: first we find features in small regions of pixels, then determine how those features combine to produce our output.

We do this with an operation called convolution.

21.1 Convolutions

Let $x(t)$ be a signal measured at discrete points $t \in \mathbb{Z}$. Let $w(a)$ be a function with values at discrete integers $a \in \mathbb{Z}$. We can define the convolution of these functions.

Definition 21.1 (Discrete convolution) The convolution of two discrete functions $x(t)$ and $w(a)$, written $x * w$, is \[ (x*w)(t) = \sum_{a = -\infty}^\infty x(a) w(t - a). \]

We can think of $w(a)$ as a weighting function that determines how to combine entries of $x(t)$ to produce a new signal. Here’s a simple example.

Example 21.1 (Local average) Let \[ w(a) = \begin{cases} \frac{1}{3} & \text{if $0 \leq a < 3$}\\ 0 & \text{otherwise}. \end{cases} \] Then \[\begin{align*} (x*w)(2) &= \sum_{a = -\infty}^\infty x(a) w(t - a)\\ &= x(-\infty) 0 + \dots + x(0) w(2) + x(1) w(1) + x(2) w(0) + x(3) 0 + \dots\\ &= \frac{x(0) + x(1) + x(2)}{3}. \end{align*}\] Hence convolution with this $w(a)$ produces a new signal $(x*w)(t)$, where every entry is the average of the three most recent entries of $x(t)$.

Convolutions appear in many places in mathematics and statistics. They can also be defined for continuous functions: if $x(t)$ and $w(a)$ are continuous functions, their convolution is \[ (x*w)(t) = \int_{-\infty}^\infty x(a) w(t - a) \, da. \] This also has a local average interpretation, depending on $w(a)$. In fact, kernel smoothing can be seen as convolving the data ($x(t)$) with the chosen kernel function ($w(a)$), producing new data where each point is a weighted average of points in the original data.

We’ll be focusing on the discrete case because we intend to apply convolution to gridded data: time series, images, videos, and so on. In these, we have discrete indices for time points or pixels. Our data also usually has finite extent: we observe $x(t)$ from $t = a$ to $t = b$, not over an infinite range. As a shortcut to avoid tracking sizes everywhere, we can instead just define that $x(t) = 0$ for $t < a$ or $t > b$.

We can further extend convolution to multiple dimensions.

Definition 21.2 (Discrete convolution in 2D) Suppose $x(i, j)$ is a grid of values and $w(m, n)$ is a weighting function. The convolution $x * w$ is \[\begin{align*} (x*w)(i, j) &= \sum_{m = -\infty}^\infty \sum_{n = -\infty}^\infty x(m, n) w(i - m, j - n)\\ &= \sum_{m = -\infty}^\infty \sum_{n = -\infty}^\infty x(i - m, j - n) w(m, n). \end{align*}\]

21.2 Convolution layers

We’ll be using convolutions in a very specific context: convolutional layers of neural networks.

Consider a two-dimensional image that is $W$ pixels wide and $H$ pixels tall. Each pixel has a value $x(i, j)$ for $i = 1, \dots, H$ and $j = 1, \dots, W$. Since convolution is theoretically for infinite grids, we can let $x(i, j) = 0$ for indices outside the image.

Consider defining $w(m, n)$ to similarly be a grid $N$ pixels wide and $M$ pixels tall, where $N \leq W$ and $M \leq H$. By “a grid” I mean it has nonzero values for $m, n$ in that range, and its value is 0 outside that range.

What does the convolution of $x$ and $w$ look like?

TODO draw a diagram showing striding across the image

We could hence define a network layer that uses a convolution of the previous layer, rather than being fully connected. Such a layer would have one or more functions $w$, called the kernels or filters. Each kernel would be convolved with the previous layer. Call the output of the previous layer $x(i, j)$; then the convolution $x * w$ produces a new grid of values. The new values become the output of our convolution layer, typically after we run them all through an activation function..

21.2.1 Setting up the layer

To define a convolution layer, then, we must choose the following:

The number of convolutions, i.e. the number of distinct kernels or filters.
The size of those convolutions, i.e. $M$ and $N$.
What to do at the boundaries of the previous layer. The output $(x * w)(1, 1)$ may depend on the value of $x(-1, -1)$, depending on $M$ and $N$; do we treat that value as 0, “padding” the input with zeros, or do we only produce outputs that do not involve convolution with out-of-bounds $x$ entries?
Do we add a bias? We could optionally add a bias to the convolution, which would be a single constant value for each filter.
What activation function do we apply to the convolved output?

The actual filters—the values of $w_k(m, n)$ for filter $k$—are parameters we learn during gradient descent. There are $M \times N$ distinct values to learn for each filter. Crucially, the nature of convolution means that these $M \times N$ values are shared across the image: each pixel of the output involves applying the same weights to different regions of the input image.

To be concrete, suppose the previous hidden layer is a $10 \times 15$ image, represented as a tensor with dimensions $(10, 15)$. Suppose we choose to have 4 filters that are each $5 \times 5$. What shape will the output of this layer be?

The output will be 3-dimensional, because we’ll be producing 4 separate two-dimensional convolutions. Each of the four convolutions will be a grid. If we do not pad the input with zeros, the grid will be 6 pixels tall (the input is 10 pixels tall and we take 5, moving down by 1 pixel at a time) and 11 pixels wide. Hence the output will be a tensor with shape $(4, 6, 11)$.

The output hence has $4 \times 6 \times 11 = 264$ values, determined by $4 \times 5 \times 5 = 100$ weight parameters that we must learn during gradient descent. If we included biases, there would be 4 additional biases, for 104 parameters.

Compare that to a fully connected layer. If a fully connected layer took an input layer with $10 \times 15 = 150$ values and produced an output with 264 values, we’d have $150 \times 264 = 39600$ weight parameters and 264 biases, for a total of 39,864 parameters.

That is about 380 times more parameters to produce the same number of outputs. You can quickly see how the structure imposed by a convolutional layer dramatically reduces the number of parameters to learn. If we are right that extracting local features from the input is the right way to solve our problem, this reduction in parameter space should not make our model worse, and should make it much easier to fit.

In PyTorch, the convolution layer described above would be a Conv2d layer defined like this:

nn.Conv2d(1, 4, (5, 5))

21.2.2 Additional options

We don’t always have to do a full convolution. One thing we can adjust is the stride. In the example above, we had a stride of 1: we consider $(x * w)(i, j)$ for $i$, $i + 1$, $i + 2$, and so on, for all valid values.

But if we had a stride of 2, we’d only consider every other value: $i$, $i + 2$, $i + 4$, and so on. It’d be like throwing out every other pixel from the output of the convolution.

Additionally, convolution layers can be defined when the previous layer is itself a stack of images. For example, our simple convolutional layer above produced a $(4, 6, 11)$ tensor. We could take that as input to another convolutional layer. In the second layer, the value at $(i, j)$ is the sum of the convolutions of the filter with each of the 4 outputs from the previous layer. In PyTorch, we could write

nn.Conv2d(4, 6, (4, 4))

to say there are 4 input channels—4 convolutions from the previous layers—and we’d like to apply six $4 \times 4$ filter to them.

There are additional options to, for instance, have this layer’s filters each see a specific subset of the previous layer’s outputs; but let’s skip that complexity for now.

Exercise 21.1 (Interpret a CNN) Adam Harley’s interactive convolutional network can classify digits and lets you see the activations in each layer. The input layer is at the bottom, and the first layer above it is a convolutional network as we described.

How many filters does it have? How big is each filter? What activation function is applied after convolution?

Write the dimensions of its output in the notation we used above ($(a, b, c, d)$).

21.3 Pooling

There are other ways to impose structure on gridded data.

One type of structure we might impose is invariance to small translations. We say a function is invariant if certain changes to its inputs do not change the output; invariance to translation means that if we shift the input in one direction or another, the output does not change at all.

In many types of gridded data, we expect translational invariance. If we’re classifying images of handwritten digits or of animals, moving them a pixel to the left shouldn’t change the classification.

One way to achieve this is with a pooling layer. The simplest and most common pooling is called max pooling.

You can think of pooling as being fundamentally similar to convolution. Just like convolution, we look at $M \times N$ sections of the input and produce a grid of outputs. But instead of convolving the input with a filter, a max pooling layer simply outputs the maximum of the values in the $M \times N$ window.

TODO draw an example

In PyTorch, we can write

nn.MaxPool2d((4, 5))

to define a layer that looks at $4 \times 5$ regions of the previous layer and takes the maximum of those.

If the previous layer had multiple filters—such as our layer that output a $(4, 6, 11)$ tensor—then the max pooling would be applied to each of those separately.

We can again choose the padding: do we only pool over the range of the input, or do we also pool over $M \times N$ windows that “hang over” the edge of the input? We’d pad those as $-\infty$, so the maximum is always one of the “real” pixel values, not a pooled value. We could turn on padding with the padding argument to nn.MaxPool2d().