Pooling

A convolution reads a picture and answers with a map nearly as large as the picture it read, one map per detector. Most of what those maps hold says the same thing twice. A detector that responds to a short vertical edge responds again when the window slides one cell along, since almost the same cells are under it, so a single edge in the picture shows up as a small bright patch in the map rather than as one bright cell.

Carrying every position of that patch forward means carrying the same finding several times.

The layers above pay for it twice over. They have more numbers to read, and they have to learn that a finding two cells to the left means what the same finding here means, which is a fact about geometry that they are being asked to work out from examples. A layer that summarised each small neighbourhood would spare them both.

Look at the two grids in the box at the top of the page. The left one is a patch of a feature map, four numbers by four, and the right one is what came back after the patch went through a pooling layer. A window two cells wide sat over the top left corner, the four numbers under it became one, the window moved two cells across and did it again, and four windows gave four answers. Nothing was multiplied and nothing was learned.

What is thrown away is the point of the exercise. The answer for a window says something was found in this neighbourhood and deliberately does not say where inside it, which is the complex cell’s property written as arithmetic. Press the vertical stroke button and then nudge right once. The picture has moved a whole column and the pooled map has not changed by a single number, because the stroke stayed inside the same windows.

Nudge again and the bright column of the pooled map moves one cell along, because this time the stroke crossed a boundary.

A bank of eight detectors over a picture answers with eight maps, and pooling leaves that eight alone. Each map is pooled by itself and the answers are never combined across maps, because two detectors are two different questions and the largest response of one says nothing whatever about the other. So an arrangement of eight maps of twenty-six by twenty-six comes out as eight maps of thirteen by thirteen, and the leading eight is carried through untouched.

(8, 26, 26)   →   (8, 13, 13)

This is why the arrangement has to be written as extents per side rather than as one count. Five thousand four hundred and eight numbers arranged as eight maps of twenty-six by twenty-six is a thing a pooling layer can read, and the same five thousand four hundred and eight numbers laid out in a single row is not, and a shape that only counted would call those two the same.

The first summary keeps the largest number under the window and discards the other three. On the running patch, with a window of two at a stride of two, the top left window holds 1, 5, 4 and 2, so the answer is 5. The other three windows hold 1, 3, 4, 0 and 0, 1, 2, 1 and 3, 1, 7, 5.

max      [[5, 4],
          [2, 7]]

Reading that map as a report, it says the strongest response in this neighbourhood was 5, and it says nothing about how many cells were nearly as strong. Section 6 has two windows in it that make the omission plain, one holding a single 8 among three zeros and one holding four 2s, and a maximum answers 8 and 2, which is the difference between them stated as loudly as it can be.

The second summary keeps the mean. The same four windows of the patch sum to 12, 8, 4 and 16, and each holds four cells.

12 / 4 = 3,   8 / 4 = 2,   4 / 4 = 1,   16 / 4 = 4

average  [[3, 2],
          [1, 4]]

Now go back to the two windows of the previous section and the reading reverses. The one holding a single 8 and the one holding four 2s both average 2, so a mean cannot tell them apart at all where a maximum could. In exchange, a mean is pulled down by the quiet cells around a strong one, which a maximum ignores. Which of those two behaviours is wanted is a question about the data rather than about the layer, and the layer itself has no opinion.

The two kinds differ by one function, and one window is enough to see the whole of it. The grid on the left below is a window and the two on the right are what each kind owes each position in it, which is the derivative of the answer with respect to that position. The next part is about why those grids matter; they are here because they are what the two layers actually differ by.

A dense layer forms a weighted sum and then applies an activation function, and a convolution multiplies a kernel at every position. This layer does neither. There is no weight anywhere in it, so there is nothing for a training step to move and nothing for a saved model to store, and asking such a layer to take a step gives back the same layer object it was asked of.

Pooling applies its summary directly, without a separate activation stage. Max pooling is itself a nonlinear operation; average pooling is linear. This library therefore stores the same result as both the layer’s score and output. Neither pooling method has parameter gradients, since neither has trainable parameters. Both still calculate input gradients so earlier layers can learn.

