It Was a Matrix Multiply All Along
Last timeBuying Reach and Width More Cheaply
Write a convolution as an ordinary matrix and the constraint becomes visible: nearly every entry is zero, and the ones that are not are the same few numbers repeated.
A convolution is linear. That was noted in the first lesson and nothing since has
changed it: every operation in this course scales when the input scales and adds
when inputs add. Every linear operation from one list of numbers to another is a
matrix. So there is a matrix which, multiplied by the input laid out flat, gives
the output of a convolution, and writing it down is the most direct way to see
what the whole arrangement assumes.
- the input written as one long column, all positions in order
- a matrix with one row per output position and one column per input position
- the filter, the only numbers the matrix actually contains
- the offset of the input from the output, which is the only thing the entry depends on
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
|---|---|---|---|---|---|---|---|
| first output | 1 | -2 | 1 | 0 | 0 | 0 | 0 |
| second output | 0 | 1 | -2 | 1 | 0 | 0 | 0 |
| third output | 0 | 0 | 1 | -2 | 1 | 0 | 0 |
| fourth output | 0 | 0 | 0 | 1 | -2 | 1 | 0 |
| fifth output | 0 | 0 | 0 | 0 | 1 | -2 | 1 |
Read the picture twice. The first reading is the zeros. An entry is zero exactly
when that input position falls outside the window of that output position, so the
band of non-zeros is the locality constraint and its width is the window width.
Widening the window widens the band; spacing the taps apart puts holes inside the
band; a stride of two deletes alternate rows.
The second reading is the repetition. Follow any diagonal and the same number
appears all the way down. That is the sharing constraint. A matrix with the same
band but independent entries would be a local layer without sharing, the
intermediate case named in the second lesson, and it would have as many weights
as there are entries in the band.
- a general matrix, one weight per pair of positions
- local but unshared, one weight per entry in the band
- local and shared, the filter and nothing else, with no mention of how many positions there are
How it is actually computed
Nobody builds that matrix. It is mostly zeros, and multiplying by zeros is work
that produces nothing. What is done instead is a rearrangement in the other
direction: extract the patch under each window position and write it out as a
column, so that an input of one picture becomes a dense matrix with one column
per output position and one row per weight in a filter.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents