Convolution Operation

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

# 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

# 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.

# 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.