Machine Learning from First Principles

Chapter 18 · Part IV: Deep Learning

Recurrent Networks and Sequence Models

Text, speech, video, and sensor streams are sequences of varying length. Recurrent networks process them one step at a time with a learned memory; understanding why that memory fades, and how gates fix it, explains both the LSTM and the move to attention.

After this chapter you will be able to

  • Map sequence tasks (one-to-many, many-to-one, many-to-many) to recurrent architectures.
  • Write the forward pass of a recurrent network and derive backpropagation through time.
  • Explain vanishing and exploding gradients through products of Jacobians, and use gradient clipping.
  • Write the LSTM and GRU equations and explain why the cell state preserves gradients.
  • Build encoder–decoder models, train them with teacher forcing, and decode with greedy and beam search.
  • Describe image captioning with a CNN encoder and a recurrent decoder, with and without attention.

The networks of the previous chapters map a fixed-size input to a fixed-size output. Many problems involve sequences: a sentence to translate, an audio clip to transcribe, a video to describe, a stream of sensor readings to monitor. Sequences have variable length, and the meaning of each element depends on its context. Recurrent neural networks (RNNs) handle both by applying the same function at every step while carrying a hidden state from one step to the next. Transformers (Chapter 19) have since replaced them in most applications, but the ideas introduced here (sequence-to-sequence learning, teacher forcing, beam search, the analysis of gradients through time, gating) remain essential, and recurrent models are returning in the form of state-space models.

18.1Sequences and Sequence Tasks

Sequence problems come in a few shapes:

  • One-to-many. A fixed input produces a sequence: image captioning (an image in, a sentence out).
  • Many-to-one. A sequence produces a single output: sentiment classification of a review, activity recognition from a sensor trace.
  • Many-to-many, aligned. One output per input step: tagging each word with its part of speech, labeling each video frame.
  • Many-to-many, unaligned. An input sequence produces an output sequence of a different length: machine translation, speech recognition, summarization.

Language modeling, predicting the next element of a sequence from the previous ones, is the many-to-many aligned case with the targets shifted by one, and it is the self-supervised task behind large language models (Chapter 24).

18.2Recurrent Neural Networks

A recurrent network reads inputs $\vx_1,\vx_2,\dots,\vx_T$ one at a time and updates a hidden state $\vh_t\in\R^n$ that summarizes everything seen so far:

$$\vh_t=\tanh\big(\mW_{hh}\vh_{t-1}+\mW_{xh}\vx_t+\vb_h\big),\qquad \vy_t=\mW_{hy}\vh_t+\vb_y, \tag{18.1}$$

with $\vh_0=\mathbf 0$. The same weights are used at every step, so the network handles sequences of any length with a fixed number of parameters, the temporal analog of weight sharing in convolutions (Chapter 17). Unrolling the recurrence over $T$ steps gives a deep feed-forward network with $T$ layers that share weights, one output $\vy_t$ per step, and a loss that sums the per-step losses:

$$\Loss=\sum_{t=1}^T\Loss_t(\vy_t,\text{target}_t). \tag{18.2}$$

For a many-to-one task only the last step has a loss.

Character-level language models. Feed a text one character at a time as one-hot vectors, and train $\vy_t$ (through a softmax) to predict character $t+1$. To generate text, sample a character from the predicted distribution, feed it back as the next input, and repeat. Dividing the logits by a temperature $\tau$ before the softmax controls the randomness: $\tau<1$ gives conservative, repetitive text, $\tau>1$ creative but error-prone text. Trained on Shakespeare, source code, or mathematics written in LaTeX, such models learn spelling, punctuation, indentation, and matching brackets, and individual hidden units can be found that track quotes or line length (Karpathy et al. 2016).

18.3Backpropagation Through Time

Training applies ordinary backpropagation to the unrolled graph, which is called backpropagation through time (BPTT) (Werbos 1990). Because $\mW_{hh}$ is used at every step, its gradient sums contributions from every step, and the loss at step $t$ depends on the hidden state at an earlier step $k$ through all the intermediate states:

