> ## Documentation Index
> Fetch the complete documentation index at: https://aegean.ai/llms.txt
> Use this file to discover all available pages before exploring further.

# Simple RNN

> The simple RNN and backpropagation through time.

The simplest RNN has a single layer of neurons that receive the input $\mathbf{x}$.

![A single RNN layer unrolled over time, mapping each input to a hidden state](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/simple-rnn-simple-layer.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=184ef1a5b46b31a14f0b93639bcf2792)

*Simple RNN layer with $n_{neurons}$ RNN neurons that map the input to the hidden state at each time step.*

A more practical simple RNN adds recurrences between the hidden units and an output at every step.

![An RNN with hidden-to-hidden recurrence and an output and loss at each time step, shown folded and unrolled](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/rnn-hidden-recurrence.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=6d5c5bd8c4458758700ea5010959c049)

*Simple RNN with recurrences between hidden units. This architecture can compute any computable function, so it is as powerful as a [Universal Turing Machine](http://alvyray.com/CreativeCommons/BizCardUniversalTuringMachine_v2.3.pdf).*

Notice how the input $\mathbf x_{t-1}$ affects the label $\mathbf y_{t}$ through the hidden state. Notice also that the outputs $\mathbf y$ are conditionally independent of each other given the inputs $\mathbf x$.

> [!NOTE]
>
> To use this diagram for backpropagation, swap the roles of its nodes and edges. In a computational graph the tensors sit on the edges and the RNN functions (gates) sit in the nodes.

## Dimensioning simple RNNs

In the table below, $m$ is the number of examples in the mini-batch.

| Variable | Dimensions |
| - | - |
| $\mathbf{h}_t$ | $n_{neurons} \times 1$ or $m \times n_{neurons}$ |
| $\mathbf{x}_t$ | $n_{input} \times 1$ or $m \times n_{input}$ |
| $\mathbf{U}$ | $n_{neurons} \times n_{input}$ |
| $\mathbf{W}$ | $n_{neurons} \times n_{neurons}$ |
| $\mathbf{b}$ | $n_{neurons} \times 1$ |
| $\mathbf{V}$ | $n_{output} \times n_{neurons}$ |
| $\mathbf{o}$ | $n_{output} \times 1$ |
| $\mathbf{c}$ | $n_{output} \times 1$ |

You can stack several such layers on top of each other. Each layer keeps its own hidden state.

## Forward propagation

This network maps an input sequence to an output sequence of the same length. Its forward pass is:

$$
\begin{aligned}
\mathbf a_t &= \mathbf W \mathbf h_{t-1} + \mathbf U \mathbf x_t + \mathbf b \\
\mathbf h_t &= \tanh(\mathbf a_t) \\
\mathbf o_t &= \mathbf V \mathbf h_t + \mathbf c \\
\hat{\mathbf y}_t &= \mathtt{softmax}(\mathbf o_t)
\end{aligned}
$$

The [time series forecasting section](https://aegean.ai/aiml-common/lectures/rnn/time-series-forecasting/index.md) implements the first two lines as a small PyTorch module and checks it against `nn.RNN`.

The loss over a sequence of length $\tau$ is the KL divergence between the empirical distribution of the data and the model distribution. Up to a constant that does not depend on $\boldsymbol\theta$, it is the negative log-likelihood:

$$
\begin{aligned}
L &= D_{KL}\big[\hat p_{data}(\mathbf y | \mathbf x) \,\|\, p_{model}(\mathbf y | \mathbf x; \boldsymbol\theta)\big] \\
&= - \mathbb E_{\mathbf y | \mathbf x \sim \hat{p}_{data}} \log p_{model}(\mathbf y | \mathbf x ; \boldsymbol\theta) \\
&= - \sum_t \log p_{model}(y_t | \mathbf x_1, \dots, \mathbf x_t ; \boldsymbol\theta)
\end{aligned}
$$

where $L$ is shorthand for $L(\hat{\mathbf y}_1, \dots , \hat{\mathbf y}_{\tau}, \mathbf y_1, \dots , \mathbf y_{\tau})$.

RNNs can model very general distributions $\log p_{model}(\mathbf x, \mathbf y ; \boldsymbol\theta)$. The simple RNN above models the conditional distribution $\log p_{model}(\mathbf y | \mathbf x ; \boldsymbol\theta)$. Because of the conditional independence assumption, that distribution factorizes into $\sum_t \log p_{model}(y_t | \mathbf x_1, \dots, \mathbf x_t ; \boldsymbol\theta)$.

> [!NOTE]
>
> You can remove this simplifying assumption by connecting $\mathbf y_{t-1}$ to $\mathbf h_t$ through another matrix, for example $\mathbf R$. The network can then model an arbitrary distribution $\log p_{model}(\mathbf y | \mathbf x ; \boldsymbol\theta)$. As in other deep network architectures, the connectivity directly affects the representational capacity of the hypothesis set.

In many problems only the label $y_\tau$ at the end of the sequence matters. Suppose you classify speech or video from inside a car cabin to detect the psychological state of the driver. The same architecture covers this case: you keep only $\mathbf o_\tau$, $L_\tau$ and $y_\tau$ and ignore the outputs at earlier steps.

An example makes the forward equations concrete.

![A six-token sentence fed one token at a time into an unrolled RNN](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/example-sentence.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=a4fde3c3284b06e8c4fae40839b17433)

*Example sentence as input to the RNN*

The figure shows a short document (a sentence) broken into *tokens*. Here a token is a word, and the sentence has $\tau=6$ tokens. Suppose you need one label for the whole document. At $t=1$ the network receives the first token $\mathbf x_1$. Starting from the hidden state $\mathbf h_0 = 0$, it computes $\mathbf h_1$ with the forward equations and ignores the output $\mathbf o_1$. It repeats this unrolling for each new input $\mathbf x_2, \mathbf x_3, \dots$ until it reaches the end-of-sentence token $\mathbf x_6$. Only at that step does it compute the output $y_6$ and the loss

$$
- \log p_{model} (y_6|\mathbf x_1, \dots , \mathbf x_6; \boldsymbol\theta)
$$

where $\boldsymbol\theta = \{ \mathbf W, \mathbf U, \mathbf V, \mathbf b, \mathbf c \}$.

## Backpropagation through time (BPTT)

Training uses backpropagation on the unrolled network.

![Computational graph of two unrolled recurrences, t minus 1 and t, with the backward gradient flow](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/rnn-BPTT.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=893695d69a2fa4f498fe8043bb52228b)

*Understanding RNN memory through the BPTT procedure*

Backpropagation in an RNN looks like backpropagation in other networks, because the unrolled architecture resembles a feed-forward one. There is one important difference, which the computational graph above shows for recurrences $t-1$ and $t$. The computation of $\mathbf h_t$ uses the value $\mathbf h_{t-1}$ from the previous recurrence. When you apply the chain rule in the backward pass, every node that involves such a recurrent variable receives a *non-local* gradient from a later step ($t$ in the figure). In the networks you have seen so far, each gate only used gradients local to it.

This is why a simple RNN is said to have *memory*. Look at the backward pass in recurrence $t-1$, at the junction between $\tanh$ and $\mathbf V \mathbf h_{t-1}$. The gradient $\nabla_{\mathbf h_{t-1}}L_t$ arrives there from the backpropagation of the $\mathbf W \mathbf h_{t-1}$ node in recurrence $t$. Because the node is a junction, this gradient is added to the gradient that flows down from the output of recurrence $t-1$:

$$
\nabla_{\mathbf h_{t-1}}L_{t-1} \leftarrow \nabla_{\mathbf h_{t-1}}L_{t-1} + \nabla_{\mathbf h_{t-1}}L_t
$$

[Section 10.2.2 of Goodfellow, Bengio and Courville](https://www.deeplearningbook.org/contents/rnn.html) gives the exact equations. The intuition behind the computational graph is enough to follow the rest of this chapter.

In practice BPTT is [*truncated*](https://proceedings.mlr.press/v115/aicher20a.html). Without truncation, a single gradient update would need a full forward pass and a full backward pass over the training sequence, which for a language model is very long. If the truncation length is too short, the bias it introduces can stop SGD from converging. The truncation length is usually chosen by a heuristic, larger than the expected memory of the system, or by cross-validation.

PyTorch runs BPTT for you: calling `backward()` on a loss computed from an unrolled `nn.RNN` sends the gradient back through every step. The [time series forecasting section](https://aegean.ai/aiml-common/lectures/rnn/time-series-forecasting/index.md) trains simple and deep RNNs this way to predict the next values of a series.

## Vanishing or exploding gradients

> [!NOTE]
>
> The figure below is a conceptual picture of a recurrence over time. It is called an infinite impulse response (IIR) filter, for reasons that become clear shortly.
>
> ![A first-order IIR filter: the input is added to the delayed output scaled by a weight w](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/rnn-IIR.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=57aaed833fa6b0c76e07b5ddc5008204)
>
> *Infinite impulse response (IIR) filter with weight $w$*
>
> Let $D$ denote a unit delay, a memory location that stores a value for one step. The recurrence of this system is
>
> $$
> h_t = w h_{t-1} + x_t
> $$
>
> where $w$ is a scalar weight. Feed an impulse $x_t = \delta_t$ into the system with $w=-0.9$:
>
> $$
> \begin{aligned}
> h_0 &= -0.9\, h_{-1} + \delta_0 = 1 \\
> h_1 &= -0.9\, h_{0} + \delta_1 = -0.9 \\
> h_2 &= -0.9\, h_{1} + \delta_2 = 0.81 \\
> h_3 &= -0.9\, h_{2} + \delta_3 = -0.729
> \end{aligned}
> $$
>
> With $w=-0.9$, the impulse response $h_t$ follows a decaying exponential envelope. With $|w| > 1$ it would follow a growing exponential envelope. If the recurrence continues, the response vanishes or explodes long after the impulse entered at $t=0$. In this simple filter, the weight alone decides which of the two happens.

The RNN hidden-state recurrence behaves the same way in the backward pass, which runs from $t=\tau$ back to $t=1$. When $\tau$ is large, the gradient can *vanish* or *explode*. The scalar $w$ of the IIR filter becomes the matrix $\mathbf W$, and the signal $h$ becomes the gradient $\nabla_{\mathbf h_{t}}L_{t}$. [Pascanu, Mikolov and Bengio](http://proceedings.mlr.press/v28/pascanu13.pdf) analyze this in detail.

The derivative of the $\tanh$ non-linearity, shown below, lies between 0 and 1. It shrinks the gradients and slows down training.

![Plot of the derivative of tanh, which peaks at 1 at the origin and decays toward 0](https://mintcdn.com/aegeanaiinc/kzxVP5xXTKVusMDe/aiml-common/lectures/rnn/simple-rnn/images/tanh-derivative.png?fit=max\&auto=format\&n=kzxVP5xXTKVusMDe\&q=85\&s=21d9a6a83c75e0c537bd6f41928a06b5)

*Derivative of the $\tanh$ non-linearity*

The repeated multiplication by $\mathbf W$ has a similar effect. If you ignore the non-linearity, the hidden state is $\mathbf h_{t} = \mathbf W \mathbf h_{t-1}$, so after $\tau$ steps

$$
\mathbf h_{\tau} = \mathbf W^\tau \mathbf h_{0}
$$

The same power of $\mathbf W$ appears in the expression for $\nabla_{\mathbf h_{t}}L_{t}$ (see [section 10.2.2](https://www.deeplearningbook.org/contents/rnn.html)). If the magnitudes of the eigenvalues of $\mathbf W$ are below 1, the gradients vanish. If they are above 1, the gradients explode. The long short-term memory (LSTM) architecture in the next section addresses this problem.

## PyTorch reference

| PyTorch class | Description |
| - | - |
| [`nn.RNN`](https://docs.pytorch.org/docs/2.12/generated/torch.nn.RNN.html) | Multi-layer Elman RNN with tanh or ReLU. |
| [`nn.RNNCell`](https://docs.pytorch.org/docs/2.12/generated/torch.nn.RNNCell.html) | One Elman RNN cell with tanh or ReLU. |
| [`nn.Linear`](https://docs.pytorch.org/docs/2.12/generated/torch.nn.Linear.html) | Affine transformation $y = xA^T + b$. |

Key references: (Graves et al., n.d.; Jaderberg et al., 2016; Parisotto et al., 2016)

## References

* Graves, A., Wayne, G., Danihelka, I. (n.d.). *Neural Turing Machines*. [Link](http://arxiv.org/abs/1410.5401v2)
* Jaderberg, M., Czarnecki, W., Osindero, S., Vinyals, O., Graves, A., et al. (2016). *Decoupled Neural Interfaces using Synthetic Gradients*. arXiv \[cs.LG]. [Link](http://arxiv.org/abs/1608.05343)
* Parisotto, E., Mohamed, A., Singh, R., Li, L., Zhou, D., et al. (2016). *Neuro-Symbolic Program Synthesis*. arXiv \[cs.AI]. [DOI](https://doi.org/10.48550/arXiv.1611.01855)

***

Found an error on this page? [Report an issue](https://github.com/aegean-ai/eaia-feedback/issues/new?template=page-issue.yml\&page=/aiml-common/lectures/rnn/simple-rnn).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.