§9.0 Networks for grid-structured data
Convolutional networks (CNNs, LeCun 1989) are neural networks specialized for data with a known, grid-like topology: a 1-D grid of time samples, a 2-D grid of image pixels, a 3-D volume. The name says it all — they use a mathematical operation called convolution convolution A specialized linear operation, s(t)=∫x(a)w(t−a)da = (x∗w)(t); a CNN uses it in place of general matrix multiplication in ≥1 layer. Discrete 2-D: S(i,j)=Σₘₙ I(m,n)K(i−m,j−n). defined in ch. 9 — open in glossary (a special kind of linear operation) in place of general matrix multiplication in at least one of their layers. They have been enormously successful, and the best architectures are consistently built from the handful of building blocks in this chapter.
§9.1 The convolution operation
Convolution starts as a weighted average. Imagine a noisy laser sensor reporting a spaceship’s position ; to smooth it, average recent readings with a weighting that favors newer measurements. Applied at every instant, that gives . The first argument is the input, the second is the kernel kernel The (usually small, learned) array of parameters convolved with the input — the second argument of the convolution. defined in ch. 9 — open in glossary , and the output is the feature map feature map The output of a convolution — a map of where a feature (kernel response) appears across the input. defined in ch. 9 — open in glossary . On a computer, everything is discrete and multidimensional — for a 2-D image and 2-D kernel :
Term by term
| the input PATCH sitting under the kernel when its top-left corner is at output position (i,j) | the patch | |
| the small kernel of learned weights — the SAME weights reused at every position (parameter sharing) | the kernel | |
| each output cell is the dot product of the overlapped patch with the kernel. (This is the CROSS-CORRELATION form — no kernel flip — which most libraries call “convolution”) | multiply & sum |
Watch it happen — slide the kernel over the image and each output cell is the patch-times-kernel sum. Switch kernels to see different features light up:
Each output cell is the sum of the overlapped input patch times the kernel. Slide across the image and the same small kernel detects its feature everywhere — the vertical-edge kernel lights up the dark→bright boundary. Flipping the kernel is the only difference between convolution and the cross-correlation libraries actually use.
Convolution vs cross-correlation — the flip
True convolution flips the kernel: as increases, the input index increases but the kernel index decreases. This flip is what makes convolution commutative () — handy for proofs, but irrelevant in practice. So most machine-learning libraries implement cross-correlation cross-correlation Convolution WITHOUT flipping the kernel: S(i,j)=Σₘₙ I(i+m,j+n)K(m,n). Most ML libraries implement this but call it convolution — the learned kernel just comes out flipped. defined in ch. 9 — open in glossary (no flip) and simply call it convolution. It does not matter which you use: the learning algorithm just learns a kernel that is flipped relative to the other convention. Toggle “flip kernel” above — for a symmetric kernel (identity) nothing changes; for the edge kernels the output flips sign/orientation.
Finally, a useful lens: a discrete convolution discrete convolution Convolution over integer indices, s(t)=Σₐ x(a)w(t−a); implemented as a finite sum since the kernel and input are zero outside a finite set of points. defined in ch. 9 — open in glossary is just matrix multiplication by a structured matrix. For 1-D convolution that matrix is a Toeplitz matrix toeplitz matrix The structured matrix of a 1-D discrete convolution: each row equals the row above shifted by one element (2-D convolution ↔ a doubly block circulant matrix). defined in ch. 9 — open in glossary — each row equals the row above, shifted by one element; in 2-D it is a doubly block circulant matrix. The single small kernel is copied into many entries of a huge, mostly-zero (sparse) matrix — which is exactly why convolution is so much cheaper than a dense layer, as the next section shows.
Next: why convolution helps — sparse interactions, parameter sharing, and equivariance — the motivation for convolution.
Check yourself — the convolution operation
1.What makes a network 'convolutional', and what kind of data is it for?
2.In the 2-D formula S(i,j) = Σ I(i+m,j+n)K(m,n), what is each output cell?
3.In ConvLab, click different output cells with the vertical-edge kernel. Why do the cells over the dark→bright boundary have large values?
4.What is the difference between convolution and cross-correlation, and does it matter in practice?
5.In what sense is a discrete convolution a matrix multiplication, and why does that explain its efficiency?