Recurrent neural networks

The convolutional classifier of the previous note sees a window of $k$ tokens and forgets position at pooling. The n-gram language model of the earlier note sees $n - 1$ tokens and cannot generalize across them. Both have a context of fixed, small size. This note introduces a model whose context is, in principle, the entire prefix: it reads tokens in order and keeps a summary in a vector that it updates at every step.

Notation. Input token vectors $x_1, \dots, x_T \in \mathbb R^{d}$; hidden states $h_t \in \mathbb R^{H}$; outputs $y_t$. Weight matrices $W_x \in \mathbb R^{H \times d}$, $W_h \in \mathbb R^{H \times H}$, $W_y \in \mathbb R^{K \times H}$ and biases $b, b_y$. $\odot$ is the element-wise product.

The recurrence#

$$h_t = \tanh\big(W_x x_t + W_h h_{t-1} + b\big), \qquad h_0 = 0,$$ $$y_t = W_y h_t + b_y .$$

$W_x$ reads the current token, $W_h$ carries the previous state forward, and $\tanh$ keeps every coordinate of $h_t$ in $(-1, 1)$. The same $W_x, W_h, b$ are used at every step, so the parameter count is $H d + H^2 + H$ whatever $T$ is: a sequence of 5 tokens and one of 500 run the same cell 5 or 500 times. Unrolled over time, the computation is a chain of identical cells with the hidden state as the only connection between them.

Shapes for a batch: input $[B, T, d]$, hidden states $[B, T, H]$, final state $[B, H]$. The PyTorch module nn.RNN(d, H, batch_first=True) returns both the full sequence of states and the last one.

Worked example#

Scalar case, $d = H = 1$, $W_x = 1$, $W_h = 0.5$, $b = 0$, inputs $x = (1, 0, 0)$:

$t$	$x_t$	$W_x x_t + W_h h_{t-1}$	$h_t = \tanh(\cdot)$
1	1	$1 + 0 = 1$	$0.762$
2	0	$0 + 0.381 = 0.381$	$0.363$
3	0	$0 + 0.182 = 0.182$	$0.180$

The input at step 1 is still visible in $h_3$, attenuated by $0.5$ per step and by the $\tanh$. With $W_h = 2$ instead, the same input would grow: $h_2 = \tanh(1.52) = 0.909$, $h_3 = \tanh(1.82) = 0.949$, saturating at the edge of $\tanh$‘s range. The recurrent weight decides whether the past fades or floods, and it is the same weight at every step, so whatever it does, it does $T$ times.

Step by step#

Figure

One step of a recurrent network: what goes where

The numbers in the figure follow one application of the cell:

1. Read the input. $W_x x_t$ is what the current token contributes, a vector of $H$ numbers.
2. Read the memory. $W_h h_{t-1}$ is what the previous state contributes; at the first step $h_0 = 0$ and the term vanishes.
3. Add. The two vectors and the bias $b$ are summed coordinate by coordinate.
4. Squash. $\tanh$ maps every coordinate into $(-1, 1)$; the result is the new state $h_t$.
5. Predict, if needed. $W_y h_t + b_y$ gives scores over the classes or over the vocabulary, and a softmax turns them into probabilities.
6. Pass the state on. $h_t$ becomes the $h_{t-1}$ of the next step, which repeats steps 1–5 with the same $W_x$, $W_h$ and $b$.

The models of the following notes keep this skeleton, a state carried from step to step and updated from the current input, and each changes one piece of it. The LSTM changes how the state is updated, seq2seq hands the final state from one network to another, attention lets the second network look back at every state of the first, and self-attention drops the chain altogether. Their figures use the same colours: green for inputs, blue for states, amber for weights and gates, red for outputs, and an amber outline for what a model adds to the previous one.

Two ways to use the states#

Figure

One recurrence, two ways to use its states

RNN as a classifier#

Read the whole document and use the last state as its representation: $\hat y = \mathrm{softmax}(W_y h_T + b_y)$. Unlike max-pooling, $h_T$ is computed in order, so it can in principle distinguish not good from good not. In the AG News setting of the previous note, a one-layer GRU (a gated cell from the next note) with $H = 128$ reads the same 100-dimensional Word2Vec vectors and feeds its last state to a linear layer. It has $3(100 \cdot 128 + 128 \cdot 128 + 2 \cdot 128) + 128 \cdot 4 + 4 = 88{,}836$ parameters, comparable to the convolutional models.

One practical point. The last state of a padded sequence is the state after the padding tokens, not after the last real one. Either pack the sequences so the recurrence stops at the true length, or feed the padding at the start, or read the state at index length - 1 per example.

RNN as a language model#

Produce an output at every step and make it a distribution over the vocabulary:

$$P(w_{t+1} \mid w_{\le t}) = \mathrm{softmax}(W_y h_t + b_y), \qquad W_y \in \mathbb R^{|V| \times H}.$$

This is the chain-rule factorization of the n-gram note with the Markov assumption removed: the conditional depends on $h_t$, which depends on the whole prefix. Training uses teacher forcing: the input sequence is the text shifted by one, $x = (w_1, \dots, w_{T-1})$, the targets are $y = (w_2, \dots, w_T)$, and the loss is the cross-entropy summed over positions, which is exactly the per-token negative log-likelihood whose exponential is the perplexity. Padding positions are excluded from the loss with ignore_index. At generation time the model’s own sample is fed back as the next input, as in every autoregressive model.

Shapes: ids $[B, T]$ → embeddings $[B, T, E]$ → states $[B, T, H]$ → logits $[B, T, |V|]$. The cross-entropy is computed on the flattened $[B \cdot T, |V|]$ logits against $[B \cdot T]$ targets.

Take a model over a BPE vocabulary of $|V| = 37{,}580$ tokens with $E = 256$ and $H = 512$: it has 9.6 M parameters in the input embedding, 0.39 M in the recurrent cell, and 19.3 M in the output layer, 29.3 M in total. Two thirds of the model is the output softmax, the same cost structure that drove negative sampling in Word2Vec; for a language model the full softmax is kept because the distribution itself is the output. The GPT note returns to neural language-model perplexities with a Transformer.

Gradients through time#

Training unrolls the recurrence and backpropagates through every step. The gradient of the loss at step $T$ with respect to the state at step $t$ passes through $T - t$ applications of the cell:

$$\frac{\partial h_T}{\partial h_t} = \prod_{s=t+1}^{T} \frac{\partial h_s}{\partial h_{s-1}} = \prod_{s=t+1}^{T} \mathrm{diag}\big(1 - h_s^2\big)\, W_h .$$

Each factor is the same $W_h$ scaled by the derivative of $\tanh$ (at most 1). If the largest singular value of $W_h$ is below 1 the product shrinks geometrically and the gradient vanishes: the loss at the end of a sentence cannot adjust what the cell did at its start. If it is above 1 the product can grow, and the gradient explodes (Pascanu, Mikolov and Bengio, 2013 show that this condition is necessary, not sufficient). With a scalar recurrent weight $w = 2$ and states in the linear part of $\tanh$, where its derivative is close to 1, fifty steps multiply the gradient by $2^{50} \approx 10^{15}$. The figure below, shared with the Generative Models note where the computation is written out, shows the mechanism.

Figure

Unrolled RNN with recurrent weight w = 2

Two consequences for practice. Gradient clipping rescales the gradient vector when its norm exceeds a threshold, such as 1.0, which stops explosions from destroying the weights but does nothing for vanishing. And vanishing is the binding constraint: a plain RNN learns dependencies over a handful of tokens and loses the rest, which is why “context is the whole prefix” is true of the forward pass and not of what the model learns (Bengio, Simard and Frasconi, 1994). The next note changes the cell so that the state has an additive path with a gradient factor near 1.

What changed#

	CNN classifier	N-gram LM	RNN
