From Convolution to CNNs

Hand-designed features (colour histograms, SIFT, HOG) followed by a trained classifier was the recipe for image recognition until about 2012. A convolutional neural network learns both halves at once, straight from the pixels. This page builds one from the bottom: why the obvious learned classifiers fail on images, what a convolutional layer does instead, the two formulas that size every layer, pooling and receptive fields, what the filters actually learn, and why very deep networks only train once you give them residual connections. 𐃏

The training side (backpropagation, optimisers, augmentation, transfer learning) is on the Backpropagation and Optimisers pages, and regularisation and initialisation in practice are in Improving the Way Neural Networks Learn. Convolution as a filtering operation, and its frequency-domain view, is on the Seeing in Frequency page.

why a linear classifier and an MLP struggle#

one template per class#

Flatten an image into \(\mathbf x \in \mathbb R^D\). For a \(32\times32\) colour image, \(D = 32\cdot32\cdot3 = 3072\).

Row \(j\) of \(\mathbf W\) is a template for class \(j\): the score is the dot product of the image with that template, a correlation evaluated at a single position. Ten classes on \(32\times32\times3\) images need \(10\cdot3072 + 10 = 30\,730\) parameters, and each class gets exactly one template. A cat facing left and a cat facing right have to share it.

The decision boundaries \(z_j = z_k\) are hyperplanes, so a class must occupy a half-space (more precisely, an intersection of half-spaces). Three toy problems in the plane show what that rules out.

Hand-made features can rescue a particular case (\(x_1x_2\) separates the quadrants, \(r^2 = x_1^2 + x_2^2\) separates the annulus), but each fix needs you to know the shape of the answer in advance. The point of a neural network is to learn such features.

hidden layers, and why they need a non-linearity#

A fully connected (FC) layer maps \(\mathbf a \in \mathbb R^n\) to \(\mathbf W\mathbf a + \mathbf b \in \mathbb R^m\), with one weight per input–output pair. A multilayer perceptron alternates FC layers with an elementwise activation \(g\), usually the ReLU \(g(z) = \max(0, z)\): \[ \mathbf z = \mathbf W^{(2)}\max\bigl(0,\ \mathbf W^{(1)}\mathbf x + \mathbf b^{(1)}\bigr) + \mathbf b^{(2)} . \]

The activation does all the work.

With the ReLU in place, a single hidden layer of four units solves the quadrant problem.

That picture is the whole idea of deep learning in miniature: the hidden layers transform the input until the last layer, which is just a linear classifier, can do its job.

why not just use an MLP on pixels?#

Two reasons, and they are the two things a convolutional layer fixes.

Parameter count

Every hidden unit sees every pixel. A \(224\times224\times3\) input into 4096 hidden units needs \(150\,528\cdot4096 + 4096 = 616\,566\,784\) parameters in the first layer alone.

No notion of neighbourhood

Flattening throws the grid away. A stroke detector learned in the top-left corner has to be learned again, with different weights, at every other position, and a one-pixel shift of the input can change the output arbitrarily.

FC layers are the right tool on short feature vectors, which is exactly where a CNN uses them: at the end, after the convolutional layers have done the spatial work.

proofs#

the convolutional layer#

intuition: small, shared, local#

Keep the image as a grid. Let each output unit look only at a small \(k\times k\) neighbourhood (local connectivity), and use the same weights at every position (parameter sharing). That is exactly a filter slid over the image, as in classical spatial filtering, except that the filter’s weights are now learned. A stroke detector learned at one position automatically works at every position, and the parameter count no longer depends on the image size.

Three facts that trip people up:

It is a correlation

The formula has \(A(x + i, y + j)\), not \(A(x - i, y - j)\). Deep-learning “convolution” is correlation. Because the weights are learned it makes no difference: training would simply learn the flipped kernel.

A filter spans the full input depth

On an RGB input a \(5\times5\) filter is really \(5\times5\times3\). Its three slices are summed into one feature map, so the output depth is the number of filters, whatever \(c_{\text{in}}\) is.

The weights are not designed

