Machine Learning 1, companion to the lecture on feed-forward networks
A fully connected layer multiplies its input by a matrix. A convolutional layer does too. Its matrix is mostly zeros, and the rest is filled with three numbers that repeat in every row. This page starts from a free matrix, shows a test it fails, and then builds the convolution from the two constraints that make it pass.
Written as a list of numbers, a signal becomes a vector in ℝ16. The numbers are all still there, but their order no longer means anything to the math. Sample 7 sits next to sample 8 because they are neighboring places in the signal. As coordinates of a vector they are no closer than 7 and 15.
A fully connected layer works with the vector as it is. Every output is a weighted sum of all sixteen inputs, each with its own weight. If you shuffled the samples before feeding them in, and shuffled the columns of W the same way, you would get exactly the same layer. So the layer cannot make any use of the order of the samples.
Shift the signal by a few samples. It is the same bump in a different place, so whatever the layer detected before, it should now detect a few places further along, and the output should shift by the same amount.
For the fully connected layer it does not. After a single step the new output differs from the shifted old output by more than the size of the output itself. The layer treats position 4 and position 11 as unrelated, so it would have to learn the same detector once for every position.
A convolution is also a linear layer, so it also has a matrix. With the three weights w−1, w0, w+1 it is
Wjk = wk−j
Entry Wjk depends only on the difference k − j, and is zero unless that difference is −1, 0 or +1. Written out, the matrix product is the familiar sum
aj = ∑k Wjk xk = ∑d = −1+1 wd xj+d
which is the small window sliding along the signal. Moving the window along the signal and moving the band down the matrix are the same operation.
The band comes from two separate constraints on the free matrix, and they do different jobs.
| layer | constraint | parameters | shift test |
|---|---|---|---|
| fully connected | none | 256 | fails |
| local | only neighbors contribute | 48 | fails |
| convolution | only neighbors, same weights in every row | 3 | passes exactly |
Locality lets each output use only its own neighborhood. It sets 208 of the 256 weights to zero and makes the layer five times cheaper. It does not fix the shift test, because each row still has its own three weights, so a feature learned at position 4 is a separate set of parameters from the same feature at position 11.
Weight sharing makes every row use the same three weights, each row a copy of the one above moved one place to the right. It reduces 48 parameters to 3, and it is the constraint that makes the shift test pass. Locality makes the layer cheap; weight sharing gives it the symmetry.
A layer is equivariant when transforming the input transforms the output in the same way. With S the operation that shifts a signal by one sample, the last step of the figure checks
W (S x) = S (W x) for every x, that is, W S = S W
The converse also holds, and it is the more important direction. Of all linear maps on a signal of length 16, which have 256 parameters, the ones that commute with the shift form a space of dimension exactly 16, one parameter per offset, and every one of them is a convolution. So a linear layer that respects the positions in its input has to be a convolution. Locality is an extra choice on top of that: a kernel as wide as the signal is also equivariant, it is just not cheap.
This is the one-dimensional, periodic case of a general theorem. A linear map between signals is equivariant to a group of symmetries if and only if it is a convolution over that group. For translations of the plane this gives the convolutional layer of a CNN, and adding rotations gives new kinds of layers. The statement and a proof sketch are in Geometric Deep Learning, lecture 1.7.
About the picture
The signal wraps around, so sample 15 counts as the neighbor of sample 0. That is why the matrix has entries in its top-right and bottom-left corners, and why the shift test holds exactly. In practice a convolutional layer has to handle the ends of the signal, usually by padding with zeros. That is the same matrix without the corner entries, and the ends are where the symmetry breaks.
The figure shows a single layer without a nonlinearity. An activation function after the matrix changes nothing here, because it acts on each entry separately and so commutes with the shift. A stack of convolutions and activations is shift-equivariant for the same reason.
The same argument works for images. Flattened, a 32×32 image is a vector of length 1024, and a fully connected layer on it is a 1024×1024 matrix with just over a million parameters. Requiring the layer to commute with shifts in both directions leaves one weight per offset (d1, d2). Adding locality leaves a 3×3 kernel, nine numbers used at every pixel. The 1024×1024 matrix still exists, but in practice it is never built.