Chapter 12Recurrent Networks

A window that will not close

Chapter 11 fixed one blindness and left the other in plain sight. The feed-forward language model concatenates $n-1$ embeddings into a single vector, that vector is its whole memory, and its length is decided before training begins. So the model reads a sentence through a slot of fixed width, and everything outside falls away exactly as it did for the counter.

Consider “the book that the committee rejected was short”, where the verb agrees with book eight words back and a window of three cannot see it. Widening the window is not a fix, because the hidden matrix $W_h$ has shape $(n-1)d \times H$ and its size grows with every word you admit. And no fixed width is ever wide enough, since sentences have no maximum length.

What we want is a model that reads left to right, keeping a running summary of everything so far and updating it at each word. The summary is a state and the update rule is a recurrence.

The recurrence

A recurrent neural network keeps a hidden state $h_t$ and rewrites it at every time step:

$$\begin{align} h_t &= \tanh\!\big(W\,x_t + U\,h_{t-1} + b_h\big), \label{eq:rnn-state}\\ \hat{y}_t &= \operatorname{softmax}\!\big(V\,h_t + b_y\big). \label{eq:rnn-out} \end{align}$$

Here $x_t$ is the embedding of the word read at step $t$, while $h_0$ is conventionally the zero vector.

Three matrices carry the whole model, where $W$ maps the current word into the state, $U$ maps the previous state into the new one, and $V$ maps the state to a score for every vocabulary word.

The important word is same, because the same $W$, $U$ and $V$ are used at every step however long the sentence, and that reuse is what recurrent means.

Equation (12.8) therefore does something the feed-forward model could not, since $h_{t-1}$ was itself computed from $h_{t-2}$ and so on back to the first word. The state at step $t$ depends on every word read so far, so there is no window and no cliff.

Unrolling, worked

Take a model small enough to print, with two hidden units, embeddings of size two and a vocabulary of three words.

$$W = \begin{pmatrix} 0.6 & -0.3 \\ 0.2 & 0.5 \end{pmatrix}, \quad U = \begin{pmatrix} 0.4 & 0.1 \\ -0.2 & 0.7 \end{pmatrix}, \quad b_h = (0.05,\, -0.05).$$

Read the sentence the dog ran, starting from $h_0 = (0, 0)$.

Follow the third row, whose input column depends only on ran while its $h_t$ depends on $h_2$, which depended on $h_1$, which depended on the. So $h_3$ is a summary of the whole prefix, nothing was thrown away, and no parameter was added to make room for it.

Why $\tanh$

The lectures ask why $\tanh$ rather than the sigmoid, and the answer is worth keeping. $\tanh$ is symmetric about the origin so its output is zero-centred, and states that average to zero train faster than states that average to $0.5$. Its derivative is also steeper, since the sigmoid’s lies in $[0, 0.25]$ while $\tanh$’s lies in $[0, 1]$.

A derivative capped at $0.25$ shrinks the gradient by at least a factor of four at every step, and Section 12.5 shows why that is fatal, with $\tanh$ merely delaying the problem rather than removing it.

Modern architectures mostly use ReLU and its variants, which pass gradient unchanged on the positive side, though ReLU has its own failure in that a unit whose input is always negative stops passing any gradient at all and never recovers. Leaky ReLU, $\max(\alpha x, x)$ with small $\alpha$, exists to prevent that.

An RNN is a language model

Equation (12.9) already produces one distribution over the vocabulary per time step, which is exactly what a language model needs. Train it by predicting the next word at every position, where the loss at step $t$ is the cross-entropy of Chapter 11 and the loss for a sentence is their sum:

$$\begin{equation} E_t \;=\; -\sum_k y_{t,k} \log \hat{y}_{t,k}, \qquad \mathcal{L} \;=\; \sum_t E_t . \label{eq:rnn-loss} \quad\text{(12.1)} \end{equation}$$

Everything from Chapter 10 carries over, since the task, the maximum likelihood objective and the perplexity of Section that section are all untouched. Only the machinery producing $\hat{y}_t$ has changed again.

The parameter count stops growing

The clearest argument for the recurrence is a table of shapes. Take $|V| = 10{,}000$, embeddings of size $d = 100$ and $H = 500$ hidden units, which are the lecture’s numbers.

