Gated Units

The hidden state of the previous lesson did not choose to hold the information. At every step it was multiplied by the same matrix, the magnitude of the factor determined what would remain, and the measured factor was 0.62 per step. The same factor was applied to both the new reading and the marker at the start, though the lifetimes of the two should differ: the reading is unnecessary one step later, the marker is needed until the end of the sequence.

The gated unit adds two separate computations to the state: how much of it is to be retained and what is to be written in its place. Both are computed from the input of that step and the state so far, that is, the unit decides separately at every step. The measure here: how many steps back does this decision carry the dependency, and does the gain come from the gate.

• AR37. The set and the split do not change. The fictional reading sequence of the previous lesson is generated with the same seed: twelve periods, 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 split is 200/100/200, and the baseline is separate for each length.
• AR38. The gated unit is built from two blocks. The update gate $u_t$ has a sigmoid output and gives a number between 0 and 1 for each unit. The candidate value $a_t$ has a hyperbolic tangent output. The new state is a mixture of the two: $h_t = u_t h_{t-1} + (1 - u_t) a_t$.
• AR39. The path the gate opens is selective, not multiplicative. If $u_t$ is close to one, the old state passes almost as it is; if it is close to zero, the candidate value is written. In the plain unit there is no such option, every step applies the same transformation.
• AR40. The bias of the update gate is initialized positive (value 1). The gate is open at the start and training learns to close it; initialization in the opposite direction requires waiting for the gate to open before learning can begin.
• AR41. The parameter counts are compared. Because the gated unit carries two blocks, it holds about twice the parameters of the plain unit at the same number of hidden units. For this reason an equal-budget plain network is also put in the table: the plain network with 9 units carries about the same parameters as the gated network with 6 units.
• AR42. The measure has two layers. The first is the share of the marker remaining in the last hidden state of the untrained network — what the structure can carry. The second is the difference of the trained network from the baseline — what it carries.
• AR43. The three structures are trained with the same budget: 30 epochs, learning rate 0.05, the same split, the same order generator. The numbers of the plain network with 6 units are identical to the previous lesson.
• AR44. No library is called; the gated unit, backpropagation through time and the training loop are written inside the lesson and are a model. The structure is referred to by its name, never abbreviated.
• AR45. Every network is run twice; in the second run only the initial values change.

The Gated Unit

# gated.py — MODEL. The FICTIONAL reading sequence of 04 is generated with the same seed.
# Plain: h_t = tanh(...). Gated: h_t = u_t * h_(t-1) + (1 - u_t) * a_t.
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
    return d


