Recurrent Neural Networks

The big picture

Think of a clerk who reads a long list of orders, one at a time, and keeps one summary sheet. Each order is read, the sheet is rewritten with the same method every time, and the old sheet is discarded. At the end, the clerk’s sheet holds a summary of the whole list. A recurrent neural network works like that clerk. The sheet is the hidden state , one number per hidden unit, and the method is one set of weights used at every step.

Chapter 10.1 showed the unfolding that makes this precise. This page adds the parts a network needs in practice: an output at every step, a loss, and gradients that flow back through time.

In the demo below, the clerk reads five words. The card is a single number, and each word moves it. The word values are invented for this demo and are not learned, so read the demo for the mechanism, not for the meaning of the words.

The card changes by a fixed rule each time, and the rule has the same form at every word. Words read early still influence the card after many words, although their influence fades. Sections 1 and 5 turn this picture into equations.

The forward pass

The book gives the forward pass for one common design: a recurrent network with hidden-to-hidden connections, an output at every step, and a softmax over discrete outputs. It starts from an initial state , which the book leaves to the designer. The demo below uses . Then, for each step from 1 to , four updates are applied:

• Equation 10.8 adds the bias , the recurrent term and the input term . This sum is the pre-activation .
• Equation 10.9 squashes each entry into the range (−1, 1) with the hyperbolic tangent, giving the new hidden state.
• Equation 10.10 reads an output vector from the hidden state. These entries are unnormalized log probabilities.
• Equation 10.11 turns them into probabilities with the softmax, so that the entries add up to 1.

The demo uses a toy network with two hidden units and three symbols A, B and C. The symbols are one-hot inputs. The weights were chosen for this page and are not from the book. Press Feed A, Feed B or Feed C to feed a sequence, one step at a time.

Predict first. The network has read only the symbol A. Which symbol does it give the highest probability to next?

Each step depends on the one before. The hidden state after depends on all three symbols you fed, which is why the forward pass cannot be split over time: each step waits for the one before it. The book notes that the runtime is O() and cannot be reduced by parallelization, because the forward graph is inherently sequential. The memory cost is also linear in .

The loss over time

The network is trained on a sequence of targets , one target for each step. At each step the loss measures how wrong the prediction is. The book uses the negative log probability that the model gives to the correct target:

The sequence loss is the sum of the step losses (the book writes it in the form of equations 10.12 and 10.13):

The book points out that the loss should follow the task. Cross-entropy is the usual choice for a discrete output, and mean squared error is the cross-entropy of a unit Gaussian output, so the same framework covers it.

This module uses the natural logarithm, so the loss is measured in nats. The choice of base only rescales the loss. A probability of 1 for the correct symbol gives zero loss, and a probability close to 0 gives a large loss.

Predict first. The model gives the correct symbol probability 0.5 at each of four steps. What is the total loss?

Choose a value to see the answer.

Each step contributes its own term, so one badly predicted step can dominate the sum. The total does not depend on the order in which the steps are listed. The sum is the quantity that gradient descent reduces, and Section 5 explains how its gradient is computed.

Equation 10.12 writes the loss as a function of the whole input and target sequences. The forward pass is the step that makes the per-step losses available, and it is the reason the loss cannot be computed in parallel over time.

Three wirings of the recurrence

The forward pass above used one wiring. The book shows three common designs, and they differ in which connections exist. Figure 10.3 has hidden-to-hidden connections and an output at every step. Figure 10.4 has no hidden-to-hidden connections: the only link to the next step is the output. Figure 10.5 has hidden-to-hidden connections and a single output at the end, which summarizes the sequence.

Predict first. Which of the three figures has no hidden-to-hidden connection?

Choose a figure to see the answer.

The book states that the wiring of Figure 10.3 is universal: any function a Turing machine can compute can be computed by a finite network of this kind, after a number of steps that grows linearly with the Turing machine’s steps and with the input length. The book also states that the wiring of Figure 10.4 is strictly less powerful and cannot simulate a universal Turing machine, because its only link forward is the output. The book adds that unless that output is very high-dimensional and rich, Figure 10.4 will usually lack important information from the past. Its advantage is that it is easier to train, because each step can be trained in isolation.

The single-output wiring of Figure 10.5 is the natural choice when the task is to read a whole sequence and produce one answer. Figure 10.3 is the representative design that the rest of the chapter follows.

Teacher forcing

The wiring of Figure 10.4 has one attractive property. Because the only link forward is the output, the training target at each step can be used as the input to the next step. The book calls this teacher forcing. The likelihood of the sequence factorizes into one-step predictions, and each prediction can be trained in isolation:

In equation 10.16 the prediction for is conditioned on the true previous target , not on the model’s own guess. This is the maximum likelihood criterion at work.

The price is a mismatch. At test time the true targets are unknown, so the model must feed its own outputs back, and its inputs are then different from the ones it saw in training. The demo below makes that gap visible. In this toy, the model predicts the next symbol correctly with probability whenever its input is correct, and its prediction depends only on the input it receives.

In this toy the two runs share the same random draws, so the only difference is the input. In free running, each prediction comes from the previous output, so one wrong output becomes the next input and the error carries forward. The book suggests two remedies: train on both teacher-forced and free-running inputs, or gradually replace the true inputs with generated ones (curriculum learning).

Figure 10.6 of the book draws the same two situations as a train-time graph and a test-time graph. The book also notes that teacher forcing alone avoids back-propagation through time only when the model has no hidden-to-hidden connections. Once the hidden units depend on earlier steps, BPTT is needed, and some models are trained with both.

Back-propagation through time

