--- title: Pooling source: 'https://academia.sh/en/courses/deep-learning/pooling' course: 'Deep Learning' language: en updated: '2026-10-21T05:03:23+00:00' license: 'CC BY-SA 4.0' objectives: - 'Defines max and average pooling and computes the number of discarded cells from the window size' - 'Measures the information pooling makes unrecoverable by the number of recoverable cells and the remaining uncertainty' - 'Counts what pooling adds to shift invariance and to the held-out number, together with two runs' --- # Pooling Counting what pooling discards and what it gives in return: 2x2 max pooling reduces 144 cells to 36, 96.9 cells can be recovered on average and an uncertainty of 46.0 bits remains. When the raw grid is pooled the line information is lost entirely and agreement falls from 0.9380 to 0.4220; when the same pooling is applied to the feature map, shift invariance rises from 0.0% to 38.1%, and to 88.7% with global pooling. With a baseline of 0.5850, the network without pooling gives 0.5150 and 0.5350 with 309 parameters, the 2x2 pooled network gives 0.6100 and 0.6150 with 93 parameters, and the globally pooled network gives 0.8050 and 0.8050 with 23 parameters; the number of decisions that change on the shifted test set is 84, 49 and 12 respectively. The convolutional network of the previous lesson produced a response at 144 positions in its first layer and used only the largest of them. The remaining 143 numbers were discarded; the network no longer knew **where** the line was, only **whether** there was one. This is the most extreme form of discarding. The name of this discarding operation is **pooling**, and it is not limited to the extreme form: the window size is a hyperparameter and can take every value from 1 up to the whole grid. The measure of this lesson has two sides — what pooling discards in a way that cannot be recovered, and what it gives in return. - **AR10. The set, the split and the baseline do not change.** The fictional coverage grid of the previous lesson is generated with the same seed: 12x12 cells, 9% activity, a line of three adjacent cells as the label. The split is 200/100/200, and the most frequent class on the test set is **0.5850**. - **AR11. Max pooling** reduces each of the $p \times p$ disjoint windows to the largest value in that window. **Average pooling** reduces the same window to its mean. Neither carries a parameter to be learned. - **AR12. Pooling is a reduction whose stride equals the window size**; the output side is $12/p$. When the window size reaches 12 a single number remains; this extreme case is called **global pooling**. - **AR13. Recoverability is counted.** In a binary grid, max pooling determines all the cells of a window that gives zero and none of the cells of a window that gives one. The remaining uncertainty is the binary logarithm of the number of original grids that could give the same pooled output. - **AR14. Where pooling is applied matters.** Pooling applied to the raw grid and pooling applied to the output of a convolution — the **feature map** — are the same operation with different results. - **AR15. Shift invariance** is the fraction of examples whose representation is preserved exactly when the grid is shifted by one cell. Grids whose map is entirely zero are left out of this measure, because shifting changes nothing in them anyway. - **AR16. The shift is one cell down**; a row of zeros is added at the top and the bottom row falls off. In grids where the line is on the bottom edge, information is genuinely lost; this is part of the measure. - **AR17. No library is called;** pooling, convolution and the training loop are written inside the lesson and are **a model**. - **AR18. Every network is run twice;** in the second run only the initial values change. ## What Pooling Discards ```python # pooling.py — MODEL: the FICTIONAL coverage grid of 01 is generated with the same seed. import math SEED, M32, SIDE = 20260218, 0xFFFFFFFF, 12 DENSITY, TRACE_RATE, RUN_LENGTH = 0.09, 0.42, 3 def rng(t): x = ((t ^ (t >> 16)) * 2246822507) & M32 x = ((x ^ (x >> 13)) * 3266489909) & M32 s = [(x ^ (x >> 16)) & M32] def next_value(): s[0] = (s[0] * 1664525 + 1013904223) & M32 return s[0] / 4294967296 return next_value def grid(subscriber_id): r = rng(SEED + 300000 + subscriber_id) g = [[1 if r() < DENSITY else 0 for _ in range(SIDE)] for _ in range(SIDE)] trace = 1 if r() < TRACE_RATE else 0 if trace: horizontal, a, b = r() < 0.5, int(r() * SIDE), int(r() * (SIDE - RUN_LENGTH + 1)) for k in range(RUN_LENGTH): if horizontal: g[a][b + k] = 1 else: g[b + k][a] = 1 return g, trace def shuffle(n, seed): r, s = rng(seed), list(range(n)) for i in range(n - 1, 0, -1): j = int(r() * (i + 1)) s[i], s[j] = s[j], s[i] return s RAW = [grid(i) for i in range(500)] DATA = [RAW[i] for i in shuffle(500, SEED + 90000)] TRAIN, TEST = DATA[:200], DATA[300:] BASELINE = max(sum(y for _, y in TEST), len(TEST) - sum(y for _, y in TEST)) / len(TEST) def pool(m, p, average=False): n = len(m) // p return [[(sum(m[i * p + a][j * p + b] for a in range(p) for b in range(p)) / (p * p) if average else max(m[i * p + a][j * p + b] for a in range(p) for b in range(p))) for j in range(n)] for i in range(n)] def has_line(m, k): n = len(m) for i in range(n): for j in range(n - k + 1): if all(m[i][j + t] > 0 for t in range(k)) or \ all(m[j + t][i] > 0 for t in range(k)): return True return False print(f"{'window':>8}{'output':>8}{'cells':>7}{'discarded':>10}" f"{'recovered':>14}{'possible grids (log2)':>23}") for p in (1, 2, 3, 4): n = SIDE // p known, uncertain = 0, 0 for g, y in DATA: s = sum(sum(r) for r in pool(g, p)) known += (n * n - s) * p * p + (s * p * p if p == 1 else 0) uncertain += s known, uncertain = known / len(DATA), uncertain / len(DATA) print(f"{f'{p}x{p}':>8}{f'{n}x{n}':>8}{n * n:>7}{SIDE * SIDE - n * n:>10}" f"{known:>13.1f} {uncertain * math.log2(2 ** (p * p) - 1):>22.1f}") print(f"\n{'pooling':>10}{'line sought':>12}{'agreement with label':>22}") for p, k in ((1, 3), (2, 2), (3, 2)): agree = sum(1 for g, y in DATA if has_line(pool(g, p), k) == (y == 1)) print(f"{('none' if p == 1 else f'{p}x{p}'):>10}{k:>12}{agree / len(DATA):>22.4f}") print(f"baseline (most frequent class on the test set) {BASELINE:.4f}") actual = sum(sum(sum(r) for r in g) for g, _ in DATA) / len(DATA) largest = sum(sum(sum(r) for r in pool(g, 2)) for g, _ in DATA) / len(DATA) mean = sum(sum(sum(r) for r in pool(g, 2, True)) * 4 for g, _ in DATA) / len(DATA) print(f"active cell count {actual:.2f}; lower bound read from 2x2 max pooling " f"{largest:.2f}, read from average pooling {mean:.2f}") ``` ``` window output cells discarded recovered possible grids (log2) 1x1 12x12 144 0 144.0 0.0 2x2 6x6 36 108 96.9 46.0 3x3 4x4 16 128 60.0 84.0 4x4 3x3 9 135 30.8 113.2 pooling line sought agreement with label none 3 0.9380 2x2 2 0.4220 3x3 2 0.4060 baseline (most frequent class on the test set) 0.5850 active cell count 13.96; lower bound read from 2x2 max pooling 11.78, read from average pooling 13.96 ``` The first table gives the size of the discarding. A 2x2 window reduces 144 cells to 36; 108 cells are gone. Not all of the gone cells are unrecoverable: a window that gives zero says that all four of its cells are zero, so the values of **96.9** cells on average are determined. The share that remains uncertain is **46.0 bits** — there are original grids of the order of $2^{46}$ that give the same pooled output. When the window rises to 4x4 the uncertainty climbs to 113.2 bits and the recovered cells fall to 30.8. The second table is the real warning. When a line of three cells is sought in the raw grid, agreement is 0.9380. When the same grid is pooled 2x2 and a line of two cells is sought, agreement falls to **0.4220**, that is, **below** the baseline of 0.5850. When pooling is applied to the raw input, noise cells move close together and produce false lines, and a real line can no longer be told apart from chance. Here pooling does not merely **discard** information; it discards exactly the information that tells the cases apart. The last line gives the difference between the two kinds of pooling. The number of active cells is read back exactly from average pooling: 13.96. What is read from max pooling is only a **lower bound**, 11.78. Average pooling preserves the count, max pooling preserves presence; which one does the job depends on the question being asked. ## Pooling on the Feature Map ```python # feature_map.py — pooling is applied not to the raw grid but to the FEATURE # MAP produced by the convolution. The kernels are the hand-written kernels of 01. PADDING = 1 HORIZONTAL = [[0, 0, 0], [1, 1, 1], [0, 0, 0]] VERTICAL = [[0, 1, 0], [0, 1, 0], [0, 1, 0]] def active_cells(g): return [(i, j) for i in range(SIDE) for j in range(SIDE) if g[i][j]] def convolve(active, K, bias): n = SIDE + 2 * PADDING - 3 + 1 output = [[bias] * n for _ in range(n)] for (i, j) in active: for di in range(3): for dj in range(3): p, q = i + PADDING - di, j + PADDING - dj if 0 <= p < n and 0 <= q < n: output[p][q] += K[di][dj] return output def representation(g, p): active, rep = active_cells(g), [] for K in (HORIZONTAL, VERTICAL): m = [[max(0.0, v) for v in s] for s in convolve(active, K, -2.5)] rep += [v for s in (pool(m, p) if p > 1 else m) for v in s] return rep def shift(g): # shift one cell down return [[0] * SIDE] + [s[:] for s in g[:-1]] NONZERO = [g for g, y in TEST if any(v > 0 for v in representation(g, 1))] print(f"test grids whose map is not entirely zero {len(NONZERO)}/{len(TEST)}") print(f"{'pooling':>10}{'map':>9}{'head input':>12}{'head params':>13}" f"{'total params':>14}{'same after shift':>17}") for p in (1, 2, 3, 12): n = SIDE // p head = 2 * n * n same = sum(1 for g in NONZERO if all(abs(x - y) < 1e-9 for x, y in zip(representation(g, p), representation(shift(g), p)))) print(f"{('none' if p == 1 else f'{p}x{p}'):>10}{f'{n}x{n}':>9}{head:>12}" f"{head + 1:>13}{20 + head + 1:>14}{same / len(NONZERO):>16.1%}") ``` ``` test grids whose map is not entirely zero 97/200 pooling map head input head params total params same after shift none 12x12 288 289 309 0.0% 2x2 6x6 72 73 93 38.1% 3x3 4x4 32 33 53 55.7% 12x12 1x1 2 3 23 88.7% ``` The same operation in a different place gives the opposite result. When pooling is applied to the output of the convolution the line information is not lost, because the kernel has **already found** the line; what remains on the map is the position and strength of the line, and pooling only makes the position coarser. The gain is in the last column. In the representation without pooling, a one-cell shift changes the map in **every** grid: invariance is 0.0%. With 2x2 pooling the representation is preserved exactly in **38.1%** of the grids, with 3x3 in 55.7%, and with global pooling in **88.7%**. The reason is something that can be counted: as long as the largest value moves around inside the window, the output of the window does not change, that is, pooling absorbs a shift as large as the window size. The remaining 11.3% is the share where the shift genuinely carries information away: if the line is in the bottom row, the shift throws it out of the grid. The three middle columns write the price — the input of the head falls from 288 to 2, and the total parameter count from 309 to 23. ## Three Poolings, Three Networks Until now the kernels were written by hand. Below the kernels are learned, and the only thing that changes is the pooling window. ```python # train.py — MODEL: kernels are learned, the pooling window changes. # Output sigmoid, loss cross-entropy, update per example. TRAIN_ACTIVE = [(active_cells(g), y) for g, y in TRAIN] TEST_ACTIVE = [(active_cells(g), y) for g, y in TEST] SHIFTED_ACTIVE = [(active_cells(shift(g)), y) for g, y in TEST] def sigmoid(z): return 1 / (1 + math.exp(-z)) if z > -30 else 0.0 def build(count, p, seed): r, n = rng(seed), SIDE // p return [[[[(r() * 2 - 1) / 3 for _ in range(3)] for _ in range(3)] for _ in range(count)], [0.0] * count, [(r() * 2 - 1) / (count * n * n) ** 0.5 for _ in range(count * n * n)], [0.0], p] def forward(P, active): Ks, b, v, c, p = P n, z, record, idx = SIDE // p, c[0], [], 0 for k, K in enumerate(Ks): m = convolve(active, K, b[k]) for i in range(n): for j in range(n): best, bp, bq = m[i * p][j * p], i * p, j * p for a in range(p): for t in range(p): if m[i * p + a][j * p + t] > best: best, bp, bq = m[i * p + a][j * p + t], i * p + a, j * p + t h = max(0.0, best) record.append((k, bp, bq, h)) z += v[idx] * h idx += 1 return record, sigmoid(z) def train_model(P, data, epochs, lr, seed): r, n = rng(seed), len(data) Ks, b, v, c, p = P for _ in range(epochs): s = list(range(n)) for i in range(n - 1, 0, -1): j = int(r() * (i + 1)) s[i], s[j] = s[j], s[i] for idx in s: active, y = data[idx] record, out = forward(P, active) d = out - y D = [[[0.0] * SIDE for _ in range(SIDE)] for _ in Ks] for t, (k, bp, bq, h) in enumerate(record): if h > 0.0: D[k][bp][bq] += d * v[t] v[t] -= lr * d * h c[0] -= lr * d for k in range(len(Ks)): b[k] -= lr * sum(sum(s2) for s2 in D[k]) for di in range(3): for dj in range(3): Ks[k][di][dj] -= lr * sum( D[k][i + PADDING - di][j + PADDING - dj] for (i, j) in active if 0 <= i + PADDING - di < SIDE and 0 <= j + PADDING - dj < SIDE) return P def accuracy(P, data): return sum(1 for active, y in data if (forward(P, active)[1] >= 0.5) == (y == 1)) / len(data) print(f"{'pooling':>10}{'param':>7}{'run':>7}{'train':>8}{'test':>8}" f"{'decisions changed on shift':>28}") print(f"{'baseline':>10}{0:>7}{'-':>7}{'-':>8}{BASELINE:>8.4f}{'-':>28}") for p in (1, 2, 12): for k, seed in enumerate((SEED + 11, SEED + 12)): P = train_model(build(2, p, seed), TRAIN_ACTIVE, 25, 0.05, seed + 500) changed = sum(1 for (a1, y), (a2, _) in zip(TEST_ACTIVE, SHIFTED_ACTIVE) if (forward(P, a1)[1] >= 0.5) != (forward(P, a2)[1] >= 0.5)) print(f"{('none' if p == 1 else f'{p}x{p}') if k == 0 else '':>10}" f"{(20 + 2 * (SIDE // p) ** 2 + 1) if k == 0 else '':>7}{k + 1:>7}" f"{accuracy(P, TRAIN_ACTIVE):>8.4f}{accuracy(P, TEST_ACTIVE):>8.4f}{changed:>28d}") ``` ``` pooling param run train test decisions changed on shift baseline 0 - - 0.5850 - none 309 1 1.0000 0.5150 84 2 1.0000 0.5350 88 2x2 93 1 0.8950 0.6100 49 2 0.7900 0.6150 31 12x12 23 1 0.8250 0.8050 12 2 0.8200 0.8050 11 ``` Three numbers stand inside the table. The baseline is **0.5850**. The network without pooling memorizes the training set completely with 309 parameters and reads **0.5150** on the test set — below the baseline. The 2x2 pooled network reads **0.6100** with 93 parameters, and the globally pooled network reads **0.8050** with 23 parameters. As pooling grows the network shrinks and the held-out number rises. The last column confirms the same order with an independent measure. When the 200 test grids are shifted one cell down, the decision of the network without pooling changes in **84** examples, in the 2x2 pooled one in 49, and in the globally pooled one in **12**. The shift does not change the label. **The second run** is written in all three rows, and it speaks loudest in 2x2 pooling: the test numbers of the two runs are 0.6100 and 0.6150, that is, close to each other, but their training numbers are 0.8950 and 0.7900 and the decisions changed on shift are 49 and 31. Two runs of the same capacity give a similar number on the held-out set while opening a **difference of eighteen examples** in how the decision behaves against the shift. The held-out number reports this difference in no way. ## Summary - 2x2 max pooling reduces 144 cells to 36; 96.9 cells can be recovered on average, an uncertainty of 46.0 bits remains, and with a 4x4 window the uncertainty rises to 113.2 bits. - Pooling applied to the raw grid destroys the line information: agreement falls from 0.9380 to 0.4220, that is, below the baseline. - Average pooling preserves the active cell count exactly (13.96), while max pooling gives only a lower bound (11.78). - When the same pooling is applied to the feature map, shift invariance rises from 0.0% to 38.1%, and to 88.7% with global pooling; the price is the head input falling from 288 to 2. - With a baseline of 0.5850, the network without pooling reads 0.5150 and 0.5350 with 309 parameters, the 2x2 pooled network 0.6100 and 0.6150 with 93 parameters, and the globally pooled network 0.8050 and 0.8050 with 23 parameters. - The number of decisions that change on the shifted test set is 84, 49 and 12; the two runs of 2x2 pooling give the same test number while they diverge between 49 and 31 on this count. ## Next Step The network up to here is **two-layered**: one convolution, one pooling, one linear head. Global pooling gave the best number but threw away the position of the line entirely — this network cannot answer the question "are there two lines". The way to do that is, instead of reducing the map to zero in one go, to **stack convolution and pooling in sequence**: each layer sees a larger area of the output of the one before it. The next lesson measures the price of this stacking: as the number of layers grows, it is counted whether the gradient coming from the output reaches the first layer, how much a **skip connection** fixes this is measured, and a point where a deeper network cannot beat a shallower one is shown.