Convolutional Network Architectures

The previous two lessons used a single convolution layer. That layer looks through a 3x3 window and sees only that much of the grid; to answer a question like “are two lines close to each other” it has to look at a wider area. The way to do this is not to enlarge the kernel but to stack layers: the second layer looks at 3x3 on the output of the first and, indirectly, sees a much larger area of the input.

Stacking has a price, and that is the measure of this lesson. The gradient coming from the loss starts at the output and is carried back layer by layer; each layer multiplies it once more. As the stack deepens, the gradient reaching the first layer shrinks, and after a point the first layer is never updated. Three things will be measured: the receptive field that grows with depth, the magnitude of the gradient reaching the first layer, and the difference depth adds to the held-out number.

• AR19. The set, the split and the baseline do not change. The fictional coverage grid is generated with the same seed; the split is 200/100/200, and the most frequent class on the test set is 0.5850.
• AR20. The stack is fixed, and the only thing that changes is the number of blocks. Layer 0: two 3x3 kernels, padding 1, a rectified linear unit, then 4x4 pooling — a 3x3 map per channel remains. Then $D$ blocks, then global pooling and a linear head.
• AR21. A block is a 3x3 convolution applied to the map of one channel followed by a rectified linear unit; the channels do not mix.
• AR22. A skip connection means adding the input of the block to its output. The block no longer changes the input, it learns a correction to the input; the gradient goes backward by two paths, and one of them is not shrunk by any factor.
• AR23. The receptive field is the side length of the square formed by the input cells that can affect the value of an output unit. Since the pooling window is 4 and the growth per block is 2 windows, the side is $4(2D+1)+2$.
• AR24. The gradient measurement is taken at initialization and averaged over 80 training grids; the measured number is the sum of the absolute values of the kernel gradients of the first layer. The question asked is whether training can start.
• AR25. Initialization is fixed and the gain is not scaled: all kernel weights are drawn from the same range, so that what happens with depth can be seen.
• AR26. No library is called; the stack, the forward pass, backpropagation and the training loop are written inside the lesson and are a model. No architecture is named after a person or an institution; it is named by its structure.
• AR27. Every network is run twice; in the second run only the initial values change.

The Stack and the Receptive Field

# architecture.py — MODEL: the FICTIONAL coverage grid of 01 is generated with the same seed.
# Stack: convolution (3x3, padding 1, two kernels) -> rectified -> pooling 4x4
# -> 3x3 map; then D blocks (3x3 convolution + rectified on each channel,
# in the skip version
# the input of the block is added to the output); then global pooling and linear head.
import math

SEED, M32, SIDE = 20260218, 0xFFFFFFFF, 12
DENSITY, TRACE_RATE, RUN_LENGTH = 0.09, 0.42, 3
PADDING, POOL, MAP_SIDE, CHANNELS = 1, 4, 3, 2


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_ACTIVE = [([(i, j) for i in range(SIDE) for j in range(SIDE) if g[i][j]], y)
                for g, y in DATA[:200]]
TEST_ACTIVE = [([(i, j) for i in range(SIDE) for j in range(SIDE) if g[i][j]], y)
               for g, y in DATA[300:]]
BASELINE = max(sum(y for _, y in TEST_ACTIVE),
               len(TEST_ACTIVE) - sum(y for _, y in TEST_ACTIVE)) / len(TEST_ACTIVE)


def build(D, seed, a=1 / 3):
    r = rng(seed)
    return [[[[[(r() * 2 - 1) * a for _ in range(3)] for _ in range(3)]
              for _ in range(CHANNELS)] for _ in range(D + 1)],
            [[0.0] * CHANNELS for _ in range(D + 1)],
            [(r() * 2 - 1) * 0.5 for _ in range(CHANNELS)], [0.0], D]


