7 Recurrent Networks and Sequence Modelling

Course week 7.

Learning objectives

Distinguish sequence tasks by what the network reads and writes
Explain recurrence, the hidden state and shared parameters across time
Trace sequence generation and distinguish teacher forcing from inference
Explain backpropagation through time and why gradients can vanish or explode
Describe how LSTM and GRU gates control retained and new information
Explain the encoder–decoder pattern in translation and image captioning

No previous study of recurrent networks is assumed.

Chapter 6 showed how a network can produce a prediction at every image location. Some visual tasks require a different kind of output. An image caption is a sequence of words whose length varies, and choosing each word requires information from both the image and the caption produced so far.

This chapter develops recurrent networks, which process a sequence by updating a running state. We use a simple copying task to follow how a network reads and generates sequences, examine how it learns across many steps, and then apply the same ideas to translation and image captioning.

7.1 Sequence modelling

A sequence is an ordered collection of elements, such as the frames of a video or the words of a caption. Order matters: rearranging the frames changes the action we see, and rearranging words can change a sentence’s meaning. Sequence lengths may also vary. A video may contain many frames or only a few; an image caption may need three words or fifteen.

Sequence tasks differ in their inputs and outputs. Video classification maps many frames to one label, while image captioning maps one image to many words. Frame labelling produces one output for each input frame; translation produces an output sequence that may differ in length and word order. Figure 7.1 places these arrangements side by side.

Five diagrams in two rows, each headed by an arrangement and a task: one to one, image classification; one to many, image captioning writing a dog sits eos; many to one, video classification of three frames as running; many to many in step, frame labelling walk walk stand; many to many read then write, translation of ibhola lami elibomvu into my red ball eos, with a dashed line between reading and writing. — Figure 7.1: Sequence tasks differ in what they read and what they write. Classification reads one image and writes one label; captioning writes a sequence from one image; video classification reads a sequence of frames and writes one label; frame labelling writes a label for every frame; translation, as implemented here, reads the whole sentence before writing. Blue cells read, teal cells write, and gold arrows carry the state.

Two arrangements are central to this chapter. Captioning is a one-to-many task: an image provides the visual input, and the network generates words one at a time until it emits a stop symbol. Translation maps one sequence to another, often producing a sequence of a different length, and corresponding words need not appear in matching positions. We will examine an encoder–decoder arrangement that reads the full input before generating its output. To make the flow of information easier to follow, we use a simpler task: copying a short string of digits. For this copying task, we require the model to finish reading before it begins writing, so it has to retain the information needed to reproduce the string.

7.2 Recurrence

A recurrent neural network (RNN) processes a sequence by updating a hidden state. At each step, it combines the next input with the previous state to produce a new state. This state is a fixed-length vector that learns to summarise information relevant to the task. Its size stays the same as more inputs are read.

The operation that updates the state is called a recurrent cell. The same cell uses the same learned parameters at every timestep. Longer sequences therefore require more computation, but no additional parameters.

Let $x_t$ represent the input at step $t$, and $h_{t-1}$ the previous hidden state. The update is

\[ h_t=f_W(x_t,h_{t-1}), \]

where $W$ denotes the cell’s learned parameters. The first step uses an initial state $h_0$, often set to zero. The state carries information between steps of one sequence; for a new, independent sequence, the encoder starts again from its initial state. A simple recurrent cell computes

\[ h_t=\tanh(W_xx_t+W_hh_{t-1}+b). \]

Here, $W_x$ is the learned input-to-hidden weight matrix, $W_h$ is the learned hidden-to-hidden weight matrix, and $b$ is the learned bias vector. The two matrix products map the current input and the previous state into the hidden-state space; adding the bias and applying $\tanh$ element-wise produces the updated representation. These parameters are shared across all timesteps.

Consider the digit string 4 2 7. Each symbol is converted into an embedding: a vector retrieved from a learned table. The cell reads the embedding of 4 and updates its state, then reads 2 alongside that state, and finally reads 7. Drawing these steps side by side is called unrolling the network. The drawing shows several copies of the cell, all using the same parameters.

Left, one cell f_W whose output state h_t loops back through a box marked next step to re-enter as h_t-1. Right, three copies of f_W joined by gold states h_0 to h_3, each reading an embedding x_1, x_2, x_3 of the digits 4, 2 and 7. — Figure 7.2: An unrolled recurrent network applies one learned operation at every step. In the loop form on the left, the state the cell produces returns as its input at the next step. Unrolled, the same cell reads the embeddings of 4, 2 and 7 in turn from an initial state $h_0$, and every copy uses the same parameters $W$.

This resembles the weight sharing of a convolution, but the dependency differs. A convolution can process its positions in parallel because their inputs already exist. A recurrent cell must wait for the preceding state before computing the next one.

For our copying task, reading is followed by writing. An encoder reads the input sequence, and its final hidden state initialises a separate recurrent decoder. In this arrangement, the final encoder state is the decoder’s only direct access to the input sequence.

At each decoder step, an output layer converts the hidden state into scores for the possible symbols, and a softmax turns those scores into probabilities. A special start symbol, <sos>, supplies the first input. During generation, each selected symbol becomes the next step’s input, and the decoder stops when it selects <eos>. The desired output for our example is therefore 4 2 7 <eos>.

During training, we can supply the correct preceding symbol instead of the decoder’s own prediction. This is called teacher forcing. The model must still predict the next symbol, and cross-entropy measures its error at each output step. Because the input to the next step can differ from the decoder’s own choice, the hidden states that follow differ too.

For 4 2 7, the training inputs are <sos> 4 2 7, and the corresponding targets are 4 2 7 <eos>. Even if the decoder predicts the first digit incorrectly, its next training input is the correct digit 4.

Input 4 passes through an embedding into a teal decoder cell that takes state s_1 and passes s_2 to the next step. An output layer gives logits over the symbols 0 to 9 and eos, softmax turns them into probabilities with 7 highest and 2 second, and 7 is selected. The target 2 and the probabilities meet at a cross-entropy node. A junction feeds either the selected 7 or the target 2 to the next step. — Figure 7.3: One decoder step can be supervised and continued in two ways. At the second step of copying 4 2 7, the decoder updates its state from $s_1$ to $s_2$ and assigns its highest probability to 7, while the target is 2. Cross-entropy compares the probabilities with the target. During generation the next input is the selected 7; with teacher forcing it is the target 2. The probabilities are illustrative.

The encoder and decoder each reuse their own parameters across steps; they need not share parameters with one another. Figure 7.4 animates the complete read-then-write process and the state connecting its two halves.

Figure 7.4: An encoder–decoder copies 4 2 7 one operation at a time. The blue encoder updates its gold state with each embedded input, and its final state becomes the teal decoder’s first state. The decoder starts from <sos> and feeds each symbol it writes back in as its next input until it writes <eos>. Step through it and note where the decoder could last receive information about the input.

7.3 Learning across recurrent steps

7.3.1 Backpropagation through time

An error at the end of a sequence may depend on information read near the beginning. In our copying task, an incorrect output digit may reflect how the encoder represented that digit, how subsequent updates changed the state, or how the decoder used the final summary. Training must assign responsibility across these operations.

