Forward Propagation

In the two lessons the network always stayed the same: twelve inputs, eight units, a single output. How many units the hidden layer would carry was never chosen, and what would change if it were chosen was not measured. This lesson ties two cost numbers and one return number to that choice.

The cost side is found by calculation and does not change from run to run: the parameter count — the number of weights and biases the network holds in memory — and the multiplications per example — the number of multiplications made for one subscriber to pass through the network once. Both are read from the structure of the forward pass. The return side can be found only by measuring and, by the rule of this course, is written with two runs.

• NN15. The set, the split, the seed, the twelve columns and the training set reduced to 300 rows are as in 01–02. The baseline on the test set is 0.7579.
• NN16. The activation of the hidden layer in this lesson is the rectified linear unit and is held fixed; 02 measured three activations, and here the only variable is the width.
• NN17. The output layer is a sigmoid, because the output has to be a probability. The threshold is 0.5, and that the threshold is a decision was measured in the Logistic Regression lesson of the Supervised Learning course.
• NN18. The parameter count is computed over layer pairs as $\sum (a_i b_i + b_i)$ and the multiplications per example as $\sum a_i b_i$; $a_i$ is the input and $b_i$ the output width. Additions and activation calls are not counted, because the measure is the number of multiplications.
• NN19. The total multiplications in training is the multiplications per example times 300 rows and 100 epochs; the backward pass is not counted, the measure is only that of the forward pass.
• NN20. The number of widths tried is 5 (2, 4, 8, 16, 32) and the choice is made from the validation set, by looking at the sum of the two runs. Choosing by looking at a single run is not accepted in this course.
• NN21. The learning rate is 0.3 and the number of epochs is 100; this is the setting chosen from validation in 01 and is held fixed throughout the width sweep.

Two Cost Numbers

The cost of a layer is read from its shape. A layer going from twelve inputs to eight units carries 96 weights and eight biases; the layer going from eight units to a single output carries eight weights and one bias. The total is 113. The same calculation is made for multiplications, and the biases stay out, because a bias is added, not multiplied.

# forward_propagation.py — MODEL: the same FICTIONAL subscriber table, the same seed and the same
# split; the training set is reduced to 300 rows as in 01.
import math
import statistics

SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21, 0.00), ("south", 0.22, 17, -0.10),
          ("east", 0.18, 26, 0.30), ("west", 0.14, 14, -0.05),
          ("central", 0.18, 23, 0.05)]


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 pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


SUBSCRIBERS, DATA = [], []
for i in range(RAW):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    household = 1 + pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    rating = 1 + pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        SUBSCRIBERS.append({"id": 10001 + i, "region": b, "household": household,
                            "satisfaction": rating})