A pooling layer is three settings and no more. How wide the square window is, how far it moves between positions, and which summary it keeps. The window starts at the top left corner, the summary is taken, the window moves across by the stride, and at the end of a row it drops down by the stride and starts again from the left.

Every one of those is a choice made when the layer is built, and none of them depends on what the numbers turn out to be. So how many positions the window can take along a side, and therefore what arrangement the layer answers with, is decided at that same moment.

Along one side, the first window occupies positions zero up to the window width, and each later one starts a stride further on. The last window that fits is the last one whose far edge has not passed the end of the side, so the count is how many whole strides fit in what is left after the first window, plus the first window itself.

pooled extent = ⌊(extent − window) / stride⌋ + 1

For an eight by eight patch under a window of two at a stride of two that gives four on each side, so sixty-four numbers become sixteen. At a stride of one it gives seven, so sixty-four numbers become forty-nine, and the windows overlap. A window of one at a stride of one gives eight, which is the picture back again.

When the stride divides the side evenly and equals the window, every cell belongs to exactly one window and nothing is left over. Change either and that stops being true. Under a window of two at a stride of three over an eight by eight patch the windows sit at columns zero, three and six, so columns two and five are covered by nothing at all, and twenty-eight of the sixty-four cells lie in no window. The layer never reads them, the answers do not depend on them, and no correction ever reaches them.

Choose the rows in the table and watch the grid beside it. At a window of two and a stride of two nothing is pale. At a window of three and a stride of three the last two rows and the last two columns are, twenty-eight cells again by a different route. At a window of one and a stride of two, which throws away three cells in four without looking at them, forty-eight are pale.

There is no padding here, so the far edge is simply dropped rather than extended with zeros, and a five by five patch under a window of two at a stride of two comes out two by two with its fifth row and fifth column ignored.

A stride smaller than the window makes consecutive windows share cells, which is legal and is what the 2012 ImageNet network chose. A stride larger than the window makes consecutive windows skip cells, which is also legal and is almost never wanted. Both are accepted here, and the second produces the gaps of the previous section at their worst. A window of two at a stride of three over a four by four patch answers with a single number and leaves fifteen of the sixteen cells outside every window.

The count of numbers a layer answers with is the product of the extents it answers with, and for a pooling layer the channel count is a factor that never changes. Take the arrangement the convolution page ends on, eight filters of three by three over a twenty-eight by twenty-eight picture, which answers with eight maps of twenty-six by twenty-six.

A quarter is the usual figure because a window of two at a stride of two halves each spatial side, and halving two sides quarters their product. Repeat it and the effect compounds, so three such layers leave a sixty-fourth of the spatial extent, which is how a network gets from a picture to a few hundred numbers a dense layer can read.

On the way back, the layer above hands this layer one number per answer, saying how much the loss would move if that answer moved. The pooling layer’s whole job is to convert that into one number per input cell, saying how much the loss would move if that cell moved, and it does so by the chain rule and nothing else. A cell’s share of an answer, times the slope arriving at that answer.

blame on cell i  =  arriving slope  ×  ∂answer / ∂cell i

Turn the overlay on in the box at the top of the page, with max chosen. A slope of one is being sent to each of the four answers, which makes the arithmetic easy to read, since the blame on a cell is then just its share.

A maximum is a selection rather than a calculation. Over the range where the winning cell keeps winning, the answer simply is that cell, so moving the winner by a little moves the answer by exactly as much, and moving any other cell in the window by a little does not move the answer at all.

y = max(x₁, …, xₙ)

∂y/∂xᵢ = 1 if i won the window, and 0 otherwise

So the whole arriving slope goes to one cell and the rest of the window receives nothing. In the top left window the answer 5 was 5 because of the cell holding 5, and the cells holding 1, 4 and 2 could each have been anything smaller without changing the answer, so a correction reaching them would be a correction for something they did not cause.

An average has no such asymmetry. Every cell enters the answer with the same coefficient, one over the number of cells, so every cell is responsible for that much of it.

y = (x₁ + … + xₙ) / n

∂y/∂xᵢ = 1 / n  for every i

