The Shape Guarantee

Build a network for the digit picture and you write down a list of layers in order. A convolution that sweeps eight small kernels across the picture, a pooling layer that shrinks what it found, another convolution, another pooling layer, and then dense layers that read everything at once and answer with ten numbers, one per digit. Nothing about that list mentions data. It is a description of what each step reads and what it hands upward.

Two of those steps can disagree. A convolution hands upward something with channels, rows and columns, and a dense layer reads a single row of numbers, so putting one straight above the other asks a layer to read something it has no idea how to read. In the box above, load the missing flatten preset and the seam between the two cards turns red. Load the digit chain and every seam is green.

Notice what happened in between. Nothing was trained, no picture was sent, and no array was reserved for one. The verdict on each seam is a comparison of two short tuples of whole numbers, and the digit chain holds six of those seams, so the answer for the whole network is six such comparisons.

Suppose the check happened later instead, at the moment the first block of pictures reached the offending layer. The network would already have been constructed, the weights already drawn at random, an optimiser already built around them, and the training loop already started. The failure would arrive somewhere inside a matrix multiplication, and what it could say is that one array had a certain number of columns and another had a different number, which is a true statement about arrays and says nothing about which seam of which network the writer got wrong.

Checking first costs nothing worth measuring. The digit chain above holds seven layers, which is six seams, which is six comparisons of tuples that are at most three long. No memory is reserved for a batch and no epoch begins.

Only the two ends of a chain have anything to do with the data. The first layer has to read what the pictures actually are, which for a handwritten digit is one channel of twenty-eight rows by twenty-eight columns. The last layer has to answer with what the task wants, which for ten digits is ten numbers. Everything between those two is internal, chosen by whoever wrote the network, and settled among the layers themselves.

The digit chain in the box reports that it reads (1, 28, 28) and answers (10,), and those are the only two figures a reader has to reconcile against the world. The 5408 numbers the first convolution hands upward, the 1352 the first pooling layer leaves, the 400 that arrive at the bridge, are facts about the chain and about nothing else.

Every layer carries a shape, and a shape here is a pair. One side is what one input to the layer looks like and the other is what one output looks like. Each side is written as a tuple of extents, one number per side of the arrangement, so the digit picture is (1, 28, 28) and a row of thirty-six numbers is (36,).

A dense layer is not a special case, only the case where the arrangement happens to have one side. Ten neurons reading a row of thirty-six have the shape (36,) to (10,), which is the same object as the convolution’s (1, 28, 28) to (8, 26, 26) with shorter tuples in it.

reads    (1, 28, 28)
answers  (8, 26, 26)

The alternative would be to describe each side with a single number, how many values it holds. That works perfectly for a dense layer, whose neurons hold one weight per arriving number and have no notion of a row or a column, and it destroys the only thing a convolution cares about.

Take the smallest example that shows the difference at all. Eight numbers arranged as two channels of two rows by two columns, written (2, 2, 2), and the same eight numbers laid out in a single row, written (8,). Those are different arrangements of an identical amount of data.

Ask for each of them as a shape on its own and the answer keeps both facts. The first reads (2, 2, 2) and holds 8 numbers; the second reads (8,) and holds 8 numbers. The counts are equal and the arrangements are not, which is the whole of the distinction this page is built on.

This is also the fixture that can tell a correct report from a wrong one. A chain built only out of layers that read rows cannot, because for those the arrangement and the count are written with the same number, so a report that quietly collapsed (36,) into 36 would look identical to a report that did not. Build a chain that starts by reading (2, 2, 2) and it says it reads (2, 2, 2), where a collapsed report would say (8,) and be refused by the chain’s own first layer.

An extent is a whole number of at least one, and both of the ways that can fail are refused when the shape is made. Ask for a picture of height zero and nothing is built. Ask for a negative width and nothing is built. Ask for a side with no extents at all and nothing is built.

Zero is worth dwelling on, since it looks like the harmless edge and is the dangerous one. A layer of height zero is not a degenerate layer that happens to do nothing; it is an absent layer, and its shape would agree with whatever sat above it for free, since a product with a zero in it is zero and a tuple with a zero in it matches nothing anyone meant.

Beside the arrangement, each side of a shape reports how many numbers it holds, and that figure is simply the extents multiplied together. It is a genuinely useful number, since a dense layer really does need exactly that many weights per neuron, and it is a lossy summary of the thing it was computed from.

(8, 26, 26)   holds  8 × 26 × 26  =  5408 numbers
(26, 8, 26)   holds  26 × 8 × 26  =  5408 numbers
(4, 52, 26)   holds  4 × 52 × 26  =  5408 numbers
(5408,)       holds              5408 numbers

