Sequence Modeling · Unfolding Graphs · Recurrent Neural Networks

§10.0 Networks built for sequences

A recurrent neural network (RNN, Rumelhart 1986) is to a sequence what a convolutional network is to a grid. A CNN processes an image $\mathbf{X}$ ; an RNN processes an ordered list of values $x^{(1)}, \dots, x^{(\tau)}$ — words in a sentence, frames of audio, measurements over time. And just as CNNs scale to large images and handle variable sizes, RNNs scale to sequences far longer than an unspecialized network could, and most can process variable-length inputs.

The single idea that turns a feedforward net into a recurrent one is sharing parameters across time. Consider the two sentences “I went to Nepal in 2009” and “In 2009, I went to Nepal.” To extract the year the narrator went to Nepal, we want the model to spot 2009 whether it is the sixth word or the second. A fully-connected feedforward net over fixed-length sentences has separate weights for each input position, so it must relearn the same rule at every slot. An RNN instead applies the same update rule to each step — one set of weights, reused everywhere.

Two ways to share across time — convolution vs recurrence

A 1-D convolution across a temporal sequence — a time-delay neural network — also shares parameters across time by sliding one kernel along the sequence. But it is shallow: each output depends on a small window of neighboring inputs. Recurrence shares parameters differently: each output is a function of the previous outputs, produced by the same update rule applied again and again. That recurrent formulation shares parameters through a very deep computational graph — one layer per time step.

This chapter extends the computational graph (§6.5) to include cycles: the present value of a variable influencing its own value at a future step. Those cycles are what define a recurrent network.

§10.1 Unfolding computational graphs

Start from the classical form of a dynamical system — a value that feeds back into its own definition:

The recurrence, and its unfolding

s^{(t)} = f\!\left(s^{(t-1)}; \theta\right) \quad\Longrightarrow\quad s^{(3)} = f\!\left(f\!\left(s^{(1)};\theta\right);\theta\right)

$s^{(t)}$	the STATE of the system at step t — everything carried forward	vector
$f(\cdot\,; \theta)$	the transition function, parametrized by θ — the SAME θ at every step	shared map
$s^{(t-1)}$	refers back to the same definition one step earlier — this back-reference is what makes it recurrent	vector
$f(f(\cdots))$	unfolding = apply the definition τ−1 times, turning the recurrence into a plain nested composition with no cycle	acyclic

Unfolding for $\tau = 3$ yields an expression with no recurrence left — just $f$ composed with itself — which is a plain directed acyclic graph:

Fig 10.1 — the classical dynamical system s⁽ᵗ⁾=f(s⁽ᵗ⁻¹⁾;θ) unfolded: one shared f maps each state to the next.

Now drive the system with an external input $x^{(t)}$ , and rename the state $h$ to signal that it is the network’s hidden units:

$h^{(t)} = f\!\left(h^{(t-1)}, x^{(t)}; \theta\right)$

The state $h^{(t)}$ now carries information about the whole past sequence. A network trained to predict the future from the past learns to use $h^{(t)}$ as a lossy summary of the task-relevant history $x^{(t)}, x^{(t-1)}, \dots, x^{(1)}$ — necessarily lossy, because it maps an arbitrary-length past into a fixed-length vector. A language model need only keep enough to predict the rest of the sentence; the most demanding case is an autoencoder (chapter 14) that must let $h^{(t)}$ approximately reconstruct the input.

The same recurrence can be drawn two ways — and the unfold operation maps one to the other:

Fig 10.2 — a recurrent net with no outputs. Left: the circuit (the black square = a one-step delay). Right: the same net unfolded, one node per time instance.

Writing the state after $t$ steps as one big function $g^{(t)}$ of the entire past, unfolding factorizes it into repeated applications of the single function $f$ :

$h^{(t)} = g^{(t)}\!\left(x^{(t)}, \dots, x^{(1)}\right) = f\!\left(h^{(t-1)}, x^{(t)}; \theta\right)$

That factorization buys two decisive advantages:

Fixed input size. The model is specified as a transition from one state to the next, not as a function of a variable-length history — so its input size never changes, however long the sequence.
One shared function. The same transition $f$ with the same parameters $\theta$ is used at every step. So we learn a single model that generalizes to sequence lengths never seen in training, from far fewer examples than a separate $g^{(t)}$ per length would need.

The folded graph is succinct; the unfolded graph makes the flow of information explicit — forward in time to compute outputs and losses, backward in time to compute gradients.

§10.2 Recurrent neural networks

Armed with unfolding and parameter sharing, we can design many RNNs. The workhorse — the one we return to all chapter — produces an output every step and has hidden-to-hidden recurrence (fig 10.3). Toggle it between the folded circuit and the unfolded graph, grow the length $\tau$ , and highlight a weight matrix to watch it get reused at every step:

Fig 10.3 (interactive) — the workhorse RNN. U (input→hidden), W (hidden→hidden recurrent), V (hidden→output). Slide τ and highlight U/W/V: the same 3 matrices serve every time step.

