% ============================================================================ % Artificial Neural Networks — Methods, Equations and Graphical % Representations % Author : Simon-Pierre Boucher — contact@spboucher.ai % Chapter 5 : Recurrent Networks — RNN, LSTM and GRU (chapters/05-rnn.tex) % ============================================================================ \chapter{Recurrent Networks: RNN, LSTM and GRU} \label{chap:rnn} Feedforward architectures map a fixed-size input to a fixed-size output; they have no mechanism for processing sequences of arbitrary length, nor any notion of order or memory. Recurrent neural networks (RNNs) remove this limitation by maintaining a \emph{hidden state} that is updated at every time step and acts as a compressed summary of everything the network has seen so far. This chapter develops the vanilla recurrent network and its training algorithm, backpropagation through time; analyzes why gradients vanish or explode over long horizons; and presents the two gated architectures — the long short-term memory (LSTM) of Hochreiter and Schmidhuber \cite{hochreiter1997} and the gated recurrent unit (GRU) of Cho et al.\ \cite{cho2014} — that made learning long-range dependencies practical. We close with bidirectional networks and the encoder--decoder paradigm for sequence-to-sequence learning. % ---------------------------------------------------------------------------- \section{The simple recurrent network} \label{sec:rnn-simple} \begin{definition}[Recurrent neural network] A recurrent neural network processes a sequence $\vect{x}_1, \vect{x}_2, \dots, \vect{x}_T$, with $\vect{x}_t \in \R^{d}$, by maintaining a hidden state $\vect{h}_t \in \R^{n}$ computed from the current input and the previous state, $\vect{h}_t = f(\vect{h}_{t-1}, \vect{x}_t; \theta)$, where the parameters $\theta$ are \emph{shared across all time steps}. \end{definition} The standard (Elman) form uses a $\tanh$ nonlinearity for the state update and a linear read-out: \begin{equation} \vect{h}_t = \tanh\!\left(\mat{W}_{h}\,\vect{h}_{t-1} + \mat{W}_{x}\,\vect{x}_t + \vect{b}\right), \label{eq:rnn-hidden} \end{equation} \begin{equation} \vect{y}_t = \mat{W}_{y}\,\vect{h}_t + \vect{b}_y, \label{eq:rnn-output} \end{equation} with $\mat{W}_{x} \in \R^{n \times d}$, $\mat{W}_{h} \in \R^{n \times n}$ and $\mat{W}_{y} \in \R^{m \times n}$. For classification tasks the output \eqref{eq:rnn-output} is typically passed through a softmax, $\hat{\vect{y}}_t = \softmax(\mat{W}_{y}\vect{h}_t + \vect{b}_y)$. Weight sharing across time is the defining structural property: the same pair $(\mat{W}_h, \mat{W}_x)$ is applied at every step, so the RNN is a discrete-time dynamical system whose parameters do not grow with the sequence length. Figure~\ref{fig:rnn-unrolled} shows the two equivalent views of this computation: the \emph{folded} form, a single cell with a feedback loop, and the \emph{unfolded} form, a deep network with one layer per time step and tied weights. \begin{figure}[htbp] \centering \begin{tikzpicture} % ---------- folded form ---------- \node[ninput] (fx) at (0,0) {$\vect{x}_t$}; \node[mem, minimum width=1.3cm] (fc) at (0,1.9) {$\vect{h}$}; \node[noutput] (fy) at (0,3.8) {$\vect{y}_t$}; \draw[fleche] (fx) -- (fc) node[midway,right,etiquette] {$\mat{W}_x$}; \draw[fleche] (fc) -- (fy) node[midway,right,etiquette] {$\mat{W}_y$}; \draw[fleche] (fc.east) .. controls +(1.5,1.0) and +(1.5,-1.0) .. (fc.east) node[pos=0.5, right=0.25cm, etiquette] {$\mat{W}_h$}; % ---------- unfold symbol ---------- \node at (3.35,1.9) {\Large $=$}; \node[etiquette] at (3.35,2.5) {unfold}; % ---------- unfolded form ---------- \foreach \i/\lab in {1/{t-1}, 2/{t}, 3/{t+1}} { \node[ninput] (x\i) at (3.0+\i*2.5, 0) {$\vect{x}_{\lab}$}; \node[mem, minimum width=1.3cm] (c\i) at (3.0+\i*2.5, 1.9) {$\vect{h}_{\lab}$}; \node[noutput] (y\i) at (3.0+\i*2.5, 3.8) {$\vect{y}_{\lab}$}; \draw[fleche] (x\i) -- (c\i); \draw[fleche] (c\i) -- (y\i); } \draw[fleche] (4.3,1.9) -- (c1.west) node[very near start, above, etiquette] {$\cdots$}; \draw[fleche] (c1) -- (c2) node[midway, above, etiquette] {$\mat{W}_h$}; \draw[fleche] (c2) -- (c3) node[midway, above, etiquette] {$\mat{W}_h$}; \draw[fleche] (c3.east) -- (11.7,1.9) node[very near end, above, etiquette] {$\cdots$}; \end{tikzpicture} \caption{The two equivalent views of a recurrent network. Left: folded form — a single cell whose hidden state $\vect{h}$ feeds back into itself through $\mat{W}_h$. Right: unfolded form — the same cell replicated over time steps $t-1$, $t$, $t+1$, with all replicas sharing the weights $(\mat{W}_x, \mat{W}_h, \mat{W}_y)$ of \eqref{eq:rnn-hidden}--\eqref{eq:rnn-output}.} \label{fig:rnn-unrolled} \end{figure} % ---------------------------------------------------------------------------- \section{Backpropagation through time} \label{sec:rnn-bptt} Training proceeds by \emph{unrolling} the recurrence into the feedforward network of Figure~\ref{fig:rnn-unrolled} (right) and applying standard backpropagation to the unrolled graph — hence the name backpropagation through time (BPTT). For a sequence-level loss $\Loss = \sum_{t=1}^{T} \Loss_t$, the gradient with respect to the recurrent matrix accumulates contributions over all pairs of time steps: \begin{equation} \frac{\partial \Loss}{\partial \mat{W}_h} = \sum_{t=1}^{T} \sum_{k=1}^{t} \frac{\partial \Loss_t}{\partial \vect{h}_t} \left( \prod_{i=k+1}^{t} \frac{\partial \vect{h}_i}{\partial \vect{h}_{i-1}} \right) \frac{\partial \vect{h}_k}{\partial \mat{W}_h}. \label{eq:rnn-loss-grad} \end{equation} The critical object in \eqref{eq:rnn-loss-grad} is the product of Jacobians that transports the error signal from step $t$ back to step $k$. Differentiating \eqref{eq:rnn-hidden}, each factor is $\mat{W}_h\transp$ scaled by the local slope of the nonlinearity, so \begin{equation} \frac{\partial \vect{h}_t}{\partial \vect{h}_k} = \prod_{i=k+1}^{t} \frac{\partial \vect{h}_i}{\partial \vect{h}_{i-1}} = \prod_{i=k+1}^{t} \operatorname{diag}\!\bigl(\tanh'(\vect{a}_i)\bigr)\, \mat{W}_h\transp, \label{eq:rnn-jacobian} \end{equation} where $\vect{a}_i = \mat{W}_h \vect{h}_{i-1} + \mat{W}_x \vect{x}_i + \vect{b}$ is the pre-activation. Bounding each factor by its largest singular value $\sigma_{\max}(\mat{W}_h)$ and using $|\tanh'| \le \gamma = 1$ gives \begin{equation} \left\lVert \frac{\partial \vect{h}_t}{\partial \vect{h}_k} \right\rVert \;\le\; \bigl(\gamma\, \sigma_{\max}(\mat{W}_h)\bigr)^{\,t-k}. \label{eq:rnn-jacobian-bound} \end{equation} Equation \eqref{eq:rnn-jacobian-bound} exposes the fundamental pathology of the simple RNN. If $\sigma_{\max}(\mat{W}_h) < 1/\gamma$, the bound decays exponentially in the time lag $t-k$: gradients \emph{vanish}, and the network cannot learn dependencies spanning more than a few dozen steps. Conversely, if the spectral radius of $\mat{W}_h$ exceeds $1$ — a necessary condition — the product can grow exponentially: gradients \emph{explode}, producing loss spikes and numerical overflow. Both regimes are generic; only a narrow band around unit gain propagates error signals faithfully over long horizons. \begin{remark}[Gradient clipping] Exploding gradients admit a simple remedy: rescale the gradient $\vect{g} = \nabla_\theta \Loss$ whenever its norm exceeds a threshold $\tau$, \begin{equation} \vect{g} \;\leftarrow\; \begin{cases} \dfrac{\tau}{\lVert \vect{g} \rVert}\, \vect{g} & \text{if } \lVert \vect{g} \rVert > \tau, \\[2ex] \vect{g} & \text{otherwise.} \end{cases} \label{eq:rnn-clip} \end{equation} Vanishing gradients have no comparably simple fix; they are an \emph{architectural} problem, and it is precisely this problem that the gated cells of Sections~\ref{sec:rnn-lstm} and~\ref{sec:rnn-gru} solve. \end{remark} Algorithm~\ref{alg:rnn-bptt} assembles the complete estimation procedure: a forward sweep that stores all pre-activations and states, a backward sweep that transports the error signal $\vect{\delta}_t$ from step $T$ down to step $1$ while accumulating the shared-weight gradients of \eqref{eq:rnn-loss-grad}, followed by clipping \eqref{eq:rnn-clip} and a gradient step. \begin{algorithm}[htbp] \caption{Backpropagation through time (BPTT) for the simple RNN} \label{alg:rnn-bptt} \begin{algorithmic}[1] \Require sequence $(\vect{x}_1, \dots, \vect{x}_T)$, losses $\Loss_t$, parameters $(\mat{W}_x, \mat{W}_h, \mat{W}_y, \vect{b}, \vect{b}_y)$, learning rate $\eta$, clipping threshold $\tau$ \State $\vect{h}_0 \gets \vect{0}$ \For{$t = 1, \dots, T$} \Comment{forward pass: store all $\vect{a}_t, \vect{h}_t$} \State $\vect{a}_t \gets \mat{W}_h \vect{h}_{t-1} + \mat{W}_x \vect{x}_t + \vect{b}$;\quad $\vect{h}_t \gets \tanh(\vect{a}_t)$ \State $\vect{y}_t \gets \mat{W}_y \vect{h}_t + \vect{b}_y$ \EndFor \State $\nabla_{\mat{W}_x}, \nabla_{\mat{W}_h}, \nabla_{\mat{W}_y}, \nabla_{\vect{b}}, \nabla_{\vect{b}_y} \gets \vect{0}$;\quad $\vect{\delta} \gets \vect{0}$ \For{$t = T, \dots, 1$} \Comment{backward pass: $\vect{\delta}$ carries $\partial\Loss/\partial\vect{h}_t$} \State $\vect{\delta} \gets \mat{W}_y\transp\, \nabla_{\vect{y}_t}\Loss_t + \vect{\delta}$ \State $\vect{\delta}_a \gets \vect{\delta} \odot \bigl(\vect{1} - \tanh^2(\vect{a}_t)\bigr)$ \State $\nabla_{\mat{W}_y} \gets \nabla_{\mat{W}_y} + \nabla_{\vect{y}_t}\Loss_t\, \vect{h}_t\transp$;\quad $\nabla_{\vect{b}_y} \gets \nabla_{\vect{b}_y} + \nabla_{\vect{y}_t}\Loss_t$ \State $\nabla_{\mat{W}_h} \gets \nabla_{\mat{W}_h} + \vect{\delta}_a \vect{h}_{t-1}\transp$;\quad $\nabla_{\mat{W}_x} \gets \nabla_{\mat{W}_x} + \vect{\delta}_a \vect{x}_t\transp$;\quad $\nabla_{\vect{b}} \gets \nabla_{\vect{b}} + \vect{\delta}_a$ \State $\vect{\delta} \gets \mat{W}_h\transp \vect{\delta}_a$ \Comment{transport the error to step $t-1$} \EndFor \State clip each gradient by \eqref{eq:rnn-clip} with threshold $\tau$ \State update each parameter $\theta \gets \theta - \eta\, \nabla_\theta$ \end{algorithmic} \end{algorithm} % ---------------------------------------------------------------------------- \section{Long short-term memory (LSTM)} \label{sec:rnn-lstm} The long short-term memory network \cite{hochreiter1997} replaces the purely multiplicative recurrence \eqref{eq:rnn-hidden} with an \emph{additive} one. It introduces a second state vector, the \emph{cell state} $\vect{c}_t$, which traverses time along a path modified only by elementwise gating — the ``constant error carousel.'' Three learned gates, each a sigmoid layer reading the current input $\vect{x}_t$ and the previous hidden state $\vect{h}_{t-1}$, control what the cell forgets, what it writes, and what it exposes: \begin{align} \vect{f}_t &= \sigma\!\left(\mat{W}_f \vect{x}_t + \mat{U}_f \vect{h}_{t-1} + \vect{b}_f\right) && \text{(forget gate)} \label{eq:rnn-lstm-f} \\ \vect{i}_t &= \sigma\!\left(\mat{W}_i \vect{x}_t + \mat{U}_i \vect{h}_{t-1} + \vect{b}_i\right) && \text{(input gate)} \label{eq:rnn-lstm-i} \\ \vect{o}_t &= \sigma\!\left(\mat{W}_o \vect{x}_t + \mat{U}_o \vect{h}_{t-1} + \vect{b}_o\right) && \text{(output gate)} \label{eq:rnn-lstm-o} \\ \tilde{\vect{c}}_t &= \tanh\!\left(\mat{W}_c \vect{x}_t + \mat{U}_c \vect{h}_{t-1} + \vect{b}_c\right) && \text{(candidate content)} \label{eq:rnn-lstm-ctilde} \\ \vect{c}_t &= \vect{f}_t \odot \vect{c}_{t-1} + \vect{i}_t \odot \tilde{\vect{c}}_t && \text{(cell state update)} \label{eq:rnn-lstm-c} \\ \vect{h}_t &= \vect{o}_t \odot \tanh(\vect{c}_t) && \text{(hidden state)} \label{eq:rnn-lstm-h} \end{align} Here $\sigma$ is the logistic sigmoid, so each gate takes values in $(0,1)^n$ and acts as a soft, differentiable switch applied coordinatewise through the Hadamard product $\odot$. The forget gate $\vect{f}_t$ decides how much of the previous cell $\vect{c}_{t-1}$ to retain; the input gate $\vect{i}_t$ decides how much of the new candidate $\tilde{\vect{c}}_t$ to write; the output gate $\vect{o}_t$ decides how much of the (squashed) cell to reveal in the hidden state. Figure~\ref{fig:rnn-lstm-cell} traces these six equations through the cell. \begin{property}[Constant error carousel] \label{prop:rnn-cec} Along the cell-state path of \eqref{eq:rnn-lstm-c}, the Jacobian of the recurrence is diagonal, \begin{equation} \frac{\partial \vect{c}_t}{\partial \vect{c}_{t-1}} = \operatorname{diag}(\vect{f}_t) \quad (\text{holding the gates fixed}), \label{eq:rnn-lstm-cec} \end{equation} with entries in $(0,1)$ controlled by the forget gate rather than by repeated multiplication with $\mat{W}_h$. When the network sets $\vect{f}_t \approx \vect{1}$, error signals flow backward through \eqref{eq:rnn-lstm-cec} essentially unattenuated over hundreds of steps, in contrast with the exponential bound \eqref{eq:rnn-jacobian-bound} of the simple RNN. \end{property} \begin{remark} A useful practical consequence of Property~\ref{prop:rnn-cec} is to initialize the forget-gate bias $\vect{b}_f$ to a positive value (e.g.\ $1$ or $2$), so that $\vect{f}_t \approx \vect{1}$ at the start of training and the network begins by \emph{remembering}, only later learning what to forget. \end{remark} \begin{figure}[htbp] \centering \begin{tikzpicture} % ================= cell state line (top, violet) ================= \node[mem, minimum width=1.2cm] (cprev) at (0.2,5) {$\vect{c}_{t-1}$}; \node[op] (multf) at (2.6,5) {$\odot$}; \node[op] (plus) at (6.4,5) {$+$}; \node[mem, minimum width=1.2cm] (cnew) at (12.4,5) {$\vect{c}_t$}; \draw[fleche, cmem!70!black, very thick] (cprev) -- (multf); \draw[fleche, cmem!70!black, very thick] (multf) -- (plus); \draw[fleche, cmem!70!black, very thick] (plus) -- (cnew); \fill[cmem!70!black] (8.6,5) circle (1.6pt); % ================= gates (bottom row) ================= \node[gate] (fgate) at (2.6,1.2) {$\sigma$}; \node[gate] (igate) at (4.6,1.2) {$\sigma$}; \node[gate] (cgate) at (6.4,1.2) {$\tanh$}; \node[gate] (ogate) at (10.4,1.2) {$\sigma$}; % ================= interior op nodes ================= \node[op] (multi) at (6.4,3.3) {$\odot$}; % i_t (.) c~_t \node[op] (tanhc) at (8.6,3.3) {$\tanh$}; % tanh(c_t) \node[op] (multo) at (10.4,2.2) {$\odot$}; % o_t (.) tanh(c_t) % ================= gate outputs ================= \draw[fleche] (fgate) -- (multf) node[pos=0.55, right, etiquette] {$\vect{f}_t$}; \draw[fleche, rounded corners=3pt] (igate.north) |- (multi.west) node[pos=0.25, right, etiquette] {$\vect{i}_t$}; \draw[fleche] (cgate) -- (multi) node[pos=0.5, right, etiquette] {$\tilde{\vect{c}}_t$}; \draw[fleche] (multi) -- (plus); \draw[fleche] (ogate) -- (multo) node[pos=0.5, right, etiquette] {$\vect{o}_t$}; % ================= tanh branch from the state line ================= \draw[fleche] (8.6,5) -- (tanhc); \draw[fleche, rounded corners=3pt] (tanhc.south) |- (multo.west); % ================= h_t output ================= \node[mem, minimum width=1.2cm] (hnew) at (12.4,2.2) {$\vect{h}_t$}; \draw[fleche] (multo) -- (hnew); \draw[fleche, rounded corners=3pt] (11.6,2.2) |- (12.4,0.6) node[pos=1.0, right, etiquette] {to $\vect{y}_t$}; \fill[black!70] (11.6,2.2) circle (1.4pt); % ================= input trunk (bottom) ================= \node[mem, minimum width=1.2cm] (hprev) at (-0.6,0) {$\vect{h}_{t-1}$}; \node[ninput] (xt) at (1.2,-1.5) {$\vect{x}_t$}; \draw[thick] (hprev.east) -- (10.4,0); \draw[fleche] (xt) -- (1.2,0); \foreach \x in {1.2, 2.6, 4.6, 6.4} \fill[black!70] (\x,0) circle (1.4pt); \draw[fleche] (2.6,0) -- (fgate.south); \draw[fleche] (4.6,0) -- (igate.south); \draw[fleche] (6.4,0) -- (cgate.south); \draw[fleche] (10.4,0) -- (ogate.south); % ================= cell frame ================= \begin{scope}[on background layer] \node[draw=black!35, dashed, rounded corners=6pt, fill=black!2, fit={(1.7,-0.6) (11.7,5.75)}, inner sep=2pt] (frame) {}; \end{scope} \node[etiquette, anchor=south west] at (1.75,5.85) {LSTM cell}; \end{tikzpicture} \caption{The LSTM cell, tracing equations \eqref{eq:rnn-lstm-f}--\eqref{eq:rnn-lstm-h}. The cell state runs horizontally along the top (violet): it is first scaled by the forget gate ($\odot$ with $\vect{f}_t$), then incremented ($+$) with the gated candidate $\vect{i}_t \odot \tilde{\vect{c}}_t$. The three $\sigma$ gates and the $\tanh$ candidate layer (bottom, green) all read the shared input trunk carrying $\vect{h}_{t-1}$ and $\vect{x}_t$. The updated cell $\vect{c}_t$ is squashed by $\tanh$ and multiplied by the output gate $\vect{o}_t$ to produce the hidden state $\vect{h}_t$, which exits right and branches toward the output.} \label{fig:rnn-lstm-cell} \end{figure} % ---------------------------------------------------------------------------- \section{Gated recurrent unit (GRU)} \label{sec:rnn-gru} The gated recurrent unit \cite{cho2014} is a streamlined gated cell that merges the LSTM's cell and hidden states into a single vector $\vect{h}_t$ and uses only two gates — roughly $25\%$ fewer parameters than the LSTM: \begin{align} \vect{z}_t &= \sigma\!\left(\mat{W}_z \vect{x}_t + \mat{U}_z \vect{h}_{t-1} + \vect{b}_z\right) && \text{(update gate)} \label{eq:rnn-gru-z} \\ \vect{r}_t &= \sigma\!\left(\mat{W}_r \vect{x}_t + \mat{U}_r \vect{h}_{t-1} + \vect{b}_r\right) && \text{(reset gate)} \label{eq:rnn-gru-r} \\ \tilde{\vect{h}}_t &= \tanh\!\left(\mat{W}_h \vect{x}_t + \mat{U}_h (\vect{r}_t \odot \vect{h}_{t-1}) + \vect{b}_h\right) && \text{(candidate state)} \label{eq:rnn-gru-htilde} \\ \vect{h}_t &= (\vect{1} - \vect{z}_t) \odot \vect{h}_{t-1} + \vect{z}_t \odot \tilde{\vect{h}}_t && \text{(interpolation)} \label{eq:rnn-gru-h} \end{align} The reset gate $\vect{r}_t$ controls how much of the past state contributes to the candidate \eqref{eq:rnn-gru-htilde}: with $\vect{r}_t \approx \vect{0}$ the unit ignores its history and behaves like a freshly initialized network. The update gate $\vect{z}_t$ then interpolates \eqref{eq:rnn-gru-h} between copying the old state and writing the new candidate — the same leaky-integration principle as the LSTM's forget/input pair, realized as an explicit convex combination. Empirically, GRU and LSTM perform comparably across language and speech benchmarks, with the LSTM slightly more robust on tasks requiring precise counting; the GRU is often preferred when parameter economy or training speed matters. % ---------------------------------------------------------------------------- \section{Bidirectional networks and sequence-to-sequence learning} \label{sec:rnn-seq2seq} \paragraph{Bidirectional RNNs.} The recurrences above are causal: $\vect{h}_t$ summarizes only $\vect{x}_1, \dots, \vect{x}_t$. Many labeling tasks (tagging, speech frames, contextual encoding) benefit from future context as well. A bidirectional RNN runs two independent recurrent networks over the sequence — one forward, one backward — and concatenates their states: \begin{equation} \overrightarrow{\vect{h}}_t = f\!\left(\overrightarrow{\mat{W}} \vect{x}_t + \overrightarrow{\mat{U}}\, \overrightarrow{\vect{h}}_{t-1}\right), \qquad \overleftarrow{\vect{h}}_t = f\!\left(\overleftarrow{\mat{W}} \vect{x}_t + \overleftarrow{\mat{U}}\, \overleftarrow{\vect{h}}_{t+1}\right), \label{eq:rnn-bidir} \end{equation} \begin{equation} \vect{y}_t = g\!\left(\mat{V}\, [\,\overrightarrow{\vect{h}}_t \,;\, \overleftarrow{\vect{h}}_t\,] + \vect{b}\right), \label{eq:rnn-bidir-out} \end{equation} so each output sees both past and future. The price is that the full sequence must be available in advance: bidirectional models suit offline labeling, not streaming generation. \paragraph{Encoder--decoder (seq2seq).} To map an input sequence to an output sequence of different length — machine translation being the canonical example — the encoder--decoder architecture \cite{cho2014} uses two recurrent networks. An \emph{encoder} consumes the source $\vect{x}_1, \dots, \vect{x}_{T_x}$ and compresses it into a context vector $\vect{c}$ (typically its final hidden state); a \emph{decoder} then generates the target autoregressively, each token conditioned on the context and on all previously generated tokens: \begin{equation} p(\vect{y}_1, \dots, \vect{y}_{T'} \mid \vect{x}_1, \dots, \vect{x}_{T_x}) = \prod_{t=1}^{T'} p\!\left(\vect{y}_t \mid \vect{y}_{