$$\pd{\Loss}{\mW_{hh}}=\sum_{t=1}^T\sum_{k=1}^t\pd{\Loss_t}{\vh_t}\Bigg(\prod_{j=k+1}^{t}\pd{\vh_j}{\vh_{j-1}}\Bigg)\frac{\partial^+\vh_k}{\partial\mW_{hh}}, \tag{18.3}$$

where $\partial^+\vh_k/\partial\mW_{hh}$ is the “immediate” derivative that treats $\vh_{k-1}$ as a constant. In code, nobody evaluates this double sum: the backward pass walks from $t=T$ down to $1$, carrying $\partial\Loss/\partial\vh_t$ and accumulating the weight gradients, exactly like backpropagation through $T$ layers.

Truncated BPTT. Memory grows with the sequence length, since every hidden state must be stored for the backward pass. For long sequences, split them into chunks of, say, 100 steps; carry the hidden state forward across chunk boundaries, but backpropagate only within each chunk. The model can still use information from far back, through the carried state, but it cannot learn dependencies longer than a chunk.

18.4Vanishing and Exploding Gradients

The product in Equation (18.3) is the crux. For the network Equation (18.1),

$$\pd{\vh_j}{\vh_{j-1}}=\diag\big(1-\vh_j^2\big)\,\mW_{hh},\qquad \Bigg\Vert\prod_{j=k+1}^{t}\pd{\vh_j}{\vh_{j-1}}\Bigg\Vert\le\big(\sigma_{\max}(\mW_{hh})\big)^{t-k}, \tag{18.4}$$

because $|\tanh'|\le1$. If the largest singular value of $\mW_{hh}$ is below 1, the contribution of step $k$ to the gradient at step $t$ shrinks exponentially in the lag $t-k$: the network cannot learn long-range dependencies, because their gradient signal is buried under the short-range ones (Bengio et al. 1994). If the recurrent matrix has eigenvalues above 1, the product can instead grow exponentially, and a single step can throw the parameters far away (Pascanu et al. 2013). This is the deep-network problem of Section 16.1 in its worst form: the depth is the sequence length, and every layer has the same weight matrix, so its spectrum is raised to a power.

Remedies. Gradient clipping (Section 16.5) handles explosion: rescale the gradient whenever its norm exceeds a threshold. Vanishing has no such quick fix. Careful initialization (for example an orthogonal $\mW_{hh}$, whose singular values are all 1) helps at the start of training, but the real solution is to change the architecture so that information can flow across many steps along a path whose Jacobian is close to the identity, as residual connections do across layers.

18.5Long Short-Term Memory

The long short-term memory (LSTM) network (Hochreiter and Schmidhuber 1997) adds a second state, the cell $\vc_t$, that is updated additively and controlled by multiplicative gates with values between 0 and 1. From $\vh_{t-1}$ and $\vx_t$ it computes four vectors, each with its own weights:

$$\begin{gathered} \vi_t=\sigma(\mW_i[\vh_{t-1};\vx_t]+\vb_i),\qquad \vf_t=\sigma(\mW_f[\vh_{t-1};\vx_t]+\vb_f),\\ \vo_t=\sigma(\mW_o[\vh_{t-1};\vx_t]+\vb_o),\qquad \vg_t=\tanh(\mW_g[\vh_{t-1};\vx_t]+\vb_g),\\ \vc_t=\vf_t\odot\vc_{t-1}+\vi_t\odot\vg_t,\qquad \vh_t=\vo_t\odot\tanh(\vc_t). \end{gathered} \tag{18.5}$$

The input gate $\vi_t$ decides how much of the candidate $\vg_t$ to write into the cell, the forget gate $\vf_t$ (added by Gers et al. (2000)) how much of the old cell to keep, and the output gate $\vo_t$ how much of the cell to expose as the hidden state.

