Recurrent Networks

For three lessons the input was a grid and was given to the network all at once. The meter readings of a subscriber, however, form a sequence: the readings arrive period by period, the place in the sequence is meaningful, and the number of readings per subscriber does not have to be the same. A kernel looking through a fixed-size window does not fit this data — the past that falls outside the window is invisible.

A recurrent network reads the sequence from start to end step by step and accumulates what it has seen up to that point in a hidden state. The same weights are used at every step; this is the counterpart on the time axis of the weight sharing that convolution does in space, and it makes the parameter count independent of the sequence length. The measure of this lesson is this: how much of a piece of information at the start of the sequence remains in the hidden state as the sequence grows longer.

• AR28. The reading sequence is fictional. Twelve periods of meter readings are generated for each subscriber; seed 20260218. The length does not exceed 12, and the sequence is a separate setup, independent of the grid in the first three lessons of this topic.
• AR29. The marker is at the start of the sequence. In about half of the subscribers the reading of the first period is zero — a meter replacement. A zero reading is seen only in the first period, so the marker is unique and its place is known.
• AR30. The label is the joint satisfaction of two conditions: a zero reading in the first period and the reading of the last period above the tariff tier of 25 m³. For the network to decide at the last step, it has to carry the information at the start of the sequence all the way to the end.
• AR31. The input of each step is two numbers: the reading divided by 40 m³ and the zero-reading indicator.
• AR32. The label depends on the sequence length, because the “last period” changes with the length. For this reason the baseline is computed separately for each length and comparisons are made as a difference from the baseline.
• AR33. The network is fixed: a hidden state of 6 units, hyperbolic tangent, and a sigmoid output read from the last hidden state. The parameter count is 61 and does not change whatever the sequence length.
• AR34. The information measurement is made on the untrained network. Only the first step of the same sequence is changed and the difference between the two last hidden states is measured. What is asked is what the structure can carry, not what training has achieved.
• AR35. No library is called; the forward pass, backpropagation through time and the training loop are written inside the lesson and are a model.
• AR36. Every network is run twice; in the second run only the initial values change.

The Sequence and the Hidden State

# sequence.py — MODEL. The reading sequence is FICTIONAL: for each subscriber twelve periods of
# meter readings are generated. In some subscribers the reading of the first period is ZERO
# (meter replacement); this is the MARKER placed at the start of the sequence. The label is the
# presence of the marker AND the last period exceeding the tariff tier TOGETHER.
import math

SEED, M32 = 20260218, 0xFFFFFFFF
LENGTH, TIER, SCALE, HIDDEN = 12, 25.0, 40.0, 6


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 reading_sequence(subscriber_id):
    r = rng(SEED + 400000 + subscriber_id)
    base = 23.0 + 8.0 * r()
    d = [math.floor(base * math.exp((r() + r() + r() - 1.5) * 0.62) * 100 + 0.5) / 100
         for _ in range(LENGTH)]
    if r() < 0.5:
        d[0] = 0.0                           # marker
    return d


def cut(d, T):
    """First T periods; two numbers per step input, the label from both conditions together."""
    x = [[v / SCALE, 1.0 if v == 0.0 else 0.0] for v in d[:T]]
    return x, 1 if (d[0] == 0.0 and d[T - 1] > TIER) else 0


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 = [reading_sequence(i) for i in range(500)]
SEQS = [RAW[i] for i in shuffle(500, SEED + 95000)]
TRAIN, TEST = SEQS[:200], SEQS[300:]


def baseline_for(T):
    p = sum(cut(d, T)[1] for d in TEST)
    return max(p, len(TEST) - p) / len(TEST)


def build(seed, H=HIDDEN):
    r = rng(seed)
    a1, a2 = (1 / 2) ** 0.5, (1 / H) ** 0.5
    return [[[(r() * 2 - 1) * a1 for _ in range(2)] for _ in range(H)],
            [[(r() * 2 - 1) * a2 for _ in range(H)] for _ in range(H)],
            [0.0] * H, [(r() * 2 - 1) * a2 for _ in range(H)], [0.0]]