def cut(d, T):
    return ([[v / SCALE, 1.0 if v == 0.0 else 0.0] for v in d[:T]],
            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


SEQS = [reading_sequence(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 sigmoid(z):
    return 1 / (1 + math.exp(-max(-30, min(30, z))))


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


def forward(P, x):
    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)
    return sigmoid(c[0] + sum(v[k] * h[k] for k in range(H))), states


def build_gated(seed, H=HIDDEN, gate_bias=1.0):
    r = rng(seed)

    def block(b0):
        return [[[(r() * 2 - 1) * (1 / 2) ** 0.5 for _ in range(2)] for _ in range(H)],
                [[(r() * 2 - 1) * (1 / H) ** 0.5 for _ in range(H)] for _ in range(H)],
                [b0] * H]
    return [block(gate_bias), block(0.0),
            [(r() * 2 - 1) * (1 / H) ** 0.5 for _ in range(H)], [0.0], H]


def forward_gated(P, x):
    U, A, v, c, H = P
    h, states = [0.0] * H, []
    for t in range(len(x)):
        u = [sigmoid(U[2][k] + U[0][k][0] * x[t][0] + U[0][k][1] * x[t][1]
                     + sum(U[1][k][j] * h[j] for j in range(H))) for k in range(H)]
        a = [math.tanh(A[2][k] + A[0][k][0] * x[t][0] + A[0][k][1] * x[t][1]
                       + sum(A[1][k][j] * h[j] for j in range(H))) for k in range(H)]
        new = [u[k] * h[k] + (1 - u[k]) * a[k] for k in range(H)]
        states.append((h, u, a, new))
        h = new
    return sigmoid(c[0] + sum(v[k] * h[k] for k in range(H))), states


def params_plain(H):
    return 2 * H + H * H + H + H + 1


def params_gated(H):
    return 2 * (2 * H + H * H + H) + H + 1


print(f"{'structure':<22}{'hidden units':>12}{'parameters':>11}")
for name, H, f in (("plain recurrent", HIDDEN, params_plain), ("plain recurrent", 9, params_plain),
                   ("gated unit", HIDDEN, params_gated)):
    print(f"{name:<22}{H:>12}{f(H):>11}")
print(f"\n{'T':>3}{'baseline':>15}")
for T in (2, 4, 8, 12):
    print(f"{T:>3}{baseline_for(T):>15.4f}")

structure             hidden units parameters
plain recurrent                  6         61
plain recurrent                  9        118
gated unit                       6        115

  T       baseline
  2         0.7200
  4         0.7200
  8         0.7450
 12         0.7100

The mixing relation of the gated unit is a single line, and what matters is the form of that line: the old state is multiplied by a coefficient computed from the input of that step, and a candidate is added on top. In the plain unit the remaining share was determined by the magnitude of the weights and was the same for all steps.

The parameter table sets the rule of the comparison. With the same 6 units the gated network holds 115 parameters and the plain network 61; comparing these two directly would credit the gate with a difference that is not its own. For this reason a plain network with 9 units and 118 parameters is also tabulated.

The Trace of the Marker in Three Structures

# trace.py — the measure of 04 repeated in three structures on the UNTRAINED network: only the
# first step of the sequence is changed, the difference in the last hidden state is measured.
def pairs(d, T):
    x = cut(d, T)[0]
    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 trace(P, T, gated):
    f = 0.0
    for d in SEQS:
        a, b = pairs(d, T)
        if gated:
            ia, ib = forward_gated(P, a)[1][-1][3], forward_gated(P, b)[1][-1][3]
        else:
            ia, ib = forward(P, a)[1][-1], forward(P, b)[1][-1]
        f += sum(abs(ia[k] - ib[k]) for k in range(len(ia)))
    return f / len(SEQS)


STRUCTURES = [("plain 6", lambda t: build(t, 6), False),
              ("plain 9", lambda t: build(t, 9), False),
              ("gated 6", lambda t: build_gated(t, 6), True)]
print(f"{'T':>3}" + "".join(f"{name + ' k' + str(k + 1):>12}"
                            for name, _, _ in STRUCTURES for k in range(2)))
first = {}
for T in (2, 4, 8, 12):
    row = []
    for name, f, gated in STRUCTURES:
        for k, seed in enumerate((SEED + 11, SEED + 12)):
            u = trace(f(seed), T, gated)
            row.append(u)
            if T == 2:
                first[(name, k)] = u
    print(f"{T:>3}" + "".join(f"{u:>12.5f}" for u in row))
print("share remaining at length 12 relative to the trace at length 2:")
for i, (name, f, gated) in enumerate(STRUCTURES):
    for k, seed in enumerate((SEED + 11, SEED + 12)):
        print(f"  {name} k{k + 1}: {trace(f(seed), 12, gated) / first[(name, k)]:.4%}")

  T  plain 6 k1  plain 6 k2  plain 9 k1  plain 9 k2  gated 6 k1  gated 6 k2
  2     0.92844     1.39970     2.23946     1.75462     0.32959     0.46329
  4     0.34417     0.24972     0.65803     0.40122     0.17443     0.22063
  8     0.05986     0.01560     0.10734     0.01796     0.07712     0.06693
 12     0.00913     0.00067     0.01600     0.00083     0.03077     0.02610
share remaining at length 12 relative to the trace at length 2:
  plain 6 k1: 0.9837%
  plain 6 k2: 0.0478%
  plain 9 k1: 0.7143%
  plain 9 k2: 0.0473%
  gated 6 k1: 9.3350%
  gated 6 k2: 5.6329%

Raw numbers are misleading, the ratio lines correct them. The gated network carries less trace than the plain network at length 2 (0.32959 against 0.92844), because the update gate slows the new information too. What is to be measured is not the trace at the start but the share remaining after ten steps.

That share is 0.98% and 0.05% in the plain network with 6 units; in the gated network it is 9.34% and 5.63%. The gate enlarges the remaining share of the marker ten to a hundred times.

The two middle columns write what the gate is not. Widening the plain network from 6 units to 9 lowers the remaining share from 0.98% to 0.71%: the forgetting speed results not from the number of units but from the multiplication applied at every step. Only the form of the mixing relation changes the carrying capacity.

How Many Steps Back

# train_model.py — MODEL: three structures on the same data, 30 epochs, learning rate 0.05.
# Backpropagation through time is written by hand.
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, new = (states[t - 1] if t > 0 else [0.0] * H), [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 train_gated(P, data, epochs, lr, seed):
    U, A, v, c, H = P
    r, n = 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_gated(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][3][k]
            c[0] -= lr * d
            for t in range(len(x) - 1, -1, -1):
                previous, u, a, _ = states[t]
                new = [0.0] * H
                for k in range(H):
                    du = dh[k] * (previous[k] - a[k]) * u[k] * (1 - u[k])
                    da = dh[k] * (1 - u[k]) * (1 - a[k] ** 2)
                    U[2][k] -= lr * du
                    A[2][k] -= lr * da
                    for i2 in (0, 1):
                        U[0][k][i2] -= lr * du * x[t][i2]
                        A[0][k][i2] -= lr * da * x[t][i2]
                    new[k] += u[k] * dh[k]
                    for j in range(H):
                        new[j] += du * U[1][k][j] + da * A[1][k][j]
                        U[1][k][j] -= lr * du * previous[j]
                        A[1][k][j] -= lr * da * previous[j]
                dh = new
    return P


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


print(f"{'T':>3}{'baseline':>10}" + "".join(f"{name + ' k' + str(k + 1):>12}"
                                           for name, _, _ in STRUCTURES for k in range(2)))
for T in (2, 4, 8, 12):
    tr = [cut(d, T) for d in TRAIN]
    te = [cut(d, T) for d in TEST]
    tb, row = baseline_for(T), []
    for name, builder, gated in STRUCTURES:
        for seed in (SEED + 11, SEED + 12):
            P = builder(seed)
            (train_gated if gated else train_model)(P, tr, 30, 0.05, seed + 500)
            row.append(accuracy(P, te, gated) - tb)
    print(f"{T:>3}{tb:>10.4f}" + "".join(f"{u:>+12.4f}" for u in row))

  T  baseline  plain 6 k1  plain 6 k2  plain 9 k1  plain 9 k2  gated 6 k1  gated 6 k2
  2    0.7200     +0.2300     +0.2800     +0.2350     +0.2800     +0.2250     +0.2650
  4    0.7200     +0.2350     +0.2350     +0.2300     +0.2450     +0.2300     +0.2550
  8    0.7450     +0.2100     +0.1700     +0.2000     +0.1800     +0.1750     +0.1800
 12    0.7100     +0.0250     +0.0050     +0.2700     +0.1700     +0.2650     +0.2050

The numbers are differences from the baseline: since the label is defined by the last period, each length has its own baseline. In the first three rows the three structures cannot be told apart — up to length 8 all of them beat the baseline by between 0.1700 and 0.2800, and a plain matrix can carry the dependency too.

The last row opens the distinction. The plain network with 61 parameters drops to 0.0250 and 0.0050, that is, to what the baseline says; the gated network gives 0.2650 and 0.2050. The dependency is carried between eight and ten steps in the plain network with 6 units, and twelve in the gated network — the whole sequence.

The third pair is not hidden and is the most important row of the lesson. The wide plain network at an equal parameter budget also carries twelve steps: 0.2700 and 0.1700. Compared with 0.2650 and 0.2050 of the gated network, there is no measurable difference between the two structures. Moreover the difference between the two runs of the wide plain network is 0.1000; it is larger than any reading of the difference between the two structures. The untrained measurement had said that the gate enlarged the remaining share ten to a hundred times; the number of the trained network neither confirms nor refutes this at this length — because training can build a slowly forgetting matrix from the weights of the plain network by moving them from their initial values.

The rule: the difference a structure adds is measurable only if the task is hard enough to force it. Twelve steps are not enough, and twelve steps is the limit of this setup; a distinction is expected to open on a longer sequence, but an unmeasured expectation does not count.

Summary

• The gated unit updates the state with $h_t = u_t h_{t-1} + (1 - u_t) a_t$; the coefficient is not constant, it is computed from the input of that step.
• With the same 6 units the gated network holds 115 parameters and the plain network 61; to equalize the budget, the plain network with 9 units and 118 parameters is also measured.
• In the untrained network the share remaining at length 12 is 0.98% and 0.05% in the plain network with 6 units, 0.71% and 0.05% in the plain network with 9 units, and 9.34% and 5.63% in the gated network; width does not change the forgetting speed.
• Up to length 8 all three structures beat the baseline by 0.1700–0.2800 and cannot be told apart.
• At length 12 the plain network with 6 units drops to 0.0250 and 0.0050; the gated network gives 0.2650 and 0.2050, and the wide plain network gives 0.2700 and 0.1700.
• The advantage of the gate over the equal-budget plain network cannot be measured at this length: the difference of 0.1000 between the two runs of the wide plain network is larger than the difference between the two structures.

Next Step

The gated unit carried the long dependency, but the form of carrying did not change: the information still had to pass through a single hidden state, and that state was rewritten at every step. A distant step arrives by being transferred over all the steps in between; it is not read directly. The next lesson asks this: what would the network gain if it could choose which step of the sequence to look at at the moment of decision. What will be measured is where the weights fall: how many of the selections go to the correct step, and does a high weight mean that that step really determines the decision.