DL S025 · The Convolution — From Cross-Correlation to Feature Maps

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 25 / 80 · Module M05 · ~2 hours

The story

Story hook · Yann LeCun at the post office

It is 1989. Yann LeCun, 29 years old, freshly arrived at Bell Labs from a postdoc with Geoff Hinton, has been handed a problem the US Postal Service will not stop complaining about: hand-written zip codes. Every day, tens of millions of envelopes come through automated sorters, and every single digit that a machine can't read gets kicked to a human. Humans are slow and expensive. The Post Office wants a neural network that can read the five digits on the corner of an envelope.

The obvious attempt — flatten each 16×16 grayscale digit to 256 numbers and shove it into a fully-connected MLP — half-works. It gets maybe 4% error, which sounds fine until you multiply by hundreds of millions of envelopes a year and realise you've just misrouted the population of Denmark. LeCun's frustration was more specific though. He noticed that the MLP had to re-learn what a "loop" looked like at the top-left of the image, at the top-right, at the middle, at the bottom-left. It had one weight for every (pixel, hidden unit) pair, and no way to say "the same little detector should slide across the whole image".

So he tried something borrowed from Fukushima's Neocognitron (1980) and from Hubel & Wiesel's cat-visual-cortex experiments (1962): share a tiny 5×5 patch of weights across every location of the image. The paper he wrote — "Backpropagation Applied to Handwritten Zip Code Recognition" (Neural Computation, 1989) — quietly published the first convolutional neural network trained end-to-end with backprop. It hit 1% error. The USPS started using it in 1993. By 1998 LeCun had polished the design into LeNet-5, which read ~10% of all US bank cheques by the early 2000s.

And then… nothing happened for about 14 years. GPUs weren't fast enough. ImageNet didn't exist yet. Nobody outside a small circle at Bell Labs and Toronto believed a network with a million parameters could be trained. LeCun kept the flame alive teaching NYU students. The world caught up in 2012, when Krizhevsky, Sutskever & Hinton took the same idea, scaled it to 60M parameters, ran it on two GTX 580s for a week, and won ImageNet by a 10-percentage-point margin — the AlexNet moment that started the modern deep-learning era.

Everything you're about to read — every ResNet, every ConvNeXt, every ViT patch-embed layer — descends from LeCun's idea to slide one small kernel across every position in the image. Today we build that idea from scratch. Two hours. By the end, you compute one by hand.

The puzzle we're solving today

For 24 sessions we've been working with fully-connected layers — every input neuron talks to every output neuron. That worked fine when our inputs were 784 pixels (MNIST flattened). But if I hand you a 224×224 colour image and ask you to feed it into a fully-connected layer with 1000 hidden units, the weight matrix alone is 224·224·3·1000 = 150,528,000 parameters. For one layer. And that layer will overfit MNIST-level datasets in about six batches, because 150M parameters can memorise anything smaller than the internet.

There's also a deeper problem. That fully-connected layer treats the pixel at (0, 0) and the pixel at (0, 1) as totally unrelated inputs — completely different weight columns, no shared knowledge. But we know as humans that neighbouring pixels are correlated, and that "an edge" in the top-left corner should be detected by the same machinery as "an edge" in the bottom-right corner. The fully-connected layer has to rediscover this fact separately for every position, from scratch.

Convolution fixes both problems in one go. One tiny kernel — say 3×3×3 = 27 weights — is dragged over every location in the image, computing a dot product at each spot. That's 27 parameters, not 150 million. And because the same 27 weights are applied at every spot, whatever the layer learns to detect at (0, 0) it detects everywhere else too. "Vertical edge" gets learned once and applied 50,000 times.

That's it. That is the entire architectural idea behind every image model of the last 15 years, from LeNet to ResNet to ConvNeXt to the stem of a modern vision transformer. Two hours today. By the end you'll compute one by hand and never be afraid of a Conv2d shape error again.

Prerequisites