Classical kernels (Sobel, Laplacian) are a useful mental model for what a filter might learn, nothing more.

Example (A 5 by 5 input and a 3 by 3 filter)

Stride 1, no padding, so the output is \(3\times3\).

Top-left output, row by row of the patch against the filter: \[ (0\cdot0 + 2\cdot1 + 1\cdot(-4)) + (0\cdot0 + 1\cdot2 + 2\cdot0) + (1\cdot(-1) + 0\cdot4 + 2\cdot3) = -2 + 2 + 5 = 5 . \] One column to the right: \[ (0 + 1 + 0) + (0 + 4 + 0) + (0 + 8 + 0) = 13. \] The other seven positions give \[ J = \begin{pmatrix}5&13&-4\\-8&5&8\\-1&11&15\end{pmatrix}, \qquad \operatorname{ReLU}(J) = \begin{pmatrix}5&13&0\\0&5&8\\0&11&15\end{pmatrix}. \] The output is large where large pixels sit under the large positive taps (4, 3, 2) and negative where they sit under the \(-4\). ReLU keeps only the matches: the layer is a bank of learned template detectors, each run everywhere.

the volume picture#

On a \(32\times32\times3\) image, one \(5\times5\times3\) filter gives one number \(\mathbf w^\top\mathbf x + b\) (a 75-dimensional dot product) per position, and sliding it over the \(28\times28\) positions where it fits gives one \(28\times28\) map. Six filters give six maps, stacked into a \(28\times28\times6\) output volume: a grid with a six-dimensional feature vector at every pixel. The next layer’s filters are then \(k\times k\times6\), and so on.

Here is one filter, a horizontal-derivative kernel standing in for a learned first-layer filter, run through a full conv, ReLU, pool block on a real photograph.

ReLU throws away the bright-to-dark edges entirely, which is one reason a layer has many filters: a second filter of the opposite sign picks them up.

output size and parameter counting#

Two formulas carry almost every calculation about a CNN. Getting the size wrong is the commonest bug when building one, because the next layer’s input, and the length of the flattened vector entering the FC head, both follow from it.

the output-size formula#

Count the positions where the filter fits. On a \(7\times7\) input with a \(3\times3\) filter and no padding, stride 1 gives 5 positions per side, stride 2 gives 3 (left edges at 0, 2, 4), and stride 3 gives 2: the next window, starting at column 6, would hang off the edge.

The quantity \(k_{\text{eff}} = d(k-1) + 1\) is the span of a dilated filter, so with \(d = 1\) the formula is the familiar \((n_{\text{in}} + 2p - k)/s + 1\). The special cases worth knowing by heart:

Valid (\(s = 1\), \(p = 0\))

\(n_{\text{out}} = n_{\text{in}} - k + 1\): each layer eats \(k - 1\) pixels.

Same (\(s = 1\), \(k\) odd, \(p = (k-1)/2\))

\(n_{\text{out}} = n_{\text{in}}\). Hence \(3\times3\) with padding 1, \(5\times5\) with padding 2. An even \(k\) has no symmetric “same” padding, one reason kernels are odd.

Strided

Stride \(s\) divides the size by about \(s\). If \((n_{\text{in}} + 2p - k_{\text{eff}})/s\) is not an integer, the hyperparameters “do not fit”; PyTorch silently drops the leftover pixels, which is what the floor expresses.

The last row is why AlexNet’s input is really \(227\times227\): with 224, \((224 - 11)/4 + 1 = 54.25\) does not fit.

counting parameters#

Stride and padding change the output size, not the parameter count; a larger stride gives a smaller output, more padding a larger one. Those two distinctions are what exam questions test.

proofs#

pooling#

After convolution and ReLU the feature maps are still image-sized, and there are many of them. Pooling shrinks them.

Pooling detects nothing; the features are found by the convolution filters, and pooling only summarises each window. Max pooling says “the feature occurred somewhere in here”. That buys two things: later layers see a larger part of the image for the same kernel size, and a feature that moves by a pixel but stays inside its window produces the same pooled value. The insensitivity is only partial (a shift across a window boundary changes the output), but stacking pooling layers widens the range of shifts absorbed.