Backpropagation through time applies ordinary backpropagation to the unrolled network. Starting from the output losses, the chain rule carries gradients backwards through the decoder and into the encoder. Each application of the recurrent cell contributes to the gradient of its shared parameters; these contributions are added before the parameters are updated (Section D.2). Figure 7.5 shows this for three steps with a loss at each: every step sends its own contribution to the single set of parameters $W$, and the update uses their sum.

Three blue cells f_W joined by gold states h_0 to h_3, each reading an input x and producing a loss L_1, L_2, L_3 that sum to L. From each cell a red contribution dL/dW at that step runs down to a red sum feeding a box labelled shared parameters W, beside the formula dL/dW equals the sum over t of the per-step terms. — Figure 7.5: Backpropagation through time adds the gradient contributions from every step. The same parameters $W$ are used at each of the three steps, so each application contributes a term to their gradient, and the update uses the sum. Appendix D derives the individual terms.

7.3.2 Vanishing and exploding gradients

For a loss at a later step, let $g_t=\partial L/\partial h_t$ be the gradient arriving at hidden state $h_t$. For the simple tanh cell above, one step backwards gives

\[ g_{t-1}=W_h^\top\left[(1-h_t^2)\odot g_t\right]. \]

Here, $\odot$ means element-wise multiplication, and $1-h_t^2$ is the element-wise derivative of tanh. Writing $D_t=\operatorname{diag}(1-h_t^2)$ for the diagonal matrix of these derivatives, the step is $g_{t-1}=W_h^\top D_t\,g_t$, the form Figure 7.6 uses. Each backward step therefore applies $W_h^\top$ again, together with that step’s activation derivatives. For a linear recurrence, with no tanh, start from a loss at the final step $T$. The repeated multiplication is especially clear:

\[ \begin{aligned} g_{T-1} &= W_h^\top g_T,\\ g_{T-2} &= W_h^\top g_{T-1} = (W_h^\top)^2 g_T,\\ g_{T-3} &= W_h^\top g_{T-2} = (W_h^\top)^3 g_T,\\ &\vdots\\ g_{T-k} &= (W_h^\top)^k g_T. \end{aligned} \]

The nonlinear cell includes the activation derivatives between these matrix multiplications. It is their combined effect that determines whether the gradient shrinks or grows. Losses at several output steps contribute additional gradient terms, but each follows the same backward rule.

Two blue cells computing h_t-1 and h_t from inputs x, joined by gold states, feed a loss L. Below, red gradients run right to left from g_t to g_t-1 to g_t-2, each hop passing a box D then a box W_h transpose. The product g_t-2 equals W_h transpose D_t-1 W_h transpose D_t g_t is written beneath. — Figure 7.6: Backpropagation through two steps of a tanh recurrent network carries one loss’s gradient backwards. Each step back multiplies the gradient first by $D_t=\operatorname{diag}(1-h_t^2)$, the tanh derivatives, and then by $W_h^\top$, so the gradient at $h_{t-2}$ is a product of two such factors. Losses at other steps add further terms.

Backpropagating through many recurrent steps involves repeatedly multiplying gradients by the derivatives of the state updates. When these transformations repeatedly shrink the signal, contributions from distant steps can become very small, producing a vanishing gradient. The network then receives little guidance on how to change an early state to improve a much later prediction.

When the transformations repeatedly amplify the signal, the gradient can instead become very large: an exploding gradient. This can lead to unstable parameter updates. Both are learning difficulties across many steps, even when a useful representation could in principle fit into the state.

Three rows labelled vanishing, exploding and usable flow, each a chain h1 to h5 feeding a loss. Backward arrows below each chain get thinner towards h1 in the vanishing row, thicker in the exploding row, and stay the same width in the usable row. — Figure 7.7: The gradient reaching earlier steps can shrink, grow or stay usable. Each row shows the same chain of five steps with a loss after the last, and the width of each backward arrow sketches the gradient’s size; the widths are schematic, not measured. Vanishing gradients leave early steps with little signal, and exploding ones make updates unstable.

Gradient clipping helps control exploding gradients by rescaling the combined gradient when its norm exceeds a chosen threshold. It limits unusually large updates, but does not restore a learning signal that has already vanished.

7.3.3 Gated memory: LSTMs and GRUs

Long short-term memory (LSTM) networks and gated recurrent units (GRUs) modify the state update to make information easier to retain across many steps [1], [2]. They use learned gates—values between zero and one—to control how much information is carried forward or replaced. The gates depend on the current input and previous state, allowing the network to learn when to preserve information and when to update it.

An LSTM carries a separate cell state $c_t$ alongside its hidden state $h_t$. Three learned gates control how memory is retained, updated and exposed:

The forget gate, $f_t$, scales the previous cell state. A value near one retains that component; a value near zero removes it.
The input gate, $i_t$, controls how much candidate information is written into the cell state.
The output gate, $o_t$, controls how much of the transformed cell state contributes to the hidden state.

Each gate is a vector, computed by applying a sigmoid to a learned combination of the current input $x_t$ and previous hidden state $h_{t-1}$. Its components therefore lie between zero and one. A separate tanh transformation produces the candidate memory $\tilde{c}_t$. The cell update is

\[ c_t=\underbrace{f_t\odot c_{t-1}}_{\text{retained memory}}+\underbrace{i_t\odot\tilde{c}_t}_{\text{new information}}, \qquad h_t=o_t\odot\tanh(c_t). \]

A boxed LSTM cell. The gold cell state c_t-1 runs along the top through a multiply and an add to c_t. Below, four boxes fed by a shared input of x_t and h_t-1: a gold forget gate feeding the multiply, a teal input gate and teal candidate meeting at a multiply that feeds the add, and a blue output gate multiplying tanh of c_t to give h_t. — Figure 7.8: One LSTM step keeps, writes and exposes memory through three gates. The forget gate $f_t$ scales the previous cell state; the input gate $i_t$ scales a candidate $\tilde c_t$, and the two are added to give $c_t$. The output gate $o_t$ sets how much of $\tanh(c_t)$ becomes $h_t$. Gold marks keeping, teal writing and blue exposing; each gate is a learned affine map of $x_t$ and $h_{t-1}$.

Here, $\odot$ means element-wise multiplication. If the forget gate is near one and the input gate near zero, the cell can carry its previous memory forward with little change. Along this direct memory path, the backward gradient is scaled by the forget gate rather than repeatedly multiplied by the recurrent weight matrix. Figure 7.9 compares this route with the tanh RNN’s; other gradient paths pass through the gates themselves.

Two aligned rows of three unrolled steps. Top, a tanh RNN with red backward arrows labelled W_h transpose D_1, D_2, D_3. Bottom, an LSTM whose gold cell-state line passes a forget multiplication and an addition at each step, with red backward arrows labelled element-wise f_1, f_2, f_3. — Figure 7.9: The cell state gives an LSTM a backward path without repeated weight matrices. Each step back through a tanh RNN multiplies the gradient by $W_h^\top$ and the tanh derivatives; each step back along the cell state multiplies it element-wise by that step’s forget gate. With forget gates of 0.99, 0.605 of the signal survives 50 steps of this path. Other paths, through the gates, also carry gradient.

