--- title: 'Convolution Operation' source: 'https://academia.sh/en/courses/deep-learning/convolution-operation' course: 'Deep Learning' language: en updated: '2026-10-21T05:03:22+00:00' license: 'CC BY-SA 4.0' objectives: - 'Defines the convolution operation through kernel, stride and padding and computes the output size from these three numbers' - 'Counts the parameters and multiplications of a fully connected layer and a convolution layer that produce the same output side by side' - 'Measures what weight sharing adds on the held-out set together with the baseline and the second run of the same network' --- # Convolution Operation Counting how many weights the first layer that uses the structure of the input needs: a fully connected layer producing the same 144 outputs holds 20,880 numbers while a 3x3 convolution kernel holds 10, a ratio of 2,088 times. Two hand-written kernels give 0.8900 agreement without padding and 0.9380 with padding 1, and the difference is entirely the edge cells. On the test set the most frequent class gives 0.5850, while a fully connected network with 1,169 parameters memorizes the training set completely and reads 0.5100 and 0.5350, and a convolutional network with 23 parameters reads 0.8000 and 0.8150: the difference between the two runs is 0.0250 for the fully connected network and 0.0150 for the convolutional network. Over nine lessons the network stayed **fully connected**: every input column was tied to every unit with its own weight. In such a layer the order of the columns means nothing; if the columns were shuffled, what the network learns would not change, only the positions of the weights would. In the subscriber table this is not a loss, because there is no adjacency between household size and mean consumption. When the input is a **grid**, the situation changes. What is sought lies not in a single cell but in the arrangement of several adjacent cells. A fully connected layer does not use this: it learns a separate weight for every cell, and when the same arrangement appears somewhere else it has to learn it again. This is the measure of this lesson — with how many weights a fully connected layer does the same job, and with how many convolution does. - **AR1. The coverage grid is fictional.** In the Visualization, Reporting and Analysis at Scale course the regions were divided into a 12x12 grid of cells; here the same grid is turned into a learning input. Each cell is a coverage unit, and its value is whether the unit has a reading above the threshold. Seed 20260218. - **AR2. The label is fictional too, and structural.** A grid is labeled 1 if a **line of three adjacent cells** has been planted in it. The line stands for a leak trace running along a pipeline; scattered single cells are noise. - **AR3. The label cannot be read exactly from the grid.** About 9% of the cells are active on their own; in some grids with no line planted, a three-cell arrangement also appears by chance. - **AR4. The split is 200/100/200** and fixed in this grid set. The training set is deliberately **reduced**; the scale is kept small. - **AR5. The baseline is read from the grid set.** Saying the most frequent class on the test set gives 0.5850. The 0.7579 of the Introduction to Machine Learning, Data Preparation and Feature Engineering, and Supervised Learning courses belongs to the **subscriber table** and cannot be compared with this set. - **AR6. The kernel** is a small weight matrix slid over the grid; the **stride** is the shift between two neighboring positions, and the **padding** is the thickness of the frame of zeros added to the edge. - **AR7. Weight sharing** is the definition of convolution: the same kernel is used at all positions. This makes the parameter count independent of the number of positions. - **AR8. No library is called;** the convolution and the training loop are written inside the lesson and are **a model**. - **AR9. Every network is run twice.** In the second run only the initial values change; the data, the split, the number of epochs and the learning rate are the same. ## The Coverage Grid and the Parameter Count ```python # grid.py — MODEL: the coverage grid is FICTIONAL: the 12x12 coverage grid of the # Visualization, Reporting and Analysis at Scale course becomes a learning input # here. Each cell is a coverage unit; its value is whether it has a reading above the threshold. 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): """A subscriber's coverage grid. Label: whether a leak trace was planted.""" 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: # a line of three adjacent cells 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, VAL, TEST = DATA[:200], DATA[200:300], DATA[300:] BASELINE = max(sum(y for _, y in TEST), len(TEST) - sum(y for _, y in TEST)) / len(TEST) example = next(g for g, y in DATA if y == 1 and any( all(g[i][j + k] for k in range(RUN_LENGTH)) for i in range(SIDE) for j in range(SIDE - RUN_LENGTH + 1))) print("grid with a horizontal line planted (1 = reading above threshold), label 1:") for row in example: print(" " + "".join("#" if x else "." for x in row)) print(f"grid {SIDE}x{SIDE} = {SIDE * SIDE} cells, mean active cells " f"{sum(sum(sum(s) for s in g) for g, _ in DATA) / len(DATA):.2f}") print(f"split {len(TRAIN)}/{len(VAL)}/{len(TEST)}, most frequent class on the test set " f"{BASELINE:.4f}") FC_HIDDEN = 8 fc_params = SIDE * SIDE * FC_HIDDEN + FC_HIDDEN + FC_HIDDEN + 1 fc_layer = (SIDE * SIDE) ** 2 + SIDE * SIDE print(f"\n{'layer':<34}{'weight':>9}{'bias':>7}{'total':>9}") print(f"{'fully connected 144 -> 144':<34}{(SIDE * SIDE) ** 2:>9}{SIDE * SIDE:>7}" f"{fc_layer:>9}") print(f"{'convolution 3x3, single kernel':<34}{9:>9}{1:>7}{10:>9}") print(f"ratio for the same output size {fc_layer / 10:.0f}x") ``` ``` grid with a horizontal line planted (1 = reading above threshold), label 1: #..#........ ....#....... ..#...#..... ............ #.#......... .....#..#... #....#.....# .####....##. .......##... ..........#. ..........#. ............ grid 12x12 = 144 cells, mean active cells 13.96 split 200/100/200, most frequent class on the test set 0.5850 layer weight bias total fully connected 144 -> 144 20736 144 20880 convolution 3x3, single kernel 9 1 10 ratio for the same output size 2088x ``` In the example grid, three of the four adjacent cells in the eighth row are the planted line, and the fourth is a noise cell that happened to land next to it. The remaining active cells are scattered. The table at the bottom is the lesson's number. A fully connected layer that produces one output per cell holds **20,880** numbers. A single 3x3 kernel that produces the same output size holds **10**: nine weights and one bias. The ratio is **2,088 times**. The difference is not an optimization trick but an **assumption**. The fully connected layer says "every position may have its own rule" and reserves room for 144 separate rules; convolution says "the pattern sought is the same pattern wherever it is" and learns a single rule. If the assumption is wrong, convolution cannot learn. On this grid it holds, because the line is planted anywhere. ## Kernel, Stride and Padding ```python # convolution.py — the convolution operation is written by hand: the kernel is slid over the # grid and the same weights are used at every position. The input is binary, so the loop # runs only over active cells; the computed number does not change, the run gets shorter. 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, stride=1, padding=0): c = len(K) n = (SIDE + 2 * padding - c) // stride + 1 output = [[bias] * n for _ in range(n)] for (i, j) in active: for di in range(c): for dj in range(c): p, q = i + padding - di, j + padding - dj if p % stride == 0 and q % stride == 0 and 0 <= p // stride < n \ and 0 <= q // stride < n and p >= 0 and q >= 0: output[p // stride][q // stride] += K[di][dj] return output HORIZONTAL = [[0, 0, 0], [1, 1, 1], [0, 0, 0]] VERTICAL = [[0, 1, 0], [0, 1, 0], [0, 1, 0]] def fires(g, padding): active = active_cells(g) return (max(max(r) for r in convolve(active, HORIZONTAL, -2.5, 1, padding)) > 0 or max(max(r) for r in convolve(active, VERTICAL, -2.5, 1, padding)) > 0) print("horizontal kernel output (+ = line found), padding 1, 12x12:") for row in convolve(active_cells(example), HORIZONTAL, -2.5, 1, 1): print(" " + "".join("+" if v > 0 else "." for v in row)) for padding in (0, 1): agree = sum(1 for g, y in DATA if fires(g, padding) == (y == 1)) print(f"two hand-written kernels, padding {padding}: agreement with label " f"{agree / len(DATA):.4f}") print(f"\n{'stride':>7}{'padding':>8}{'output':>8}{'weight':>9}{'mults':>9}" f"{'fully connected mults':>23}") for stride, padding in ((1, 0), (1, 1), (2, 0), (2, 1), (3, 1)): n = (SIDE + 2 * padding - 3) // stride + 1 print(f"{stride:>7}{padding:>8}{f'{n}x{n}':>8}{10:>9}{n * n * 9:>9}" f"{n * n * SIDE * SIDE:>23}") ``` ``` horizontal kernel output (+ = line found), padding 1, 12x12: ............ ............ ............ ............ ............ ............ ............ ..++........ ............ ............ ............ ............ two hand-written kernels, padding 0: agreement with label 0.8900 two hand-written kernels, padding 1: agreement with label 0.9380 stride padding output weight mults fully connected mults 1 0 10x10 10 900 14400 1 1 12x12 10 1296 20736 2 0 5x5 10 225 3600 2 1 6x6 10 324 5184 3 1 4x4 10 144 2304 ``` When the kernel is written by hand, what it does becomes visible. The horizontal kernel takes the sum of three adjacent cells and, with a bias of $-2.5$, produces a positive value only if all three are active; on the example grid it fires at two positions of the seventh row, because there are four adjacent cells there. These two kernels, with no training at all, give **0.9380** agreement over the whole set. The difference between the two agreement numbers is the measure of **padding** alone. When working without padding, the center of the kernel cannot sit on the first and last rows, lines at the edge are not seen, and agreement drops to 0.8900. Adding one row of zeros closes a gap of **0.0480**; padding is not a tuning convenience but a decision about whether to see the information at the edge. The table below shows that the output size follows from the relation $n = \lfloor (12 + 2d - c)/s \rfloor + 1$ with stride $s$, padding $d$ and kernel size $c$. The column to watch is the **weight** column: it is 10 whatever the stride and padding. Stride changes only the number of **multiplications** — from 1,296 to 144. The fully connected layer does sixteen times more multiplications in every row, and every one of those multiplications has a weight of its own. ## Two Networks Side by Side The parameter count is a promise; the number on the held-out set is what it amounts to. Two networks are trained on the same data with the same budget; the only difference is the form of the first layer. ```python # train.py — MODEL: two networks are trained on the same data with the same epoch budget. # Output sigmoid, loss cross-entropy, update per example. PADDING, N = 1, SIDE + 2 * 1 - 3 + 1 TRAIN_ACTIVE = [(active_cells(g), y) for g, y in TRAIN] TEST_ACTIVE = [(active_cells(g), y) for g, y in TEST] def sigmoid(z): return 1 / (1 + math.exp(-z)) if z > -30 else 0.0 def fully_connected(H, seed): # 144 -> H -> 1 r, a = rng(seed), (1 / (SIDE * SIDE)) ** 0.5 return [[[(r() * 2 - 1) * a for _ in range(SIDE * SIDE)] for _ in range(H)], [0.0] * H, [(r() * 2 - 1) * (1 / H) ** 0.5 for _ in range(H)], [0.0]] def fc_forward(P, active): W, b, v, c = P h = [max(0.0, b[k] + sum(W[k][i * SIDE + j] for (i, j) in active)) for k in range(len(b))] return h, sigmoid(c[0] + sum(v[k] * h[k] for k in range(len(h)))) def convolutional(count, seed): # count kernels -> max -> 1 r, a = rng(seed), (1 / 9) ** 0.5 return [[[[(r() * 2 - 1) * a for _ in range(3)] for _ in range(3)] for _ in range(count)], [0.0] * count, [(r() * 2 - 1) * (1 / count) ** 0.5 for _ in range(count)], [0.0]] def conv_forward(P, active): Ks, b, v, c = P h, arg = [], [] for k, K in enumerate(Ks): m = convolve(active, K, b[k], 1, PADDING) best, bp, bq = m[0][0], 0, 0 for p in range(N): for q in range(N): if m[p][q] > best: best, bp, bq = m[p][q], p, q h.append(max(0.0, best)) arg.append((bp, bq)) return (h, arg), sigmoid(c[0] + sum(v[k] * h[k] for k in range(len(h)))) def train_model(P, forward, data, epochs, lr, seed, is_conv): r, n = rng(seed), len(data) W, b, v, c = 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] cache, p = forward(P, active) h = cache[0] if is_conv else cache d = p - y for k in range(len(b)): if h[k] > 0.0: dh = d * v[k] b[k] -= lr * dh if is_conv: bp, bq = cache[1][k] for (i, j) in active: di, dj = i + PADDING - bp, j + PADDING - bq if 0 <= di < 3 and 0 <= dj < 3: W[k][di][dj] -= lr * dh else: for (i, j) in active: W[k][i * SIDE + j] -= lr * dh v[k] -= lr * d * h[k] c[0] -= lr * d return P def accuracy(P, forward, data, is_conv): return sum(1 for active, y in data if (forward(P, active)[1] >= 0.5) == (y == 1)) / len(data) conv_params = 2 * (9 + 1) + 2 + 1 print(f"{'network':<25}{'parameters':>11}{'run':>7}{'train':>8}{'test':>8}") print(f"{'baseline':<25}{0:>11}{'-':>7}{'-':>8}{BASELINE:>8.4f}") for name, build, forward, is_conv, params in ( ("fully connected 144-8-1", lambda t: fully_connected(8, t), fc_forward, False, fc_params), ("convolutional 2x3x3", lambda t: convolutional(2, t), conv_forward, True, conv_params)): for k, seed in enumerate((SEED + 11, SEED + 12)): P = train_model(build(seed), forward, TRAIN_ACTIVE, 60, 0.10, seed + 500, is_conv) print(f"{name if k == 0 else '':<25}{params if k == 0 else '':>11}{k + 1:>7}" f"{accuracy(P, forward, TRAIN_ACTIVE, is_conv):>8.4f}" f"{accuracy(P, forward, TEST_ACTIVE, is_conv):>8.4f}") ``` ``` network parameters run train test baseline 0 - - 0.5850 fully connected 144-8-1 1169 1 1.0000 0.5100 2 0.9950 0.5350 convolutional 2x3x3 23 1 0.7850 0.8000 2 0.8150 0.8150 ``` Three numbers stand side by side. The baseline is **0.5850**. The fully connected network memorizes the training set completely with **1,169** parameters — 1.0000 in the first run — and reads **0.5100** on the test set, that is 0.0750 **below** the baseline. The convolutional network reads **0.8000** on the test set with **23** parameters, passing the baseline by 0.2150. The failure of the fully connected network is not a training defect. Two hundred grids never resemble each other in a 144-dimensional binary space; the network is wide enough to memorize each of them separately, and memorizing is easier than learning where the line is. When the line appears somewhere else, none of the memorized weights is of any use. **The third number** is written for both networks. The two runs of the fully connected network read 0.5100 and 0.5350, a difference of **0.0250**; those of the convolutional network read 0.8000 and 0.8150, a difference of **0.0150**. With capacity, data and budget fixed, changing only the initial values opens a measurable difference. Writing the number of a single run means making this uncertainty invisible. The convolutional network cannot reach even the 0.9380 of the two hand-written kernels. The cause is not capacity but the structure after the first layer: the **largest** value over the entire grid is taken for each kernel and the remaining 143 positions are discarded. This network answers the question "is there a line" and does not answer "where". ## Summary - The coverage grid is fictional: 12x12 cells, 9% activity, the label is a line of three adjacent cells; the most frequent class on the test set gives 0.5850. - A fully connected layer producing the same 144 outputs holds 20,880 numbers, a single 3x3 convolution kernel holds 10; the ratio is 2,088 times and its source is weight sharing. - The output size is computed from stride, padding and kernel size; the number of weights is independent of these three and only the number of multiplications changes (1,296 at stride 1 padding 1, 144 at stride 3). - Working without padding does not see the lines at the edge: agreement rises from 0.8900 to 0.9380, a difference of 0.0480. - A fully connected network with 1,169 parameters memorizes the training set and reads 0.5100 and 0.5350 on the test set, staying below the baseline; a convolutional network with 23 parameters reads 0.8000 and 0.8150. - The difference the second run opens is 0.0250 for the fully connected network and 0.0150 for the convolutional network. ## Next Step The first layer of the convolutional network produced a response at 144 positions, but the network used only **the largest** one and threw away the remaining 143 numbers. This is the most extreme example of discarding: all of the position information is gone. The next lesson turns this into an **adjustable step**; the responses of neighboring positions are combined in small windows. Three things will be measured: how far the output size drops, how many of the discarded cells can be rebuilt, and in how many examples the decision changes when the grid is shifted by one cell.