A two by two window therefore hands each of its four cells a quarter of whatever arrives, at every step, whatever the cell holds. Nothing is ever starved, which is what makes an average the gentler of the two on a deep stack, and the cost is that a cell which contributed almost nothing to the answer is corrected as much as the cell that carried it.

On the four by four patch under a window of two at a stride of two, with a slope of one arriving at each of the four answers, the counting is finished in a sentence. A maximum gives 1 to each of four cells and 0 to the other twelve. An average gives 0.25 to every one of the sixteen. The overlay in the box prints both, and the emerald rings mark the cells that receive anything.

Twelve of the sixteen cells beneath a maximum receive nothing on this step, so whatever layer sits below learns through four cells only. On the next step a different four may win, since the numbers will have moved, and that is the argument that the starvation is temporary rather than structural. It is an argument about the data and not a guarantee, and a region that is uniformly quiet can sit unwinning for a long time.

Both grids of shares in section 6 added up to one, and that is a property of the family rather than a coincidence of those two members. Each answer here is a weighted mean of its window with weights adding to one, a maximum putting all the weight on one cell and an average spreading it evenly, and the shares are those same weights.

Σᵢ ∂y/∂xᵢ = 1

A layer whose shares came to something other than one would be scaling every gradient that passed through it, quietly, by a factor nobody chose. Shares adding to 1.5 would inflate the correction reaching every layer below by half as much again at every pooling layer in the stack, which compounds. So the sum is worth checking rather than assuming, and it is checked for both kinds at a range of window sides.

In float64 the claim is true to within rounding and not exactly. An average over a window of seven hands out forty-nine shares of one forty-ninth, that reciprocal has no exact representation, and the forty-nine of them add up to 0.9999999999999999. Sides 2 and 4 and 8 are exact because their reciprocals are, and the rest are a matter of which way the rounding went.

Sixteen of the first thirty-two sides miss, which is half of them, and the furthest away is side 31, at 1.0000000000000004, which is 4.4e-16 above one. That is far below the rounding already present in any gradient reaching the layer, so the practical answer is that this does not matter. The reason it is worth a section is that a test asserting the sum is exactly one passes at side 2 and fails at side 7, and a test written only against a window of two would never find out.

A maximum, whose shares are a single 1 and some zeros, is exact at every side.

Slide the stride down to one in the box at the top of the page, keeping the window at two, and the four windows become nine. The cell in the middle of the patch now belongs to four of them, an edge cell to two, and a corner cell to one. That cell affects four different answers, so four different arriving slopes reach it, and what it is owed is the sum of the four.

blame on cell i  =  Σ over the windows holding i of   arriving slope × ∂answer / ∂cell i

So the backward pass adds into the block it is building rather than writing into it. Writing instead of adding keeps only whichever window was visited last, which produces a gradient of exactly the right arrangement, full of plausible finite numbers, on a layer that carries on training. Nothing about the shapes would catch it and no answer would look wrong.

Since the shares inside a window add up to one, whatever arrives at a window is handed down in full. Sum over the windows and the total blame handed down equals the total slope that arrived, whatever the stride and whichever kind.

It is tempting to say that overlapping windows send more blame down, and that is only true in the sense that there are more windows sending it. Ask the same question with the totals matched and the answer is that overlap changes nothing about the amount.

What does change is where the total lands. At a stride of two on the patch, no cell can receive more than one under a maximum, since each cell belongs to a single window and can win it at most once. At a stride of one the cell holding 4 in the second row wins three of the nine windows and receives 3, and under an average an interior cell belongs to four windows and receives four quarters, which is exactly 1.

Under a maximum the effect is uneven in a way worth knowing about. A cell that is large relative to a whole neighbourhood wins every window that contains it, so it collects the blame from all of them, and its neighbours collect none. Under an average the same overlap is smooth, and the interior of the patch is corrected four times as much as the corners simply because it takes part in four times as many windows.

When two cells in a window hold the same largest value the derivative does not exist, and that is a fact about the function rather than a gap in the implementation. The maximum of two crossing lines has a corner at the crossing, and the slope approaching from one side gives the whole of it to the first cell while the slope approaching from the other gives it to the second. There is no single right answer to compute, so an implementation chooses one.