A GRU uses a single hidden state. Its update gate controls the mixture of the previous state and a candidate replacement, while its reset gate controls how much of the previous state contributes to that candidate [2]. Writing the update and reset gates as $z_t$ and $r_t$, respectively,

\[ \tilde{h}_t=\tanh\!\left(W_xx_t+W_h(r_t\odot h_{t-1})+b\right), \qquad h_t=\underbrace{z_t\odot h_{t-1}}_{\text{retained state}}+\underbrace{(1-z_t)\odot\tilde{h}_t}_{\text{new information}}. \]

A boxed GRU cell. The gold state h_t-1 runs along the top through a multiply by z_t and an add to give h_t. A gold branch drops to a blue multiply with the reset gate r_t, whose result r_t times h_t-1 enters a teal candidate box with x_t. The candidate output tilde h_t and 1 minus z_t meet at a teal multiply that feeds the add. — Figure 7.10: One GRU step mixes the previous state with a candidate through two gates. The update gate $z_t$ keeps $z_t$ of the old state and takes $1-z_t$ of the candidate. The reset gate $r_t$ scales the old state before $W_h$ is applied inside the candidate. There is no separate cell state and no output gate. As in Figure 7.8, gold marks keeping and teal writing; blue marks the reset.

The gates are sigmoid outputs computed from the current input and previous hidden state; $W_x$, $W_h$ and $b$ are learned parameters. In this convention, an update gate near one keeps the previous state, while a value near zero favours the candidate. A reset gate near zero reduces the previous state’s influence on that candidate.

Both designs provide paths that can preserve information and support gradient flow. They make long dependencies easier to learn, but do not guarantee stable gradients or perfect memory. Appendix D develops the gate equations and gradient behaviour.

Gated cells can serve as the encoder and decoder in the copying model above. The same arrangement also supports tasks in which the output describes or transforms the input.

7.4 Translation and image captioning

7.4.1 Machine translation

In machine translation, a recurrent encoder reads a sentence in one language, and a recurrent decoder generates a sentence in another [3]. The training data consists of paired source sentences and their translations. Each sentence is split into tokens—words or pieces of words—which are represented by integer IDs and then looked up in an embedding table. The source and target languages can have different vocabularies and separate embedding tables.

To make the data flow concrete, consider a single-layer GRU encoder and decoder. The encoder starts from a zero hidden state and reads the source embeddings in order. After the last source token, its final state summarises the sentence. A learned projection maps that state into the decoder’s initial hidden state; its output width must match the decoder’s hidden-state width. We write the decoder’s states as $s_t$, starting from $s_0$, to keep them apart from the encoder’s $h_t$. The encoder and decoder have separate learned parameters.

The decoder first receives the embedding of <sos>. It combines that embedding with $s_0$ to compute its next hidden state, $s_1$, then a linear output layer produces one score, or logit, for each token in the target vocabulary. Softmax turns these scores into probabilities. The state is carried to the next recurrent step, while the next token is supplied through the embedding table. These are two distinct inputs: the state carries the accumulated information, and the token says what was just written.

For the isiZulu source ibhola lami elibomvu, a target translation is my red ball. We treat each written word as one token in this example. With teacher forcing, the decoder inputs are <sos> my red ball, and the targets are my red ball <eos>. Cross-entropy is evaluated against the next target token at each step, including the end token. Its gradient passes back through the decoder, the projection and the encoder, so the source representation is learned for the translation task. For batches with padded target sequences, padding positions are excluded from the loss. A padded source must likewise use the encoder state after its last real token, rather than after the padding.

At inference, the target translation is unavailable. We can use greedy decoding: select the highest-probability token, feed its embedding into the next step, and continue until <eos> is selected. A maximum output length also prevents a model that has not learned to stop from generating indefinitely. The output can have a different length and word order from the source; in this example, ibhola (“ball”) precedes lami (“my”) and elibomvu (“red”), while English places “my” and “red” before “ball”.

Left, a blue GRU encoder starting from h_0 equals 0 reads ibhola, lami, elibomvu through a source embedding table, with the glosses ball, my, red beneath. A gold learned projection turns h_3 into s_0. Right, a teal GRU decoder takes inputs sos, my, red, ball through a target embedding table E; a shared output layer and softmax at each step are compared by CE with the targets my, red, ball, eos. — Figure 7.11: A GRU encoder–decoder translates isiZulu into English one token at a time. The encoder reads the source from a zero state, and a learned projection of its final state gives the decoder’s first state $s_0$. With teacher forcing, each decoder input is the previous target token, and cross-entropy (CE) compares each prediction with the next target. The glosses show the reordering; the model is not given them. The example phrase is from *Ibhola lami elibomvu*, by Marion Drew, translated into isiZulu by Margaret Nokuthula Zondi (African Storybook / Storybooks Saide).

7.4.2 Image captioning

Image captioning uses the same encoder–decoder pattern with an image as the input. Training pairs consist of an image and a caption describing it. A CNN computes visual features, and a recurrent decoder predicts the caption tokens. Show and Tell combines a CNN with an LSTM decoder [4]. It supplies the image representation as an input once, before the word inputs; the recurrent state then carries visual information as the caption is generated.

A simple variant projects the CNN’s features directly into a GRU’s initial hidden state. Let $I$ be the image and $F$ its CNN feature map. Flatten the feature map into a vector, then apply a learned linear map and tanh:

\[ F=\operatorname{CNN}(I),\qquad s_0=\tanh\!\left(W_{\mathrm{init}}\operatorname{vec}(F)+b_{\mathrm{init}}\right). \]

Here, $\operatorname{vec}$ flattens the feature map by listing its values in a fixed order. Features from different image locations occupy different entries in the vector, so the learned projection can give different weights to features on the left and on the right. It combines these entries into an initial hidden state of the width required by the GRU. This implementation uses a fixed image size so that the projection always receives the same number of inputs.

The decoder now follows the same process as in translation. If $y_{t-1}$ is the preceding token and $E$ is the learned embedding table, one step is

\[ s_t=\operatorname{GRU}\!\left(E[y_{t-1}],s_{t-1}\right),\qquad \ell_t=W_{\mathrm{out}}s_t+b_{\mathrm{out}}. \]

The vector $\ell_t$ contains the next-token logits. The initial token is <sos>; subsequent inputs are correct preceding tokens during teacher forcing and selected predictions during generation. The embedding table, GRU and output layer are reused at every step. During training, cross-entropy sends gradients through the output layer and recurrent steps back into the image projection and CNN. If the loss implementation accepts logits and includes softmax internally, pass $\ell_t$ directly rather than applying softmax first.

The same architecture can read a row of handwritten digits: the CNN encodes the image, and the GRU generates the digits in order from left to right. An image of 4 2 7 uses decoder inputs <sos> 4 2 7 and targets 4 2 7 <eos>. Each digit is a vocabulary symbol with a learned embedding. Place the images on a fixed-size canvas, padding shorter rows with blank space. Separately, pad target sequences when assembling a batch, exclude those padding positions from the loss, and keep the end token as a genuine prediction target. At inference, show the image and generate the digits without supplying the correct string. Lab 7 develops this example into a complete image-to-sequence recogniser.