length τ = 3

Highlight a shared weight:

Only 3 weight matrices — U, W, V — plus biases parametrize the whole model. The parameter count is independent of τ: unfolding reuses one transition function f across all steps, so the model generalizes to sequence lengths never seen in training.

Three important design patterns recur throughout the chapter — they differ in where the recurrence lives, and that changes both their power and how cheaply they train:

RNN design patterns (figs 10.3–10.5) — click a cell for the trade-off.
	Recurrence	Output	Power & training
Fig 10.3	hidden → hidden	one per step	Most powerful; expensive
Fig 10.4	output → hidden	one per step	Weaker; parallelizable
Fig 10.5	hidden → hidden	single, at the end	Summarizer

Dotted-underlined cells have explanations — click one.

“Universal” — an RNN is a Turing machine

The fig 10.3 RNN is universal: any function computable by a Turing machine can be computed by a finite-size RNN of this form (Siegelmann & Sontag 1995 use 886 units). The Turing machine’s input is a specification of the function to compute, so a single fixed network suffices for all problems. This is a statement about representational power, not about how easily gradient descent finds the right weights.

Forward propagation. Take the hidden nonlinearity to be $\tanh$ and the output to be discrete (predicting words or characters), so $o^{(t)}$ holds unnormalized log-probabilities and softmax normalizes them. Starting from an initial state $h^{(0)}$ , each step $t = 1 \dots \tau$ runs:

Forward propagation (eqs 10.8–10.11)

a^{(t)} = b + W h^{(t-1)} + U x^{(t)}, \;\; h^{(t)} = \tanh\!\big(a^{(t)}\big), \;\; o^{(t)} = c + V h^{(t)}, \;\; \hat{y}^{(t)} = \operatorname{softmax}\!\big(o^{(t)}\big)

$W h^{(t-1)}$	the RECURRENT term — the previous state carried forward through the shared hidden→hidden matrix W	the memory
$U x^{(t)}$	the INPUT term — this step's input mapped through the shared input→hidden matrix U	the new evidence
$a^{(t)}$	hidden pre-activation: recurrent term + input term + bias b	\|h\| vector
$h^{(t)} = \tanh(a^{(t)})$	the new hidden STATE, squashed into (−1, 1) — the lossy summary of the past	\|h\| vector
$o^{(t)} = c + V h^{(t)}$	logits read out of the state through the shared hidden→output matrix V + bias c	\|y\| vector
$\hat{y}^{(t)}$	softmax turns the logits into a probability distribution over the discrete output	probabilities

Try a tiny numeric step. Suppose a scalar state with $b=0$ , $W=0.5$ , $U=1$ , previous state $h^{(t-1)} = 0.4$ and input $x^{(t)} = 1$ . Then $a^{(t)} = 0 + 0.5(0.4) + 1(1) = 1.2$ , so $h^{(t)} = \tanh(1.2) \approx 0.83$ — the input pushed the state up, and the recurrent term $0.2$ nudged it further using the same $W$ every step.

The loss over the whole sequence is simply the sum of the per-step negative log-likelihoods:

Total sequence loss (eqs 10.12–10.14)

L\big(\{x^{(1)},\dots,x^{(\tau)}\}, \{y^{(1)},\dots,y^{(\tau)}\}\big) = \sum_t L^{(t)} = -\sum_t \log p_{\text{model}}\big(y^{(t)} \mid x^{(1)},\dots,x^{(t)}\big)

$L^{(t)}$	per-step loss: the negative log-likelihood of the correct target y⁽ᵗ⁾ given all inputs up to t	scalar
$\sum_t$	the sequence loss is just the SUM of per-step losses over all τ steps	scalar
$p_{\text{model}}(y^{(t)}\mid\cdots)$	read off as the y⁽ᵗ⁾ entry of the output distribution ŷ⁽ᵗ⁾	probability

The price of power. Computing this gradient runs a forward pass left-to-right through the unrolled graph, then a backward pass right-to-left. The runtime is $O(\tau)$ and cannot be parallelized — each step needs the previous one — and every forward state must be stored until the backward pass reuses it, so memory is $O(\tau)$ too. Back-propagation applied to the unrolled graph is called back-propagation through time (BPTT). The hidden-to-hidden RNN is very powerful, but expensive to train. Is there a cheaper alternative? That question — and the exact BPTT gradient equations — come next: teacher forcing and computing the gradient.

Check yourself — unfolding and the recurrent neural network

1.Why does a recurrent network share the same parameters across every time step, rather than learning separate weights per position?

2.What are the two advantages the book gives for unfolding a recurrent computation into a computational graph?

3.In the workhorse RNN (fig 10.3), what do the weight matrices U, W, and V connect?

4.The RNN of figure 10.3 that produces an output each step with hidden-to-hidden recurrence is described as “universal.” What does that mean, and what is its training cost?

5.In the UnfoldLab widget, you increase τ from 3 to 5 and highlight the W matrix. What do you observe, and what does it teach?

5 questions