• Everything through Session 024 (fully-connected nets, backprop, optimizers). Convolution is just backprop — the twist is only in the forward pass and in how gradients propagate to shared weights.
• Comfort with NumPy shapes and slicing (Session 001–003). You will slice into small 3×3 windows many times today.

1 · Why fully-connected doesn't scale to images

Let's put actual numbers on the pain.

Input: a 224×224 RGB image. That's 224 · 224 · 3 = 150,528 scalar inputs.

A modest FC layer: 1024 hidden units. Weight matrix is 150,528 × 1024 = 154,140,672. Add a bias: +1024. That's 154 million parameters for a single hidden layer.

For comparison, all of ResNet-50 has 25 million parameters. Our one FC layer is 6× larger than a state-of-the-art ImageNet model.

There are three separate problems here:

1. Memory + compute. 154M float32 parameters is 616 MB of weights. Times two if you keep gradients. Times three if you use Adam. You'd be OOMing on a laptop GPU for one layer.
2. Statistical inefficiency. With 154M parameters you'd need probably a billion labelled examples to avoid memorising the training set. ImageNet has 1.2M — off by three orders of magnitude.
3. Wasted structure. A pixel at (0, 0) and (0, 1) have their own private weights that share nothing. The network has to learn "an edge is an edge" independently at every one of 50,176 positions.

Convolution attacks all three. Let's build up to it.

2 · Cross-correlation by hand (this is what frameworks actually compute)

Here's a dirty little secret: what PyTorch and TensorFlow call "convolution" is not the mathematical convolution from a signal processing textbook. It's cross-correlation. The difference is just a kernel flip — and since we're going to learn the kernel from data anyway, the flip is irrelevant. The gradients will happily learn the flipped version if that's what the task needs.

I will use the term "convolution" the way frameworks do, meaning cross-correlation. Signal processing people, apologies in advance.

2.1 The operation on one channel

Take a 5×5 grayscale input and a 3×3 kernel:

That kernel is a vertical Sobel-like edge detector. +1 on the left column, 0 in the middle, -1 on the right — so it fires when the left half of the 3×3 window is brighter than the right half.

The output element at position (i, j) is:

That's the whole formula. Slide the kernel to (i, j), elementwise multiply, sum. Do it for every valid (i, j).

2.2 Compute the first output by hand

Position the kernel over the top-left 3×3 window of X:

Elementwise product:

1·1 + 2·0 + 3·(-1)  =  1 + 0 - 3   = -2
0·1 + 1·0 + 2·(-1)  =  0 + 0 - 2   = -2
3·1 + 1·0 + 0·(-1)  =  3 + 0 - 0   = +3

Sum: -2 + -2 + 3 = -1. So Y[0, 0] = -1.

Now (0, 1) — slide the kernel one step right:

Rows: (2·1 + 3·0 + 0·-1) + (1·1 + 2·0 + 3·-1) + (1·1 + 0·0 + 2·-1) = (2 + 0 + 0) + (1 + 0 + -3) + (1 + 0 + -2) = 2 + -2 + -1 = -1.

So Y[0, 1] = -1.

Do this for every valid (i, j). With input 5×5 and kernel 3×3 and no padding, output shape is (5-3+1, 5-3+1) = (3, 3). Nine numbers, one dot product each.

2.3 Check with NumPy

import numpy as np
from scipy.signal import correlate2d
 
X = np.array([[1,2,3,0,1],
              [0,1,2,3,1],
              [3,1,0,2,2],
              [2,0,1,3,1],
              [1,3,2,1,0]], dtype=float)
 
K = np.array([[ 1, 0, -1],
              [ 1, 0, -1],
              [ 1, 0, -1]], dtype=float)
 
Y = correlate2d(X, K, mode="valid")
print(Y)

You should see:

[[-1. -1.  4.]
 [ 2.  0. -3.]
 [-1. -6.  1.]]

Row 0 col 0 is -1. Match. Row 0 col 1 is -1. Match. You've now computed a convolution by hand.

K = [[ 1,  1,  1],
     [ 0,  0,  0],
     [-1, -1, -1]]

3 · The output shape formula (memorise this)