The scene photograph passes through a CNN to a feature map F of twelve numbered positions with channels behind, flattened in order into vec(F), and projected to s_0 in a gold box. A teal GRU decoder with embedding table E and output layer W_out writes a dog sits eos from inputs sos a dog sits. An inset labelled Lab 7 shows handwritten 4 2 7 with targets 4, 2, 7, eos. — Figure 7.12: Captioning reuses the decoder architecture with a different encoder. A CNN computes the feature map $F$; flattening lists its values in a fixed order, so each position keeps its place in the vector, and a learned projection maps that vector to the decoder’s first state $s_0$. The caption shown is illustrative, not the output of a trained model. Lab 7 applies the same architecture to strips of handwritten digits, shown here from MNIST (LeCun, Cortes and Burges, CC BY-SA 3.0).

Both applications connect an input representation to a sequence generator. Translation uses a recurrent encoder to read a sentence; captioning uses a convolutional encoder to read an image. The recurrent decoder turns that representation into an output one step at a time. We now have the components needed to read a sequence, maintain a learned state and generate a new sequence from it.

The next chapter, Chapter 8, examines what information the decoder can access and how that access can change during generation.

Exercises

What does each task read and write? For each task, say what the network reads, what it writes, and whether the output has one element for each input step: (a) assigning one action label to a video clip; (b) labelling every frame of a video as “walking” or “standing”; (c) writing a caption for a photograph; (d) translating a sentence from English into isiZulu; (e) reading the digits from an image of a handwritten postcode. Which tasks naturally support an output at each input step? How would the others use the read-then-write arrangement introduced in this chapter?
Counting parameters. A simple recurrent cell reads 32-dimensional embeddings and keeps a 64-dimensional hidden state. Count the parameters in $W_x$, $W_h$ and $b$. How does the count change if the input string has 1,000 digits rather than 10? Add an output layer that scores eleven symbols, the ten digits and <eos>. Optional extension: Use the chapter’s LSTM and GRU equations, with one input matrix, one recurrent matrix and one bias for each gate or candidate, to count the parameters of an LSTM cell and a GRU cell of the same sizes.
One update at a time. A recurrent cell with a scalar state computes $h_t=\tanh(0.5\,x_t+0.8\,h_{t-1})$, starting from $h_0=0$. Each digit enters as $x_t=\text{digit}/10$. Compute $h_1$, $h_2$ and $h_3$ for the string 4 2 7, then for 7 2 4. The two strings contain the same digits. Explain why their final states differ, and what that implies about how the state represents order.
Training with the answer in hand. The target string is 3 1 4 1. Under teacher forcing, write the decoder’s input and target at each step, including <sos> and <eos>. Suppose the decoder assigns probabilities 0.6, 0.3, 0.8, 0.5 and 0.9 to the correct symbol at the five steps. Compute the cross-entropy at each step and the mean over the sequence. At inference, the decoder predicts 7 instead of 1 at the second step. What does it receive as input at the third step, and why might training with teacher forcing leave it unprepared for that input?
Repeated multiplication. In a linear recurrence with a scalar state, $h_t=w\,h_{t-1}+u\,x_t$, the gradient reaching $h_{T-k}$ is $w^k$ times the gradient at $h_T$. Compute this factor for $w=0.9$ and $w=1.1$, at $k=20$ and $k=50$. Now add a tanh, set $w=1.2$, and suppose every state along the path has the value 0.5, so that each step also contributes the derivative $1-0.5^2$. Compute the factor after 20 steps. What does the result say about judging gradient behaviour from the recurrent weight alone?
Clipping a gradient. A combined gradient is $(3,4,12)$, and gradients are clipped to a norm of 5. Compute the clipped gradient and show that its direction is unchanged. Explain why clipping can prevent a destructive update, but cannot help when the gradient reaching early steps has already become very small.
How long does an LSTM remember? One component of an LSTM’s cell state holds the value 1.0. For the next ten steps, the input gate is zero in that component. What fraction of the value remains if the forget gate is 0.9 at every step? What if it is 0.99? Describe the gate values that would erase the component and write a candidate value of 0.6 in a single step. Finally, relate the product of forget gates to the gradient along the direct cell-state path.
The GRU’s two gates. In one component, $h_{t-1}=1.0$ and the candidate is $\tilde{h}_t=-0.5$. Using the chapter’s convention, compute $h_t$ for update gates $z_t=0.9$ and $z_t=0.2$. Then explain what a reset gate near zero changes: which quantity it affects, and how that differs from the effect of a small update gate.
Where the input goes. Draw the encoder–decoder that copies 4 2 7, and the image-captioning model from this chapter. On each, mark what the decoder receives about the input, and at which step. What difficulties might arise when copying longer strings while the hidden-state size stays fixed? Distinguish a model trained on these lengths from one tested on strings much longer than those seen during training.
An image of any width. The image encoder in this chapter flattens a CNN feature map and projects it into the decoder’s initial hidden state. Why does this require a fixed image width? Design an alternative encoder for rows of handwritten digits whose images have a fixed height but varying widths. It should use the same learned parameters for every width, preserve the left-to-right order, and supply a fixed-size initial state to the decoder. Do not resize every image to the same width or assume a maximum width for padding. Sketch your design using components from this chapter and explain how information flows through it. Which parts grow with image width, and which stay fixed? Would accepting wider images necessarily mean reading longer digit strings accurately?

Lab 7

Lab 7: an image-to-sequence recogniser that reads strips of handwritten digits, with a CNN encoder and a GRU decoder trained with teacher forcing, scored by exact-string accuracy and character error rate; then longer strings than it was trained on.

Open in Colab

References

