What is a Convolution Anyway? (Part 2)

Late in the 1950s, two young neuroscientists, David Hubel and Torsten Wiesel, spent their nights listening to a single neuron in the visual cortex of a cat. The cat looked at a screen, and they projected spots of light onto it, one after another, hoping the neuron would respond. For hours, it did almost nothing.

Then one of them slid a new glass slide into the projector. As it went in, the faint shadow of its edge swept across the screen, and the neuron erupted, firing so fast that its clicks on the loudspeaker ran together (Hubel later compared it to a machine gun). It had never cared about spots of light at all. It cared about an edge: a line between dark and light, at one particular angle, crossing one particular patch of the screen. Turn the edge a little, or move it somewhere else, and the neuron fell silent again.

In Part 1, we followed the photons as far as the optic nerve, where a hundred million rods and cones had already been squeezed into a summary a hundred times smaller. This is where that summary arrives. After one stop on the way (a relay station deep in the brain called the lateral geniculate nucleus), it reaches the first visual area of the cortex, V1, at the back of the head. Hubel and Wiesel found that V1 is tiled with neurons like the one they had heard: each one watching its own small patch of the visual field, each one waiting for its own small pattern. The work earned them a Nobel Prize in 1981.

If that sounds familiar, it should. A neuron that scans one small patch for one pattern is doing almost exactly what our filter $w'$ did in Part 1. But a cat is not an edge. Somewhere between a neuron that sees a line in a tiny window and the moment you recognise your cat across the room, small windows have to become big ones. That is the question Part 1 ended on, and the one we’ll answer first.

Where we left off

Here is the whole of Part 1, on one page.

We wanted a way to ask “does this part of the data look like the pattern I care about?” The dot product $x^\top w$ measures how aligned two vectors are, but a pattern is usually much smaller than the data it hides in. So we slid a short filter $w' \in \mathbb{R}^k$ along a long input $x \in \mathbb{R}^d$, taking a dot product at every position. The scores formed a new vector $z$, and the operation is a cross-correlation, which machine learning calls a convolution.

We padded $x$ with $p$ zeros at each end so its edges get a fair say, and let the filter take steps of $s$. The number of positions it can occupy, and so the length of $z$, is the master formula:

$$\text{Dimension of } z = \lfloor \frac{(d+2p)-k}{s} \rfloor + 1$$

Then we saw that all the slides together are one matrix multiplication, $z = Tx$, where every row of $T$ holds the same filter, shifted one place to the right:

$$T = \begin{bmatrix} w'_1 & w'_2 & w'_3 & 0 & 0 \\ 0 & w'_1 & w'_2 & w'_3 & 0 \\ 0 & 0 & w'_1 & w'_2 & w'_3 \end{bmatrix}$$

A convolution is a fully connected layer with two constraints: locality (each output looks only at a small neighbourhood, the band of $T$) and weight sharing (every output uses the same weights, the repeated row). And the patch of input an output depends on is its receptive field: after one layer, exactly $k$ inputs wide.

Which left us with four questions:

1. Stack a second 3-wide convolution on top of the first. How many $x$’s does one of its outputs depend on?
2. What about after ten layers? Does the receptive field grow by the same amount each time?
3. What changes if the first layer uses stride 2?
4. Inside a receptive field, does every input count equally?

Two layers deep

Let’s take the smallest example that can answer the first question. Our input is $x \in \mathbb{R}^5$, and the first layer slides $w' \in \mathbb{R}^3$ along it with no padding and stride 1. By the master formula, that gives $(5 - 3) + 1 = 3$ outputs:

$$z_1 = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$ $$z_2 = x_2 w'_1 + x_3 w'_2 + x_4 w'_3$$ $$z_3 = x_3 w'_1 + x_4 w'_2 + x_5 w'_3$$

Now the second layer. It has a filter of its own, $v \in \mathbb{R}^3$, and it slides along $z$ exactly the way $w'$ slid along $x$. Since $z$ and $v$ are both of length 3, $v$ is locked in place, and there is only one slide:

Slide 1 (and only):

$$\begin{array}{cccccc} z = & [ & \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & ] \\ v = & [ & \mathbf{v_1} & \mathbf{v_2} & \mathbf{v_3} & ] \end{array}$$ $$\rightarrow y = z_1 v_1 + z_2 v_2 + z_3 v_3$$

On its own, $y$ looks at only three numbers. But each of those numbers is itself a summary of three $x$’s, so let’s substitute them in:

$$\begin{aligned} y = \; & v_1 (x_1 w'_1 + x_2 w'_2 + x_3 w'_3) \\ + \; & v_2 (x_2 w'_1 + x_3 w'_2 + x_4 w'_3) \\ + \; & v_3 (x_3 w'_1 + x_4 w'_2 + x_5 w'_3) \end{aligned}$$

and collect the terms by which $x$ they multiply:

$$\begin{aligned} y = \; & (v_1 w'_1)\, x_1 \\ + \; & (v_1 w'_2 + v_2 w'_1)\, x_2 \\ + \; & (v_1 w'_3 + v_2 w'_2 + v_3 w'_1)\, x_3 \\ + \; & (v_2 w'_3 + v_3 w'_2)\, x_4 \\ + \; & (v_3 w'_3)\, x_5 \end{aligned}$$

Every one of the five $x$’s appears. So the answer to the first question is 5: one output of the second layer depends on five inputs, even though each layer only ever looked at three numbers at a time.

The matrix view says the same thing. The second layer is a $1 \times 3$ matrix (just the row $v$), and applying it after $T$ (the matrix from the recap) means multiplying the two:

$$\begin{bmatrix} v_1 & v_2 & v_3 \end{bmatrix} T = \begin{bmatrix} u_1 & u_2 & u_3 & u_4 & u_5 \end{bmatrix}$$

where $u_1 = v_1 w'_1$, $u_2 = v_1 w'_2 + v_2 w'_1$, and so on: exactly the five brackets above. The band of a single layer was 3 wide. The band of two layers together is 5 wide.

Look closely at that result, though, because it is stranger than it seems. Two convolutions in a row gave us $y = u^\top x$: a single dot product with a single 5-wide filter $u$. In other words, two 3-wide convolutions, one after the other, are secretly one 5-wide convolution. Hold on to that. It will come back to bite us.

Ten layers deep

What happens if we keep stacking? Each new layer looks at three neighbouring outputs of the layer before it. The middle one adds nothing new, but the outer two each reach one input further than anything the middle one could see: one on the left, one on the right. So every 3-wide layer widens the receptive field by exactly 2.

Layers	1	2	3	4	10
Receptive field	3	5	7	9	21

For a filter of any width $k$, each layer adds $k - 1$ inputs, $\frac{k-1}{2}$ on each side. Calling the receptive field after $n$ layers $r_n$, and starting from $r_0 = 1$ (before any convolution, each input sees only itself):

$$r_n = 1 + n(k - 1)$$

Ten layers of 3-wide filters: $r_{10} = 1 + 10 \times 2 = 21$. That answers the second question: with stride 1, the receptive field grows by the same amount every time. It grows linearly.

And linear is slow. If our cat is 500 pixels across, a network made only of 3 × 3 filters with stride 1 would need about 250 layers before a single output could see the whole of it.

So why does everyone use such small filters? Why not one big 21-wide filter and be done with it? Part of the answer is that a stack of small filters reaches just as far for far fewer weights. This is the argument at the heart of VGG (Simonyan and Zisserman, 2014), a network built almost entirely from 3 × 3 convolutions. Two stacked 3 × 3 filters have the same receptive field as one 5 × 5; three of them have the same receptive field as one 7 × 7. But three 3 × 3 filters hold $3 \times 9 = 27$ weights, where one 7 × 7 filter holds $49$. (The other part of the answer, which matters even more, needs the problem we just saw coming. We’ll get to it.)

x1234

Layer 4, output 12 sees x₁₂ to x₂₀: 9 inputs.

Taking bigger steps

The third question asks what stride does to all this. Let’s reuse our strided example from Part 1: $d = 7$, $k = 3$, $s = 2$. The three slides gave

$$z_1 = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$ $$z_2 = x_3 w'_1 + x_4 w'_2 + x_5 w'_3$$ $$z_3 = x_5 w'_1 + x_6 w'_2 + x_7 w'_3$$

Now put our second 3-wide filter $v$ on top, with stride 1. Again it can only sit in one place, $y = z_1 v_1 + z_2 v_2 + z_3 v_3$, but look at what those three $z$’s cover between them: $z_1$ starts at $x_1$, and $z_3$ ends at $x_7$. One output of the second layer now depends on 7 inputs, where without the stride it depended on 5.

Why? Because the stride spread the $z$’s out. With $s = 1$, neighbouring $z$’s started on neighbouring $x$’s. With $s = 2$, $z_1$ starts on $x_1$ and $z_2$ starts on $x_3$: neighbours in $z$ are now two apart in $x$. So when the second layer’s filter reaches one $z$ further to each side, it reaches two $x$’s further.

That distance deserves a name. Let’s call the gap, measured in inputs, between two neighbouring outputs of layer $l$ its jump, $j_l$. Before any layer, neighbouring inputs are one apart, so $j_0 = 1$. A layer with stride $s_l$ puts its outputs $s_l$ positions apart in the layer below, and each of those positions is $j_{l-1}$ inputs apart, so:

$$j_l = j_{l-1} \, s_l$$

And each layer, as before, reaches $k_l - 1$ positions further than a single position of the layer below. But a position of the layer below is now worth $j_{l-1}$ inputs, not one:

$$r_l = r_{l-1} + (k_l - 1) \, j_{l-1}$$

Let’s check it on our example. The first layer has $k_1 = 3$ and $s_1 = 2$: $r_1 = 1 + (3 - 1) \times 1 = 3$ and $j_1 = 1 \times 2 = 2$. The second has $k_2 = 3$ and $s_2 = 1$: $r_2 = 3 + (3 - 1) \times 2 = 7$. Which matches what we counted!

If you would like to be sure this works for any stack of layers, and not just the ones we tried, here is the argument. Number the outputs of every layer from 1, and suppose (this is our claim) that output $i$ of layer $l - 1$ depends on the inputs from $(i - 1) j_{l-1} + 1$ to $(i - 1) j_{l-1} + r_{l-1}$. It is certainly true for $l - 1 = 0$, where $j_0 = r_0 = 1$ and input $i$ depends on input $i$ alone. Now output $i$ of layer $l$ reads positions $(i - 1) s_l + 1$ through $(i - 1) s_l + k_l$ of layer $l - 1$. The first of those starts at input

$$\big((i - 1) s_l\big) j_{l-1} + 1 = (i - 1) j_l + 1$$

and the last, position $m = (i - 1) s_l + k_l$, ends at input

$$(m - 1) j_{l-1} + r_{l-1} = (i - 1) j_l + \underbrace{(k_l - 1) j_{l-1} + r_{l-1}}_{r_l}$$

So output $i$ of layer $l$ covers exactly the stretch the claim promises for layer $l$, with $r_l$ and $j_l$ given by our two formulas. True for one layer means true for the next, and so (by induction) true for every layer.

Now the answers come quickly. Ten layers of 3-wide filters, with stride 2 only in the first: $r_1 = 3$, $j_1 = 2$, and the other nine layers each add $2 \times 2 = 4$, so $r_{10} = 3 + 9 \times 4 = 39$. One strided layer, at the very bottom of the stack, almost doubled the reach of everything above it.

What if every layer has stride 2? Then the jump doubles every layer, $j_l = 2^l$, and each layer adds twice as much as the one before:

$$\begin{aligned} r_n &= 1 + 2(1 + 2 + 4 + \dots + 2^{n-1}) \\ &= 1 + 2(2^n - 1) = 2^{n+1} - 1 \end{aligned}$$

Ten such layers give $r_{10} = 2^{11} - 1 = 2047$. The receptive field now grows exponentially. A stride of 2 is the difference between 21 and 2047.

There is, of course, a price. The master formula tells us how many outputs each layer leaves behind, and with stride 2 that is about half as many as it was given. Take a row of 1000 pixels and pad each layer with $p = 1$: the lengths go

$$\begin{gathered} 1000 \rightarrow 500 \rightarrow 250 \rightarrow 125 \rightarrow 63 \rightarrow 32 \\ \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \end{gathered}$$

After ten layers, a single number is left, and its receptive field (2047) is more than wide enough to see the whole row. Stride trades resolution for reach: every output sees more, but there are fewer of them, and we no longer know as precisely where anything is.

x123

Layer 3, output 6 sees x₁₁ to x₂₁: 11 inputs.

Holes in the filter: dilation

Is there a way to grow the receptive field quickly without throwing resolution away? There is, and it is a lovely trick. Instead of spacing out the outputs, we space out the filter.

A dilated filter (also called an atrous filter, from the French à trous, “with holes”) reads inputs that are not next to each other. Its dilation $\delta$ is the distance between the inputs it reads: $\delta = 1$ is the ordinary filter we have used so far, and $\delta = 2$ reads every second input. (We can’t call it $d$, because $d$ is already the length of $x$.) Here is our 3-wide filter with $\delta = 2$, sliding along an input of length 9:

Slide 1:

$$\begin{array}{cccccccccccc} x = & [ & \mathbf{x_1} & x_2 & \mathbf{x_3} & x_4 & \mathbf{x_5} & x_6 & x_7 & x_8 & x_9 & ] \\ w' = & [ & \mathbf{w'_1} & 0 & \mathbf{w'_2} & 0 & \mathbf{w'_3} & ] & & & & \end{array}$$ $$\rightarrow z_1 = x_1 w'_1 + x_3 w'_2 + x_5 w'_3$$

