Overlapping Max Pooling

ImageNet Classification with Deep Convolutional Neural Networks

Easy

Problem

Theory

Pooling is a downsampling operation in CNNs that reduces spatial dimensions of feature maps by summarizing local regions into single values. In AlexNet (Krizhevsky, Sutskever, and Hinton, 2012), overlapping max pooling was a deliberate architectural choice that contributed to the network's landmark top-5 error rate of 15.3% on ILSVRC-2012.

What Pooling Does

Pooling slides a fixed-size window across an input feature map and computes a single summary value per position, producing a smaller output that retains the most important information while discarding fine-grained spatial detail.

Key purposes:

• Spatial downsampling: Reduces height and width, decreasing activations for subsequent layers. In AlexNet, pooling reduces dimensions from 55x55 to 6x6.
• Translation invariance: Small spatial shifts produce similar pooled outputs, helping generalization.
• Reducing computational cost: Smaller feature maps mean fewer operations in subsequent layers.
• Controlling overfitting: Summarizing local regions acts as regularization. The AlexNet paper notes overlapping pooling made the model "slightly more difficult to overfit."

Pooling operates independently per channel, so channel count is unchanged. Only spatial dimensions (height and width) are reduced.

Max Pooling vs Average Pooling

Max Pooling

Selects the largest value from each k \times k window:

y_{i,j} = \max_{0 \leq m < k, \; 0 \leq n < k} x_{i+m, \; j+n}

During backpropagation, the gradient flows only to the position that held the maximum; all others receive zero gradient.

Average Pooling

Computes the arithmetic mean of all values within each window:

y_{i,j} = \frac{1}{k^2} \sum_{m=0}^{k-1} \sum_{n=0}^{k-1} x_{i+m, \; j+n}

Distributes gradient equally to all positions during backpropagation.

Why AlexNet Used Max Pooling

• Preserves strongest activations: After ReLU, the most informative signal is the magnitude of the strongest activation. Average pooling dilutes it by blending in weaker or zero activations.
• Better gradient flow: Gradients flow only through the max position, strengthening the most discriminative features.
• Robustness to sparse activations: After ReLU, many activations are zero. Max pooling ignores zeros; average pooling is dragged down by them.
• Empirical performance: Max pooling consistently outperformed average pooling on image classification benchmarks of that era.

Key Equations

Output Dimension Formula

For input size H_{in} \times W_{in}, kernel size k, and stride s with no padding:

H_{out} = \left\lfloor \frac{H_{in} - k}{s} \right\rfloor + 1

W_{out} = \left\lfloor \frac{W_{in} - k}{s} \right\rfloor + 1

AlexNet pooling always uses p = 0. The convolution formula includes a +2p term in the numerator; do not confuse the two.

Max Pooling Operation

For input X with C channels, the output at position (i, j) for channel c:

Y(c, i, j) = \max_{0 \leq m < k, \; 0 \leq n < k} X(c, \; i \cdot s + m, \; j \cdot s + n)

The channel index c is the same in input and output since pooling operates per channel independently.

Full Output Shape

Input (N, C, H_{in}, W_{in}) produces output:

(N, \; C, \; H_{out}, \; W_{out})

Batch size N and channel count C are unchanged. Only spatial dimensions H and W are reduced -- a key distinction from convolutional layers, which can change channel count via number of filters.

Overlapping vs Non-Overlapping Pooling

Non-Overlapping Pooling

When s = k, adjacent windows tile the input without sharing pixels. Common: k = 2, s = 2 (halves dimensions). Each input pixel contributes to exactly one output value.

Overlapping Pooling

When s < k, adjacent windows share pixels. The overlap is k - s pixels along each axis. AlexNet uses k = 3, s = 2, giving 1 pixel of overlap.

1D example with input [0, 1, 2, 3, 4], k=3, s=2:

• Window 1: positions [0, 1, 2]
• Window 2: positions [2, 3, 4]

Position 2 is shared -- this is the overlapping pixel.

Why Overlapping Pooling Helps

Shared pixels create information redundancy, acting as a mild regularizer that produces a smoother representation and makes it harder to memorize exact spatial configurations.

It also provides gentler downsampling: k=3, s=3 turns 27x27 into 9x9, while $ s=2$ yields 13x13, preserving more spatial resolution.

Paper Context and Design Decisions

What the Paper Says

Krizhevsky et al. (2012) state: "We generally observe that models with overlapping pooling find it slightly more difficult to overfit." This was significant because overfitting was a major concern for AlexNet's ~60 million parameters trained on only 1.2 million images.