Context	$k$ tokens per filter	$n - 1$ tokens	Whole prefix (in principle)
Parameters vs length	Independent	Table grows with data	Independent
Position	Lost at pooling	Last $n-1$ only	Encoded in state order
Generalizes across tokens	Yes (embeddings)	No	Yes
Generation	No	Yes	Yes, with $\lvert V \rvert$-way output
Parallel over $T$	Yes	—	No: $h_t$ needs $h_{t-1}$

Limitations#

• Short effective memory. Gradients vanish over tens of steps; the state cannot be trained to keep information for long.
• Sequential computation. Step $t$ waits for step $t - 1$, so an RNN cannot use a GPU’s parallelism along the sequence. Training time grows linearly with $T$ per example, and the Transformer note will make this the central argument against recurrence.
• One state for everything. A single vector $h_T$ must summarize the whole input. For classification that is adequate; for translating a 30-word sentence it is the bottleneck that the seq2seq note runs into.
• Padding interacts with the last state. Variable lengths need packing or masking that the convolutional model did not.

What you should remember#

• $h_t = \tanh(W_x x_t + W_h h_{t-1} + b)$: the same cell at every step, parameters independent of length, state carries the prefix.
• Classifier: last state → linear. Language model: every state → softmax over $|V|$, trained by teacher forcing on the shifted sequence with padding ignored.
• The gradient through $T - t$ steps is a product of $T - t$ copies of $\mathrm{diag}(1 - h^2)W_h$; it vanishes or explodes geometrically. Clipping handles explosion only.
• Recurrence is sequential: no parallelism along the sequence.

Notebook#

Two notebooks. Cell numbers count every cell, markdown included, from 1. Quoted numbers come from the run saved with the course; cells changed since then for current library versions have no saved output.

week02_NN_text_classification.ipynb, cells 40–43: SimpleRNN wraps nn.GRU(100, 128, batch_first=True) and a linear layer on the last hidden state, trained with the same loop as the convolutional models for 5 epochs. The final printout is absent from the saved outputs, so the course has no accuracy to compare this GRU with the convolutional classifiers and the TF-IDF baseline. The classifier takes the final state after the padding tokens rather than after the last real token, the simplification discussed under RNN as a classifier.

week03_lm.ipynb:

• Cells 46–49 BPE-tokenize the joke corpus and build a 37,580-entry vocabulary with fixed ids for <pad> (0) and <unk> (1).
• Cell 51 builds batches: each joke is cut to 128 tokens, inputs are s[:-1], targets s[1:], both padded with 0.
• Cell 52 defines SimpleRNNLM: nn.Embedding(V, 256, padding_idx=0), nn.RNN(256, 512, batch_first=True), nn.Linear(512, V), the 29.3 M-parameter model counted in RNN as a language model.
• Cell 53 runs one epoch: cross-entropy with ignore_index=0, gradient-norm clipping at 1.0, and perplexity as $\exp$ of the token-weighted mean loss (set to $\infty$ above a loss of 20 to avoid overflow). Cell 55 trains for three epochs with AdamW at $3 \times 10^{-3}$ and batches of 64; the run saved with the course was interrupted after a few batches, so there are no saved perplexities. The softmax over 37,580 tokens makes this cell practical only on a CUDA GPU, as the markdown cell before it says.

Next#

The recurrence gives the model a memory and the gradient takes it away. The next note keeps the recurrence and redesigns the cell: a separate memory line that is updated additively and gates that decide what to write, keep and read, so that the gradient along the memory line is a product of factors close to 1 rather than of $W_h$.

References#

• J. L. Elman. Finding Structure in Time. Cognitive Science, 14(2), 1990. The simple recurrent network.
• Y. Bengio, P. Simard, P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2), 1994.
• R. Pascanu, T. Mikolov, Y. Bengio. On the difficulty of training recurrent neural networks. ICML, 2013. The product-of-Jacobians analysis and gradient clipping.
• T. Mikolov, M. Karafiát, L. Burget, J. Černocký, S. Khudanpur. Recurrent neural network based language model. Interspeech, 2010.
• I. Goodfellow, Y. Bengio, A. Courville. Deep Learning. MIT Press, 2016. Chapter 10 (sequence modelling, teacher forcing, long-term dependencies).