Recurrent Neural Networks (RNNs)

feedforward networks eat fixed-size vectors. sequences — text, audio, sensor streams — have no fixed size, and worse, their order carries the meaning. the recurrent neural network solves both problems with one idea: maintain a hidden state that is updated by the same function at every time step. 𐃏 parameter count stops depending on sequence length, and the state becomes a lossy summary of everything seen so far (Goodfellow, Ian, 2016).

the recurrence#

the vanilla (elman) rnn maintains a hidden state \(h_t \in \mathbb{R}^H\) driven by inputs \(x_t \in \mathbb{R}^V\):

\begin{equation} h_t = \tanh\!\left(W_h h_{t-1} + W_x x_t + b\right), \qquad o_t = W_y h_t + b_y, \end{equation}

with \(h_0\) fixed (usually zero) and \(o_t\) fed to whatever head the task demands — a softmax over the vocabulary for language modelling, a single regression output at the final step for classification.

• the same \(W_h, W_x, b\) act at every step: parameter sharing across time, exactly analogous to a convolution’s sharing across space. an rnn is a deep network whose depth is the sequence length, but whose layers are all the same layer.
• \(\tanh\) keeps the state bounded in \((-1,1)^H\); without a squashing nonlinearity the linear dynamics \(h_t = W_h h_{t-1} + \dots\) would diverge or die geometrically according to the eigenvalues of \(W_h\). (it delays this fate; as we will see, it does not escape it.)
• the state is a bottleneck by design: \(h_t\) must compress the entire prefix \(x_1, \dots, x_t\) into \(H\) numbers.

unrolling#

recursion is just a loop, and a loop can be drawn flat. unrolling the recurrence over \(T\) steps produces an ordinary feedforward computation graph with tied weights — which is what makes the network trainable by standard backpropagation.

backpropagation through time#

bptt is nothing more than backpropagation applied to the unrolled graph, with one bookkeeping subtlety: because the weights are shared, the gradient with respect to \(W_h\) is the sum of the gradients from every step at which it was used.

the gradient chain#

let the total loss be \(L = \sum_{t=1}^{T} L_t\) with \(L_t\) depending on \(h_t\) through the output head. the chain rule through the recurrence gives, for the influence of an early state \(h_k\) on a late loss \(L_t\) (\(k < t\)):

\begin{equation} \frac{\partial L_t}{\partial h_k} = \frac{\partial L_t}{\partial h_t} \, \prod_{j=k+1}^{t} \frac{\partial h_j}{\partial h_{j-1}}, \qquad \frac{\partial h_j}{\partial h_{j-1}} = \operatorname{diag}\!\bigl(1 - h_j^{\odot 2}\bigr)\, W_h, \end{equation}

where \(1 - h_j^{\odot 2}\) is the elementwise \(\tanh\) derivative (via the identity \(\tanh’ = 1 - \tanh^2\)). in the backward pass this product is applied transposed, one factor per step:

\begin{equation} \delta_{j-1} = W_h^\top \operatorname{diag}\!\bigl(1 - h_j^{\odot 2}\bigr)\, \delta_j , \end{equation}

and the parameter gradients accumulate along the way:

\begin{align*} \frac{\partial L}{\partial W_h} &= \sum_{t=1}^{T} \operatorname{diag}\!\bigl(1 - h_t^{\odot 2}\bigr)\,\delta_t \, h_{t-1}^\top, & \frac{\partial L}{\partial W_x} &= \sum_{t=1}^{T} \operatorname{diag}\!\bigl(1 - h_t^{\odot 2}\bigr)\,\delta_t \, x_t^\top, \end{align*}

where \(\delta_t = \partial L / \partial h_t\) collects both the local contribution (from \(L_t\)) and the future one (from \(\delta_{t+1}\) flowing back through \(W_h^\top\)). cost: one forward and one backward sweep, \(O(T)\) time, \(O(T)\) memory to store the states.

why the product explodes or vanishes#

the long-range factor is a product of \(t - k\) matrices of the form \(D_j W_h\) with \(D_j = \operatorname{diag}(1 - h_j^{\odot 2})\), \(\lVert D_j \rVert \le 1\). take norms:

\begin{equation} \left\lVert \prod_{j=k+1}^{t} D_j W_h \right\rVert \ \le\ \prod_{j=k+1}^{t} \lVert D_j \rVert \, \lVert W_h \rVert \ \le\ \sigma_{\max}(W_h)^{\,t-k}. \end{equation}