You will type this into shape-error debugging comments for the rest of your ML career. Might as well learn it now.

For an input of spatial size W (height and width are computed independently), kernel size k, stride s, and padding p:

Two things trip everyone up:

1. Padding is on both sides. That's why it's 2p, not p. Padding p=1 adds 1 row on top and 1 row on bottom.
2. The floor. If your input isn't divisible, some rows on the right/bottom get silently dropped. You will discover this the hard way when your feature map is 1 pixel shorter than expected.

3.1 The three combinations you'll actually see in practice

The general rule for "same" convolutions with stride 1: pick p = (k - 1) / 2. That's why kernel sizes in modern nets are almost always odd — 1, 3, 5, 7 — so that same-padding is a whole integer.

3.2 Worked shape examples

Example A. Input (N=1, C=3, H=224, W=224), Conv2d(3, 64, kernel=7, stride=2, padding=3).

H_out = floor((224 + 6 - 7)/2) + 1 = floor(223/2) + 1 = 111 + 1 = 112.

Output: (1, 64, 112, 112). That's the stem of ResNet — you've just computed the first layer of every image classifier from 2015–2020.

Example B. Input (1, 64, 56, 56), Conv2d(64, 128, kernel=3, stride=2, padding=1).

H_out = floor((56 + 2 - 3)/2) + 1 = floor(55/2) + 1 = 27 + 1 = 28.

Output: (1, 128, 28, 28). That's a typical "stage transition" in a ResNet where spatial resolution halves and channel count doubles.

Example C. Input (8, 3, 32, 32) (CIFAR-10 batch), Conv2d(3, 16, kernel=5, stride=1, padding=0).

H_out = floor((32 + 0 - 5)/1) + 1 = 27 + 1 = 28.

Output: (8, 16, 28, 28). You lost 4 pixels — 2 from each side — because you asked for a "valid" 5×5 conv.

4 · From single channel to multi-channel — the big shape jump

Real images have 3 channels (R, G, B), and internal feature maps have many more (32, 64, 128, 512...). This is where people get lost. So slow down.

4.1 The convention: (N, C, H, W)

PyTorch convention (also the default in most modern frameworks):

• N — batch size (how many images at once)
• C — number of channels (3 for RGB input; 64, 128, ... for hidden feature maps)
• H, W — spatial height and width

TensorFlow's default is (N, H, W, C) — same axes, different order. PyTorch chose channels-first because it's marginally faster on most GPUs.

4.2 What does a kernel look like when the input has 3 channels?

A single "3×3 kernel" applied to a 3-channel RGB image is actually a 3 × 3 × 3 tensor — 3 rows, 3 columns, and one plane per input channel. All 27 numbers get multiplied elementwise with the corresponding 3×3×3 window of the input, and summed to produce one scalar output.

So one kernel of shape (C_in, k, k) produces one output channel. If you want C_out output channels, you need C_out such kernels — a full weight tensor of shape (C_out, C_in, k, k).

Weight tensor: W  of shape (C_out, C_in, k, k)
Input:        X  of shape (N,     C_in, H, W)
Output:       Y  of shape (N,     C_out, H_out, W_out)

4.3 Parameter count (this is the punchline)

A Conv2d(C_in=3, C_out=64, kernel=7) layer has:

64 · 3 · 7 · 7 = 9,408 weights, plus 64 biases = 9,472 parameters.

Compare that with the fully-connected equivalent from Section 1: 154 million. We just replaced a 154M layer with a 9.5K layer. That's a 16,000× reduction in parameter count, and it's why conv nets scaled to ImageNet while fully-connected nets never did.

4.4 Small numeric example — 2-channel input, 2 output kernels

import numpy as np
 
# Input: batch 1, 2 channels, 4x4 spatial
X = np.random.default_rng(0).standard_normal((1, 2, 4, 4))
 
# Weights: 2 output channels, 2 input channels, 3x3 kernel
W = np.random.default_rng(1).standard_normal((2, 2, 3, 3))
b = np.zeros(2)
 