This one chooses the first cell in row-major order, the top row before the bottom and the left before the right. Load the flat patch in the box at the top, where every window is a four-way tie, and each window sends its whole slope to its own top left cell, four of the sixteen in total.

The alternative, splitting the slope evenly among the tied cells, is a perfectly legitimate reading of the corner and is what a symmetric argument suggests. It is not what established implementations do, and on data where exact ties in float64 are essentially confined to constant regions there is nothing to choose between them.

The forward pass knows which cell won each window, and could hand a record of that to the backward pass. This implementation does not. What the forward pass hands on already includes the block it read, and the winner is a function of those frozen numbers, so the backward pass asks the same question of the same numbers with the same tie rule and cannot arrive at a different answer.

The cost is a second scan of every window, and it is real rather than negligible, since the backward pass does the same scan the forward pass did plus an accumulation on top. Recording the winners on the way up would move that work rather than remove it, and it would widen the type every layer shares for the benefit of this one.

A dropout layer reaches the opposite conclusion about the same question, and the two are worth reading together. Its mask was drawn at random, so it cannot be recomputed at all and has to be carried. Recovering it later from which outputs are zero fails quietly on any input that was genuinely zero and genuinely kept, which the dropout page measures.

The property the whole layer is for can be measured rather than described. Take an eight by eight patch lit along its third column and dark elsewhere, pool it at a window of two and a stride of two, then move the whole picture one column to the right and pool it again.

That is the complex cell’s property in four numbers. The layer beneath saw a large change and the layer above saw none, and the layers above that never have to learn that the two pictures were the same digit.

Four things are easy to read into the previous section that are not there. The layer is not invariant to shift in general, only to shift that stays inside a window, and the measurement above shows exactly where the second column crosses the line. It is not invariant to rotation or to scale, which nothing in a window summary addresses.

Stacking several such layers widens the window in the original picture rather than removing the boundary, so the same knife edge is there at a coarser spacing. And a network can be tolerant to shift without this layer at all, by learning from examples at many positions, which is more expensive and is what the argument for replacing the layer with a strided convolution turns on.

A pooling layer looks like the simplest thing in a network and has a surprising number of decisions in it, most of which are invisible until two implementations disagree. A complete one states the arrangement it reads, the window and the stride and whether they may differ per axis, whether any padding is applied and with what value, which summary it keeps, how a tie in a maximum breaks, whether the leftover margin at the far edge is dropped or covered by a partial window, whether the backward pass accumulates over overlapping windows, what it reports when asked for a gradient it does not have, and what it does when asked to take a training step.

Below is every edge asked of a pooling layer as this page loads, with what came back rather than what ought to. Thirteen of the sixteen are refused and every refusal names itself in words that say what was wrong, including the two that a bare Python failure would otherwise escape through, giving a whole number where three extents are wanted and giving a flag where a whole number is wanted.

Three are accepted, and each of the three is a decision rather than an oversight. A stride larger than the window is legal, and a window of two at a stride of three over a four by four patch answers with a single number and leaves fifteen of the sixteen cells outside every window, which is section 11 as a refusal that never comes.

A window of one at a stride of one is the identity, answering with the arrangement it read and handing every one of the sixteen cells exactly 1. And a step asked of a layer with nothing to learn gives back the same layer object.

Two things a reader might expect are missing from that table, and both are missing for the same reason. There is no unfitted state to guard against and no feature names to match, because a pooling layer learns nothing and reads positions rather than named columns. Its whole contract is the arrangement, so every refusal it has is about an arrangement or about a number that cannot be a window.

One case is neither refused nor right, and the block at the bottom of the widget above is it. The backward pass checks that the response it was handed came from a layer of this shape and that the arriving block has this layer’s own arrangement, which catches every mistake about extents. It cannot catch a mistake between two layers whose extents agree.

Closing it would mean every response carrying a record of which layer produced it, which is a field on the type every layer shares, added for a case that a network assembled as a stack cannot reach, since a stack pairs layer k with response k by construction. The exposure is to a caller pairing the two by hand, which is what a step-by-step walk through a single layer does. So it is written down rather than defended, and this section is where it is written down.