When to use what. Max pooling is the default inside a classification feature extractor. Average pooling suits smooth summaries, above all global average pooling, which averages each channel over the whole map just before the classifier. A strided convolution downsamples too, with learned weights instead of a fixed rule.

The head of the network is short. Flatten the last \(n\times n\times c\) maps into a vector of length \(n^2c\), pass it through one or more FC layers, and turn the final \(C\) scores into probabilities with the softmax, \[ p_j = \frac{e^{z_j}}{\sum_{k=1}^C e^{z_k}} , \] computed in practice as the softmax of \(\mathbf z - \max_k z_k\) (the same probabilities, with no overflow).

receptive fields#

Why do small kernels suffice? Because what matters for a deep unit is how much of the input it can see, and every layer enlarges that.

For \(C = 64\): \(49\cdot64^2 = 200\,704\) weights against \(27\cdot64^2 = 110\,592\). The stack is deeper, more non-linear and 45% smaller. That one observation is VGG’s entire design.

Strides multiply in: after a stride-2 layer, every later \(3\times3\) kernel adds 4 input pixels instead of 2. This is how pooling and strided convolutions let a network see the whole image in a modest number of layers. Dilation is the other cheap way to grow the receptive field: a \(3\times3\) filter with \(d = 2\) spans \(k_{\text{eff}} = 5\) pixels with nine weights instead of 25. Its failure mode is that detail finer than the gap falls between the taps, and stacking layers with the same \(d\) leaves a regular grid of input pixels that never influence an output (gridding). Use it where you need context without downsampling, as in per-pixel labelling.

proofs#

a whole network: learned filters on Chinese-MNIST#

Put the blocks together. A classic small digit network: two valid \(5\times5\) convolutions, each followed by \(2\times2\) max pooling, then flatten, an FC ReLU layer and a softmax.

The same architecture with 6 and 16 filters, 64 hidden units and 15 outputs was trained from scratch on the \(64\times64\) Chinese-MNIST handwritten numerals (12,000 training images, 3000 test, four epochs of Adam). Shapes run \(64 \to 60 \to 30 \to 26 \to 13\), the parameter count is 176,667, and test accuracy reached 71.2%. Better accuracy needs longer training, but the interesting part is already visible in the first layer.

The filters started as random noise and were shaped only by the class labels. Each has become a stroke or edge detector with a positive and a negative side, tuned to one orientation or polarity, which is what the first layer of almost every image CNN learns. Deeper layers combine these into corners and stroke junctions, then into parts of characters; the receptive-field arithmetic is what lets them.

why depth degrades#

If small stacked kernels are good, more of them should be better. A deeper network contains a shallower one (the extra layers could just copy their input), so on the training set more depth should never hurt. In practice it does: a 56-layer plain CNN has higher training and test error than a 20-layer one.

The cause is that plain layers find the identity map hard to learn, and gradients reaching early layers are products of many Jacobians, which shrink or blow up geometrically with depth. Batch normalisation helps but does not cure it.

residual connections#

ResNet’s fix starts from the observation above: a deeper model should be at least as good as a shallower one, because extra layers could be identities. So make the identity the default.

If the best thing a block can do is nothing, it only has to drive \(\mathcal F\) to zero, which is easy. And the shortcut carries the gradient back undamped.

Back to the experiment. Adding the shortcuts to the 22-layer network, and changing nothing else, brings its training loss from 1.421 down to 0.446, level with the shallow network.

A second reading: unroll \(n\) residual blocks, each of which either passes through \(\mathcal F_i\) or skips it, and you get \(2^n\) paths of different lengths from input to output. A ResNet behaves like an ensemble of shallower networks.

The bottleneck block makes depth affordable. A basic block on 64 channels has \(2\cdot9\cdot64^2 = 73\,728\) weights. A bottleneck on 256 channels has \(256\cdot64 + 9\cdot64^2 + 64\cdot256 = 69\,632\): four times the channels for slightly fewer weights. A basic block on 256 channels would cost \(1\,179\,648\). That is why ResNet-50 costs about the same as ResNet-34 (3.8 against 3.6 GFLOPs) while being half again as deep.