• if \(\sigma_{\max}(W_h) < 1\) the long-range gradient is guaranteed to vanish geometrically — the right-hand side already dies, and it is only an upper bound.
• growth is governed by the spectral radius \(\rho(W_h)\): over many steps the product behaves like \(\rho(W_h)^{t-k}\) along the dominant eigendirection (up to the damping from the \(D_j\)). \(\rho > 1\) is the signature of exploding gradients; \(\rho \le 1\) plus any tanh saturation (each \(D_j\) shrinks things further, since \(1 - h^2 < 1\) whenever \(h \ne 0\)) gives vanishing ones. 𐃏
• the uncomfortable middle: there is no setting of \(W_h\) that preserves gradient norm over hundreds of steps while also doing anything interesting with the state. long-range credit assignment in a vanilla rnn is structurally broken (Goodfellow, Ian, 2016).

numerically, with jacobians evaluated in the mild-activation regime (where \(\tanh’ \approx 1\), the regime this linearised argument describes):

import numpy as np

rng = np.random.default_rng(1)
H = 64

def gradient_norms(rho, steps=60):
    W = rng.normal(0, 1, (H, H))
    W *= rho / max(abs(np.linalg.eigvals(W)))     # rescale to spectral radius rho
    delta = rng.normal(0, 1, H); delta /= np.linalg.norm(delta)
    norms = []
    for t in range(steps):
        a = rng.normal(0, 0.3, H)                  # mild pre-activations: tanh' near 1
        delta = W.T @ ((1.0 - np.tanh(a) ** 2) * delta)   # one bptt step
        if (t + 1) % 20 == 0:
            norms.append(np.linalg.norm(delta))
    return norms

for rho in (0.7, 1.0, 1.3):
    n20, n40, n60 = gradient_norms(rho)
    print(f"rho = {rho:.1f}:  |grad| after 20 steps {n20:9.2e}, 40 steps {n40:9.2e}, 60 steps {n60:9.2e}")

rho = 0.7:  |grad| after 20 steps  8.05e-05, 40 steps  1.40e-08, 60 steps  2.28e-12
rho = 1.0:  |grad| after 20 steps  6.18e-02, 40 steps  7.61e-03, 60 steps  1.41e-03
rho = 1.3:  |grad| after 20 steps  2.43e+01, 40 steps  7.53e+02, 60 steps  3.03e+04

note the middle row: even at \(\rho = 1\) the gradient still decays, because every \(\tanh’\) factor is strictly below one — the nonlinearity itself taxes the gradient at each step.

truncated bptt#

full bptt on a million-token stream is both infeasible (memory grows with \(T\)) and pointless (the gradients from 10,000 steps back are zero anyway). truncated bptt processes the stream in windows of \(\tau\) steps:

• forward \(\tau\) steps, carrying \(h\) in from the previous window (so the state has unlimited memory),
• backward only within the window (so the gradient has horizon \(\tau\)),
• carry the final state into the next window and repeat.

the model can therefore exploit dependencies longer than \(\tau\) at inference time, but it can only learn dependencies shorter than \(\tau\) — a bias to keep in mind when choosing the window.

gradient clipping#

exploding gradients are a cliff, not a slope: a single step through a high-curvature wall can catapult the weights into garbage. the standard fix is embarrassingly blunt — if the gradient is too big, shrink it:

\begin{equation} g \leftarrow g \cdot \min\!\left(1, \frac{c}{\lVert g \rVert}\right), \end{equation}

which preserves direction while capping magnitude (elementwise clipping to \([-c, c]\), as in the code below, is the cruder cousin that also works fine in practice). clipping handles exploding gradients only; vanishing ones need an architectural fix — that is the lstm’s job.

architectural variants#

• bidirectional rnns run two chains, one left-to-right and one right-to-left, and concatenate the states: \(h_t = (\overrightarrow{h}_t, \overleftarrow{h}_t)\). the representation of token \(t\) then conditions on the whole sequence — essential for tagging tasks where the right context disambiguates, unusable for autoregressive generation (you cannot condition on a future you are about to produce).
• sequence-to-sequence (encoder-decoder): one rnn consumes the source sequence into a final state (the “thought vector”); a second rnn, initialised from that state, emits the target sequence token by token, feeding each output back in as the next input. this architecture carried machine translation until attention arrived (Sutskever, Ilya and Vinyals, Oriol and Le, Quoc V., 2014) — and its fixed-size bottleneck is precisely what attention (and then transformers) removed.
• deep rnns stack cells vertically: the state sequence of layer \(\ell\) is the input sequence of layer \(\ell + 1\). depth in space and depth in time are independent axes.

code: a char-level rnn from scratch#

everything above, in about sixty lines: one-hot characters in, softmax over next character out, bptt over a sliding window with the state carried across windows, adagrad updates, elementwise clipping. 𐃏

import numpy as np

rng = np.random.default_rng(0)