def forward(P, x):
    """h_t = tanh(Wx x_t + Wh h_(t-1) + b); the output is read from the last hidden state."""
    Wx, Wh, b, v, c = P
    H = len(b)
    h, states = [0.0] * H, []
    for t in range(len(x)):
        h = [math.tanh(b[k] + Wx[k][0] * x[t][0] + Wx[k][1] * x[t][1]
                       + sum(Wh[k][j] * h[j] for j in range(H))) for k in range(H)]
        states.append(h)
    z = c[0] + sum(v[k] * h[k] for k in range(H))
    return 1 / (1 + math.exp(-max(-30, min(30, z)))), states


example = next(d for d in SEQS if d[0] == 0.0 and d[LENGTH - 1] > TIER)
print("example sequence (m3):", " ".join(f"{v:.2f}" for v in example))
print(f"marker rate {sum(1 for d in SEQS if d[0] == 0.0) / len(SEQS):.3f}; "
      f"split {len(TRAIN)}/100/{len(TEST)}; hidden state {HIDDEN} units; "
      f"parameters {HIDDEN * 2 + HIDDEN * HIDDEN + HIDDEN + HIDDEN + 1}")
print(f"{'T':>3}{'positive':>9}{'baseline':>15}")
for T in (2, 4, 6, 8, 10, 12):
    print(f"{T:>3}{sum(cut(d, T)[1] for d in TEST):>9}{baseline_for(T):>15.4f}")

example sequence (m3): 0.00 26.80 37.98 20.95 35.18 49.78 24.15 22.38 47.64 35.14 26.95 25.18
marker rate 0.514; split 200/100/200; hidden state 6 units; parameters 61
  T positive       baseline
  2       56         0.7200
  4       56         0.7200
  6       63         0.6850
  8       51         0.7450
 10       60         0.7000
 12       58         0.7100

In the example sequence the first reading is zero and the last reading, 25.18 m³, is above the tariff tier; the label is 1. The ten periods in between say nothing for the decision — the only information the network has to carry is the zero at the start.

The parameter count is 61 and is the same for all six lengths in the table. The same weights are reused at every step; however long a sequence grows, no new weight is needed. This is the counterpart on the time axis of what convolution does in space, and it is something a fully connected layer cannot do: a fully connected layer has to know the length of the input beforehand.

The baselines wander between 0.6850 and 0.7450 with the length, because the second condition of the label is defined by the “last period” and the last period changes with the length. For this reason the comparison across lengths is made not with raw accuracy but with the difference from the baseline.

What the Hidden State Carries

# trace.py — the information the hidden state carries. ONLY the first step of the same sequence
# is changed (marked / unmarked) and the difference of the last hidden states is measured.
# The measurement is made on the UNTRAINED network: what is asked is what the structure can carry.
def pairs(d, T):
    x, _ = cut(d, T)
    a = [s[:] for s in x]
    a[0] = [0.0, 1.0]
    b = [s[:] for s in x]
    b[0] = [d[1] / SCALE, 0.0]
    return a, b


def readback(P, T):
    """Nearest-center reader: can the marker be read back from h_T."""
    hs = [(forward(P, cut(d, T)[0])[1][-1], 1 if d[0] == 0.0 else 0) for d in SEQS]
    train, test = hs[:200], hs[300:]
    centers, count = [[0.0] * HIDDEN, [0.0] * HIDDEN], [0, 0]
    for h, s in train:
        count[s] += 1
        for k in range(HIDDEN):
            centers[s][k] += h[k]
    for s in (0, 1):
        centers[s] = [u / count[s] for u in centers[s]]
    mean = [(centers[0][k] * count[0] + centers[1][k] * count[1]) / len(train)
            for k in range(HIDDEN)]
    sd = [max(1e-9, (sum((h[k] - mean[k]) ** 2 for h, _ in train) / len(train)) ** 0.5)
          for k in range(HIDDEN)]

    def distance(h, s):
        return sum(((h[k] - centers[s][k]) / sd[k]) ** 2 for k in range(HIDDEN))
    return sum(1 for h, s in test
               if (distance(h, 1) < distance(h, 0)) == (s == 1)) / len(test)


