Sequences and memory

The recurrent cell

Given an input $x_t\in\mathbb{R}^{D}$ and a state $h_{t-1}\in\mathbb{R}^{H}$, Elman’s RNN computes

with $W_x\in\mathbb{R}^{H\times D}$, $W_h\in\mathbb{R}^{H\times H}$, and $b\in\mathbb{R}^{H}$. That is $H(H+D)+H$ parameters, the same at every step: they do not grow with the length of the sentence. To predict the next word, an output layer is added, $\hat y_t=\mathrm{softmax}(W_y h_t)$ (lesson 19). In the lesson, $H=6$, $D=4$, with no bias ($60$ parameters) and random, untrained weights: only the mechanics are on display.

Blame through time

The total loss is $L=\sum_t L_t$. The blame that reaches state $h_k$ from step $T$ is the chain rule (lesson 8) applied along time:

It is a product of $T-k$ matrices. The scene shows the size of that product, $\|\partial h_T/\partial h_k\|_F/\sqrt{H}$ (the typical gain for a nudge in a random direction; $1$ = nothing is lost). Since $|1-h^2|\le 1$, if the norm of $W_h$ (its largest singular value) is $g<1$, the product falls like an exponential: $\|\partial h_T/\partial h_k\|\le g^{\,T-k}$. With a sigmoid the ceiling of the derivative is $1/4$ and everything falls faster (lesson 8). In general, Pascanu, Mikolov, and Bengio (2013) show, for a nonlinearity with $|\sigma'|\le\gamma$ ($\gamma=1$ for tanh, $\tfrac14$ for sigmoid), that $\lambda_1<1/\gamma$ is **sufficient** for the far contribution to vanish, and that $\lambda_1>1/\gamma$ is necessary for it to explode ($\lambda_1$: the largest eigenvalue of $W_h$ in absolute value).

With $\lambda_1>1/\gamma$ an explosion is not guaranteed: tanh saturates ($1-h^2\approx0$) and switches units off, as the scene shows, where with large weights the blame turns erratic, huge in some sentences and nearly zero in others. Two classic remedies: clip the gradient norm against explosion (Pascanu et al., 2013) and redesign the cell against vanishing. Bengio, Simard, and Frasconi (1994) add a dilemma: to store a datum stably against noise the dynamics must contract, and that makes long-term gradients vanish.

The LSTM

With gates $f_t,i_t,o_t\in(0,1)^H$, a candidate $\tilde c_t$, and the elementwise product $\odot$:

The belt $c_t$ is updated by addition, not by rewriting. Along it, $\partial c_t/\partial c_{t-1}=\mathrm{diag}(f_t)$ (plus indirect paths through $h$), so the blame is multiplied only by the forget gate: with $f\approx1$ it arrives nearly intact, the “constant error carousel” of the 1997 paper. The original LSTM had input and output gates; the forget gate was added by Gers, Schmidhuber, and Cummins (2000). A practical trick: initialize the bias $b_f$ near $1$ so the belt starts open (Jozefowicz et al., 2015). A layer has $4H(H+D)+4H$ parameters: four times those of the RNN. With $H=D=1000$ that is $8{,}004{,}000$. Stacked LSTMs went far: Google’s neural machine translation system (Wu et al., 2016) used eight LSTM layers in the encoder and eight in the decoder, with attention and residual connections.

In the lesson the gates are fixed numbers and there is a single cell: $c_t=f\,c_{t-1}+i_t\tanh(v_t)$, $h_t=o\tanh(c_t)$, where $v_t$ are illustrative grammatical-number cues (plural for “flowers,” singular for “market”) and $i_t=1$ at the key word. A trained network computes $f_t$ and $i_t$ from the word and the state. In 2019, Lakretz et al. found that, in an LSTM trained as a language model, long-distance number information is largely managed by two “number units,” just what our toy cell does.

In code

import numpy as np

def influence(g, steps):
    """How much of a nudge to the initial state survives after `steps` steps (2-unit RNN with tanh)."""
    c, s = np.cos(0.8), np.sin(0.8)
    Wh = g * np.array([[c, -s], [s, c]])        # a 0.8 rad rotation, scaled by g
    x = np.array([0.5, -0.3])                   # the “word” that arrives at every step
    h, P = np.zeros(2), np.eye(2)
    for _ in range(steps):
        h = np.tanh(Wh @ h + x)
        P = ((1 - h**2)[:, None] * Wh) @ P      # P = J_t · P, with J_t = diag(1 − h²) · Wh
    return np.linalg.norm(P) / np.sqrt(2)

for g in (0.5, 0.9, 1.5, 2.0):
    print(g, [round(float(influence(g, n)), 4) for n in (1, 5, 10, 20)])
# 0.5 [0.4266, 0.0083, 0.0001, 0.0]
# 0.9 [0.7679, 0.0989, 0.0152, 0.0004]
# 1.5 [1.2798, 0.8562, 1.218, 1.154]
# 2.0 [1.7064, 2.2703, 2.4696, 1.3574]

With $g=0.5$ or $0.9$ the nudge dies out; with $g=2$ it is amplified; around $g=1.5$ and with this fixed input there is a narrow window where it holds. A small move takes you out of it.

import math

cues = [0, 1.2, 0.3, -0.5, 0.2, -0.1, -0.9]      # number cue for each word (illustrative)

def cell(f, i, o):
    c = 0.0
    for t, v in enumerate(cues, start=1):
        gate_in = 1.0 if t == 2 else i               # “flowers” opens the input gate
        c = f * c + gate_in * math.tanh(v)           # the belt: forget a little, write a little
    return o * math.tanh(c)                          # what is read at the end (positive = plural)

print(round(cell(0.6, 0.8, 1.0), 3))    # -0.5   (the cue is lost and “market” wins: singular)
print(round(cell(1.0, 0.1, 1.0), 3))    # 0.638  (plural)
print(round(0.97 ** 5, 2))               # 0.86   (blame reaching “flowers” along the belt)

What comes next

The RNN and the LSTM read in a line and squeeze everything into one vector; attention (lesson 21) lets each word look directly at the others, in parallel. Before that, lesson 13 tells why deep learning took off around 2012: data, GPUs, and a few tricks, among them residual connections, which in depth play a role similar to the LSTM’s belt.