Four different arrangements, one count. Multiplication does not care about the order of its arguments and does not remember how many of them there were, so every one of those reports 5408 and only one of them is what a particular convolution actually produced.

Between two layers there is one question. Can the upper layer read what the lower layer hands it? Everything a chain guarantees is that question asked once per seam, and the answer is an equality of two tuples.

a layer follows another when
    previous.answers  ==  this.reads

Equality of tuples compares length first and then each extent in turn, so (8, 26, 26) and (5408,) are unequal before the numbers in them are even looked at. That comparison lives on the shape rather than in whichever loop is assembling the network, because whether two layers fit together is a sentence about two shapes and about nothing else.

Now the case the whole check exists for. Sweep eight kernels of three by three across the digit picture and the answer is (8, 26, 26). Put a dense layer straight above it and write down how many numbers it reads, which anybody working it out by hand computes as eight times twenty-six times twenty-six, and the dense layer reads (5408,).

Both sides hold 5408 numbers. A check comparing counts passes it. Nothing crashes, the network trains, and it trains on a picture whose rows have been run end to end into one long strip, which throws away exactly the neighbourhood structure the convolution beneath it existed to exploit. The result is a model that works, converges, and is worse than it should be, for a reason nothing anywhere reported.

The seam is refused, and the refusal says so in as many words.

layer 0 answers with (8, 26, 26) and layer 1 reads (5408,);
both hold 5408 numbers, so it is the arrangement that
disagrees and not the width

The (5408,) reading is not the only thing that slips past a count comparison. Two of the three extents swapped, so the rows become the channels, gives (26, 8, 26). One extent halved and another doubled gives (4, 52, 26). Both hold 5408 numbers, both are refused, and neither is the harmless relabelling that a flat row at least is.

Read down the count column and the four numbers are the same. Read down the verdict column and one of those four is different. That is the gap a count comparison cannot see into, and three of the four things inside it are arrangement errors of the kind that produce a model reading the picture sideways.

State a width the counts do not even agree on and the same seam is refused with less to say. A dense layer told it reads (784,), which is the count of the picture that went in rather than the count of what came out, is placed above the same convolution and is refused with the sentence stopping after the two arrangements.

layer 0 answers with (8, 26, 26) and layer 1 reads (784,)

There is nothing surprising left to explain in that case. A reader looking at 5408 on one side and 784 on the other already knows the two do not match, and a clause telling them the arrangement is at fault would be noise.

An earlier version of that message reported the two element counts rather than the two arrangements, and on the case this whole check exists to catch it printed that layer 0 answered with 5408 numbers and layer 1 read 5408. That is a refusal whose own text says the two sides agree.

A reader meeting that message goes looking for a fault in the checking rather than for the missing layer in their own network, which is the opposite of what an early refusal is for. The message now names both arrangements, and adds the clause about the counts only when they really do agree.

There is one place where a picture and a row genuinely are interchangeable, and the tempting repair is to weaken the seam check until it lets that one place through. That would mean comparing counts, and Part 3 is what comparing counts costs.

So the extents keep having to match exactly, and the one legitimate conversion is written down as a layer of its own. A flattening layer reads (8, 26, 26) and answers (5408,), and it carries that conversion inside its own shape, so both of its seams are settled by the same exact equality as every other seam in the chain.

conv     (1, 28, 28)  →  (8, 26, 26)
flatten  (8, 26, 26)  →  (5408,)
dense    (5408,)      →  (10,)

Three layers, two seams, both green. The bridge is something a network states it has rather than a hole in the rule that would have caught its absence, and that is the entire design decision.

The full digit chain is two convolutions each followed by a pooling layer, then the bridge, then two dense layers. Watch the count of numbers along it and the shape of the whole design becomes visible in one column.

…

The picture arrives holding 784 numbers, and the first convolution takes it to 5408, since eight kernels each produce a whole picture of their own and the sides shrink by only two. The first pooling layer takes it back to 1352, the second convolution raises it to 1936, the second pooling layer brings it to 400, and the bridge leaves it at 400. Then the dense layers cut it to 32 and to 10.

The bridge is the only row in that table where the two counts are equal, and that is not a coincidence about this particular chain. Flattening is a relabelling of the numbers it was handed, so it cannot change how many there are.

Now delete the bridge from that chain and leave everything else where it was. The second pooling layer answers (16, 5, 5), the dense layer above it is written to read the 400 numbers that arrive, and the seam between them is refused.

layer 3 answers with (16, 5, 5) and layer 4 reads (400,);
both hold 400 numbers, so it is the arrangement that
disagrees and not the width