# Manual convolution
C_out, C_in, k, _ = W.shape
H, Wid = X.shape[2], X.shape[3]
H_out, W_out = H - k + 1, Wid - k + 1
Y = np.zeros((1, C_out, H_out, W_out))
 
for oc in range(C_out):
    for i in range(H_out):
        for j in range(W_out):
            window = X[0, :, i:i+k, j:j+k]     # shape (C_in, k, k)
            Y[0, oc, i, j] = np.sum(window * W[oc]) + b[oc]
 
print(Y.shape)   # (1, 2, 2, 2)

Notice the inner sum: window * W[oc] broadcasts over all C_in · k · k = 18 numbers, then np.sum collapses them to one scalar. That one scalar is one pixel in one output channel.

5 · Receptive field — why stacking small convs is so powerful

Here's a beautiful fact. A single 3×3 conv layer looks at a 3×3 neighbourhood. But stack two 3×3 conv layers on top of each other and each output pixel in layer 2 depends on a 5×5 window of the original input. Stack three, and it's 7×7. In general, stacking L layers of k×k convs gives a receptive field of L·(k-1) + 1.

Why this matters: it's why deep networks with small (3×3) kernels beat shallow ones with big (11×11) kernels. Same effective receptive field, way fewer parameters, more nonlinearities (=more expressive) between them. This is the entire insight of VGG (2014) that started the "stack lots of small convs" era we still live in.

6 · Padding, stride, and the two philosophies

There are really only two design choices for a conv layer beyond channel count:

Padding.

• padding=0 ("valid") — the output shrinks. Rarely used today except in the very first layer.
• padding=(k-1)/2 ("same") — output stays the same size. The default.

Stride.

• stride=1 — dense output; every input position produces an output. Default.
• stride=2 — subsample by 2×2 (equivalent to conv + 2×2 max-pool, but 4× cheaper). This is how modern nets downsample.

Historically people used max-pooling to downsample. Modern practice is often to just use strided convolutions. Fewer moving parts, one less hyperparameter.

7 · A minimal from-scratch conv in NumPy

Let's write the whole forward pass in ~30 lines and burn it into memory.

import numpy as np
 
def conv2d_forward(X, W, b, stride=1, padding=0):
    """
    X: (N, C_in, H, W_in)
    W: (C_out, C_in, k, k)
    b: (C_out,)
    returns Y: (N, C_out, H_out, W_out)
    """
    N, C_in, H, W_in = X.shape
    C_out, _, k, _ = W.shape
 
    # 1. Pad the input on the spatial dimensions only
    Xp = np.pad(X,
                pad_width=((0,0), (0,0), (padding,padding), (padding,padding)),
                mode="constant")
 
    # 2. Compute output spatial size
    H_out = (H + 2*padding - k) // stride + 1
    W_out = (W_in + 2*padding - k) // stride + 1
    Y = np.zeros((N, C_out, H_out, W_out))

Prose break: notice how the padding tuple has (0,0) for the batch and channel axes — we never pad those, only H and W. This is the single most common bug when people write their own conv: they accidentally pad the channel axis, and get an inscrutable dimension mismatch.

Now the main loop:

    # 3. The four nested loops (slow but obviously correct)
    for n in range(N):
        for oc in range(C_out):
            for i in range(H_out):
                for j in range(W_out):
                    hs = i * stride
                    ws = j * stride
                    window = Xp[n, :, hs:hs+k, ws:ws+k]   # (C_in, k, k)
                    Y[n, oc, i, j] = np.sum(window * W[oc]) + b[oc]
 
    return Y

Quick self-test:

X = np.random.default_rng(0).standard_normal((2, 3, 8, 8))
W = np.random.default_rng(1).standard_normal((4, 3, 3, 3))
b = np.zeros(4)
 
Y = conv2d_forward(X, W, b, stride=1, padding=1)
print(Y.shape)   # (2, 4, 8, 8) — same-padding, same H/W
 
Y2 = conv2d_forward(X, W, b, stride=2, padding=1)
print(Y2.shape)  # (2, 4, 4, 4) — downsampled by 2