def forward(P, active, skip):
    Ks, bs, v, c, D = P
    x, pooled = [], []
    for k in range(CHANNELS):                # layer 0: convolution on sparse input
        m = [[bs[0][k]] * SIDE for _ in range(SIDE)]
        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 < SIDE and 0 <= q < SIDE:
                        m[p][q] += Ks[0][k][di][dj]
        ch_rec, ch_map = [], [[0.0] * MAP_SIDE for _ in range(MAP_SIDE)]
        for i in range(MAP_SIDE):
            for j in range(MAP_SIDE):
                best, bp, bq = None, 0, 0
                for a in range(POOL):
                    for b in range(POOL):
                        u = m[i * POOL + a][j * POOL + b]
                        if best is None or u > best:
                            best, bp, bq = u, i * POOL + a, j * POOL + b
                ch_map[i][j] = max(0.0, best)
                ch_rec.append((bp, bq, best))
        x.append(ch_map)
        pooled.append(ch_rec)
    stages, pre_acts = [x], []
    for t in range(1, D + 1):                # D blocks
        prev, new, pre = stages[-1], [], []
        for k in range(CHANNELS):
            z = [[bs[t][k]] * MAP_SIDE for _ in range(MAP_SIDE)]
            for p in range(MAP_SIDE):
                for q in range(MAP_SIDE):
                    s = bs[t][k]
                    for di in range(3):
                        i2 = p + di - PADDING
                        if 0 <= i2 < MAP_SIDE:
                            xi = prev[k][i2]
                            for dj in range(3):
                                j2 = q + dj - PADDING
                                if 0 <= j2 < MAP_SIDE:
                                    s += Ks[t][k][di][dj] * xi[j2]
                    z[p][q] = s
            pre.append(z)
            new.append([[max(0.0, z[i][j]) + (prev[k][i][j] if skip else 0.0)
                         for j in range(MAP_SIDE)] for i in range(MAP_SIDE)])
        pre_acts.append(pre)
        stages.append(new)
    last, h, arg = stages[-1], [], []
    for k in range(CHANNELS):                # global pooling
        best, bp, bq = last[k][0][0], 0, 0
        for i in range(MAP_SIDE):
            for j in range(MAP_SIDE):
                if last[k][i][j] > best:
                    best, bp, bq = last[k][i][j], i, j
        h.append(best)
        arg.append((bp, bq))
    z = c[0] + sum(v[k] * h[k] for k in range(CHANNELS))
    return 1 / (1 + math.exp(-max(-30, min(30, z)))), (pooled, stages, pre_acts, h, arg)


print(f"most frequent class on the test set {BASELINE:.4f}; training {len(TRAIN_ACTIVE)} grids")
print(f"{'depth':>9}{'block':>6}{'parameters':>11}{'receptive field':>17}"
      f"{'covered grid':>17}")
for D in (0, 1, 2, 3, 5, 8):
    area = POOL * (2 * D + 1) + 2
    print(f"{D:>9}{D:>6}{20 * (D + 1) + 3:>11}{f'{area}x{area}':>17}"
          f"{min(area, SIDE) ** 2 / (SIDE * SIDE):>16.1%}")

most frequent class on the test set 0.5850; training 200 grids
    depth block parameters  receptive field     covered grid
        0     0         23              6x6           25.0%
        1     1         43            14x14          100.0%
        2     2         63            22x22          100.0%
        3     3         83            30x30          100.0%
        5     5        123            46x46          100.0%
        8     8        183            70x70          100.0%

The receptive field grows linearly with depth and saturates in one block: at depth 0 an output unit sees 25% of the grid, while at depth 1 the side rises to 14 cells and exceeds the 12-cell grid. The following blocks bring no new input cell, they only add parameters. The gain expected from depth cannot come from the receptive field here.

Does the Gradient Reach the First Layer