Why it works. Along the cell path, $\partial\vc_t/\partial\vc_{t-1}=\diag(\vf_t)$ plus terms that pass through the gates. Backpropagating from step $t$ to step $k$ along this path multiplies the gradient by $\prod_{j=k+1}^t\vf_j$ elementwise, with no weight matrix and no squashing derivative. When the forget gates are near 1, the gradient passes almost unchanged over many steps: the cell is an uninterrupted highway, just like the identity path of a residual connection (Section 16.2), except that the network learns when to open and close it. Initializing the forget-gate bias $\vb_f$ to a positive value such as 1 makes “remember” the default at the start of training.

The GRU. The gated recurrent unit (Cho et al. 2014) merges the cell and the hidden state and uses two gates:

$$\begin{gathered} \vz_t=\sigma(\mW_z[\vh_{t-1};\vx_t]),\qquad \vr_t=\sigma(\mW_r[\vh_{t-1};\vx_t]),\\ \tilde\vh_t=\tanh(\mW[\vr_t\odot\vh_{t-1};\vx_t]),\qquad \vh_t=(1-\vz_t)\odot\vh_{t-1}+\vz_t\odot\tilde\vh_t . \end{gathered} \tag{18.6}$$

The update gate $\vz_t$ interpolates between keeping the old state and writing a new candidate; the reset gate $\vr_t$ lets the candidate ignore the past. GRUs have fewer parameters than LSTMs and perform similarly on most tasks.

Deeper and bidirectional. Recurrent layers stack: the hidden states of one layer are the inputs of the next. When the whole sequence is available in advance (tagging, not generation), a bidirectional RNN runs one network forward and another backward in time and concatenates their states, so every position sees both its past and its future.

18.6Sequence-to-Sequence Models

For unaligned many-to-many tasks such as translation, the encoder–decoder or sequence-to-sequence model (Sutskever et al. 2014; Cho et al. 2014) uses two RNNs. The encoder reads the source sequence $\vx_1,\dots,\vx_S$ and its final state becomes a context vector $\vc$. The decoder is a conditional language model that generates the target one token at a time, starting from a special start token and stopping when it emits an end token:

$$p(y_1,\dots,y_T\mid\vx)=\prod_{t=1}^Tp(y_t\mid y_1,\dots,y_{t-1},\vc). \tag{18.7}$$

Teacher forcing. During training, the decoder is fed the correct previous token $y_{t-1}$ at every step, not its own prediction, and the loss is the sum of the cross-entropies of the correct tokens. This makes training parallel across target positions and stable. At test time, however, the decoder must consume its own predictions, which may be wrong in ways it never saw during training; this mismatch is called exposure bias.

The bottleneck and attention. Squeezing a whole source sentence into one fixed-size vector $\vc$ loses information, and translation quality of early seq2seq models fell with sentence length. Attention (Bahdanau et al. 2015) fixed this by letting the decoder, at every step, compute a weighted average of all encoder states, with weights that depend on the decoder’s current state. Attention turned out to be so effective that the Transformer (Chapter 19) dropped recurrence altogether.

18.7Decoding: Greedy and Beam Search

Generating the most probable output sequence $\argmax_{\vy}p(\vy\mid\vx)$ exactly is intractable: there are $V^T$ sequences for a vocabulary of size $V$. Greedy decoding picks the most probable token at each step, but an early choice that looks best locally can force a poor continuation. Beam search keeps the $B$ best partial sequences (the beam) at every step:

Algorithm 18.1  Beam search
  1. Input: model $p(y_t\mid y_{<t},\vx)$, beam width $B$, maximum length $T$
  2. beam $\gets\{(\langle\text{start}\rangle,\ \text{score }0)\}$
  3. for $t=1,\dots,T$:
    1. candidates $\gets$ every unfinished sequence in the beam extended by every token $v$, with score $+\log p(v\mid\cdot)$
    2. beam $\gets$ the $B$ highest-scoring candidates (finished sequences are kept as they are)
    3. if all sequences in the beam have ended:
      1. stop
  4. return the finished sequence with the best length-normalized score

Because every token adds a negative log-probability, raw scores favor short outputs; dividing the score by the length raised to a power $\alpha\in[0.6,1]$ (length normalization) corrects this. Beam widths of 4 to 10 are typical for translation. For open-ended generation, such as dialogue or stories, beam search produces bland and repetitive text, and sampling with a temperature or nucleus sampling (Chapter 24) works better.