This is O(N · C_out · H · W · C_in · k · k). For anything real, you'd use im2col (reshape the windows into columns and call matmul) or the framework's cuDNN wrapper. But the four-loop version is what actually happens conceptually. Read it slowly until it feels obvious.

8 · Where the gradients go (a preview of the backward pass)

Full derivation lives in Session 026, but here's the two-sentence version so you know what's coming:

• The gradient w.r.t. each kernel weight W[oc, ic, a, b] is the sum over every window position of dL/dY[n, oc, i, j] · X[n, ic, i+a, j+b]. Because the same weight is applied at every position, its gradient is a sum of contributions from every position.
• The gradient w.r.t. the input X[n, ic, i, j] is a transposed convolution of the upstream gradient with the flipped kernel. This is where the "flip" that we didn't need in the forward pass comes back to haunt us.

The consequence: shared weights get big gradients (they're summed over many positions), which is one reason convnets tolerate — even require — smaller learning rates than fully-connected nets of the same width. We'll come back to this.

War stories & pitfalls

9 · Tying it back: parameter count for a real convnet stem

Let's count the parameters of the first two layers of a ResNet-18:

• Conv2d(3, 64, kernel=7, stride=2, padding=3, bias=False) — 64·3·7·7 = 9,408 params. No bias.
• Conv2d(64, 64, kernel=3, stride=1, padding=1, bias=False) — 64·64·3·3 = 36,864 params.

Two conv layers, ~46K parameters, and they've already reduced the 224×224 input down to a 56×56 feature map with 64 useful channels. The equivalent two-layer fully-connected stack would have… well, we did the math. 154 million plus another few million. Sixteen thousand× more.

That's the whole reason vision "worked". Not fancier optimizers, not GPUs, not more data (though those all helped). It was the architectural prior that says "share weights across space." Yann LeCun proposed this in 1989. It took twenty years, a big enough dataset (ImageNet), and enough compute (GPUs) for the world to notice, but the idea was there the whole time.

10 · The 2025 pulse · why convolution refuses to die

The field's story for 2020–2022 was "transformers ate vision". ViT (Dosovitskiy et al. 2020), then Swin (Liu et al. 2021), then everyone assumed convolutions were legacy tech. Then in early 2022 Liu, Mao, Wu, Feichtenhofer et al. from FAIR + UC Berkeley published "A ConvNet for the 2020s" — the ConvNeXt paper — and the story flipped. They took a plain ResNet-50, ported over the training recipe used for Swin (AdamW, cosine schedule, MixUp, CutMix, RandAugment, stochastic depth, 300 epochs) and ported over the architectural touches (larger 7×7 depthwise kernels, LayerNorm instead of BatchNorm, GELU instead of ReLU, an inverted bottleneck like MobileNetV2). Result: 87.8% top-1 on ImageNet at 22M params, matching Swin-B while being simpler and faster on GPUs.

The punchline: most of the ViT advantage was the training recipe, not the attention. Give a convnet the same fuel and it holds its own. Then in late 2023 ConvNeXt V2 (Woo, Debnath, Hu et al. 2023) added a self-supervised masked-autoencoder pretraining stage plus a Global Response Normalization layer, and pushed the same architecture to 88.9% — well into ViT-Huge territory at a fraction of the compute.

2024–2025 kept the convolution comeback rolling:

• MobileNetV4 (Qin, Wang, Howard et al., ECCV 2024) — Google Research's newest on-device backbone. Introduces the "Universal Inverted Bottleneck" block and Mobile MQA (mobile-friendly multi-query attention). Hits 87% ImageNet accuracy in a model that runs at 3.8 ms on a Pixel 8. Every phone camera app you use for object detection or scene understanding likely runs a MobileNet descendant.
• EfficientNet-V2 (Tan & Le, 2021, still SOTA-adjacent in 2025) — the reference "scale with a compound coefficient" backbone; still the fastest to train per accuracy point for anything under 100M params.
• RepVGG / MobileOne family — "structural reparameterization" tricks where you train with a multi-branch topology (residuals, 1×1 branches) and then algebraically fold everything into a single 3×3 conv at inference. Same accuracy, half the latency.
• FastViT (Vasu et al., Apple, ICCV 2023) and EfficientFormer-V2 (Li et al. 2023) — hybrid conv+attention on-device models that ship inside iOS on-device photo intelligence.

Why hasn't convolution been retired? Three durable reasons that were true in 1989 and are still true in 2025:

1. Translation equivariance is free. A cat in the top-left activates the same feature as a cat in the bottom-right, without a single extra parameter. ViT has to learn that from positional embeddings and a mountain of data.
2. Locality is a prior that matches physics. Pixels near each other are correlated. A 3×3 kernel bakes that prior in. With small datasets (<10M images) this prior is worth ~5-15% accuracy vs a from-scratch ViT.
3. Hardware loves it. Convolutions are the single most-tuned kernel in cuDNN, TensorRT, Core ML, and every mobile inference runtime. A 3×3 depthwise conv often beats an equivalent attention op in wall-clock latency by 3-5×.

The 2025 mental model isn't "convnets vs transformers" — it's a spectrum. Pure convnets (ConvNeXt V2, MobileNetV4) on one end; pure transformers (ViT, DINOv2) on the other; hybrids (FastViT, MaxViT, Hiera) in the middle. What you pick depends on your data scale, compute budget, and deployment target — not on which was published most recently.

We'll build all three flavours in the next five sessions. Today's job: understand the atom that all three still use.

Further reading · convolution in 2025

• Liu et al. (2022) — A ConvNet for the 2020s (ConvNeXt). Section 3 is the tightest "port a ViT recipe onto a ResNet" you'll ever read.
• Woo et al. (2023) — ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders.
• Qin et al. (2024) — MobileNetV4: Universal Models for the Mobile Ecosystem.
• Ding et al. (2022) — Scaling Up Your Kernels to 31×31: Revisiting Large Kernel Design in CNNs (RepLKNet). The paper that made large-kernel convnets competitive again.
• Yann LeCun's personal LeNet demo page — click any of the videos to see the original 1993 network running on real cheques.

Retention scaffold

One-line summary (write it in your own words): ______________________________________

Spaced review: re-read section 3 (the shape formula) and section 7 (the four-loop implementation) in 24 hours. Revisit the full session on day 7 — try to redraw the kernel-sliding picture from memory before opening the page.

Next session (S026): LeNet → AlexNet → ResNet. The three architectures that mattered, built in code, with the residual add that unlocked networks 100 layers deep.

Sticky note (keep on your desk):

out = ⌊(W + 2p − k)/s⌋ + 1 · Kernel (C_out, C_in, k, k) · Tensor (N, C, H, W) · Weight sharing is the whole trick.

Legacy recall drills

Kept from an earlier version of this session — still useful.

Stretch prompt

Write the backward pass for conv2d_forward in NumPy — return dX, dW, db given upstream dY. Start with a single-channel single-example version, verify with torch.autograd, then generalize. Set a 90-minute timer.

In your own words

Explain to an interviewer, in 3 sentences and no jargon, why convolution beats fully-connected layers for images.

(Write your answer here — literally, in a notebook).

Spaced review

• Session 001–003: shape and slicing intuition — you needed it heavily today.
• Session 018: cross-entropy and backprop — the same principles apply when we differentiate the conv layer next session.

Next session

S026 — LeNet, AlexNet, ResNet: the three architectures that mattered. We'll implement LeNet from scratch on MNIST, then walk through AlexNet's tricks that made ImageNet work in 2012, then build a residual block and understand why "add the input back" was worth a decade of research.

Bring back tomorrow

• The output-shape formula: ⌊(W + 2p - k)/s⌋ + 1 — burn it in.
• Kernel shape (C_out, C_in, k, k), tensor shape (N, C, H, W).
• Weight sharing is the whole point — the same 27 numbers detect the same edge everywhere.

Previous: ← DL S024 · Next: DL S026 →