Measured Error Reduction

Switching from non-overlapping (k=2, s=2) to overlapping (k=3, s=2) reduced top-1 error by 0.4% and top-5 error by 0.3%. These fractions mattered in ILSVRC where top entries were separated by less than 1%.

Where Pooling Is Applied in AlexNet

Pooling is applied selectively, not after every conv layer:

• After Conv1: Pool1 applied
• After Conv2: Pool2 applied
• After Conv3: No pooling
• After Conv4: No pooling
• After Conv5: Pool5 applied

Pooling is omitted after Conv3/Conv4 because spatial dimensions are already small (13x13); further pooling would shrink feature maps too aggressively.

Regularization Role

Overlapping pooling was one of several regularization techniques in AlexNet, alongside data augmentation (random crops, flips, PCA color augmentation) and dropout in FC layers. Each contributed a small but additive improvement.

Where Pooling Fits in the AlexNet Pipeline

Each convolutional block follows: Conv -> ReLU -> (optional LRN) -> (optional Pool). LRN is applied after Conv1 and Conv2; pooling after Conv1, Conv2, and Conv5.

Full Spatial Dimension Trace

All pooling layers use k = 3, s = 2.

Input: 224 \times 224 \times 3

Conv1: 96 filters, 11 \times 11, stride 4, no padding.

H_{out} = \left\lfloor \frac{224 - 11}{4} \right\rfloor + 1 = 54

Some implementations use 227x227 to get exactly 55x55. Following paper convention: 55 \times 55 \times 96.

Pool1: k = 3, s = 2

H_{out} = \left\lfloor \frac{55 - 3}{2} \right\rfloor + 1 = 27

After Pool1: 27 \times 27 \times 96

Conv2: 256 filters, 5 \times 5, stride 1, padding 2. Output: $ \times 27 \times 256$

Pool2: k = 3, s = 2

H_{out} = \left\lfloor \frac{27 - 3}{2} \right\rfloor + 1 = 13

After Pool2: 13 \times 13 \times 256

Conv3: 384 filters, 3 \times 3, stride 1, padding 1. Output: $ \times 13 \times 384$ (no pooling)

Conv4: 384 filters, 3 \times 3, stride 1, padding 1. Output: $ \times 13 \times 384$ (no pooling)

Conv5: 256 filters, 3 \times 3, stride 1, padding 1. Output: $ \times 13 \times 256$

Pool5: k = 3, s = 2

H_{out} = \left\lfloor \frac{13 - 3}{2} \right\rfloor + 1 = 6

After Pool5: 6 \times 6 \times 256

Flattened to 6 \times 6 \times 256 = 9216, feeding FC6 (4096) -> FC7 (4096) -> FC8 (1000 classes) with softmax.

Numerical Example

Overlapping max pooling with k = 3, s = 2 on a 5x5 single-channel feature map.

Input Feature Map (5x5)

X = \begin{bmatrix} 1 & 3 & 2 & 7 & 4 \\ 5 & 6 & 8 & 1 & 3 \\ 2 & 9 & 4 & 6 & 5 \\ 3 & 1 & 7 & 2 & 8 \\ 4 & 5 & 3 & 9 & 1 \end{bmatrix}

Output Dimensions

H_{out} = \left\lfloor \frac{5 - 3}{2} \right\rfloor + 1 = 2

Output is 2 \times 2 with 4 pooling windows.

Window Positions and Their Contents

Window (0, 0): rows 0-2, columns 0-2

W_{0,0} = \begin{bmatrix} 1 & 3 & 2 \\ 5 & 6 & 8 \\ 2 & 9 & 4 \end{bmatrix}

\max(W_{0,0}) = 9

Window (0, 1): rows 0-2, columns 2-4

W_{0,1} = \begin{bmatrix} 2 & 7 & 4 \\ 8 & 1 & 3 \\ 4 & 6 & 5 \end{bmatrix}

\max(W_{0,1}) = 8

Window (1, 0): rows 2-4, columns 0-2

W_{1,0} = \begin{bmatrix} 2 & 9 & 4 \\ 3 & 1 & 7 \\ 4 & 5 & 3 \end{bmatrix}

\max(W_{1,0}) = 9

Window (1, 1): rows 2-4, columns 2-4

W_{1,1} = \begin{bmatrix} 4 & 6 & 5 \\ 7 & 2 & 8 \\ 3 & 9 & 1 \end{bmatrix}

\max(W_{1,1}) = 9

Output Feature Map (2x2)

Y = \begin{bmatrix} 9 & 8 \\ 9 & 9 \end{bmatrix}