proofs#

the architecture line#

Each architecture answers a failure of the one before it, and the ImageNet challenge (ILSVRC, 1000 classes) is where most of them were introduced.

LeNet-5 (1998)

Two \(5\times5\) convolution and subsampling stages, then three FC layers, tanh activations, trained by backpropagation on \(32\times32\) digits. About 61,700 weights, almost all in the FC layers. The template for everything after it.

AlexNet (2012)

Eight layers (five conv, three FC). The new ingredients were ReLU instead of saturating activations, dropout, data augmentation and training on two GPUs. It cut ImageNet top-5 error from 25.8% to 16.4%. Of its 62.4 million parameters, 94% sit in the FC layers.

VGG (2014)

Only \(3\times3\) convolutions with “same” padding, in five stages separated by \(2\times2\) pooling, channels doubling to 512. Depth buys the receptive field (three \(3\times3\) layers see \(7\times7\)). VGG-16 has 138 million parameters, 102.8 million of them in the first FC layer. Clean and heavy.

GoogLeNet / Inception (2014)

Goes wider instead of only deeper: each module runs \(1\times1\), \(3\times3\), \(5\times5\) convolutions and a pooling branch in parallel and concatenates them. Cheap \(1\times1\) convolutions shrink the channel count in front of the expensive branches, and global average pooling replaces the giant FC layer. 22 layers, 6.7% top-5.

ResNet (2015)

Identity shortcuts make 50, 101 and 152 layers trainable; bottleneck blocks keep them affordable. 3.6% top-5, below the human reference. Still the default backbone.

EfficientNet (2019)

Scales depth, width and input resolution together, \(d = \alpha^\phi\), \(w = \beta^\phi\), \(r = \gamma^\phi\) with \(\alpha\beta^2\gamma^2 \approx 2\), so each step of \(\phi\) doubles the FLOPs. EfficientNet-B7 matches GPipe’s 84.3% top-1 with 66 million parameters instead of 556 million.

ViT (2021)

Drops convolution: cut the image into \(16\times16\) patches, embed each as a token, and run a Transformer encoder with self-attention, so every patch can interact with every other from the first layer. See Visual Transformers.

Two side branches are worth a line each. SENet (2017) reweights the channels of a feature map from its global average, a cheap add-on to any block. DenseNet (2017) concatenates every earlier layer’s output instead of adding one shortcut, so channels grow by a fixed rate per layer.

Why does ViT need so much more data? Inductive bias. A CNN builds in locality and translation equivariance, so it does not have to learn that neighbouring pixels are related or that a stroke means the same thing everywhere. A ViT has neither and must learn both from data, which pays off only with very large data sets or pretraining. Its attention also costs the square of the number of tokens: 197 tokens for a \(224\times224\) image give a \(197^2 = 38\,809\)-entry attention matrix per head and layer. ConvNeXt (2022) went the other way, modernising a ResNet step by step with ViT’s design choices (a non-overlapping “patchify” stem, large depthwise kernels, fewer activations and norms) while staying a pure CNN, and reached 82.0% against ResNet-50’s 78.8% at a similar budget, level with the Swin Transformer.

Worked PyTorch implementations of AlexNet, VGG and ResNet are in the modern CNNs chapter of Dive into Deep Learning. The residual-learning paper is He et al. (2015).

see also#

• Computer Vision – the parent branch, whose image-processing section has convolution as a filter
• CNN from scratch – a convolutional network implemented by hand
• Object Detection and Semantic and Instance Segmentation – what these backbones are used for: boxes, then masks
• Seeing in Frequency – convolution as a designed filter, and its frequency response
• Feedforward Deep Neural Networks – the multilayer perceptron in depth
• Backpropagation – how every filter on this page is learned
• Perceptron – the single linear unit, and the XOR problem it cannot solve
• Transformers and Visual Transformers – self-attention, and its application to image patches