for k in SUBSCRIBERS:
    r, v = rng(SEED + 7000 + k["id"]), []
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - n * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    mean, vol, r = sum(v) / len(v), max(v) - min(v), rng(SEED + 51000 + k["id"])
    z = (0.052 * (mean - 20) + 0.85 * (min(v) == 0.0) + 0.026 * vol
         + 0.24 * (k["household"] >= 5) - 0.20 * (k["satisfaction"] >= 4) + k["region"][3]
         + 0.9 * (k["id"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"household": k["household"], "satisfaction": k["satisfaction"], "period": len(v),
         "mean_consumption": round(mean, 2), "volatility": round(vol, 2),
         "zero_readings": int(min(v) == 0.0), "suspicious": int(z > 1.35)}
    x["per_person"] = round(x["mean_consumption"] / x["household"], 3)
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)


def shuffle(data, seed):
    r, s = rng(seed), list(range(len(data)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [data[i] for i in s]


K = shuffle(DATA, SEED + 90000)
TRAIN, VAL, TEST = K[:756], K[756:1008], K[1008:]
FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period",
          "zero_readings", "per_person", "area_north", "area_south", "area_east",
          "area_west", "area_central"]
MEAN = {a: statistics.fmean(x[a] for x in TRAIN) for a in FIELDS}
STD = {a: max(1e-9, statistics.pstdev([x[a] for x in TRAIN])) for a in FIELDS}
BASELINE = sum(x["suspicious"] == 0 for x in TEST) / len(TEST)


def make_set(data):
    return ([[(x[a] - MEAN[a]) / STD[a] for a in FIELDS] for x in data],
            [float(x["suspicious"]) for x in data])


X_TR, Y_TR = make_set(TRAIN[:300])          # REDUCED training set
X_VA, Y_VA = make_set(VAL)
X_TE, Y_TE = make_set(TEST)


def squash(z):                              # S-shaped function, overflow-protected
    if z >= 0:
        return 1.0 / (1.0 + math.exp(-z)) if z < 700 else 1.0
    e = math.exp(z) if z > -700 else 0.0
    return e / (1.0 + e)


UNITS = (2, 4, 8, 16, 32)
COST = {}
print(f"{'units':>6} {'shape':>12} {'params':>10} {'mults/example':>13} "
      f"{'total mults in training':>23}")
for h in UNITS:
    sizes = [len(FIELDS), h, 1]
    params = sum(a * b + b for a, b in zip(sizes, sizes[1:]))
    mults = sum(a * b for a, b in zip(sizes, sizes[1:]))
    COST[h] = (params, mults)
    print(f"{h:>6} {str(tuple(sizes)):>12} {params:>10} {mults:>13} "
          f"{mults * len(X_TR) * 100:>23}")
p0, c0 = COST[UNITS[0]]
p1, c1 = COST[UNITS[-1]]
print(f"\nunits {UNITS[0]} to {UNITS[-1]}: params {p0} -> {p1} "
      f"({p1 / p0:.1f} times), mults {c0} -> {c1} ({c1 / c0:.1f} times)")

 units        shape     params mults/example total mults in training
     2   (12, 2, 1)         29            26                  780000
     4   (12, 4, 1)         57            52                 1560000
     8   (12, 8, 1)        113           104                 3120000
    16  (12, 16, 1)        225           208                 6240000
    32  (12, 32, 1)        449           416                12480000

units 2 to 32: params 29 -> 449 (15.5 times), mults 26 -> 416 (16.0 times)

Both columns grow in direct proportion to the width, because the twelve inputs are connected to each unit separately. When the width grows sixteen-fold, the parameters grow 15.5-fold and the multiplications 16.0-fold. The last column shows that the measure is not time: a hundred-epoch training does 780,000 multiplications in the narrowest network and 12,480,000 in the widest. These numbers do not depend on which machine they are run on.

Matrix Multiplication by Hand

The forward pass is the repetition of two steps: a matrix multiplication and an activation. Each row of the matrix multiplication belongs to one unit and pairs the weights of that unit with the input vector. When it is written by hand, where the cost comes from becomes visible: two nested loops, the outer one turning as many times as the number of units, the inner one as many times as the number of inputs.

def rectified(z):                           # activation that cuts everything below zero to zero
    return z if z > 0.0 else 0.0


def init_weights(seed, sizes):              # gain-scaled initialization, bias zero
    r, net = rng(seed), []
    for a, b in zip(sizes, sizes[1:]):
        scale = math.sqrt(2.0 / a)
        net.append(([[(r() * 2 - 1) * scale for _ in range(a)] for _ in range(b)], [0.0] * b))
    return net


def matmul(W, bias, a):                     # MATRIX MULTIPLICATION by hand: each row is a unit
    return [sum(w * v for w, v in zip(row, a)) + b
            for row, b in zip(W, bias)]


def forward(net, x):                        # FORWARD PASS: layer by layer
    a = x
    for k, (W, bias) in enumerate(net):
        z = matmul(W, bias, a)
        a = [squash(z[0])] if k == len(net) - 1 else [rectified(t) for t in z]
    return a


def forward_trace(net, x):                  # the same pass, printing every layer
    a, mults = x, 0
    print(f"  input layer        width {len(a):>3}, first three {[round(v, 3) for v in a[:3]]}")
    for k, (W, bias) in enumerate(net):
        mults += len(W) * len(a)
        z = matmul(W, bias, a)
        a = [squash(z[0])] if k == len(net) - 1 else [rectified(t) for t in z]
        name = "output layer" if k == len(net) - 1 else f"hidden layer {k + 1}"
        print(f"  {name:<18} width {len(a):>3}, first three {[round(v, 3) for v in a[:3]]}")
    return a[0], mults


for h in (4, 8):
    net = init_weights(SEED + 1, [len(FIELDS), h, 1])
    print(f"{h} units in the hidden layer, first subscriber of the test set:")
    output, mults = forward_trace(net, X_TE[0])
    print(f"  multiplications made {mults}, in the table {COST[h][1]}, "
          f"output {output:.4f}, true label {int(Y_TE[0])}")

4 units in the hidden layer, first subscriber of the test set:
  input layer        width  12, first three [-0.008, -0.63, 1.399]
  hidden layer 1     width   4, first three [0.047, 0.0, 0.673]
  output layer       width   1, first three [0.407]
  multiplications made 52, in the table 52, output 0.4068, true label 0
8 units in the hidden layer, first subscriber of the test set:
  input layer        width  12, first three [-0.008, -0.63, 1.399]
  hidden layer 1     width   8, first three [0.047, 0.0, 0.673]
  output layer       width   1, first three [0.492]
  multiplications made 104, in the table 104, output 0.4923, true label 0

The counted multiplications agree exactly with the calculation in the table: 52 and 104. The shape of the pass is visible too — 12 values drop to 4 values, 4 values to 1 value. The output of the second unit of the hidden layer is 0.0; since its weighted sum of the input stayed negative, the rectified unit cut it off. For the same subscriber the two networks give 0.4068 and 0.4923; both are below the 0.5 threshold and, since the true label is 0, both are correct.

How Much Does Width Return

While the cost grows sixteen-fold, what the return is can be found only by training. Five widths, two runs each.

def train_model(net, X, Y, rate, epochs):   # MODEL: full-batch gradient descent
    n = len(X)
    for _ in range(epochs):
        gW = [[[0.0] * len(W[0]) for _ in W] for W, _ in net]
        gb = [[0.0] * len(bias) for _, bias in net]
        for i in range(n):
            a, acts = X[i], [X[i]]
            for k, (W, bias) in enumerate(net):
                z = matmul(W, bias, a)
                a = [squash(z[0])] if k == len(net) - 1 else [rectified(t) for t in z]
                acts.append(a)
            d = [acts[-1][0] - Y[i]]
            for k in range(len(net) - 1, -1, -1):
                W, a = net[k][0], acts[k]
                for j, dj in enumerate(d):
                    if dj:
                        s = gW[k][j]
                        for p in range(len(a)):
                            s[p] += dj * a[p]
                        gb[k][j] += dj
                if k:
                    prev = [0.0] * len(a)
                    for j, dj in enumerate(d):
                        if dj:
                            s = W[j]
                            for p in range(len(a)):
                                prev[p] += dj * s[p]
                    d = [prev[p] if a[p] > 0 else 0.0 for p in range(len(a))]
        for k, (W, bias) in enumerate(net):
            for j in range(len(W)):
                s, g = W[j], gW[k][j]
                for p in range(len(s)):
                    s[p] -= rate * g[p] / n
                bias[j] -= rate * gb[k][j] / n
    return net


def accuracy(net, X, Y):
    return sum((forward(net, x)[0] > 0.5) == (y > 0.5) for x, y in zip(X, Y)) / len(X)


RESULTS = {}
print(f"{'units':>6} {'params':>10} {'run':>6} {'validation':>10} {'test':>8}")
for h in UNITS:
    RESULTS[h] = []
    for run in (1, 2):
        net = train_model(init_weights(SEED + run, [len(FIELDS), h, 1]), X_TR, Y_TR, 0.3, 100)
        RESULTS[h].append((accuracy(net, X_VA, Y_VA), accuracy(net, X_TE, Y_TE)))
        print(f"{h:>6} {COST[h][0]:>10} {run:>6} {RESULTS[h][-1][0]:>10.4f} "
              f"{RESULTS[h][-1][1]:>8.4f}")
CHOSEN = max(UNITS, key=lambda h: sum(t[0] for t in RESULTS[h]))
all_runs = [t[1] for h in UNITS for t in RESULTS[h]]
best_runs = [max(t[1] for t in RESULTS[h]) for h in UNITS]
run_gap = max(abs(RESULTS[h][0][1] - RESULTS[h][1][1]) for h in UNITS)
print(f"\nwidth chosen on validation {CHOSEN} units ({COST[CHOSEN][0]} parameters)")
print(f"baseline {BASELINE:.4f}, network number {RESULTS[CHOSEN][0][1]:.4f}, "
      f"second run {RESULTS[CHOSEN][1][1]:.4f}")
print(f"band of ten runs {min(all_runs):.4f}-{max(all_runs):.4f} "
      f"({round((max(all_runs) - min(all_runs)) * len(X_TE))} subscribers)")
print(f"what width adds (the good run of each width) {min(best_runs):.4f}-{max(best_runs):.4f} "
      f"= {round((max(best_runs) - min(best_runs)) * len(X_TE))} subscribers")
print(f"largest run difference at a single width {run_gap:.4f} "
      f"= {round(run_gap * len(X_TE))} subscribers")

 units     params    run validation     test
     2         29      1     0.8135   0.7579
     2         29      2     0.8016   0.7659
     4         57      1     0.8254   0.7540
     4         57      2     0.8135   0.7738
     8        113      1     0.8214   0.7857
     8        113      2     0.8056   0.7698
    16        225      1     0.8135   0.7659
    16        225      2     0.7937   0.7778
    32        449      1     0.8056   0.7817
    32        449      2     0.8056   0.7698

width chosen on validation 4 units (57 parameters)
baseline 0.7579, network number 0.7540, second run 0.7738
band of ten runs 0.7540-0.7857 (8 subscribers)
what width adds (the good run of each width) 0.7659-0.7857 = 5 subscribers
largest run difference at a single width 0.0198 = 5 subscribers

The last two lines should be read side by side. A 15.5-fold difference in parameters produces five subscribers between the good runs of each width. At a single width, with nothing changed except the initial values, the largest difference is again five subscribers. The difference between doubling the width and retraining the network cannot be told apart to this extent.

The validation column carries a separate warning. When the choice is made from validation, the winner is 4 units, that is, one of the narrowest of the five candidates; with 57 parameters. The test number of that candidate is 0.7540 and this is below the baseline — saying the most frequent class gives 0.7579. The second run of the same candidate gives 0.7738; there are five subscribers between the two runs and the validation set cannot choose between them, because on validation too it moves between 0.8254 and 0.8135. The difference that the tuning budget inflates had been measured in the Hyperparameter Search lesson of the Supervised Learning course; what is added here is that the movement within the same candidate spoils the choice.

Summary

• The forward pass is the repetition of a matrix multiplication and an activation. Each row of the matrix multiplication belongs to one unit and, when it is written by hand, the cost is read from two nested loops.
• When the hidden layer grows from 2 to 32 units, the parameters grow from 29 to 449 (15.5 times), the multiplications per example from 26 to 416 (16.0 times), and the total multiplications of a hundred-epoch training from 780,000 to 12,480,000. All three numbers are independent of the machine.
• When a single subscriber is traced, the counted multiplications agree exactly with the calculation in the table: 52 with 4 units, 104 with 8 units; 12 values drop first to the width of the hidden layer, then to a single probability.
• The triple: baseline 0.7579, network number 0.7540, second run 0.7738. The width chosen by validation is 4 units and its first run stays below the baseline.
• A 15.5-fold difference in parameters amounts to five subscribers, and the difference between two runs at the same width also amounts to five subscribers; all ten runs stand in a band between 0.7540 and 0.7857, a band of eight subscribers.

Next Step

In three lessons the output of the network was always a probability, and that probability was always compared with the target in the same way: the difference was taken and passed backward. This comparison is itself a choice and has never been discussed. The next lesson treats the loss function not as a preference but as a number: if the same network, the same data, is trained with two separate losses, do they give two separate results, and how many subscribers is the difference. In the same lesson a second distinction is built — the loss that governs training and the metric that reports performance are not the same thing, and a change that lowers the loss can worsen the metric.