print(f"{'T':>3}{'h diff k1':>12}{'h diff k2':>12}{'per step k1':>16}"
      f"{'readback k1':>15}{'readback k2':>15}")
previous = [None, None]
for T in (2, 4, 6, 8, 10, 12):
    row = []
    for P in (build(SEED + 11), build(SEED + 12)):
        f = 0.0
        for d in SEQS:
            a, b = pairs(d, T)
            ia, ib = forward(P, a)[1][-1], forward(P, b)[1][-1]
            f += sum(abs(ia[k] - ib[k]) for k in range(HIDDEN))
        row.append((f / len(SEQS), readback(P, T)))
    ratio = "-" if previous[0] is None else f"{(row[0][0] / previous[0]) ** 0.5:.3f}"
    previous[0] = row[0][0]
    print(f"{T:>3}{row[0][0]:>12.5f}{row[1][0]:>12.5f}{ratio:>16}"
          f"{row[0][1]:>15.4f}{row[1][1]:>15.4f}")

  T   h diff k1   h diff k2     per step k1    readback k1    readback k2
  2     0.92844     1.39970               -         1.0000         0.9750
  4     0.34417     0.24972           0.609         0.7850         0.9350
  6     0.15338     0.06435           0.668         0.8000         0.6350
  8     0.05986     0.01560           0.625         0.5900         0.5500
 10     0.02362     0.00333           0.628         0.4600         0.4600
 12     0.00913     0.00067           0.622         0.5300         0.4750

The first column is the lesson’s number. When only the first step of the same sequence is changed, the difference remaining in the last hidden state is 0.92844 at length 2 and 0.00913 at length 12 — less than 1% of it. The fourth column gives the form of the shrinking: the per-step factor lies between 0.609 and 0.668, that is, an exponential decrease with a constant factor. The hidden state does not decide to forget the information; at every step it is multiplied by the same matrix, and since the magnitude of the factor is less than one, the trace is erased by itself.

The second run shows the same form at a different speed: at length 12 the difference is 0.00067, one fourteenth of the first run’s. Only the initial values changed; the forgetting speed is not a constant of the architecture but a result of initialization.

The last two columns write what this means. At length 2 the marker is read back from the last hidden state with an accuracy of 1.0000. At length 8 it falls to 0.5900, at length 10 to 0.4600 — since the marker rate is 0.514, this is chance level. The 0.5300 at length 12 is not a recovery, but measurement wobble at the same level. The information is not in the hidden state; no reader can bring it back.

How Far Back It Is Carried

# train_model.py — MODEL: backpropagation through time is written by hand. Same network, same
# epoch budget, the only thing that changes is the sequence length.
def train_model(P, data, epochs, lr, seed):
    Wx, Wh, b, v, c = P
    H, r, n = len(b), rng(seed), len(data)
    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:
            x, y = data[idx]
            p, states = forward(P, x)
            d = p - y
            dh = [d * v[k] for k in range(H)]
            for k in range(H):
                v[k] -= lr * d * states[-1][k]
            c[0] -= lr * d
            for t in range(len(x) - 1, -1, -1):
                previous = states[t - 1] if t > 0 else [0.0] * H
                new = [0.0] * H
                for k in range(H):
                    g = dh[k] * (1 - states[t][k] ** 2)
                    b[k] -= lr * g
                    Wx[k][0] -= lr * g * x[t][0]
                    Wx[k][1] -= lr * g * x[t][1]
                    for j in range(H):
                        new[j] += g * Wh[k][j]
                        Wh[k][j] -= lr * g * previous[j]
                dh = new
    return P


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


