Feed a 224 by 224 color photo to a fully connected layer with 1,000 hidden units and that one layer needs $224 \times 224 \times 3 \times 1000 \approx 150$ million weights. Worse, nothing in it knows that a cat in the top-left corner is the same thing as a cat in the center. It would have to learn "cat" separately at every position.

For a decade, two architectures solved problems like this by building the structure of the data into the network. Convolutional networks assume images are made of local patterns that can appear anywhere. Recurrent networks assume sequences are processed one step at a time with the same rule. Then residual connections and gates made both trainable at depth. Transformers have since replaced them for most tasks, but their ideas did not go away. Patch embeddings are convolutions, the residual stream is a residual connection, gating returns in SwiGLU and in state-space models, and the fixed-size-state bottleneck of recurrent networks is exactly what attention was invented to remove. This section teaches convolutions and residual connections at interview depth, including the forward and backward passes you may be asked to write, and gives recurrence a short treatment that Chapter 3 completes.

Convolution is a small dense layer, reused everywhere

Take a 1-D signal $\mathbf{x} = (1, 2, 3, 4, 5)$ and a filter (kernel) $\mathbf{w} = (1, 0, -1)$. Slide the filter along the signal and, at each position, take the dot product with the three values under it. The first output is $1\cdot1 + 2\cdot0 + 3\cdot(-1) = -2$, and every other position also gives $-2$, so the output is $(-2, -2, -2)$. This filter measures the local slope, and the signal has a constant slope. (Deep learning libraries compute exactly this sliding dot product and call it convolution, although mathematicians call it cross-correlation. True convolution flips the filter first. Since the filter is learned, the distinction does not matter.)

For images with channels the idea is the same in more dimensions. An input $\mathbf{X} \in \mathbb{R}^{C \times H \times W}$ ($C$ channels, height $H$, width $W$) and a bank of $F$ filters $\mathbf{W} \in \mathbb{R}^{F \times C \times k \times k}$ with biases $\mathbf{b} \in \mathbb{R}^F$ give an output with $F$ channels,

where $s$ is the stride, and the input has been zero-padded beforehand if requested. In plain words, each output value is a small dense layer applied to one $k \times k$ patch across all input channels, and the same weights are used at every position.

That one sentence contains two inductive biases. The first is locality. Each output depends only on a small neighborhood, so the network builds up from edges to textures to parts to objects. The second is weight sharing. The same filter is applied everywhere, which makes the layer translation equivariant. Shift the input by one pixel and the output shifts by one pixel (exactly so for stride 1), so a pattern learned in one place is recognized in every place. Weight sharing is also what makes convolutions cheap in parameters. A $3 \times 3$ convolution from 64 to 128 channels has $128 \cdot 64 \cdot 9 = 73{,}728$ weights (plus 128 biases), however large the image is.

Its compute, though, does grow with the image. Every output position does $C k^2$ multiply-adds per filter. On a $56 \times 56$ feature map that same layer costs $56 \cdot 56 \cdot 128 \cdot 64 \cdot 9 \approx 231$ million multiply-adds. Convolutional networks are compute-heavy and parameter-light, the reverse of the fully connected layers they replaced.

The filter lights up on the left and right edges of the square, with opposite signs. Shift the square and the response shifts with it, unchanged. That is equivariance, and it is why a CNN does not need to see a cat at every position to recognize one anywhere.

Padding, stride, and the output-size formula

Three settings control the output's spatial size. Padding $p$ adds $p$ zeros around the border so filters can be centered on edge pixels. Stride $s$ moves the filter $s$ positions at a time, downsampling the output. Dilation $d$ spaces out the filter's taps, so a $3 \times 3$ filter with $d = 2$ covers a $5 \times 5$ area with 9 weights. For an input of size $n$ along one axis and a kernel of size $k$,

In plain words, the dilated kernel spans $d(k-1) + 1$ inputs. Count how many times that span fits in the padded input, stepping by $s$.

Two cases are worth memorizing. With stride 1 and $p = (k - 1)/2$ for odd $k$ ("same" padding), the output has the input's size. And the ResNet stem works like this, from a $224 \times 224$ image. A $7 \times 7$ convolution with stride 2 and padding 3 gives $\lfloor(224 + 6 - 6 - 1)/2\rfloor + 1 = 112$. A $3 \times 3$ max pool with stride 2 and padding 1 gives $\lfloor(112 + 2 - 2 - 1)/2\rfloor + 1 = 56$. The first ResNet stage keeps $56 \times 56$, and each of the last three halves it, to 28, 14, and finally 7.

Receptive fields