Identifying the Overlap Regions

• Horizontal overlap (0,0)-(0,1): Column 2 (rows 0-2), values (0,2)=2, (1,2)=8, (2,2)=4 shared.
• Vertical overlap (0,0)-(1,0): Row 2 (cols 0-2), values (2,0)=2, (2,1)=9, (2,2)=4 shared.
• Horizontal overlap (1,0)-(1,1): Column 2 (rows 2-4), values (2,2)=4, (3,2)=7, (4,2)=3 shared.
• Vertical overlap (0,1)-(1,1): Row 2 (cols 2-4), values (2,2)=4, (2,3)=6, (2,4)=5 shared.
• Corner overlap: Pixel (2,2)=4 is shared by all four windows.

With non-overlapping k = 2, s = 2, no pixel would appear in more than one window.

Pooling in Modern Architectures

Strided Convolutions Replacing Pooling

Springenberg et al. (2015) showed max pooling can be replaced by stride-2 convolutions without accuracy loss. ResNet (He et al., 2015) adopted this. The advantage: downsampling becomes learnable rather than fixed.

Global Average Pooling

Lin et al. (2014) introduced GAP as a replacement for FC layers. It computes the spatial average per channel, outputting a vector of length C from a C \times H \times W feature map. This dramatically reduces parameters and was adopted by GoogLeNet (Szegedy et al., 2015) and ResNet.

Adaptive Pooling in PyTorch

PyTorch's nn.AdaptiveMaxPool2d and nn.AdaptiveAvgPool2d let you specify desired output size rather than kernel/stride. For example, nn.AdaptiveAvgPool2d((1, 1)) implements GAP regardless of input size.

Why Pooling Is Less Common in Modern Designs

• Information loss: Max pooling permanently discards spatial info, harming tasks requiring fine-grained detail (detection, segmentation).
• Learnable alternatives: Strided convolutions achieve the same reduction while learning optimal downsampling via backpropagation.
• Architectural simplicity: Modern architectures favor uniform building blocks.
• Attention mechanisms: Transformer-based vision models use patch merging rather than pooling.

Despite these trends, GAP before the final classifier remains common, and max pooling persists in lightweight edge models.

Pitfalls

Confusing the Pooling Output Formula with the Convolution Output Formula

AlexNet pooling uses zero padding. The correct formula is:

H_{out} = \left\lfloor \frac{H_{in} - k}{s} \right\rfloor + 1

Do not add a +2p term as for convolution. This error propagates through the network, causing dimension mismatches.

Forgetting That Pooling Preserves the Channel Count

Pooling operates per channel and does not change channel count. Input 96 \times 27 \times 27 with k=3, s=2 produces 96 \times 13 \times 13. Unlike convolution, where output channels equal number of filters.

Off-by-One Errors with Overlapping Windows

The floor operation and +1 are easy to forget. Example: H_{in}=13, k=3, s=2:

H_{out} = \left\lfloor \frac{13 - 3}{2} \right\rfloor + 1 = 6

Forgetting +1 gives 5 instead of 6. Also, overlap width is $ - s$ pixels (1 pixel for $ s=2$), not 2.

Assuming Pooling Has Learnable Parameters

Max and average pooling have zero learnable parameters. When counting AlexNet's ~60M parameters, pooling contributes zero. Behavior is fixed once k and s are chosen.

Ignoring That Pooling Discards Spatial Information Permanently

Max pooling is not invertible -- the locations and values of non-max elements are permanently lost.

• For classification: Acceptable, since final prediction only needs to know what is in the image.
• For segmentation/detection: Problematic. Architectures like U-Net and FPN use skip connections to recover discarded spatial info.
• For unpooling: Requires storing max indices during forward pass, adding memory overhead.

Examples

Hints

1. Slice each window with row * stride and column * stride as its top-left corner.
2. np.max(window, axis=(1, 2)) preserves the batch and channel axes.

Requirements

• Compute the maximum value in every valid spatial window.
• Pool each batch item and channel independently.
• Do not pad the input.
• Return a new float64 NumPy array.

Constraints

• x has shape (B,H,W,C).
• kernel_size and stride are positive integers.
• kernel_size is no larger than the input height or width.
• Output sizes are H_{out}=\lfloor(H-K)/s\rfloor+1 and W_{out}=\lfloor(W-K)/s\rfloor+1.

Starter Code

import numpy as np

def max_pool2d(x: np.ndarray, kernel_size: int, stride: int) -> np.ndarray:
    """
    Returns the float64 NHWC max-pooled tensor.
    """
    pass

Test Cases