The dense layer itself was built without complaint, because 400 weights per neuron is a perfectly ordinary layer and nothing about it is wrong in isolation. Every seam above it holds too, since the dense layers agree with each other. One seam out of five is red, and the chain does not exist.

Hand a flattening layer a row instead of a picture and it reads (36,) and answers (36,). It is the identity, it moves nothing, and it is still worth having, because it states a join that a reader would otherwise be carrying in their head.

A chain of a bridge over a row followed by a dense layer holds, with the seam green and the chain reporting that it reads (36,). Nothing objects to the redundancy and nothing needs to.

When a network learns, blame travels down the chain in the opposite direction, and the bridge has to send it back to where it came from. That step is the forward reshape read backwards and nothing more, since the number at position k of the row is the number that was at position k of the picture, so the slope of the loss at one of them is the slope at the other.

What has to hold is that the two reshapes agree about which position is which, which is why both use the same ordering, with the last extent varying fastest. Choose differently in one of the two directions and the layer would still run, the shapes would still all agree, and the blame would arrive at the wrong pixels.

position = c × (h × w) + i × w + j

channel 1, row 0, column 1 of (2, 2, 2)
position = 1 × (2 × 2) + 0 × 2 + 1 = 5

The bridge also has no parameters, so it produces no gradient at all rather than a gradient full of zeros. A block of zeros would be a small false claim about having something to learn, and the honest answer is that there is nothing here for a step to move.

Every extent a convolution or a pooling layer answers with comes from one counting argument. Lay a window of width k along a side of width n and slide it s at a time. The first position is at the left edge, and after that there is one more position for every whole stride that fits in what is left over.

positions  =  (n − k) // s  +  1

Set the window and the stride below and count the green bars. Each one is one place the window can start, and the number of them is the extent the layer answers with along that side.

A three-wide window along an eight-wide side, one step at a time, starts at six different places, so a convolution reading (1, 8, 8) answers with sides of six. A window of one starts everywhere and leaves the side at eight; a window of eight starts in exactly one place and leaves the side at one.

Padding adds p rows and columns of zeros at each edge before any of this happens, so the side the window walks along is wider by 2p. That is the whole of its effect on the arithmetic, and it enters the same sum.

positions  =  (n − k + 2p) // s  +  1

Read the second and sixth rows together. A window of three with one row of padding and a window of five with two both leave the side at eight, which is the pairing worth remembering, since a window of width 2m + 1 with m of padding always does.

output side = floor((8 + 2 × 0 − 3) / 2) + 1
            = floor(5/2) + 1
            = 2 + 1 = 3
output values = 4 channels × 3 × 3 = 36

convolution, window 3, stride 1    (28 − 3) // 1 + 1 = 26
pooling, window 2, stride 2        (26 − 2) // 2 + 1 = 13
convolution, window 3, stride 1    (13 − 3) // 1 + 1 = 11
pooling, window 2, stride 2        (11 − 2) // 2 + 1 = 5      remainder 1

numbers arriving    16 × 11 × 11 = 1936
numbers covered     16 × 10 × 10 = 1600
never read          1936 − 1600  = 336

Push the window wider than what it reads and the sum would go to zero or below, and a layer of extent zero is not a layer. Both kinds refuse it, and the two refusals are phrased differently because the two layers reach the failure differently.

The convolution spells out its arithmetic because padding and stride are both in it and a reader needs to see which of the four terms they got wrong. The pooling layer has no padding, so the sentence can name the two numbers and stop.

The other two rules need no arithmetic worth the name. A flattening layer answers with the product of the extents it reads, all of them in a single side, which is why it changes no number and only changes their arrangement. A dense layer answers with its neuron count whatever it read, since each neuron contributes exactly one number.

flatten  (c, h, w)  →  (c × h × w,)
dense    (n,)       →  (neurons,)

Those two are where the count and the arrangement come back together. A dense layer really does only need the count of what arrives, and the bridge is what turns an arrangement into that count legitimately.

Look back at what those rules need. The window, the stride and the padding were chosen by whoever wrote the network. The neuron count was chosen the same way. The incoming extents come from the layer beneath by the same argument, and that recursion bottoms out at the picture the network was told it would read.

So every extent in the chain is a function of choices already made, and there is no term anywhere in it that a batch of data could supply. That is why the whole thing is decidable at construction rather than merely convenient to check there.

Suppose the seam comparison were offered as a function a caller runs. It would answer correctly every time it was asked, and a caller could assemble a network out of layers that do not chain, never ask it once, and find out hours later inside a matrix multiplication.