# Recurrent Networks and Sequence Modelling {#sec-sequences} *Course week 7.* ::: {.callout-note icon=false} ## Learning objectives - Distinguish sequence tasks by what the network reads and writes - Explain recurrence, the hidden state and shared parameters across time - Trace sequence generation and distinguish teacher forcing from inference - Explain backpropagation through time and why gradients can vanish or explode - Describe how LSTM and GRU gates control retained and new information - Explain the encoder–decoder pattern in translation and image captioning No previous study of recurrent networks is assumed. ::: Chapter 6 showed how a network can produce a prediction at every image location. Some visual tasks require a different kind of output. An image caption is a sequence of words whose length varies, and choosing each word requires information from both the image and the caption produced so far. This chapter develops recurrent networks, which process a sequence by updating a running state. We use a simple copying task to follow how a network reads and generates sequences, examine how it learns across many steps, and then apply the same ideas to translation and image captioning. ## Sequence modelling {#sec-sequence-shapes} A sequence is an ordered collection of elements, such as the frames of a video or the words of a caption. Order matters: rearranging the frames changes the action we see, and rearranging words can change a sentence’s meaning. Sequence lengths may also vary. A video may contain many frames or only a few; an image caption may need three words or fifteen. Sequence tasks differ in their inputs and outputs. Video classification maps many frames to one label, while image captioning maps one image to many words. Frame labelling produces one output for each input frame; translation produces an output sequence that may differ in length and word order. @fig-seq-shapes places these arrangements side by side. ![Sequence tasks differ in what they read and what they write. Classification reads one image and writes one label; captioning writes a sequence from one image; video classification reads a sequence of frames and writes one label; frame labelling writes a label for every frame; translation, as implemented here, reads the whole sentence before writing. Blue cells read, teal cells write, and gold arrows carry the state.](../figures/ch07/fig-seq-shapes.png){#fig-seq-shapes fig-alt="Five diagrams in two rows, each headed by an arrangement and a task: one to one, image classification; one to many, image captioning writing a dog sits eos; many to one, video classification of three frames as running; many to many in step, frame labelling walk walk stand; many to many read then write, translation of ibhola lami elibomvu into my red ball eos, with a dashed line between reading and writing."} Two arrangements are central to this chapter. Captioning is a one-to-many task: an image provides the visual input, and the network generates words one at a time until it emits a stop symbol. Translation maps one sequence to another, often producing a sequence of a different length, and corresponding words need not appear in matching positions. We will examine an encoder–decoder arrangement that reads the full input before generating its output. To make the flow of information easier to follow, we use a simpler task: copying a short string of digits. For this copying task, we require the model to finish reading before it begins writing, so it has to retain the information needed to reproduce the string. ## Recurrence {#sec-recurrence} A **recurrent neural network** (RNN) processes a sequence by updating a **hidden state**. At each step, it combines the next input with the previous state to produce a new state. This state is a fixed-length vector that learns to summarise information relevant to the task. Its size stays the same as more inputs are read. The operation that updates the state is called a **recurrent cell**. The same cell uses the same learned parameters at every timestep. Longer sequences therefore require more computation, but no additional parameters. Let $x_t$ represent the input at step $t$, and $h_{t-1}$ the previous hidden state. The update is $$ h_t=f_W(x_t,h_{t-1}), $$ where $W$ denotes the cell’s learned parameters. The first step uses an initial state $h_0$, often set to zero. The state carries information between steps of one sequence; for a new, independent sequence, the encoder starts again from its initial state. A simple recurrent cell computes $$ h_t=\tanh(W_xx_t+W_hh_{t-1}+b). $$ Here, $W_x$ is the learned input-to-hidden weight matrix, $W_h$ is the learned hidden-to-hidden weight matrix, and $b$ is the learned bias vector. The two matrix products map the current input and the previous state into the hidden-state space; adding the bias and applying $\tanh$ element-wise produces the updated representation. These parameters are shared across all timesteps. Consider the digit string `4 2 7`. Each symbol is converted into an **embedding**: a vector retrieved from a learned table. The cell reads the embedding of `4` and updates its state, then reads `2` alongside that state, and finally reads `7`. Drawing these steps side by side is called **unrolling** the network. The drawing shows several copies of the cell, all using the same parameters. ![An unrolled recurrent network applies one learned operation at every step. In the loop form on the left, the state the cell produces returns as its input at the next step. Unrolled, the same cell reads the embeddings of 4, 2 and 7 in turn from an initial state $h_0$, and every copy uses the same parameters $W$.](../figures/ch07/fig-rnn-unrolled.png){#fig-rnn-unrolled fig-alt="Left, one cell f_W whose output state h_t loops back through a box marked next step to re-enter as h_t-1. Right, three copies of f_W joined by gold states h_0 to h_3, each reading an embedding x_1, x_2, x_3 of the digits 4, 2 and 7."} This resembles the weight sharing of a convolution, but the dependency differs. A convolution can process its positions in parallel because their inputs already exist. A recurrent cell must wait for the preceding state before computing the next one. For our copying task, reading is followed by writing. An **encoder** reads the input sequence, and its final hidden state initialises a separate recurrent **decoder**. In this arrangement, the final encoder state is the decoder’s only direct access to the input sequence. At each decoder step, an output layer converts the hidden state into scores for the possible symbols, and a softmax turns those scores into probabilities. A special start symbol, `<sos>`, supplies the first input. During generation, each selected symbol becomes the next step’s input, and the decoder stops when it selects `<eos>`. The desired output for our example is therefore `4 2 7 <eos>`. During training, we can supply the correct preceding symbol instead of the decoder’s own prediction. This is called **teacher forcing**. The model must still predict the next symbol, and cross-entropy measures its error at each output step. Because the input to the next step can differ from the decoder's own choice, the hidden states that follow differ too. For `4 2 7`, the training inputs are `<sos> 4 2 7`, and the corresponding targets are `4 2 7 <eos>`. Even if the decoder predicts the first digit incorrectly, its next training input is the correct digit `4`. ![One decoder step can be supervised and continued in two ways. At the second step of copying 4 2 7, the decoder updates its state from $s_1$ to $s_2$ and assigns its highest probability to 7, while the target is 2. Cross-entropy compares the probabilities with the target. During generation the next input is the selected 7; with teacher forcing it is the target 2. The probabilities are illustrative.](../figures/ch07/fig-rnn-decoding.png){#fig-rnn-decoding fig-alt="Input 4 passes through an embedding into a teal decoder cell that takes state s_1 and passes s_2 to the next step. An output layer gives logits over the symbols 0 to 9 and eos, softmax turns them into probabilities with 7 highest and 2 second, and 7 is selected. The target 2 and the probabilities meet at a cross-entropy node. A junction feeds either the selected 7 or the target 2 to the next step."} The encoder and decoder each reuse their own parameters across steps; they need not share parameters with one another. @fig-rnn-copying-process animates the complete read-then-write process and the state connecting its two halves. :::: {#fig-rnn-copying-process} ```{=html} <iframe src="../widgets/seq2seq-bottleneck.html?frame=process" class="widget-frame" height="560" loading="lazy" allow="fullscreen" allowfullscreen title="An encoder-decoder copying 4 2 7, stepped one operation at a time from a reset state: the encoder reads the embedded digits 4, 2 and 7, updating its state from h0 to h3; h3 becomes the decoder's first state s0; the decoder then writes 4, 2, 7 and the end symbol, starting from the start symbol and feeding each symbol it writes back in as its next input."></iframe> ``` An encoder–decoder copies 4 2 7 one operation at a time. The blue encoder updates its gold state with each embedded input, and its final state becomes the teal decoder's first state. The decoder starts from `<sos>` and feeds each symbol it writes back in as its next input until it writes `<eos>`. Step through it and note where the decoder could last receive information about the input. :::: ## Learning across recurrent steps {#sec-rnn-learning} ### Backpropagation through time An error at the end of a sequence may depend on information read near the beginning. In our copying task, an incorrect output digit may reflect how the encoder represented that digit, how subsequent updates changed the state, or how the decoder used the final summary. Training must assign responsibility across these operations. **Backpropagation through time** applies ordinary backpropagation to the unrolled network. Starting from the output losses, the chain rule carries gradients backwards through the decoder and into the encoder. Each application of the recurrent cell contributes to the gradient of its shared parameters; these contributions are added before the parameters are updated (@sec-bptt). @fig-bptt-accumulation shows this for three steps with a loss at each: every step sends its own contribution to the single set of parameters $W$, and the update uses their sum. ![Backpropagation through time adds the gradient contributions from every step. The same parameters $W$ are used at each of the three steps, so each application contributes a term to their gradient, and the update uses the sum. Appendix D derives the individual terms.](../figures/ch07/fig-bptt-accumulation.png){#fig-bptt-accumulation fig-alt="Three blue cells f_W joined by gold states h_0 to h_3, each reading an input x and producing a loss L_1, L_2, L_3 that sum to L. From each cell a red contribution dL/dW at that step runs down to a red sum feeding a box labelled shared parameters W, beside the formula dL/dW equals the sum over t of the per-step terms."} ### Vanishing and exploding gradients For a loss at a later step, let $g_t=\partial L/\partial h_t$ be the gradient arriving at hidden state $h_t$. For the simple tanh cell above, one step backwards gives $$ g_{t-1}=W_h^\top\left[(1-h_t^2)\odot g_t\right]. $$ Here, $\odot$ means element-wise multiplication, and $1-h_t^2$ is the element-wise derivative of tanh. Writing $D_t=\operatorname{diag}(1-h_t^2)$ for the diagonal matrix of these derivatives, the step is $g_{t-1}=W_h^\top D_t\,g_t$, the form @fig-rnn-backward-computation uses. Each backward step therefore applies $W_h^\top$ again, together with that step’s activation derivatives. For a linear recurrence, with no tanh, start from a loss at the final step $T$. The repeated multiplication is especially clear: $$ \begin{aligned} g_{T-1} &= W_h^\top g_T,\\ g_{T-2} &= W_h^\top g_{T-1} = (W_h^\top)^2 g_T,\\ g_{T-3} &= W_h^\top g_{T-2} = (W_h^\top)^3 g_T,\\ &\vdots\\ g_{T-k} &= (W_h^\top)^k g_T. \end{aligned} $$ The nonlinear cell includes the activation derivatives between these matrix multiplications. It is their combined effect that determines whether the gradient shrinks or grows. Losses at several output steps contribute additional gradient terms, but each follows the same backward rule. ![Backpropagation through two steps of a tanh recurrent network carries one loss's gradient backwards. Each step back multiplies the gradient first by $D_t=\operatorname{diag}(1-h_t^2)$, the tanh derivatives, and then by $W_h^\top$, so the gradient at $h_{t-2}$ is a product of two such factors. Losses at other steps add further terms.](../figures/ch07/fig-rnn-backward-computation.png){#fig-rnn-backward-computation fig-alt="Two blue cells computing h_t-1 and h_t from inputs x, joined by gold states, feed a loss L. Below, red gradients run right to left from g_t to g_t-1 to g_t-2, each hop passing a box D then a box W_h transpose. The product g_t-2 equals W_h transpose D_t-1 W_h transpose D_t g_t is written beneath."} Backpropagating through many recurrent steps involves repeatedly multiplying gradients by the derivatives of the state updates. When these transformations repeatedly shrink the signal, contributions from distant steps can become very small, producing a **vanishing gradient**. The network then receives little guidance on how to change an early state to improve a much later prediction. When the transformations repeatedly amplify the signal, the gradient can instead become very large: an **exploding gradient**. This can lead to unstable parameter updates. Both are learning difficulties across many steps, even when a useful representation could in principle fit into the state. ![The gradient reaching earlier steps can shrink, grow or stay usable. Each row shows the same chain of five steps with a loss after the last, and the width of each backward arrow sketches the gradient's size; the widths are schematic, not measured. Vanishing gradients leave early steps with little signal, and exploding ones make updates unstable.](../figures/ch07/fig-recurrent-gradient-flow.svg){#fig-recurrent-gradient-flow fig-alt="Three rows labelled vanishing, exploding and usable flow, each a chain h1 to h5 feeding a loss. Backward arrows below each chain get thinner towards h1 in the vanishing row, thicker in the exploding row, and stay the same width in the usable row."} **Gradient clipping** helps control exploding gradients by rescaling the combined gradient when its norm exceeds a chosen threshold. It limits unusually large updates, but does not restore a learning signal that has already vanished. ### Gated memory: LSTMs and GRUs {#sec-gated-memory} **Long short-term memory** (LSTM) networks and **gated recurrent units** (GRUs) modify the state update to make information easier to retain across many steps [@hochreiter1997lstm; @cho2014gru]. They use learned **gates**—values between zero and one—to control how much information is carried forward or replaced. The gates depend on the current input and previous state, allowing the network to learn when to preserve information and when to update it. An LSTM carries a separate **cell state** $c_t$ alongside its hidden state $h_t$. Three learned gates control how memory is retained, updated and exposed: - The **forget gate**, $f_t$, scales the previous cell state. A value near one retains that component; a value near zero removes it. - The **input gate**, $i_t$, controls how much candidate information is written into the cell state. - The **output gate**, $o_t$, controls how much of the transformed cell state contributes to the hidden state. Each gate is a vector, computed by applying a sigmoid to a learned combination of the current input $x_t$ and previous hidden state $h_{t-1}$. Its components therefore lie between zero and one. A separate tanh transformation produces the candidate memory $\tilde{c}_t$. The cell update is $$ c_t=\underbrace{f_t\odot c_{t-1}}_{\text{retained memory}}+\underbrace{i_t\odot\tilde{c}_t}_{\text{new information}}, \qquad h_t=o_t\odot\tanh(c_t). $$ ![One LSTM step keeps, writes and exposes memory through three gates. The forget gate $f_t$ scales the previous cell state; the input gate $i_t$ scales a candidate $\tilde c_t$, and the two are added to give $c_t$. The output gate $o_t$ sets how much of $\tanh(c_t)$ becomes $h_t$. Gold marks keeping, teal writing and blue exposing; each gate is a learned affine map of $x_t$ and $h_{t-1}$.](../figures/ch07/fig-lstm-cell.png){#fig-lstm-cell fig-alt="A boxed LSTM cell. The gold cell state c_t-1 runs along the top through a multiply and an add to c_t. Below, four boxes fed by a shared input of x_t and h_t-1: a gold forget gate feeding the multiply, a teal input gate and teal candidate meeting at a multiply that feeds the add, and a blue output gate multiplying tanh of c_t to give h_t."} Here, $\odot$ means element-wise multiplication. If the forget gate is near one and the input gate near zero, the cell can carry its previous memory forward with little change. Along this direct memory path, the backward gradient is scaled by the forget gate rather than repeatedly multiplied by the recurrent weight matrix. @fig-lstm-cell-state-gradient compares this route with the tanh RNN's; other gradient paths pass through the gates themselves. ![The cell state gives an LSTM a backward path without repeated weight matrices. Each step back through a tanh RNN multiplies the gradient by $W_h^\top$ and the tanh derivatives; each step back along the cell state multiplies it element-wise by that step's forget gate. With forget gates of 0.99, 0.605 of the signal survives 50 steps of this path. Other paths, through the gates, also carry gradient.](../figures/ch07/fig-lstm-cell-state-gradient.png){#fig-lstm-cell-state-gradient fig-alt="Two aligned rows of three unrolled steps. Top, a tanh RNN with red backward arrows labelled W_h transpose D_1, D_2, D_3. Bottom, an LSTM whose gold cell-state line passes a forget multiplication and an addition at each step, with red backward arrows labelled element-wise f_1, f_2, f_3."} A GRU uses a single hidden state. Its update gate controls the mixture of the previous state and a candidate replacement, while its reset gate controls how much of the previous state contributes to that candidate [@cho2014gru]. Writing the update and reset gates as $z_t$ and $r_t$, respectively, $$ \tilde{h}_t=\tanh\!\left(W_xx_t+W_h(r_t\odot h_{t-1})+b\right), \qquad h_t=\underbrace{z_t\odot h_{t-1}}_{\text{retained state}}+\underbrace{(1-z_t)\odot\tilde{h}_t}_{\text{new information}}. $$ ![One GRU step mixes the previous state with a candidate through two gates. The update gate $z_t$ keeps $z_t$ of the old state and takes $1-z_t$ of the candidate. The reset gate $r_t$ scales the old state before $W_h$ is applied inside the candidate. There is no separate cell state and no output gate. As in @fig-lstm-cell, gold marks keeping and teal writing; blue marks the reset.](../figures/ch07/fig-gru-cell.png){#fig-gru-cell fig-alt="A boxed GRU cell. The gold state h_t-1 runs along the top through a multiply by z_t and an add to give h_t. A gold branch drops to a blue multiply with the reset gate r_t, whose result r_t times h_t-1 enters a teal candidate box with x_t. The candidate output tilde h_t and 1 minus z_t meet at a teal multiply that feeds the add."} The gates are sigmoid outputs computed from the current input and previous hidden state; $W_x$, $W_h$ and $b$ are learned parameters. In this convention, an update gate near one keeps the previous state, while a value near zero favours the candidate. A reset gate near zero reduces the previous state’s influence on that candidate. Both designs provide paths that can preserve information and support gradient flow. They make long dependencies easier to learn, but do not guarantee stable gradients or perfect memory. @sec-rnn-details develops the gate equations and gradient behaviour. Gated cells can serve as the encoder and decoder in the copying model above. The same arrangement also supports tasks in which the output describes or transforms the input. ## Translation and image captioning {#sec-rnn-applications} ### Machine translation {#sec-rnn-translation} In **machine translation**, a recurrent encoder reads a sentence in one language, and a recurrent decoder generates a sentence in another [@sutskever2014seq2seq]. The training data consists of paired source sentences and their translations. Each sentence is split into tokens—words or pieces of words—which are represented by integer IDs and then looked up in an embedding table. The source and target languages can have different vocabularies and separate embedding tables. To make the data flow concrete, consider a single-layer GRU encoder and decoder. The encoder starts from a zero hidden state and reads the source embeddings in order. After the last source token, its final state summarises the sentence. A learned projection maps that state into the decoder’s initial hidden state; its output width must match the decoder’s hidden-state width. We write the decoder’s states as $s_t$, starting from $s_0$, to keep them apart from the encoder’s $h_t$. The encoder and decoder have separate learned parameters. The decoder first receives the embedding of `<sos>`. It combines that embedding with $s_0$ to compute its next hidden state, $s_1$, then a linear output layer produces one score, or **logit**, for each token in the target vocabulary. Softmax turns these scores into probabilities. The state is carried to the next recurrent step, while the next token is supplied through the embedding table. These are two distinct inputs: the state carries the accumulated information, and the token says what was just written. For the isiZulu source `ibhola lami elibomvu`, a target translation is `my red ball`. We treat each written word as one token in this example. With teacher forcing, the decoder inputs are `<sos> my red ball`, and the targets are `my red ball <eos>`. Cross-entropy is evaluated against the next target token at each step, including the end token. Its gradient passes back through the decoder, the projection and the encoder, so the source representation is learned for the translation task. For batches with padded target sequences, padding positions are excluded from the loss. A padded source must likewise use the encoder state after its last real token, rather than after the padding. At inference, the target translation is unavailable. We can use **greedy decoding**: select the highest-probability token, feed its embedding into the next step, and continue until `<eos>` is selected. A maximum output length also prevents a model that has not learned to stop from generating indefinitely. The output can have a different length and word order from the source; in this example, `ibhola` (“ball”) precedes `lami` (“my”) and `elibomvu` (“red”), while English places “my” and “red” before “ball”. ![A GRU encoder–decoder translates isiZulu into English one token at a time. The encoder reads the source from a zero state, and a learned projection of its final state gives the decoder's first state $s_0$. With teacher forcing, each decoder input is the previous target token, and cross-entropy (CE) compares each prediction with the next target. The glosses show the reordering; the model is not given them. The example phrase is from [*Ibhola lami elibomvu*](https://global-asp.github.io/storybooks-saide/stories/zu/0143/), by Marion Drew, translated into isiZulu by Margaret Nokuthula Zondi (African Storybook / Storybooks Saide).](../figures/ch07/fig-translation-encoder-decoder.png){#fig-translation-encoder-decoder fig-alt="Left, a blue GRU encoder starting from h_0 equals 0 reads ibhola, lami, elibomvu through a source embedding table, with the glosses ball, my, red beneath. A gold learned projection turns h_3 into s_0. Right, a teal GRU decoder takes inputs sos, my, red, ball through a target embedding table E; a shared output layer and softmax at each step are compared by CE with the targets my, red, ball, eos."} ### Image captioning {#sec-rnn-captioning} **Image captioning** uses the same encoder–decoder pattern with an image as the input. Training pairs consist of an image and a caption describing it. A CNN computes visual features, and a recurrent decoder predicts the caption tokens. **Show and Tell** combines a CNN with an LSTM decoder [@vinyals2015showtell]. It supplies the image representation as an input once, before the word inputs; the recurrent state then carries visual information as the caption is generated. A simple variant projects the CNN’s features directly into a GRU’s initial hidden state. Let $I$ be the image and $F$ its CNN feature map. Flatten the feature map into a vector, then apply a learned linear map and tanh: $$ F=\operatorname{CNN}(I),\qquad s_0=\tanh\!\left(W_{\mathrm{init}}\operatorname{vec}(F)+b_{\mathrm{init}}\right). $$ Here, $\operatorname{vec}$ flattens the feature map by listing its values in a fixed order. Features from different image locations occupy different entries in the vector, so the learned projection can give different weights to features on the left and on the right. It combines these entries into an initial hidden state of the width required by the GRU. This implementation uses a fixed image size so that the projection always receives the same number of inputs. The decoder now follows the same process as in translation. If $y_{t-1}$ is the preceding token and $E$ is the learned embedding table, one step is $$ s_t=\operatorname{GRU}\!\left(E[y_{t-1}],s_{t-1}\right),\qquad \ell_t=W_{\mathrm{out}}s_t+b_{\mathrm{out}}. $$ The vector $\ell_t$ contains the next-token logits. The initial token is `<sos>`; subsequent inputs are correct preceding tokens during teacher forcing and selected predictions during generation. The embedding table, GRU and output layer are reused at every step. During training, cross-entropy sends gradients through the output layer and recurrent steps back into the image projection and CNN. If the loss implementation accepts logits and includes softmax internally, pass $\ell_t$ directly rather than applying softmax first. The same architecture can read a row of handwritten digits: the CNN encodes the image, and the GRU generates the digits in order from left to right. An image of `4 2 7` uses decoder inputs `<sos> 4 2 7` and targets `4 2 7 <eos>`. Each digit is a vocabulary symbol with a learned embedding. Place the images on a fixed-size canvas, padding shorter rows with blank space. Separately, pad target sequences when assembling a batch, exclude those padding positions from the loss, and keep the end token as a genuine prediction target. At inference, show the image and generate the digits without supplying the correct string. Lab 7 develops this example into a complete image-to-sequence recogniser. ![Captioning reuses the decoder architecture with a different encoder. A CNN computes the feature map $F$; flattening lists its values in a fixed order, so each position keeps its place in the vector, and a learned projection maps that vector to the decoder's first state $s_0$. The caption shown is illustrative, not the output of a trained model. Lab 7 applies the same architecture to strips of handwritten digits, shown here from MNIST (LeCun, Cortes and Burges, CC BY-SA 3.0).](../figures/ch07/fig-image-to-sequence-decoder.png){#fig-image-to-sequence-decoder fig-alt="The scene photograph passes through a CNN to a feature map F of twelve numbered positions with channels behind, flattened in order into vec(F), and projected to s_0 in a gold box. A teal GRU decoder with embedding table E and output layer W_out writes a dog sits eos from inputs sos a dog sits. An inset labelled Lab 7 shows handwritten 4 2 7 with targets 4, 2, 7, eos."} Both applications connect an input representation to a sequence generator. Translation uses a recurrent encoder to read a sentence; captioning uses a convolutional encoder to read an image. The recurrent decoder turns that representation into an output one step at a time. We now have the components needed to read a sequence, maintain a learned state and generate a new sequence from it. The next chapter, @sec-attention, examines what information the decoder can access and how that access can change during generation. ## Exercises {.unnumbered} 1. **What does each task read and write?** For each task, say what the network reads, what it writes, and whether the output has one element for each input step: (a) assigning one action label to a video clip; (b) labelling every frame of a video as “walking” or “standing”; (c) writing a caption for a photograph; (d) translating a sentence from English into isiZulu; (e) reading the digits from an image of a handwritten postcode. Which tasks naturally support an output at each input step? How would the others use the read-then-write arrangement introduced in this chapter? 2. **Counting parameters.** A simple recurrent cell reads 32-dimensional embeddings and keeps a 64-dimensional hidden state. Count the parameters in $W_x$, $W_h$ and $b$. How does the count change if the input string has 1,000 digits rather than 10? Add an output layer that scores eleven symbols, the ten digits and `<eos>`. **Optional extension:** Use the chapter’s LSTM and GRU equations, with one input matrix, one recurrent matrix and one bias for each gate or candidate, to count the parameters of an LSTM cell and a GRU cell of the same sizes. 3. **One update at a time.** A recurrent cell with a scalar state computes $h_t=\tanh(0.5\,x_t+0.8\,h_{t-1})$, starting from $h_0=0$. Each digit enters as $x_t=\text{digit}/10$. Compute $h_1$, $h_2$ and $h_3$ for the string `4 2 7`, then for `7 2 4`. The two strings contain the same digits. Explain why their final states differ, and what that implies about how the state represents order. 4. **Training with the answer in hand.** The target string is `3 1 4 1`. Under teacher forcing, write the decoder’s input and target at each step, including `<sos>` and `<eos>`. Suppose the decoder assigns probabilities 0.6, 0.3, 0.8, 0.5 and 0.9 to the correct symbol at the five steps. Compute the cross-entropy at each step and the mean over the sequence. At inference, the decoder predicts `7` instead of `1` at the second step. What does it receive as input at the third step, and why might training with teacher forcing leave it unprepared for that input? 5. **Repeated multiplication.** In a linear recurrence with a scalar state, $h_t=w\,h_{t-1}+u\,x_t$, the gradient reaching $h_{T-k}$ is $w^k$ times the gradient at $h_T$. Compute this factor for $w=0.9$ and $w=1.1$, at $k=20$ and $k=50$. Now add a tanh, set $w=1.2$, and suppose every state along the path has the value 0.5, so that each step also contributes the derivative $1-0.5^2$. Compute the factor after 20 steps. What does the result say about judging gradient behaviour from the recurrent weight alone? 6. **Clipping a gradient.** A combined gradient is $(3,4,12)$, and gradients are clipped to a norm of 5. Compute the clipped gradient and show that its direction is unchanged. Explain why clipping can prevent a destructive update, but cannot help when the gradient reaching early steps has already become very small. 7. **How long does an LSTM remember?** One component of an LSTM’s cell state holds the value 1.0. For the next ten steps, the input gate is zero in that component. What fraction of the value remains if the forget gate is 0.9 at every step? What if it is 0.99? Describe the gate values that would erase the component and write a candidate value of 0.6 in a single step. Finally, relate the product of forget gates to the gradient along the direct cell-state path. 8. **The GRU’s two gates.** In one component, $h_{t-1}=1.0$ and the candidate is $\tilde{h}_t=-0.5$. Using the chapter’s convention, compute $h_t$ for update gates $z_t=0.9$ and $z_t=0.2$. Then explain what a reset gate near zero changes: which quantity it affects, and how that differs from the effect of a small update gate. 9. **Where the input goes.** Draw the encoder–decoder that copies `4 2 7`, and the image-captioning model from this chapter. On each, mark what the decoder receives about the input, and at which step. What difficulties might arise when copying longer strings while the hidden-state size stays fixed? Distinguish a model trained on these lengths from one tested on strings much longer than those seen during training. 10. **An image of any width.** The image encoder in this chapter flattens a CNN feature map and projects it into the decoder’s initial hidden state. Why does this require a fixed image width? Design an alternative encoder for rows of handwritten digits whose images have a fixed height but varying widths. It should use the same learned parameters for every width, preserve the left-to-right order, and supply a fixed-size initial state to the decoder. Do not resize every image to the same width or assume a maximum width for padding. Sketch your design using components from this chapter and explain how information flows through it. Which parts grow with image width, and which stay fixed? Would accepting wider images necessarily mean reading longer digit strings accurately? ## Lab 7 {.unnumbered} ::: {.lab-pointer} [Lab 7](../labs/lab-07.ipynb){download="lab-07.ipynb"}: an image-to-sequence recogniser that reads strips of handwritten digits, with a CNN encoder and a GRU decoder trained with teacher forcing, scored by exact-string accuracy and character error rate; then longer strings than it was trained on. [![Open in Colab](../figures/colab-badge.svg)](https://colab.research.google.com/github/kleinric/cv-labs/blob/main/lab-07.ipynb) ::: ## Further reading {.unnumbered} - Hochreiter and Schmidhuber [-@hochreiter1997lstm] — the LSTM cell and its approach to retaining information across recurrent steps. - Cho et al. [-@cho2014gru] — gated recurrent units in an encoder–decoder for translation. - Sutskever et al. [-@sutskever2014seq2seq] — sequence-to-sequence learning with recurrent encoders and decoders. - Vinyals et al. [-@vinyals2015showtell] — combining a CNN image encoder with a recurrent caption generator. - Pascanu et al. [-@pascanu2013difficulty] — vanishing and exploding gradients, and gradient clipping. ## References {.unnumbered} ::: {#refs} :::