Gradients are computed by applying ordinary back-propagation to the unrolled graph. No specialized algorithm is needed, and the result can be used with any general-purpose gradient-based training method. The procedure is called back-propagation through time (BPTT). The book starts from the loss and works backwards. The gradient of the loss with respect to each output is the predicted probability minus the one-hot target:

At the last step the hidden state feeds only the last output, so its gradient follows from equation 10.19. At every earlier step the hidden state feeds both its own output and the next hidden state, so the two contributions add, as in equation 10.20:

In equation 10.21 the first term carries the gradient back through the recurrent weights and the derivative of the tanh, written as . The second term carries it back through the output weights. The gradient from the future is therefore multiplied by at every step. This repeated multiplication is the source of the long-term difficulty that the book returns to in Section 10.7.

Predict first. In the one-unit case, with and the hidden state close to zero, the recurrent term multiplies the gradient from the next step by about what?

Choose a value to see the answer.

The table runs backwards from the last step. Each row takes the row below it, multiplies by , and adds the gradient from its own output. When that factor is larger than 1 in size, the gradient grows as it travels back in time. The book returns to this problem later in the chapter, when it discusses long-term dependencies. Here it is only the product in equation 10.21.

Gradients of shared weights

The same weight matrices appear at every step, so their gradients are sums over steps. The book introduces dummy variables , copies of that are each used only at step . The gradient of each copy is taken on its own, and the total gradient of is the sum of the copies:

Equation 10.26 gives the total gradient for . Each step contributes the hidden-state gradient, scaled by the tanh derivative and multiplied by the hidden state of the step before. The gradients of (equations 10.27 and 10.28), of (equation 10.23) and of the output weights (equations 10.22 and 10.24) follow the same pattern.

The demo below shows the contributions of the steps to the gradient of the recurrent weight, using the same one-unit network as Section 5. The bars add up to the total, which is checked against a numerical derivative.

Notice that the gradient can be close to zero even when every step contributes. The contributions have different signs, and their sum is what matters for the update.

Recurrent networks as graphical models

When the network is trained with a predictive log-likelihood, such as equation 10.12, it learns the distribution of the next target given the past inputs, as in equation 10.29. If the outputs also feed back into the network, the conditioning includes past targets, as in equation 10.30:

The book also views the network as a probabilistic model over the sequence of targets.

The negative log-likelihood of a sequence is then the sum of one term per step (equations 10.32 and 10.33).

Figure 10.7 draws the fully connected graph, where each target may depend on every earlier one. Figure 10.8 adds a hidden state. Its key point is that the same conditional form and the same parameters are used at every step. The demo compares the number of entries in a table of probabilities with the number of parameters of the recurrent network.

Two assumptions sit behind this view. A Markov assumption keeps only edges from the last few values, which is cheap but ignores the distant past. RNNs are useful when a value far back may still matter in a way the recent values do not capture. The parameter sharing assumes stationarity: the relation between one step and the next does not depend on t. The book notes that the price of the saving is that optimizing the parameters may be difficult, and that a missing value in the middle of a sequence is hard to predict.

Predict first. A table for a joint distribution over sequences of 5 symbols, each taking one of 10 values, has how many entries?

Choose a value to see the answer.

The table needs entries, which grows exponentially with the length. The recurrent network reuses the same input, recurrent, output and bias matrices at every step, so its count does not depend on . The count depends on the hidden size , which is a design choice.

The book also discusses how a sample is generated, and how its length is set. Three mechanisms are described: an extra end-of-sequence symbol in the vocabulary, an extra Bernoulli output that decides at each step whether to stop, and an extra output that predicts the length before the sequence is generated. This extra output adds an input to the recurrent update so that the update knows whether it is near the end. The book bases this approach on the decomposition in equation 10.34:

A fixed context

Often the network is given one fixed input, a context, that describes the whole output sequence. In the book’s Figure 10.9 the vector enters at every step through a weight matrix . The book uses this for tasks such as image captioning, where one image is the input and a sentence is the output. The demo below also uses a variant in which the context only sets the initial state . This derivation is added here and is not printed in the book.

Figure 10.10 adds connections from the output at each step to the hidden state at the next step. This removes the conditional-independence assumption of the earlier wiring, because the outputs can then depend on one another:

Equation 10.35 is the factorization that holds when the outputs are conditionally independent given the inputs. The output-to-hidden connections of Figure 10.10 allow the joint distribution to take any form. The two sequences still have the same length in this model, and the book removes that restriction in Section 10.4.

Predict first. Only the initial state carries the context, and the memory is . Does the difference between two contexts stay large at step 10?

Choose an answer to see the result.

In this scalar demo, which is added here and is not printed in the book, the state is when the context enters at every step. If it enters only through the initial state, the update is after . With a memory below 1, the initial-state effect shrinks at each step. With the context entering at every step, the input keeps pushing the state, so the two contexts stay apart.

• The forward pass applies one tanh update and one softmax per step, and each step’s hidden state depends on every earlier input.
• The loss is the sum of the per-step negative log probabilities of the correct targets. Its gradient follows from back-propagation through the unrolled graph.
• Back-propagation through time adds the contributions of all steps to each shared weight. The recurrent path multiplies the gradient by the recurrent weight and the tanh derivative at every step.
• Teacher forcing trains each step on true inputs, which decouples the steps, but at test time the model sees its own outputs, and the two can differ.
• A recurrent network has a fixed number of parameters, while a table over sequences grows exponentially with the length.
• A context can enter at every step, at the initial state, or both. The choice decides whether the context influence persists or fades.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 10.2 (pages 378–393), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.