The receptive field of a unit is the region of the input it can see. One $3 \times 3$ layer sees a $3 \times 3$ patch. A unit two layers up sees a $3 \times 3$ patch of units, each seeing $3 \times 3$ pixels, overlapping, so $5 \times 5$ pixels. Three layers give $7 \times 7$.

The general rule tracks two numbers per layer. The jump $j_l$ is the distance in input pixels between adjacent units of layer $l$, and the receptive field $r_l$ is the span of input pixels one unit sees. Starting from the input with $r_0 = 1$ and $j_0 = 1$,

In plain words, each layer widens the view by its extra kernel taps, measured in the input-pixel spacing of the layer below, and strides multiply that spacing for every layer that follows.

So strides make receptive fields grow fast. Through the ResNet stem above, the $7 \times 7$ stride-2 convolution gives $r = 7$, $j = 2$. The $3 \times 3$ stride-2 pool adds $(3 - 1)\cdot 2 = 4$, so $r = 11$, $j = 4$. One more $3 \times 3$ convolution adds $2 \cdot 4 = 8$, so $r = 19$. Explore it below. Click any output unit to light up everything it depends on.

This arithmetic is behind a classic design argument (Simonyan & Zisserman, 2015, the VGG paper). Three stacked $3 \times 3$ layers have the same $7 \times 7$ receptive field as one $7 \times 7$ layer, but with $3 \cdot 9 C^2 = 27C^2$ weights instead of $49 C^2$, and with two extra nonlinearities in between. One caution. The receptive field is where a unit can look, not where it does. Luo et al. (2016) showed that the effective receptive field, measured by how much each input pixel actually influences the output, is roughly Gaussian and occupies only a fraction of the theoretical one.

Two more designs save weights in modern CNNs. A $1 \times 1$ convolution looks at a single pixel, so it is a linear layer applied at every position, mixing channels without mixing space. A depthwise separable convolution (popularized by Xception, Chollet, 2017, and MobileNets, Howard et al., 2017) splits a $k \times k$ convolution from $C$ to $F$ channels into a per-channel $k \times k$ filter ($k^2 C$ weights) followed by a $1 \times 1$ convolution that mixes channels ($CF$ weights), instead of $k^2 CF$ weights in one go. It keeps a fraction $1/F + 1/k^2$ of the original weights, so for $k = 3$ and $C = F = 256$ it needs about 8.7 times fewer weights and multiply-adds. Mobile vision networks are built from it.

def conv_out_size(n, k, s=1, p=0, d=1):
    raise NotImplementedError

def receptive_field(layers):
    raise NotImplementedError

Pooling

A pooling layer summarizes each window with a fixed function, usually the maximum (max pooling) or the mean (average pooling), with no weights. A $2 \times 2$ max pool with stride 2 halves each spatial size and keeps the strongest response in each window, which adds a little invariance to small shifts. Global average pooling averages each channel over the whole map, turning a $C \times H \times W$ feature map into a $C$-dimensional vector. That is how a ResNet produces its final image embedding, a 2,048-dimensional vector for ResNet-50, which §1.8 uses as an image encoder. Many modern architectures replace pooling with strided convolutions, which learn how to downsample.

The backward pass of max pooling is worth knowing, since interviewers ask it. The output is the maximum of its window, so its derivative is 1 with respect to the input that achieved the maximum and 0 for the others. The upstream gradient is routed to the argmax position of each window, and if windows overlap, an input that is the maximum of several windows accumulates gradient from all of them.

import numpy as np

def maxpool_forward(X, k, s):
    raise NotImplementedError

def maxpool_backward(dY, cache):
    raise NotImplementedError

Convolution as one big matrix multiply

The six nested loops of the convolution formula are hopeless in Python and slow even in C. Every fast convolution reorganizes the work into something faster, and the oldest and simplest reorganization is im2col ("image to columns"). Copy every $k \times k \times C$ patch of the input into a row of a big matrix, and reshape the filters into a matrix with one column per filter. For a batch of $N$ images and an output of $H_{\text{out}} \times W_{\text{out}}$ positions per image, the whole convolution is then one matrix multiply,

In plain words, unroll the patches into rows, and the convolution becomes the dense layer it secretly was all along, applied to every patch at once.

This hands the work to a matrix-multiply kernel (GEMM), the most optimized routine on any hardware, which is why early GPU frameworks used it. The price is memory, since every input value is copied into up to $k^2$ patches. For a $3 \times 3$ convolution the column matrix is about 9 times larger than the input. Modern libraries such as cuDNN choose among several algorithms (implicit GEMM, which forms the patches on the fly, FFT-based methods, and Winograd transforms) per layer. Notice also how ViT's patch embedding fits in. It is a convolution whose kernel size equals its stride, so the patches do not overlap and im2col is a single reshape and transpose, the patchify step that starts every Vision Transformer (§1.8 builds it).