# gradient.py — backpropagation is written by hand. What is measured: how much of the gradient
# from the output reaches the kernels of the FIRST layer. Measured at INITIALIZATION.
def backward(P, active, cache, d, skip):
    Ks, bs, v, c, D = P
    pooled, stages, pre_acts, h, arg = cache
    dv = [d * h[k] for k in range(CHANNELS)]
    delta = [[[0.0] * MAP_SIDE for _ in range(MAP_SIDE)] for _ in range(CHANNELS)]
    for k in range(CHANNELS):
        bp, bq = arg[k]
        delta[k][bp][bq] = d * v[k]
    dK = [[[[0.0] * 3 for _ in range(3)] for _ in range(CHANNELS)] for _ in range(D + 1)]
    db = [[0.0] * CHANNELS for _ in range(D + 1)]
    for t in range(D, 0, -1):
        prev, pre2 = stages[t - 1], pre_acts[t - 1]
        new = [[[delta[k][i][j] if skip else 0.0 for j in range(MAP_SIDE)]
                for i in range(MAP_SIDE)] for k in range(CHANNELS)]
        for k in range(CHANNELS):
            z = pre2[k]
            for p in range(MAP_SIDE):
                for q in range(MAP_SIDE):
                    g = delta[k][p][q] if z[p][q] > 0 else 0.0
                    if g == 0.0:
                        continue
                    db[t][k] += g
                    for di in range(3):
                        i2 = p + di - PADDING
                        if not 0 <= i2 < MAP_SIDE:
                            continue
                        for dj in range(3):
                            j2 = q + dj - PADDING
                            if 0 <= j2 < MAP_SIDE:
                                dK[t][k][di][dj] += g * prev[k][i2][j2]
                                new[k][i2][j2] += g * Ks[t][k][di][dj]
        delta = new
    for k in range(CHANNELS):
        d0 = [[0.0] * SIDE for _ in range(SIDE)]
        t2 = 0
        for i in range(MAP_SIDE):
            for j in range(MAP_SIDE):
                bp, bq, best = pooled[k][t2]
                t2 += 1
                if best > 0 and delta[k][i][j] != 0.0:
                    d0[bp][bq] += delta[k][i][j]
        for di in range(3):
            for dj in range(3):
                dK[0][k][di][dj] = sum(
                    d0[i + PADDING - di][j + PADDING - dj] for (i, j) in active
                    if 0 <= i + PADDING - di < SIDE and 0 <= j + PADDING - dj < SIDE)
        db[0][k] = sum(sum(s) for s in d0)
    return dK, db, dv


print(f"{'depth':>9}{'plain first layer':>19}{'skip first layer':>21}"
      f"{'ratio':>12}")
for D in (0, 1, 2, 3, 5, 8):
    measured = []
    for skip in (False, True):
        P, total = build(D, SEED + 11), 0.0
        for active, y in TRAIN_ACTIVE[:80]:
            out, cache = forward(P, active, skip)
            dK = backward(P, active, cache, out - y, skip)[0]
            total += sum(abs(u) for k in range(CHANNELS) for s in dK[0][k] for u in s)
        measured.append(total / 80)
    print(f"{D:>9}{measured[0]:>19.3e}{measured[1]:>21.3e}{measured[1] / measured[0]:>12.1f}")

    depth  plain first layer     skip first layer       ratio
        0          6.405e-01            6.405e-01         1.0
        1          2.393e-02            8.261e-01        34.5
        2          2.729e-03            1.925e-01        70.6
        3          2.457e-03            7.907e-01       321.8
        5          1.984e-04            1.043e+00      5256.1
        8          9.269e-07            6.779e-01    731349.2

In the plain stack the gradient reaching the first layer is $6.405 \times 10^{-1}$ at depth 0. One block reduces it to $2.393 \times 10^{-2}$, five blocks to $1.984 \times 10^{-4}$, eight blocks to $9.269 \times 10^{-7}$ — about seven hundred thousand times. This is not a training defect but the product itself: each block multiplies the gradient going backward by its weights once more, and if the factors are less than one the product shrinks exponentially with depth.

The skip connection column stays between $1.9 \times 10^{-1}$ and $1.0$ at the same depths; it does not decrease with depth. The reason is written in AR22: since the output of the block contains its input, one copy of the gradient going backward is not multiplied by any kernel and is carried as it is. The ratio column is the size of the correction — 70.6 times at depth 2, 731,349 times at depth 8.

What Depth Adds

# train.py — MODEL: same data, same epoch budget, same learning rate.
# Only the depth and the presence of the skip connection change.
def train_model(P, data, epochs, lr, seed, skip):
    r, n = rng(seed), len(data)
    Ks, bs, v, c, D = 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]
            out, cache = forward(P, active, skip)
            d = out - y
            dK, db, dv = backward(P, active, cache, d, skip)
            for t in range(D + 1):
                for k in range(CHANNELS):
                    bs[t][k] -= lr * db[t][k]
                    for di in range(3):
                        for dj in range(3):
                            Ks[t][k][di][dj] -= lr * dK[t][k][di][dj]
            for k in range(CHANNELS):
                v[k] -= lr * dv[k]
            c[0] -= lr * d
    return P


def accuracy(P, data, skip):
    return sum(1 for active, y in data
               if (forward(P, active, skip)[0] >= 0.5) == (y == 1)) / len(data)


print(f"{'depth':>9}{'connection':>12}{'param':>7}{'run':>7}{'train':>8}"
      f"{'test':>8}{'vs baseline':>13}")