corpus = "the quick brown fox jumps over the lazy dog. " * 4
chars = sorted(set(corpus))
V = len(chars)
c2i = {c: i for i, c in enumerate(chars)}

H, T, lr = 48, 24, 0.1                       # hidden size, bptt window, adagrad rate
Wx = rng.normal(0, 0.01, (H, V))             # input -> hidden
Wh = rng.normal(0, 0.01, (H, H))             # hidden -> hidden
Wy = rng.normal(0, 0.01, (V, H))             # hidden -> output
bh, by = np.zeros(H), np.zeros(V)

def loss_and_grads(inputs, targets, h):
    xs, hs, ps = {}, {-1: h}, {}
    loss = 0.0
    # --- forward: unroll T steps ---
    for t, (ci, ct) in enumerate(zip(inputs, targets)):
        xs[t] = np.zeros(V); xs[t][ci] = 1.0
        hs[t] = np.tanh(Wx @ xs[t] + Wh @ hs[t - 1] + bh)
        z = Wy @ hs[t]
        ps[t] = np.exp(z - z.max()); ps[t] /= ps[t].sum()
        loss -= np.log(ps[t][ct])
    # --- backward: bptt ---
    g = {k: np.zeros_like(v) for k, v in
         dict(Wx=Wx, Wh=Wh, Wy=Wy, bh=bh, by=by).items()}
    dh_next = np.zeros(H)
    for t in reversed(range(len(inputs))):
        dz = ps[t].copy(); dz[targets[t]] -= 1.0        # softmax + nll gradient
        g["Wy"] += np.outer(dz, hs[t]); g["by"] += dz
        dh = Wy.T @ dz + dh_next                        # from output AND from the future
        da = (1.0 - hs[t] ** 2) * dh                    # through tanh: diag(1 - h^2)
        g["Wx"] += np.outer(da, xs[t]); g["bh"] += da
        g["Wh"] += np.outer(da, hs[t - 1])
        dh_next = Wh.T @ da                             # W_h^T carries credit backwards
    for k in g:
        np.clip(g[k], -5, 5, out=g[k])                  # gradient clipping
    return loss, g, hs[len(inputs) - 1]

# --- training loop: adagrad over sliding windows (truncated bptt) ---
params = dict(Wx=Wx, Wh=Wh, Wy=Wy, bh=bh, by=by)
mem = {k: np.zeros_like(v) for k, v in params.items()}
data = [c2i[c] for c in corpus]
h, pos = np.zeros(H), 0
for step in range(3001):
    if pos + T + 1 >= len(data):
        h, pos = np.zeros(H), 0                          # wrap: reset carry
    loss, g, h = loss_and_grads(data[pos:pos+T], data[pos+1:pos+T+1], h)
    if step % 500 == 0:
        print(f"step {step:>4}  loss/char {loss/T:.3f}  (uniform = {np.log(V):.3f})")
    for k in params:
        mem[k] += g[k] ** 2
        params[k] -= lr * g[k] / np.sqrt(mem[k] + 1e-8)  # adagrad
    pos += T

# --- sample from the trained model ---
h, ci, out = np.zeros(H), c2i["t"], "t"
for _ in range(60):
    x = np.zeros(V); x[ci] = 1.0
    h = np.tanh(Wx @ x + Wh @ h + bh)
    z = Wy @ h
    p = np.exp(z - z.max()); p /= p.sum()
    ci = int(p.argmax())                                 # greedy decode
    out += chars[ci]
print("sample:", out)

step    0  loss/char 3.332  (uniform = 3.332)
step  500  loss/char 0.015  (uniform = 3.332)
step 1000  loss/char 0.005  (uniform = 3.332)
step 1500  loss/char 0.003  (uniform = 3.332)
step 2000  loss/char 0.003  (uniform = 3.332)
step 2500  loss/char 0.002  (uniform = 3.332)
step 3000  loss/char 0.002  (uniform = 3.332)
sample: the quick brown fox jumps over the lazy dog. the quick brown

the loss starts at exactly \(\log V\) (uniform guessing over 28 characters) and collapses to near zero: with a 24-character bptt window and a 45-character period, the corpus is comfortably memorisable, and greedy decoding regenerates it verbatim — including crossing the sentence boundary, which requires state carried further than any single window. a worked application at scale lives on the sentiment analysis child page.

see also#

• long short-term memory — the architectural cure for the vanishing gradient
• sentiment analysis — an rnn earning its keep on real text
• transformers — what replaced recurrence with attention
• feedforward deep neural networks — the acyclic special case
• perceptron — the single unit all of this is built from

References#

Goodfellow, Ian (2016). Deep Learning, MIT Press.

Sutskever, Ilya and Vinyals, Oriol and Le, Quoc V. (2014). Sequence to Sequence Learning with Neural Networks.