18.8Image Captioning

Image captioning combines the two halves of this part of the book: a convolutional network that understands the image and a recurrent network that writes the sentence. In Show and Tell (Vinyals et al. 2015), a CNN pretrained on ImageNet encodes the image into a feature vector that initializes (or is fed as the first input to) an LSTM language model, which is trained with teacher forcing on human-written captions and decoded with beam search. The model is a conditional language model, Equation (18.7) with the image in the place of the source sentence.

A single vector forces the decoder to rely on a summary of the whole image. Show, Attend and Tell (Xu et al. 2015) keeps the CNN’s spatial grid of feature vectors $\va_1,\dots,\va_L$ (for example $14\times14$ positions) and at each step computes attention weights $\alpha_{t,i}$ from the decoder state, feeding the LSTM the context $\sum_i\alpha_{t,i}\va_i$. Visualizing the weights shows the model looking at the dog when it writes “dog” and at the frisbee when it writes “frisbee”. Captions are evaluated against several human references with n-gram overlap metrics such as BLEU and CIDEr, which correlate only loosely with human judgment. Today, captioning is one capability of the vision–language models of Chapter 23. Project 10 builds both the LSTM and the Transformer version on synthetic scenes.

18.9Beyond Recurrence

Recurrent networks process tokens one after another, so training cannot be parallelized across positions, and the hidden state is a fixed-size bottleneck however long the input. Transformers remove both limitations at the cost of attention that is quadratic in the sequence length, and they replaced RNNs in language, speech, and vision. But recurrence has a decisive advantage at inference: generating each token costs the same no matter how long the context is, while a Transformer’s cost per token grows with it. State-space models (SSMs), borrowed from control theory and signal processing, use a recurrence that is linear in the state:

$$\vh_t=\bar{\mA}\,\vh_{t-1}+\bar{\mB}\,x_t,\qquad y_t=\mathbf C\vh_t . \tag{18.8}$$

Because the recurrence is linear, unrolling it gives $y_t=\sum_{k\ge0}\mathbf C\bar{\mA}^k\bar{\mB}\,x_{t-k}$, a convolution, so the whole output sequence can be computed in parallel during training (as a long convolution or with a parallel scan), while generation runs as a recurrence with a constant-size state. Mamba (Gu and Dao 2023) made the matrices depend on the input (selective SSMs), giving the model gate-like control over what to remember, and closed much of the quality gap to attention on language. Hybrids that interleave such layers with attention are an active direction for long-context models.

18.10Implementation

The listing below measures the vanishing gradient directly. A batch of sequences is passed through a freshly initialized vanilla RNN and an LSTM (with forget-gate bias 1), and we compare the gradient of the loss at the last step with respect to the first input and the last input. The task is a memory task: the class is the first token, followed by $T-1$ noise tokens.

import torch, torch.nn as nn, torch.nn.functional as F

def make_batch(B, T, gen):
    # the first token (one of 4 "signal" symbols) must be recalled after T-1 noise tokens
    first = torch.randint(0, 4, (B,), generator=gen)
    noise = torch.randint(4, 8, (B, T - 1), generator=gen)
    x = torch.cat([first[:, None], noise], dim=1)
    return F.one_hot(x, 8).float(), first

class Recall(nn.Module):
    def __init__(self, cell, hidden=32):
        super().__init__()
        self.rnn = (nn.RNN if cell == "rnn" else nn.LSTM)(8, hidden, batch_first=True)
        self.out = nn.Linear(hidden, 4)
        if cell == "lstm":                              # forget-gate bias 1: remember by default
            for name, p in self.rnn.named_parameters():
                if "bias_hh" in name:
                    n = p.shape[0] // 4
                    with torch.no_grad():
                        p[n:2 * n].fill_(1.0)
    def forward(self, x):
        h, _ = self.rnn(x)
        return self.out(h[:, -1])                       # predict from the last hidden state