print(f"{'T':>3}{'baseline':>10}{'run 1':>9}{'run 2':>9}{'diff 1':>9}{'diff 2':>9}"
      f"{'run range':>15}")
for T in (2, 4, 6, 8, 10, 12):
    tr = [cut(d, T) for d in TRAIN]
    te = [cut(d, T) for d in TEST]
    tb, s = baseline_for(T), []
    for seed in (SEED + 11, SEED + 12):
        P = build(seed)
        train_model(P, tr, 30, 0.05, seed + 500)
        s.append(accuracy(P, te))
    print(f"{T:>3}{tb:>10.4f}{s[0]:>9.4f}{s[1]:>9.4f}{s[0] - tb:>+9.4f}"
          f"{s[1] - tb:>+9.4f}{abs(s[0] - s[1]):>15.4f}")

  T  baseline    run 1    run 2   diff 1   diff 2      run range
  2    0.7200   0.9500   1.0000  +0.2300  +0.2800         0.0500
  4    0.7200   0.9550   0.9550  +0.2350  +0.2350         0.0000
  6    0.6850   0.9350   0.9550  +0.2500  +0.2700         0.0200
  8    0.7450   0.9550   0.9150  +0.2100  +0.1700         0.0400
 10    0.7000   0.8850   0.8850  +0.1850  +0.1850         0.0000
 12    0.7100   0.7350   0.7150  +0.0250  +0.0050         0.0200

Training confirms what the measurement said, but not at exactly the same place. From length 2 to 10 the network beats the baseline by between 0.1700 and 0.2800. At length 12 the difference drops to 0.0250 and 0.0050: the network now says the same thing as the baseline, that is, it does not use the marker at the start at all and has turned into a rule looking only at the reading of the last period.

The untrained measurement had said that the marker could not be read back at length 10 already; the trained network, however, still produces a difference of 0.1850 at length 10. This is not a contradiction: training moves the weights away from their initial values and tunes the recurrent matrix to carry as much information as it allows. What is gained is two steps. At twelve even those two steps are not enough, because the problem is not of the kind to be solved by tuning the weights: carrying is done by multiplication, and enlarging the factor a little leads to an explosion on a long sequence, shrinking it a little leads to fading.

The run range column writes its own warning into the table. At length 8 the two runs differ by 0.0400; this is above the difference between length 8 and length 10 (0.0250). The difference added by the length and the difference added by the initial values are of the same order of magnitude, and an answer to “up to how many steps does it work” measured with a single run is therefore not reliable.

Summary

• The reading sequence is fictional: twelve periods of readings, the zero reading of the first period as the marker, and the label as the joint satisfaction of the marker and the last period exceeding the tariff tier.
• The recurrent network uses the same weights at every step; the parameter count is 61 and is independent of the sequence length.
• The difference that the marker at the first step leaves in the last hidden state is 0.92844 at length 2 and 0.00913 at length 12; the per-step factor is constant between 0.609 and 0.668.
• The accuracy of reading the marker back from the last state falls from 1.0000 to 0.4600 at length 10, that is, to chance level; in the second run the forgetting is even faster (at length 12 the difference is 0.00067).
• The trained network beats the baseline by 0.1700–0.2800 up to length 10 and by only 0.0250 and 0.0050 at length 12.
• The run range at length 8, 0.0400, is larger than the difference between length 8 and 10; the question “up to how many steps” cannot be answered with a single run.

Next Step

The hidden state does not choose to hold the information; at every step it is multiplied by the same matrix, and the magnitude of the factor determines what remains. The same factor affects the new reading and the marker at the start equally, yet the lifetimes of these two pieces of information should not be the same: the reading is unnecessary one step later, the marker is needed until the end of the sequence. The next lesson adds two decisions to the state — what to erase and what to write — and builds units that make these decisions by looking at the input. The measure stays the same and is compared directly: the plain recurrent network and the network with gated units are placed side by side on the same task, at the same lengths, each with two runs, and how many steps back the dependency can be carried is counted.