Convolution as weight sharing
A fully connected layer can connect any pixel to any output. Images do not need that. A pixel's meaning depends mostly on its neighbours, and a cat is a cat wherever it sits in the frame. Convolution bakes in exactly those two assumptions, locality and weight sharing, and in exchange removes almost all of the parameters.
The parameter count
Map a $32 \times 32 \times 3$ image to a $32 \times 32 \times 16$ output. A dense layer needs one weight per input-output pair:
$$3072 \times 16384 = 50{,}331{,}648 \text{ weights}$$
A $3 \times 3$ convolution with 16 filters produces the same output shape with
$$3 \cdot 3 \cdot 3 \cdot 16 + 16 = 448 \text{ parameters}$$
That is a factor of more than 100,000. The convolution is not a smaller model that approximates the dense one. It is the dense layer with most of its weights forced to zero and the rest forced to be equal.
Convolution as a tied matrix
Take a one-dimensional input $x = [1, 2, 3, 4, 5]$ and a kernel $k = [1, 0, -1]$. Slide the kernel and take dot products: $[1-3,\ 2-4,\ 3-5] = [-2, -2, -2]$. (Deep learning libraries call this convolution but do not flip the kernel; strictly it is cross-correlation. It makes no difference because the kernel is learned.) As a matrix product:
$$\begin{pmatrix} 1 & 0 & -1 & 0 & 0 \ 0 & 1 & 0 & -1 & 0 \ 0 & 0 & 1 & 0 & -1 \end{pmatrix} \begin{pmatrix} 1 \ 2 \ 3 \ 4 \ 5 \end{pmatrix} = \begin{pmatrix} -2 \ -2 \ -2 \end{pmatrix}$$
Every row holds the same three numbers, shifted. That is weight sharing made visible. One consequence matters for training: the gradient of a shared weight is the sum of its gradient at every position it was used,
$$\frac{\partial L}{\partial w_j} = \sum_{p} x_{p+j},\delta_p$$
where $\delta_p$ is the gradient arriving at output position $p$. Same accumulation rule as backprop, applied to a weight instead of a node.
Shapes you must be able to compute
For input size $n$, kernel $k$, padding $p$ and stride $s$:
$$n_{out} = \left\lfloor \frac{n + 2p - k}{s} \right\rfloor + 1$$
With $n = 32$, $k = 3$, $p = 1$, $s = 1$ you get 32, so the size is preserved. With $p = 0$ and $s = 2$ you get $\lfloor 29/2 \rfloor + 1 = 15$. A layer's parameters are $k^2 C_{in} C_{out} + C_{out}$. Its cost in multiply-adds is that kernel size times the output area, so a convolution is cheap in parameters and not at all cheap in compute.
Receptive fields and why 3x3 won
Stack $L$ stride-1 $3 \times 3$ layers and each output sees a $(2L+1) \times (2L+1)$ patch of the input: 5x5 after two layers, 7x7 after three. With $C$ channels in and out, three $3 \times 3$ layers cost $27C^2$ weights, while a single $7 \times 7$ layer costs $49C^2$. The stack sees the same area, has fewer parameters and puts two extra nonlinearities in between. That arithmetic is the argument behind VGG.
Equivariance, not invariance
If you shift the input, a convolution's output shifts by the same amount: it is translation equivariant. It is not invariant. Invariance comes later, from pooling or a global average at the end, which throws position away on purpose. Mixing the two words up is the most common conceptual slip about CNNs.
Convolution in one matmul
Libraries implement convolution by unrolling every patch into a column (im2col) and doing one big matrix multiply. You can do the same in six lines and check it against the library:
import torch
import torch.nn.functional as F
def conv2d(x, w, b, stride=1, pad=0):
N, C, H, W = x.shape
O, _, K, _ = w.shape
cols = F.unfold(x, K, padding=pad, stride=stride)
out = w.view(O, -1) @ cols + b.view(1, O, 1)
H2 = (H + 2 * pad - K) // stride + 1
W2 = (W + 2 * pad - K) // stride + 1
return out.view(N, O, H2, W2)
x = torch.randn(2, 3, 8, 8)
w = torch.randn(4, 3, 3, 3)
b = torch.randn(4)
print((conv2d(x, w, b, 1, 1) - F.conv2d(x, w, b, padding=1)).abs().max())
The difference should be around $10^{-6}$ in float32. unfold returns shape (N, C*K*K, L) where $L$ is the number of output positions, and w.view(O, -1) flattens each filter into a row, so the product is exactly the tied matrix above.
Common mistakes
- Off-by-one in shapes. Write the formula and compute by hand before you run the code.
- Counting only the weights. Add the bias per output channel.
- Calling pooling a requirement. Strided convolutions downsample just as well and modern networks use them.
- Believing a CNN is rotation or scale invariant. It is not. Augmentation supplies that.
Check yourself
- Write a $3 \times 3$ convolution on a $4 \times 4$ input as a matrix and say how many distinct numbers it contains.
- What is the receptive field of the output of four stacked $3 \times 3$ layers? Of a $3 \times 3$ convolution, a $2 \times 2$ pool with stride 2, then another $3 \times 3$ convolution?
- Why does the gradient for a shared weight sum over positions?
- What is the difference between equivariance and invariance, and which layer adds the second?