torch.manual_seed(0)
for cell in ["rnn", "lstm"]:
    for T in [10, 30, 60]:
        model = Recall(cell)
        x, y = make_batch(256, T, torch.Generator().manual_seed(0))
        x.requires_grad_(True)
        F.cross_entropy(model(x), y).backward()         # gradient w.r.t. every input step
        g = x.grad.norm(dim=(0, 2))
        print(f"{cell:4s} T={T:2d}: |dL/dx_1| / |dL/dx_T| = {g[0] / g[-1]:.1e}")

For the vanilla RNN, the gradient reaching the first input is about $10^{-2}$ of that at the last input after 10 steps, $10^{-7}$ after 30, and $10^{-14}$ after 60: no learning signal can reach the token that matters. The LSTM’s ratio decays far more slowly ($10^{-1}$, $10^{-2}$, $10^{-5}$), and training can amplify it by learning to keep the forget gates open.

18.11Common Pitfalls

Pitfall: Forgetting to clip

Recurrent networks occasionally produce enormous gradients when the recurrent Jacobians align. Without clipping, one such step can ruin hours of training; with clipping at a norm of 1 to 5 it is harmless.

Pitfall: Leaking the future

In language modeling and decoding, the input at step $t$ must not contain the target at step $t$. Off-by-one mistakes in shifting the targets produce models with suspiciously low training loss that generate nonsense.

Pitfall: Padding without masking

Batches of variable-length sequences are padded to a common length. The loss and, for bidirectional models, the hidden states must ignore the padded positions; use the masking or packed-sequence utilities of your framework.

18.12Summary

  • RNNs apply the same update $\vh_t=\tanh(\mW_{hh}\vh_{t-1}+\mW_{xh}\vx_t+\vb)$ at every step and handle one-to-many, many-to-one, and many-to-many tasks.
  • Backpropagation through time is backpropagation on the unrolled network; truncation bounds memory but also the dependencies that can be learned.
  • Gradients through time are products of Jacobians $\diag(1-\vh_j^2)\mW_{hh}$, which vanish or explode exponentially in the lag; clipping fixes explosion.
  • LSTMs and GRUs add gated, additive state updates; the cell path’s gradient is a product of forget gates, an adaptive identity path.
  • Encoder–decoder models trained with teacher forcing and decoded with beam search handle translation and captioning; attention removes the fixed-size bottleneck and led to Transformers.
  • Linear recurrences (state-space models) revive recurrence for efficient long-context inference.

18.13Exercises

  1. MathCount the parameters of a vanilla RNN, an LSTM, and a GRU with input size $d$ and hidden size $n$.
  2. MathFor a linear RNN $\vh_t=\mW\vh_{t-1}+\mathbf U\vx_t$ with diagonalizable $\mW$, express $\partial\vh_t/\partial\vh_k$ in terms of the eigenvalues of $\mW$ and explain when it vanishes or explodes.
  3. MathDerive $\partial\vc_t/\partial\vc_{t-1}$ for the LSTM, including the terms that pass through the gates, and show that it reduces to $\diag(\vf_t)$ when the gates do not depend on $\vh_{t-1}$.
  4. MathShow that beam search with beam width 1 is greedy decoding, and construct a two-step example with a vocabulary of two tokens in which greedy decoding does not find the most probable sequence but beam width 2 does.
  5. CodingTrain the RNN and the LSTM of the implementation on the memory task for $T=10,20,40$, with 2,000 steps each. At what length does each model fail to beat chance (25%)?
  6. CodingTrain a character-level LSTM language model on a text of your choice (a few hundred kilobytes), sample from it at temperatures $0.5$, $1$, and $1.5$, and report the validation loss in bits per character.
  7. MathShow that the linear recurrence Equation (18.8) with $\vh_0=\mathbf 0$ gives $y_t=\sum_{k=0}^{t-1}\mathbf C\bar{\mA}^k\bar{\mB}\,x_{t-k}$, a convolution with kernel $\mathbf C\bar{\mA}^k\bar{\mB}$. What happens to the kernel when all eigenvalues of $\bar{\mA}$ have magnitude below 1?
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.