Max Pooling

Convolution leaves a feature map nearly as big as the image, and neighbouring values say much the same thing. Pooling shrinks it by summarising each small window with one number. After this lesson your program max-pools and average-pools a grid and also sends a gradient backwards through the max.

Summarise each window

Slide a kh by kw window over the grid and replace each position with a single value:

• Max pooling keeps the largest value: "was the feature detected anywhere in this window?"
• Average pooling keeps the mean: a smoothed summary.

Pooling has no weights, so there is nothing to learn. What it buys: fewer numbers for later layers, and a little translation invariance, since the maximum of a window barely changes if a feature moves one cell inside it.

Stride and output size

Unlike convolution, pooling windows usually do not overlap, so the default stride equals the window height. A 2 by 2 pool with stride 2 halves each dimension. There is no padding here, and along each axis, for size n, window k, stride s:

out = floor( (n - k) / s ) + 1

A worked trace

image:   1 3 2 1        2 by 2 windows, stride 2
         4 6 5 0
         7 2 9 8
         3 1 0 4

max:     6 5            average: (1+3+4+6)/4 = 3.50    (2+1+5+0)/4 = 2.00
         7 9                      (7+2+3+1)/4 = 3.25    (9+8+0+4)/4 = 5.25

The backward pass: the winner takes the gradient

Only the cell that held the maximum influenced the output, so only that cell receives the gradient; every other cell in the window gets 0. With upstream gradients [[1, 2], [3, 4]] for the four windows above:

window top-left  : max 6 at row 1, col 1   -> that cell gets 1
window top-right : max 5 at row 1, col 2   -> that cell gets 2
window bottom-left : max 7 at row 2, col 0 -> that cell gets 3
window bottom-right: max 9 at row 2, col 2 -> that cell gets 4

result:  0 0 0 0
         0 1 2 0
         3 0 4 0
         0 0 0 0

Two details. If windows overlap (stride smaller than the window), one cell can win several windows and its gradient is the sum of what it receives. And if two cells in a window tie for the maximum, pick one consistently: this exercise uses the first in reading order (top to bottom, left to right) and only replaces the winner on a strictly larger value.

Modern practice

Many recent architectures drop pooling layers and instead use convolutions with stride 2, which downsample with learned weights. Global average pooling over the whole map, then a linear layer, replaced the large dense layers at the end of image classifiers.

Common mistakes

• Starting the running maximum at 0. A window of all negative numbers then returns 0; start from the window's first element.
• Using stride 1 when no STRIDE was given. The default is the window height.
• Dividing average pooling by the wrong count, such as the stride.
• Overwriting instead of adding when windows overlap in the backward pass.
• Sending the gradient to every cell of the window, or to the position of the largest gradient instead of the largest input.

Your exercise

The starter reads IMG, POOL, STRIDE, an optional GRAD block, and prints the answers for MAXPOOL, AVGPOOL and BACKWARD. Implement pool_out, max_pool, avg_pool and max_pool_backward.