Not one of those shapes mentions the length of the sentence. Compare the feed-forward model, whose $W_h$ has shape $(n-1)d \times H$ and therefore grows with every word of context admitted.

At a context of three the feed-forward model is actually smaller, the two cross over at five, and after that the comparison is not close. The left column grows without limit while the right column is a constant, and that one fact is what lets a recurrent network read a paragraph.

Backpropagation through time

Training needs gradients, and the loop has to be flattened before the chain rule can be applied. Unroll the network and a sentence of $T$ words becomes a feed-forward network $T$ layers deep, in which every layer shares the same weights.

This is backpropagation through time, and the algorithm is ordinary backpropagation on the unrolled graph, with the lectures working the three derivatives out in full. The output matrix is the easy one, because with a softmax and cross-entropy the error signal is again prediction minus target:

$$\begin{equation} \frac{\partial E_t}{\partial V} \;=\; \delta_{\text{out}}^{t}\, h_t^{\top}, \qquad \delta_{\text{out}}^{t} \;=\; \hat{y}_t - y_t . \label{eq:bptt-v} \quad\text{(12.2)} \end{equation}$$

The recurrent matrix needs one more link, through the $\tanh$:

$$\begin{equation} \frac{\partial E_t}{\partial U} \;=\; \Big[\big(V^{\top}(\hat{y}_t - y_t)\big) \odot (1 - h_t^2)\Big] h_{t-1}^{\top}, \label{eq:bptt-u} \quad\text{(12.3)} \end{equation}$$

where $\odot$ is elementwise multiplication and $1 - h_t^2$ is the derivative of $\tanh$. The input matrix is identical in form, with $x_t$ in place of $h_{t-1}$:

$$\begin{equation} \frac{\partial E_t}{\partial W} \;=\; \Big[\big(V^{\top}(\hat{y}_t - y_t)\big) \odot (1 - h_t^2)\Big] x_t^{\top}. \label{eq:bptt-w} \quad\text{(12.4)} \end{equation}$$

Because the weights are shared, the gradient for one matrix is the sum of its contributions from every time step, and that sum is where the trouble starts.

Why the memory fades

Take an error at step $\tau$ and ask what it says about the state at step $0$, where the chain rule gives one factor per step in between:

$$\begin{equation} \frac{\partial E^{[\tau]}}{\partial h^{[0]}} \;=\; \frac{\partial E^{[\tau]}}{\partial h^{[\tau]}} \prod_{t=1}^{\tau} \frac{\partial h^{[t]}}{\partial h^{[t-1]}} . \label{eq:bptt-product} \quad\text{(12.5)} \end{equation}$$

Each factor is a Jacobian, and Equation (12.8) says what one contains:

$$\begin{equation} \frac{\partial h^{[t]}}{\partial h^{[t-1]}} \;=\; \operatorname{diag}\!\big(\tanh'(\cdot)\big)\, U . \label{eq:bptt-jacobian} \quad\text{(12.6)} \end{equation}$$

So the product in Equation (12.5) behaves like $U$ raised to the power $\tau$, with the $\tanh$ derivative damping it at each step.

Repeated multiplication by a matrix is governed by its eigenvalues, and the outcome is binary. If every eigenvalue of $U$ satisfies $|\lambda| < 1$ then the product shrinks towards zero and gradients vanish, while if any eigenvalue satisfies $|\lambda| > 1$ then the product grows without bound and gradients explode. Only $|\lambda| = 1$ survives, and nothing in training holds it there.

How fast, in numbers

Treat the per-step factor as a single number and raise it to the distance travelled.

Notice how mild the failing factor is, because a per-step multiplier of $0.9$ looks harmless and yet after fifty steps it has removed more than $99$ per cent of the signal.

The forty-seven word example

The lectures make it concrete, so take this passage.

Raj entered CoffeeDay to meet his partner Dru. Raj said “Hi Dru”. In the next few hours they discussed their start-up and devised a plan to develop a product on knowledge management. After a long and fruitful discussion, Raj said goodbye to his .

The answer is partner. The passage runs to $44$ words, so the evidence is $37$ words behind the gap, and once the punctuation is counted as tokens, which is what the model actually steps over, the distance is $46$. Call it some $47$ steps and here is what reaches back that far.

$$0.01^{47} = 1.0 \times 10^{-94}, \qquad 0.5^{47} = 7.1 \times 10^{-15}, \qquad 1.2^{47} = 5266.46 .$$

A gradient of $10^{-94}$ is no update at all, so the weights that would have captured the link never move and the network cannot learn the dependency however reliably it holds.

One point deserves emphasis because it is easy to misread. The forward pass is fine and information does flow from the first step to the last. It is the backward pass that fails, since the network cannot assign blame across that distance and so never learns to use the information it is already carrying.

Two partial repairs

The two failures are not equally hard, and it is worth being clear about which one has a cheap fix.

Gradient clipping

Exploding gradients have a one line remedy, which is that if the gradient is longer than a threshold you rescale it while keeping its direction:

$$\begin{equation} \text{if } \lVert g \rVert > \text{threshold}, \quad g \;\leftarrow\; \frac{\text{threshold}}{\lVert g \rVert}\, g . \label{eq:clipping} \quad\text{(12.7)} \end{equation}$$

The last column is $1$ every time, because clipping changes how far the step goes and never which way it points, which is why it costs nothing in quality.

It does nothing whatever for vanishing gradients, where the problem is that the number is already too small and scaling it up would amplify noise along with signal.

Truncated backpropagation

Unrolling a sequence of thousands of steps is expensive in memory and slow, so truncated backpropagation through time splits the sequence into fixed segments and backpropagates within each, turning a sequence of $5000$ samples into $50$ segments of $100$.

The cost is honest and worth stating, because any dependency spanning a segment boundary is invisible to training, and choosing the boundaries at sentence ends reduces the damage without removing it.

Truncation is therefore a concession rather than a cure. It makes long sequences trainable by giving up on long dependencies, which were the reason for the recurrence in the first place.

Reading both ways

One more variant is worth naming, because it answers a limitation that has nothing to do with gradients. An RNN reads left to right, so $h_t$ summarises the past and knows nothing of the future, and for tagging a word that is often the wrong half of the sentence.

A bidirectional RNN (Schuster and Paliwal 1997) runs two independent recurrences, one forward and one backward, then concatenates their states at each position so that every output sees the whole sentence.

The restriction is obvious once stated. A bidirectional model cannot generate text, because the backward pass would need words that have not been produced yet, so it is for labelling rather than prediction. That distinction returns in Chapter 18, where BERT reads both ways and GPT reads one way, for exactly this reason.

Try it yourself. code/worked_examples/rnn.py produces every table in this chapter. --unroll prints the three step trace, --params the two parameter tables, --vanish the decay table and the forty-seven word arithmetic, and --clip the clipping demonstration with its unchanged directions.

Run it in ColabNotebookSource

What the RNN did and did not buy

The window is gone. State carries an unbounded prefix, the parameter count no longer depends on sentence length, and the same three matrices serve a sentence of any size.

In exchange we inherited a new failure, and it is specific rather than vague, since gradients decay geometrically with distance. The network therefore cannot be trained to use information from far back, even though it is perfectly capable of carrying it. Clipping handles one half and truncation manages the cost, while neither touches the vanishing case.

The repair has to be architectural. Multiplying by $U$ at every step is what destroys the gradient, so the state needs a path that does not pass through that multiplication. That path is a gate, and building one is the subject of Chapter 13.

Further reading.

Elman (1990) is the original recurrent network for language and remains the clearest short introduction. Rumelhart et al. (1986) introduced backpropagation, which backpropagation through time simply applies to an unrolled graph. Bengio et al. (1994) first proved that gradient descent cannot learn long-term dependencies in this architecture, and Pascanu et al. (2013) analyse both failures and propose clipping. Karpathy et al. (2015) inspect what a trained recurrent network actually stores in its state, and it is unusually readable. In a framework the recurrence of this chapter is torch.nn.RNN, which runs the same three lines over a whole batch of sequences at once. Graves (2014) shows what these models could already do with sequences.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• rnn.pyUnrolling, and the vanishing gradient

  What unrolling does to the parameter count, and what it does to the gradient.

  pip install numpy Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.