print(f"{'baseline':>9}{'-':>12}{0:>7}{'-':>7}{'-':>8}{BASELINE:>8.4f}{'0.0000':>13}")
for D, skip in ((0, False), (2, False), (2, True), (5, False), (5, True)):
    for k, seed in enumerate((SEED + 11, SEED + 12)):
        P = train_model(build(D, seed), TRAIN_ACTIVE, 25, 0.05, seed + 500, skip)
        acc = accuracy(P, TEST_ACTIVE, skip)
        print(f"{D if k == 0 else '':>9}"
              f"{('skip' if skip else 'plain') if k == 0 else '':>12}"
              f"{(20 * (D + 1) + 3) if k == 0 else '':>7}{k + 1:>7}"
              f"{accuracy(P, TRAIN_ACTIVE, skip):>8.4f}{acc:>8.4f}{acc - BASELINE:>+13.4f}")

    depth  connection  param    run   train    test  vs baseline
 baseline           -      0      -       -  0.5850       0.0000
        0       plain     23      1  0.8100  0.7850      +0.2000
                                  2  0.8200  0.8050      +0.2200
        2       plain     63      1  0.5950  0.5850      +0.0000
                                  2  0.5950  0.5850      +0.0000
        2        skip     63      1  0.8350  0.7950      +0.2100
                                  2  0.8150  0.8150      +0.2300
        5       plain    123      1  0.5950  0.5850      +0.0000
                                  2  0.5950  0.5850      +0.0000
        5        skip    123      1  0.8400  0.8150      +0.2300
                                  2  0.9000  0.8900      +0.3050

The two rows in the middle of the table are the form the second claim of this course takes in this lesson, and it is not hidden: a deeper network could not beat a shallower one. The shallow network with 23 parameters reads 0.7850 and 0.8050; the plain network with 63 parameters, three times deeper, reads 0.5850 in both runs, that is, exactly the baseline. The plain network with five blocks is in the same place with 123 parameters. These networks stay at 0.5950 on the training set too; they have not learned, nor have they memorized. The previous table writes the reason: the gradients reaching the first layer are $2.7 \times 10^{-3}$ and $2.0 \times 10^{-4}$, that is, the first layer has stayed where it was initialized and everything after it is built on a random map.

The skip connection makes the same depth work: 0.7950 and 0.8150 at depth 2, 0.8150 and 0.8900 at depth 5. The structure did not change, the parameter count did not change, the only difference is that the input of the block is added to its output.

The last comparison must be read carefully. The mean of the two runs of the shallow network is 0.7950, that of the five-block skip network 0.8525; the apparent difference depth adds is 0.0575. But the two runs of the five-block network lie between 0.8150 and 0.8900, a range of 0.0750. The difference depth adds is smaller than the difference the same network gives with only its initial values changing; a comparison made with a single run could have shown this network as above the shallow network by both 0.0850 and 0.0100.

Summary

• The receptive field grows linearly with depth and saturates in one block on this grid: 25% at depth 0, 100% at depth 1. The following blocks bring no new input cell, they only add parameters.
• In the plain stack the gradient reaching the first layer is $6.405 \times 10^{-1}$ at depth 0 and $9.269 \times 10^{-7}$ at depth 8; the shrinking comes from the product itself.
• The skip connection holds the gradient between $1.9 \times 10^{-1}$ and $1.0$ at the same depths; the correction ratio is 70.6 times at depth 2 and 731,349 times at depth 8.
• With a baseline of 0.5850, the shallow network with 23 parameters reads 0.7850 and 0.8050; the plain deep networks with 63 and 123 parameters stay at 0.5850 in both runs — a deeper network cannot beat a shallower one.
• The skip connection gives 0.7950 and 0.8150 at depth 2 and 0.8150 and 0.8900 at depth 5, with the parameter count unchanged.
• The mean difference depth adds is 0.0575, and the difference between two runs of the same network is 0.0750; as long as the second is large, the first cannot be measured with a single run.

Next Step

For three lessons the structure of the input was spatial and the whole grid was given to the network at once; there was no question of which cell came first. The meter readings of a subscriber are not like that: the readings form a sequence, the place in the sequence is meaningful, and the number of readings is not the same for every subscriber. A kernel looking through a fixed-size window cannot see the past that falls outside the window. The next lesson builds a structure that reads the input step by step from start to end and accumulates what it sees in a hidden state. What will be measured is what that state carries: how much of the information at the start of the sequence remains in the state as the sequence grows longer.