Slide 2:

$$\begin{array}{cccccccccccc} x = & [ & x_1 & \mathbf{x_2} & x_3 & \mathbf{x_4} & x_5 & \mathbf{x_6} & x_7 & x_8 & x_9 & ] \\ w' = & & [ & \mathbf{w'_1} & 0 & \mathbf{w'_2} & 0 & \mathbf{w'_3} & ] & & & \end{array}$$ $$\rightarrow z_2 = x_2 w'_1 + x_4 w'_2 + x_6 w'_3$$

(… and so on, until …)

Slide 5:

$$\begin{array}{cccccccccccc} x = & [ & x_1 & x_2 & x_3 & x_4 & \mathbf{x_5} & x_6 & \mathbf{x_7} & x_8 & \mathbf{x_9} & ] \\ w' = & & & & & [ & \mathbf{w'_1} & 0 & \mathbf{w'_2} & 0 & \mathbf{w'_3} & ] \end{array}$$ $$\rightarrow z_5 = x_5 w'_1 + x_7 w'_2 + x_9 w'_3$$

The holes are written as zeros on purpose, because that is exactly what they are. A dilated filter is just an ordinary filter with $\delta - 1$ zeros between its entries: here, $[w'_1, 0, w'_2, 0, w'_3]$. It still has only three weights to learn, but it spans five inputs. In the matrix, every row of $T$ now has zeros inside its band:

$$T = \begin{bmatrix} w'_1 & 0 & w'_2 & 0 & w'_3 & 0 & 0 & 0 & 0 \\ 0 & w'_1 & 0 & w'_2 & 0 & w'_3 & 0 & 0 & 0 \\ & & & & \vdots & & & & \\ 0 & 0 & 0 & 0 & w'_1 & 0 & w'_2 & 0 & w'_3 \end{bmatrix}$$

Because a dilated filter is an ordinary filter with zeros in it, we don’t need any new formulas. We only need its width, which we’ll call $\hat{k}$. A $k$-wide filter has $k - 1$ gaps between its entries, and dilation makes each gap $\delta$ long, so

$$\hat{k} = \delta(k - 1) + 1$$

For our example, $\hat{k} = 2 \times 2 + 1 = 5$. Put $\hat{k}$ in place of $k$ in the master formula, $\lfloor \frac{(9 + 0) - 5}{1} \rfloor + 1 = 5$, and we get our five slides. Put it in place of $k_l$ in the receptive field formula, and we get $r_l = r_{l-1} + (\hat{k}_l - 1) j_{l-1}$.

Now stack three 3-wide layers with dilations 1, 2 and 4, all with stride 1. Their widths are 3, 5 and 9, and since the jump stays at 1, the receptive field is

$$r_3 = 1 + 2 + 4 + 8 = 15$$

Keep doubling the dilation, and $n$ layers give $1 + 2(1 + 2 + \dots + 2^{n-1}) = 2^{n+1} - 1$: exactly the exponential growth that stride gave us. But this time nothing was thrown away. With padding $p = \delta$, a 3-wide dilated layer keeps its output as long as its input (check it with the master formula: $\lfloor \frac{(d + 2\delta) - (2\delta + 1)}{1} \rfloor + 1 = d$), so every layer keeps full resolution.

Two famous networks lean on this. WaveNet (van den Oord et al., 2016), which generates raw audio one sample at a time, stacks filters of width 2 with dilations $1, 2, 4, \dots, 512$. With $k = 2$, each layer adds $\delta$ to the receptive field, so ten layers see $1 + (1 + 2 + \dots + 512) = 1024$ samples. Audio at 16,000 samples a second is far too fine-grained for ordinary convolutions to reach across a whole syllable; with dilation, ten layers cover 64 milliseconds, and WaveNet repeats the block to see further still. And DeepLab, a family of networks that label every single pixel of an image (this pixel is cat, that one is sofa), uses dilated convolutions because it cannot afford to shrink the image and lose track of where the cat’s outline is.

x123

Layer 3, output 9 sees x₉ to x₂₃: 15 inputs.

There is a catch, and the last figure hints at it. The gaps have to be filled in by someone. Suppose we stack two layers that both have $\delta = 2$:

x12

Layer 2, output 12 sees x₁₂ to x₂₀: 9 inputs, but only 5 of them reach it.

The first layer only ever combines inputs two apart, and so does the second. Nothing ever mixes an odd-numbered input with an even-numbered one, so each output sees half of its receptive field and is blind to the other half. This is called gridding, and it is why dilated networks grow their dilations in a schedule (1, 2, 4, …, or the mixed rates suggested by Wang et al., 2018) rather than repeating the same one.

Pooling, and the shift that isn’t

There is one more way to grow a receptive field, and it is the oldest. Before every layer had to be learned, networks shrank their feature maps with a fixed operation called pooling: slide a window of size $F$ along the input with stride $S$, and replace each window with a single summary of it. Max pooling keeps the largest value in the window; average pooling keeps the mean.

Because pooling slides a window exactly the way a filter does, the master formula applies unchanged. The most common choice, $F = 2$ and $S = 2$, halves the length:

$$\text{Dimension of } a = \lfloor \frac{d - 2}{2} \rfloor + 1$$

And for the same reason, our receptive field formulas apply too: a pooling layer counts as a layer with $k = F$ and $s = S$. What it doesn’t have is weights. There is nothing to learn: the window just reports its maximum, or its mean.

Average pooling, in fact, is nothing new. Averaging two neighbours is a dot product with the filter $[\tfrac{1}{2}, \tfrac{1}{2}]$, so average pooling is a convolution with stride 2 and a filter nobody trains, and it has a matrix like any other:

$$\begin{bmatrix} \tfrac{1}{2} & \tfrac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & \tfrac{1}{2} & \tfrac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{bmatrix}$$

Max pooling is different. It has no matrix at all, because it isn’t linear. A matrix $M$ always satisfies $M(a + b) = Ma + Mb$, but

$$\begin{gathered} \max(1, 0) + \max(0, 1) = 2 \\ \text{while} \\ \max(1 + 0, \; 0 + 1) = 1 \end{gathered}$$

Hold on to that, too. It is the first operation in this series that is not a matrix multiplication, and it won’t be the last.

Let’s put numbers on all this with a real network. VGG-16 has five stages. Each stage is two or three 3 × 3 convolutions with stride 1, followed by a 2 × 2 max pool with stride 2. Running our two formulas through it, with each convolution adding $2 j$ and each pool adding $1 \times j$ and doubling $j$:

After stage	1	2	3	4	5
Convolutions in the stage	2	2	3	3	3
Receptive field after its convolutions	5	14	40	92	196
Receptive field after its pool	6	16	44	100	212
Jump after its pool	2	4	8	16	32

VGG takes in a 224 × 224 image, and after five halvings it is left with a 7 × 7 grid of outputs. Each of those 49 outputs has a receptive field 212 pixels wide: nearly the whole image. Notice how much of that the last stage contributed. Its three convolutions alone added $3 \times 2 \times 16 = 96$ pixels, because by then each step was worth 16.

In Part 1, we noticed that our filter didn’t need to know where the spike was: move the spike, and the high score moves with it. That property, translation equivariance, was a promise to come back to, and pooling is the right place to keep it.

Let’s use our spike detector $w' = [-1, 2, -1]$ again, on an input of length 7 that is zero except for a single 9. Here is the output $z$ for the spike at $x_3$, and again with the spike moved one place to the right, to $x_4$:

$$\text{spike at } x_3: \quad z = [-9, \; 18, \; -9, \; 0, \; 0]$$ $$\text{spike at } x_4: \quad z = [0, \; -9, \; 18, \; -9, \; 0]$$

Shift the input by one, and the output shifts by one. That is equivariance, and the matrix tells us why: every row of $T$ is the row above, shifted one place, so shifting $x$ shifts which row lines up with the spike, and nothing else. (Away from the edges, that is. Where the zero padding begins, the shift has nowhere to go.)

Now max pool each $z$ with $F = 2$ and $S = 2$, and try every spike position from $x_2$ to $x_5$:

Spike at	$x_2$	$x_3$	$x_4$	$x_5$
Pooled output	$[18, 0]$	$[18, 0]$	$[0, 18]$	$[0, 18]$

Moving the spike from $x_2$ to $x_3$ changes nothing after pooling. The 18 moved within its pooling window, and the window only reports its maximum, not where inside it the maximum was. That is a small amount of translation invariance: the output doesn’t just move with the input, it stays the same. Stack pooling layers, and the tolerance grows with them, until a high-level output can report “there is an edge like this somewhere around here” without caring exactly where.

That is precisely what Hubel and Wiesel found next. Alongside the neurons that wanted an edge at one angle in one exact place, which they called simple cells, they found complex cells: neurons that wanted the same angle, but would fire for it anywhere within a larger patch. A complex cell behaves as if it pooled over several simple cells, all tuned to the same angle, each watching a slightly different spot. In 1980, Kunihiko Fukushima built that idea into a machine, the Neocognitron, which alternated layers of “S-cells” (convolutions) with layers of “C-cells” (pooling). It is the direct ancestor of every CNN in this series.

But look at the table again. Moving the spike from $x_3$ to $x_4$, by the very same one position, changed the answer completely, because it crossed the boundary between two windows. The invariance is real, but patchy: it holds inside a window and breaks across windows.

And stride, on its own, is worse. Run the same spike detector with stride 2 and no pooling:

$$\begin{aligned} \text{spike at } x_3: \quad z &= [-9, \; -9, \; 0] \\ \text{spike at } x_4: \quad z &= [0, \; 18, \; 0] \end{aligned}$$

That isn’t a shifted copy of anything. With the spike at $x_3$, the filter’s centre steps from $x_2$ straight to $x_4$, and never once lands on the spike, so the 18 that should announce it simply vanishes. In digital signal processing this has a name, aliasing: sampling a signal too sparsely to capture its fine detail, so that the detail turns into something else. Here, the spike was finer than our sampling of it.

This is not a curiosity. Azulay and Weiss (2019) showed that shifting an image by a single pixel can change the prediction of a modern CNN, and that the strides and pooling inside it are why. Zhang (2019) applied the fix any signal-processing engineer would: blur the feature map slightly before subsampling it, so there is no fine detail left to alias. (The blur is itself a convolution, with a fixed filter.) Padding breaks equivariance too, from the other direction: the zeros at the border tell the network where the border is, and Islam et al. (2020) found that CNNs use this to learn where in the image things are, even though nothing in the convolution itself knows.

Pooling has since fallen out of fashion as the main way to shrink a network. Springenberg et al. (2014) showed that replacing every max pool with a stride-2 convolution can work just as well, and many modern networks downsample that way. The network gets to learn its own summary of each window, instead of being told to take the maximum.

Does every input count equally?

That leaves the fourth question, and for it, let’s go back to Part 1’s table. With $d = 5$ and $k = 3$, we counted how many times the filter touched each input:

	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
Times touched	1	2	3	2	1

Now look back at our two-layer network. One output $y$ depended on all five $x$’s through the filter

$$u = \begin{bmatrix} v_1 w'_1 \\ v_1 w'_2 + v_2 w'_1 \\ v_1 w'_3 + v_2 w'_2 + v_3 w'_1 \\ v_2 w'_3 + v_3 w'_2 \\ v_3 w'_3 \end{bmatrix}$$

The middle entry is a sum of three products, the next ones out a sum of two, and the outer ones just one. Every product is one path from an input up to $y$: from $x_3$, for instance, there is a path through $z_1$ (using $w'_3$ then $v_1$), one through $z_2$ ($w'_2$ then $v_2$) and one through $z_3$ ($w'_1$ then $v_3$). To see the shape without the weights getting in the way, set every weight to 1. Then each path contributes exactly 1, and

$$u = [\,1, \; 2, \; 3, \; 2, \; 1\,]$$

It’s the table! That is not a coincidence. The table counted how many of the $z$’s each $x$ feeds into, and $y$ adds up all the $z$’s, so an $x$ that feeds three $z$’s reaches $y$ along three paths. The middle bias that worried us in Part 1 was the influence profile of a two-layer network all along. So the answer to the fourth question is no: even with every weight equal, the inputs in the middle of a receptive field have more ways of reaching the output, and so more say in it.

Add a third layer and the effect sharpens. Each layer adds up three neighbours of the layer below, so each new row of counts comes from the previous one by adding up three neighbours, or, in our language, by convolving it with $[1, 1, 1]$:

$$\begin{array}{c} 1 \quad 1 \quad 1 \\ 1 \quad 2 \quad 3 \quad 2 \quad 1 \\ 1 \quad 3 \quad 6 \quad 7 \quad 6 \quad 3 \quad 1 \\ 1 \quad 4 \quad 10 \quad 16 \quad 19 \quad 16 \quad 10 \quad 4 \quad 1 \end{array}$$

Every number is the sum of the three above it. (With 2-wide filters, each number would be the sum of the two above it, and this would be Pascal’s triangle. Ours is its cousin, the trinomial triangle.) Each row is wider than the last by two, as the receptive field formula said. But the numbers are piling up in the middle much faster than they spread out.

Smoothing a signal with $[1, 1, 1]$ over and over is a classic of signal processing, and its outcome is famous: whatever you start with, the result approaches a bell curve, a Gaussian. This is the central limit theorem in disguise. A path from the output down to an input takes one step per layer, and at each layer it can go left, straight or right, each in the same number of ways. Where it lands is the sum of $n$ independent steps of $-1$, $0$ or $+1$, and a sum of many independent steps is bell-shaped.

The theorem even tells us how wide the bell is. One step of $-1$, $0$ or $+1$, each equally likely, has variance

$$\frac{(-1)^2 + 0^2 + 1^2}{3} = \frac{2}{3}$$

and variances of independent steps add up, so after $n$ layers the variance is $\frac{2n}{3}$ and the width of the bell (its standard deviation) is

$$\sigma_n = \sqrt{\frac{2n}{3}}$$

Put that next to the receptive field. After ten layers, the receptive field is 21 inputs wide, but $\sigma_{10} = \sqrt{20/3} \approx 2.6$: most of the influence comes from the middle handful of inputs. And the gap only widens with depth. The receptive field grows like $n$; the part that really matters grows like $\sqrt{n}$. A hundred layers would see 201 inputs, with $\sigma$ only about 8.

Receptive field (thin line): 5 inputs. Half the paths come from the central 3 (thick line). Paths from each input: 1 · 2 · 3 · 2 · 1.

Luo et al. (2016) gave this a name, the effective receptive field, and showed that it survives everything a real network adds: random weights, nonlinearities between the layers, and so on. The influence on each output is roughly Gaussian, and it fills only a fraction of the theoretical receptive field, a fraction that shrinks as the network gets deeper. They also found what grows it: training itself (the bell widens as the network learns), and the two tools from earlier in this article, stride and dilation.

The retina, as it happens, got there first. The centre-surround cells we met at the start of Part 1, pushed one way by light at their centre and the other way by light around it, are classically modelled as the difference between a narrow Gaussian and a wide one (Rodieck, 1965). Our hand-made spike detector $[-1, 2, -1]$ was a three-number cartoon of exactly that.

Many filters at once: channels

Everything so far has had one filter per layer, looking for one pattern. But one pattern is not much of a vocabulary. Hubel and Wiesel didn’t find a neuron that responded to edges; they found neurons for edges at every angle, and more besides. So does every useful layer: it looks for many patterns at once.

The fix is simple: give each layer many filters, say $C_{out}$ of them, and run each one over the input separately. Each filter produces its own feature map, and we stack the maps one behind another. The output of a 2D layer is no longer a grid but a block of numbers, $H_{out} \times W_{out} \times C_{out}$, and each slice of the block, the feature map of one filter, is called a channel. Channel 1 might light up wherever there is a vertical edge, channel 2 wherever there is a horizontal one, channel 3 wherever there is a patch of orange.

That changes what the next layer receives. Its input is now a block with $C_{in}$ channels, and the same is true of the very first layer, because a colour photo already has three channels: one each for red, green and blue. So a filter can no longer be a flat $F \times F$ grid. To look at one patch of the input, it has to look at that patch in every channel at once, so it becomes a block too, $K \in \mathbb{R}^{C_{in} \times F \times F}$. At each placement, it multiplies its block element-wise with the block of input underneath and adds everything up:

$$z = \sum_{c=1}^{C_{in}} \sum_{i=1}^{F} \sum_{j=1}^{F} x_{c,ij} \, w_{c,ij} + b$$

It is still the same dot product we started Part 1 with, only between longer vectors: flatten both blocks, and each has $C_{in} F^2$ entries. The new $b$ is a bias, one extra learned number per filter, added to every score it produces. It shifts how strong a match has to be before the score counts as large. (It will matter more than it looks in a moment.)

A layer, then, holds $C_{out}$ filters, each a $C_{in} \times F \times F$ block, plus one bias each. All its weights together form a four-dimensional array, $C_{out} \times C_{in} \times F \times F$, and the number of parameters is

$$\text{Parameters} = C_{out}\,(C_{in} F^2 + 1)$$

Each filter takes one dot product of length $C_{in} F^2$ at each of the $H_{out} \times W_{out}$ placements, so the work of a layer, counted in multiply-adds, is

$$\text{Multiply-adds} = H_{out} \, W_{out} \, C_{out} \, C_{in} \, F^2$$

Let’s try these on the network that started the deep learning boom. The first layer of AlexNet (Krizhevsky, Sutskever and Hinton, 2012) takes a colour image and applies 96 filters of size 11 × 11 with stride 4. The paper says its input is 224 × 224, and its output 55 × 55. Let’s check that with the master formula:

$$H_{out} = \lfloor \frac{224 - 11 + 0}{4} \rfloor + 1 = \lfloor 53.25 \rfloor + 1 = 54$$

Not 55! This is a well-known puzzle in the paper, and the floor function is how you catch it. An input of 227 × 227 is what gives 55, $\lfloor \frac{227 - 11}{4} \rfloor + 1 = 54 + 1 = 55$, and 227 is what implementations of AlexNet actually use. With $C_{in} = 3$, $F = 11$ and $C_{out} = 96$:

$$\begin{aligned} \text{Parameters} &= 96 \times (3 \times 11^2 + 1) \\ &= 96 \times 364 = 34{,}944 \end{aligned}$$ $$\begin{aligned} \text{Multiply-adds} &= 55 \times 55 \times 96 \times 3 \times 11^2 \\ &\approx 105 \text{ million} \end{aligned}$$

Now compare that with a fully connected layer doing the same job: $227 \times 227 \times 3 = 154{,}587$ inputs, each connected to every one of $55 \times 55 \times 96 = 290{,}400$ outputs. That is about $4.5 \times 10^{10}$ weights, more than a million times as many, for a layer that would have to learn separately that an edge in the top-left corner is the same thing as an edge in the bottom-right.

And now we can give VGG’s argument its real numbers. With $C$ channels going in and out of every layer, one 7 × 7 layer has $49C^2$ weights, and three 3 × 3 layers, with the same receptive field, have $3 \times 9C^2 = 27C^2$. With $C = 512$, as in VGG’s deepest layers, that is a saving of almost six million weights per stack.

The matrix view survives, as it always does. Flatten each channel into a vector, $x_1, \dots, x_{C_{in}}$ for the input and $a_1, \dots, a_{C_{out}}$ for the output. The part of filter $o$ that looks at input channel $c$ is an ordinary 2D filter, so it has an ordinary convolution matrix $T_{oc}$, and output channel $o$ adds up what every input channel contributes:

$$\begin{bmatrix} a_1 \\ \vdots \\ a_{C_{out}} \end{bmatrix} = \begin{bmatrix} T_{11} & \cdots & T_{1 C_{in}} \\ \vdots & \ddots & \vdots \\ T_{C_{out} 1} & \cdots & T_{C_{out} C_{in}} \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_{C_{in}} \end{bmatrix} + \begin{bmatrix} b_1 \mathbf{1} \\ \vdots \\ b_{C_{out}} \mathbf{1} \end{bmatrix}$$

Look at the shape of that. Across channels, it is a fully connected layer: every output channel looks at every input channel, with its own block of weights. Within each block, it is a convolution: local, and shared across space. So a convolutional layer is fully connected in what it combines and convolutional in where.

The brain, once again, seems to be organised the same way. Hubel and Wiesel found that neighbouring neurons in V1 prefer neighbouring angles, and that a small block of cortex, about a millimetre across, holds a complete set of angle detectors (for both eyes) all watching the same patch of the visual field. They called it a hypercolumn. Move along the cortex, and you get the same complete set again, for the next patch over. A hypercolumn is, very nearly, the channel dimension of one position in a feature map.

The 1 × 1 convolution

Here is a filter that sounds useless: $F = 1$. A 1 × 1 filter looks at a single position, and has no neighbours to compare. The master formula leaves the map’s size unchanged, and our receptive field formula says it adds $k - 1 = 0$ to the receptive field. What could it possibly do?

Remember that the filter is really a block, $C_{in} \times 1 \times 1$. At every position, it takes the $C_{in}$ numbers stacked there, one per channel, and combines them with $C_{in}$ weights. With $C_{out}$ such filters, a 1 × 1 convolution turns the vector of $C_{in}$ channels at each position into a vector of $C_{out}$ channels, using the same $C_{out} \times C_{in}$ matrix at every position. It is a fully connected layer, applied to every pixel separately, with its weights shared across all of them.

So it looks nowhere new, but it mixes. If channel 1 says “vertical edge here” and channel 2 says “orange here”, a 1 × 1 filter can learn “orange vertical edge here”. It recombines what the layer below found, at the place where it found it. Lin, Chen and Yan made it a building block in Network in Network (2013), and GoogLeNet (Szegedy et al., 2015) used it to squeeze the number of channels down before its more expensive filters.

That squeezing is where the 1 × 1 earns its keep. Take a 3 × 3 layer with 256 channels in and 256 out:

$$256 \times 256 \times 3^2 = 589{,}824 \text{ weights}$$

The bottleneck of ResNet (He et al., 2016) does the job in three steps instead: a 1 × 1 layer shrinks 256 channels to 64, a 3 × 3 layer works at 64 channels, and another 1 × 1 grows them back to 256:

$$\begin{aligned} & 256 \times 64 + 64 \times 64 \times 3^2 + 64 \times 256 \\ = \; & 16{,}384 + 36{,}864 + 16{,}384 = 69{,}632 \text{ weights} \end{aligned}$$

The same receptive field (the 1 × 1 layers add nothing to it), the same channels in and out, and about eight and a half times fewer weights.

Why depth needs a bend

Now for the bill we have been running up. Back in Two layers deep, we found that two convolutions in a row are secretly one convolution: $v$ after $w'$ is the single filter $u$. The same is true of any number of layers. A stack of convolutions is a product of matrices, $T_n \cdots T_2 T_1$, and a product of matrices is just one matrix. Each layer’s matrix is a band of shifted copies of its filter, and so is their product: a single, wider filter. Ten 3-wide layers, with nothing between them, are one 21-wide filter. With channels, it is still one big matrix, one convolutional layer.

That is a disaster. All our careful stacking grew a receptive field that a single layer could have had directly, and gave the network nothing new to say about what it sees. Every pattern a ten-layer stack can detect, one layer could detect too.

The way out is to put something between the layers that is not a matrix multiplication, so the product can’t collapse. The standard choice is the ReLU (rectified linear unit), applied to every number of a feature map separately:

$$\text{ReLU}(z) = \max(0, z)$$

Negative scores become zero; positive ones pass through unchanged. It is the same kind of operation as max pooling (a maximum), and for the same reason it isn’t linear:

$$\begin{gathered} \text{ReLU}(1) + \text{ReLU}(-1) = 1 \\ \text{while} \\ \text{ReLU}(1 + (-1)) = 0 \end{gathered}$$

So $T_2 \, \text{ReLU}(T_1 x)$ can’t be multiplied out into a single matrix, and the second layer finally sees something the first layer couldn’t have computed by itself. Here is where the bias comes in. A filter’s score plus its bias, passed through a ReLU, says nothing at all until the match is strong enough to overcome the bias, and then speaks in proportion to how strong it is. A threshold, then a response: not unlike a neuron, which stays quiet until its input is strong enough, then fires.

With the bend in place, depth composes. The second layer’s input is a stack of maps saying where the first layer’s patterns were found, so its filters are patterns of patterns: this edge next to that edge, at this angle. The third layer’s are patterns of those. Zeiler and Fergus (2014) looked inside a trained network to see what each layer had learned to respond to, and found exactly this ladder: edges and blobs of colour in the first layer, corners and simple textures in the second, more complex textures and repeated patterns in the third, and parts of objects, and whole objects, in the fourth and fifth: wheels, eyes, the faces of dogs.

That is the rest of VGG’s argument, too. Three 3 × 3 layers don’t only have fewer weights than one 7 × 7; they have three ReLUs where the 7 × 7 has one. They can say three times as many non-linear things about the same 7 × 7 patch.

So depth needs both halves of this article. The receptive field decides how much of the image a layer can see. The nonlinearity decides whether it can say anything new about it.

From edges to cats

Let’s go back to the cat in Hubel and Wiesel’s laboratory, and follow its visual signal past V1.

From V1, the signal travels along what neuroscientists call the ventral stream, a chain of visual areas running forward along the underside of the brain: V1, then V2, then V4, then the inferior temporal cortex, IT. Along that chain, the patterns neurons respond to get more complex: oriented edges in V1; contours and textures in V2; curves and simple shapes in V4; and in IT, whole objects, including neurons that respond to faces. At the same time, their receptive fields grow: from a fraction of a degree of the visual field in V1 (near the centre of gaze) to tens of degrees in IT, where a single neuron can respond to a face almost anywhere in a large part of what you see. Small windows become big ones, simple patterns become complex ones, and position stops mattering.

Hold that next to everything we have built. Small, local filters, the same everywhere. Many of them at each position. Pooling, to tolerate a little movement. A nonlinearity, so each layer can say something new. And layer after layer of them, with receptive fields growing until an output sees the whole cat. That is a CNN, and the resemblance is not an accident: the line runs from Hubel and Wiesel, through Fukushima’s Neocognitron (1980), to Yann LeCun’s networks that learned to read handwritten zip codes (1989), to AlexNet (2012).

But it is inspiration, not a blueprint, and it is worth being honest about where the analogy breaks.

• The brain doesn’t share weights. Every neuron has its own synapses. V1 has edge detectors for every patch of the visual field, but each one is grown separately, not copied from a single filter. Weight sharing is an engineering shortcut, not biology.
• The brain talks back. A CNN, as we’ve built it, only ever passes information forward. The visual system is full of connections running the other way. In the lateral geniculate nucleus, the relay between the eye and V1, more connections arrive from the cortex above than from the retina below.
• The brain runs in time. A CNN computes its answer in one pass. Neurons keep responding, and keep changing their responses, for as long as you look.
• The brain doesn’t see on a grid. Our input is a uniform grid of pixels. Your vision is sharp only in a small region at the centre of gaze, the fovea, and your eyes jump around several times a second to point it at whatever matters.
• The brain probably doesn’t learn this way. A CNN learns by a mathematical procedure called backpropagation. How the brain adjusts its synapses is still not settled, and it is unlikely to be backpropagation as we use it.

Still, the core idea has survived every one of those differences. Perception, as we said at the very beginning of Part 1, is the art of throwing data away: keep the edges, the shapes, the objects; discard the rest. A CNN does it one small window at a time. Each layer keeps what its filters respond to and lets everything else fall to zero at the ReLU; each stride and pool throws away a little of exactly where things were. By the last layer, of the millions of numbers in the photo, a few hundred remain, each one seeing the whole image, and from them “cat” is easy to read.

Every layer we’ve built in this article does one of two things to the map: it keeps the size, or it shrinks it. Here are some questions to sit with before Part 3:

1. Some networks don’t want a single label for a photo. They want a label for every pixel (this pixel is cat, that one is sofa), so they have to end as large as they began. How would you grow a 7 × 7 feature map back to 224 × 224, with something the network can learn?
2. Our matrix $T$ maps 5 inputs to 3 outputs. Its transpose, $T^\top$, maps 3 numbers back to 5. Write $T^\top$ out. Is it also a sliding filter? If so, what is sliding over what?
3. Now take a stride-2 $T$ and transpose it. Does every output of $T^\top$ receive the same number of contributions? (Look back at the table in The trouble with edges one last time.)
4. In Part 1, we said training adjusts the filter’s numbers “a little at a time” to reduce an error measured at the output. To reach the first layer, that error has to travel backwards through every $T$. Which matrix carries it back?

In Part 3, we’ll run the convolution in reverse, and find that the answers to all four are the same matrix.