The comparison would be correct on every occasion it was made, and it has no way of making itself happen. A guard a caller has to remember protects the callers who remember it, and the mistake this page is about is made by somebody writing down seven layers who has no reason to think anything is wrong with them.

So the chain is the object. It takes the layers in order and walks up them, and it will not come into existence unless every seam holds. There is no way to be holding a badly joined chain, because the constructor either hands one back or raises.

That is what makes every later pass cheap. A forward pass through the chain re-establishes nothing, since the interior seams were settled when it was built, and the only width anything checks is the first layer’s, which that layer checks for itself against the block it was handed.

A chain also reports its own two ends, and that report has to be in the same vocabulary its layers use. The digit chain says it reads (1, 28, 28) and answers (10,).

It said something else once. An earlier version built its own report out of the counts rather than the arrangements, so a chain beginning with a convolution over (1, 28, 28) cheerfully reported that it read (784,). Every seam inside it was still checked correctly, since the seam comparison never consulted the collapsed figure, and only the chain’s description of itself was wrong.

That is the quiet half of it. A caller sizing a block of input from what the chain said it read would build a row of 784 numbers and be refused by the chain’s own first layer, which is a confusing place to be. Every test that existed was built out of dense layers, where the arrangement and the count are the same number and so cannot be told apart, which is precisely why nothing caught it.

One thing is left open and is documented rather than defended. Two different pooling layers can carry the identical shape. A window of three at stride one over (1, 4, 4) answers (1, 2, 2), and so does a window of two at stride two, and the two reach that answer by covering different positions.

On the way back down, either of them would accept the other’s slopes without complaint, since all a layer can check is that the block it was handed matches its own shape, and blame would be routed to positions that never won a window. Closing that would need a response carrying which layer produced it.

No chain can reach the case, because a chain pairs each layer with its own response by construction, so this is a hole in what a layer can verify on its own rather than a hole in the guarantee. It is written down in the implementation instead of being guarded against.

A complete implementation has to state how a side of a shape is written and what an extent may be, whether a seam is settled by arrangement or by count, how the output extents of a windowed layer are computed and what happens to the remainder, whether padding is available and where in the sum it enters, which ordering a flattening layer uses and whether the backward direction uses the same one, whether a flattening layer produces a gradient or nothing, what a chain reports as its own two ends, whether a chain of one layer is allowed, whether an empty chain is allowed, and what a step does to a layer that appears at more than one position.

The last two on that list are where this implementation is known to be weak, and the next two steps show each of them happening rather than describing them.

Weight tying is putting the same layer object at two places in one chain, so that whatever one of them learns the other learns as well. It is how a pair of towers is made to read two inputs the same way, and it is written by simply passing the same object twice.

This chain accepts that, runs forward through it, scores it and walks the blame back down without a word. Then a step rebuilds every position from that position’s own gradient, and the two positions come back as two different layers.

One object went in and two came out. On the small square layer above, one step at a rate of 0.1 leaves the two positions 1.54375 apart at their furthest, and a rate a hundred times smaller leaves them 0.0154375 apart, so shrinking the step narrows the gap in proportion and never closes it. Nothing anywhere raised, and a network written this way would train perfectly happily while quietly not doing the thing it was written to do.

Nothing here does this today, and it is recorded rather than repaired because the repair is a real piece of design. Gradients would have to be grouped by which set of parameters they describe rather than by which position they came from, and that is a change to what a step is, not a patch to how one is applied.

Every block a layer reads goes through the same boundary. It is turned into floating point and scanned for values that are not finite, and those two things are all that happens to it. For measurements that is exactly right, since a height and a weight are quantities and being off in the last bit is meaningless.

For anything meant as a position it is wrong twice over. A value of 2.9999999999999996 goes through as itself and would be truncated to 2 by anything using it as a position, and a value of −1 goes through as itself and would wrap around to the last row of whatever table it indexed. Neither is checked, because the two checks a position wants are that it is whole and that it is in range, and neither of those is the check being made.

…

The third failure is the one that cannot be argued away. Ask for five distinct whole numbers including 9007199254740992 and the number one above it, and four distinct values come back, because floating point stops being able to tell consecutive whole numbers apart at that size. The finiteness scan passes every one of them.

Each row below was asked rather than reasoned about, and reports what came back, whether that was a refusal, an acceptance, or something documented and left alone.

Two of those twelve rows are the ones to carry away. Eight of the twelve are refusals, and two are ordinary acceptances, a chain of one layer and a bridge over a row, which do exactly what was asked. The last two are accepted and then do something the caller did not ask for. A step unties tied weights and a layer cannot be handed a position, and in both cases the implementation says so instead of pretending otherwise or quietly substituting something plausible.