import numpy as np

def conv2d(X, W, b, stride=1, pad=0):
    raise NotImplementedError

The backward pass scatters columns back

Training needs the gradients of a convolution too, and im2col makes them almost free to derive, because the forward pass is now an ordinary linear layer, $\mathbf{Y}_{\text{col}} = \mathbf{X}_{\text{col}}\mathbf{W}_{\text{col}}^\top + \mathbf{b}$. Reshape the upstream gradient $\partial\mathcal{L}/\partial\mathbf{Y}$ into the same $(N H_{\text{out}} W_{\text{out}}) \times F$ layout and call it $\mathbf{G}$. Then the linear-layer rules of §0.2 give

In plain words, each filter's gradient correlates its output errors with the patches that produced them, and each patch's gradient is the errors sent back through the filters.

The only new step is getting from the gradient of the patch matrix back to the gradient of the image. Each pixel was copied into several patches, so by the accumulation rule of §0.3 its gradient is the sum of the gradients of all its copies. That inverse of im2col, adding every patch entry back to the pixel it came from, is called col2im. It has a neat consequence. For stride 1, the gradient with respect to the input is itself a convolution of the upstream gradient with the filters flipped and their input and output channels swapped. So computing the input gradient costs about as much as the forward pass, the weight gradient costs about as much again (the same factor of two as for a linear layer in §0.2), and the transposed convolution used for upsampling in generative models is exactly this input-gradient operation, run forward.

import numpy as np

def conv2d_backward(dY, X, W, stride=1, pad=0):
    raise NotImplementedError

Residual connections, and why ResNets train

By 2015, networks with about 20 layers worked, but making them deeper made them worse, and not from overfitting. He et al. (2016) showed that a 56-layer plain network had higher training error than a 20-layer one. That is strange, since the deeper network could in principle copy the shallow one and set its extra layers to the identity. The optimizer could not find that solution. They called this the degradation problem.

Their fix was to make the identity the default. A residual block computes

where $\mathcal{F}_l$ is a small stack of layers (two or three convolutions with normalization and ReLU in ResNet). In plain words, each block adds a correction to its input instead of replacing it. If the best thing a block can do is nothing, it only has to push its weights toward zero, which is easy.

The gradient tells the deeper story. Unroll the recursion from block $l$ to the last block $L$, so $\mathbf{x}_L = \mathbf{x}_l + \sum_{i=l}^{L-1}\mathcal{F}_i(\mathbf{x}_i)$. Then by the chain rule

In plain words, the gradient at any block contains the gradient at the top unchanged, plus whatever flows through the residual branches. In a plain network the gradient must pass through every layer's Jacobian, a product that can vanish. Here there is a direct path from the loss to every layer, which cannot vanish unless the branch terms cancel it exactly (He et al., 2016b, analyze this). Veit et al. (2016) offer a complementary picture. Unrolled, a residual network is a sum over exponentially many paths of different lengths, and most of the gradient flows through the short ones, so it behaves like an ensemble of relatively shallow networks.

There is one catch, and the cell shows it. Adding branch outputs to the stream also adds their variance, so in an unnormalized residual network the activations, and the gradients, grow with depth. ResNets control this with BatchNorm inside each branch, often initializing the last normalization gain of each branch to zero so every block starts as the identity (Goyal et al., 2017). Transformers control it with LayerNorm and by scaling down the branches at initialization, the $1/\sqrt{2L}$ rule that §5.7 derives.

With PyTorch's default initialization, the 50-layer plain network's gradient vanishes by a factor of about $10^{20}$, as §0.7 predicts for a per-layer gain below 1. The residual network keeps a gradient at the first layer, but its unnormalized stream grows to enormous scale. Scaling each branch by $1/\sqrt{L}$ keeps the activations near 1 and the gradient within a small factor of it (here 3.8). That combination, an identity path plus controlled branches, is what makes networks of hundreds of layers trainable, and it is the backbone of every Transformer (the residual stream, §5.1).

Recurrence, in brief

Images come on a grid. Text, audio, and time series come in order, and with any length. A recurrent neural network (RNN) reads such a sequence one step at a time, carrying a hidden state $\mathbf{h}_t \in \mathbb{R}^{d_h}$ that summarizes everything seen so far. At each step, with input $\mathbf{x}_t \in \mathbb{R}^{d}$,

with $\mathbf{W}_{hh} \in \mathbb{R}^{d_h \times d_h}$, $\mathbf{W}_{xh} \in \mathbb{R}^{d_h \times d}$, and $\mathbf{h}_0 = \mathbf{0}$. In plain words, mix the old state with the new input, squash, and repeat with the same weights at every step. That is weight sharing again, across time instead of space. Training unrolls the recurrence into a deep graph with one copy of the cell per step, all sharing weights, and backpropagates through it (backpropagation through time). The shared weights' gradient is the sum of the contributions from every step, the accumulation rule of §0.3.

The trouble is depth in time. The gradient from step $T$ back to step $t$ is a product of $T - t$ Jacobians, $\prod_{k=t+1}^{T}\operatorname{diag}(1 - \mathbf{h}_k^2)\,\mathbf{W}_{hh}$ (with the $k = T$ factor leftmost), all involving the same matrix. Its norm is at most $\lVert\mathbf{W}_{hh}\rVert^{T-t}$, where $\lVert\cdot\rVert$ is the spectral norm, the largest factor by which a matrix can stretch a vector, equal to its largest singular value (§0.10), since the tanh derivatives are at most 1. So when the largest singular value of $\mathbf{W}_{hh}$ is below 1 the signal from distant steps vanishes exponentially. A largest singular value above 1 is necessary for the gradient to explode, though not sufficient, because the tanh derivatives can still shrink it (Pascanu et al., 2013). A feed-forward network can fix this layer by layer with initialization and normalization. An RNN cannot, because every step reuses one matrix. Clipping (§0.6) handles explosions. Vanishing needs a change of architecture.

That change is gating. The LSTM (Hochreiter & Schmidhuber, 1997, with the forget gate added by Gers et al., 2000) keeps a separate cell state updated additively, $\mathbf{c}_t = \mathbf{f}_t\odot\mathbf{c}_{t-1} + \mathbf{i}_t\odot\mathbf{g}_t$, where $\odot$ is elementwise multiplication, $\mathbf{f}_t$ and $\mathbf{i}_t$ are learned gates between 0 and 1, and $\mathbf{g}_t$ is a candidate update. Along that path the Jacobian $\partial\mathbf{c}_t/\partial\mathbf{c}_{t-1}$ contains the direct term $\operatorname{diag}(\mathbf{f}_t)$ instead of a product with a weight matrix, so with the forget gate open, gradients cross many steps nearly unchanged. It is the residual connection of the previous section, with a learned valve on the identity path. The GRU (Cho et al., 2014) achieves the same with fewer gates. The full story, RNN language models, backpropagation through time implemented and checked, the eigenvalue analysis, and LSTM and GRU cells built from scratch, is in recurrent language models (§3.3).

Why Transformers replaced them, and what survived

The decisive rows are the middle two. An LSTM must squeeze everything about the past through one fixed-size state and carry it through $T$ sequential steps, which is slow on parallel hardware and still lossy over long ranges. Attention lets every position look at every other directly, in parallel (§3.6 tells this story, and §4.7 its costs). CNNs ceded ground on images for a subtler reason. Their built-in biases help with little data and limit them with a lot, so with hundreds of millions of training images a Transformer that learns its own biases wins.

But the ideas survived. Residual connections are in every Transformer block. Gates live on in SwiGLU feed-forward layers. Convolutions still make patch embeddings and audio front ends. And the RNN's fixed-size state, with its cheap constant-memory inference, has returned in state-space models such as Mamba, which use linear recurrences that can be trained in parallel, because a linear recurrence, unlike a tanh one, can be computed with a parallel scan.

In PyTorch

Read more

• Dumoulin & Visin (2016). A guide to convolution arithmetic for deep learning. Every case of padding, stride, and dilation, with diagrams.
• Araujo, Norris & Sim (2019). Computing Receptive Fields of Convolutional Neural Networks. The receptive-field recurrences derived carefully, with interactive figures.
• He, Zhang, Ren & Sun (2016). Deep Residual Learning for Image Recognition. The degradation problem and the residual fix. Their follow-up, Identity Mappings in Deep Residual Networks, analyzes the gradient path.
• Veit, Wilber & Belongie (2016). Residual Networks Behave Like Ensembles of Relatively Shallow Networks. The many-paths view of ResNets.
• Pascanu, Mikolov & Bengio (2013). On the difficulty of training recurrent neural networks. Vanishing and exploding gradients in RNNs, and clipping.
• Luo, Li, Urtasun & Zemel (2016). Understanding the Effective Receptive Field in Deep Convolutional Neural Networks. Why the effective receptive field is much smaller than the theoretical one.

Watch next

▶

▶

▶