% ============================================================================
%  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}_{<t},\, \vect{c}\right).
  \label{eq:rnn-seq2seq}
\end{equation}
Training maximizes the log-likelihood of \eqref{eq:rnn-seq2seq} with
\emph{teacher forcing} (feeding the ground-truth $\vect{y}_{t-1}$ as the
decoder input at step $t$); inference replaces it with the model's own
predictions, usually explored with beam search.
Figure~\ref{fig:rnn-seq2seq} sketches the architecture.

\begin{figure}[htbp]
  \centering
  \begin{tikzpicture}
    % encoder
    \foreach \i in {1,2,3} {
      \node[ninput] (ex\i) at (\i*1.9-1.9, 0) {$\vect{x}_\i$};
      \node[blochidden, minimum width=1.3cm] (ec\i) at (\i*1.9-1.9, 1.6) {};
      \draw[fleche] (ex\i) -- (ec\i);
    }
    \draw[fleche] (ec1) -- (ec2);
    \draw[fleche] (ec2) -- (ec3);
    \node[etiquette] at (1.9, 2.35) {encoder};
    % context
    \node[mem, minimum width=1.1cm] (ctx) at (5.5, 1.6) {$\vect{c}$};
    \draw[fleche] (ec3) -- (ctx);
    % decoder
    \foreach \i in {1,2,3} {
      \node[blocoutput, minimum width=1.3cm] (dc\i) at (5.6+\i*1.9, 1.6) {};
      \node[noutput] (dy\i) at (5.6+\i*1.9, 3.2) {$\vect{y}_\i$};
      \draw[fleche] (dc\i) -- (dy\i);
    }
    \draw[fleche] (ctx) -- (dc1);
    \draw[fleche] (dc1) -- (dc2);
    \draw[fleche] (dc2) -- (dc3);
    \node[etiquette] at (9.4, 0.6) {decoder};
    % autoregressive feedback (dashed)
    \draw[flechep] (dy1.east) to[out=-30,in=120]
      node[pos=0.4, above=1pt, etiquette] {$\vect{y}_{t-1}$}
      ([xshift=-8pt]dc2.north);
    \draw[flechep] (dy2.east) to[out=-30,in=120]
      ([xshift=-8pt]dc3.north);
  \end{tikzpicture}
  \caption{Encoder--decoder (seq2seq) architecture. The encoder compresses
    the source sequence into a context vector $\vect{c}$; the decoder
    generates the target autoregressively following
    \eqref{eq:rnn-seq2seq}, each step receiving the previously emitted
    token (dashed arrows).}
  \label{fig:rnn-seq2seq}
\end{figure}

\begin{remark}[The bottleneck that led to attention]
The fixed-size context vector $\vect{c}$ in \eqref{eq:rnn-seq2seq} is an
information bottleneck: translation quality degrades visibly on long
sentences, because an entire source sequence must be squeezed into a
single vector. Letting the decoder look back at \emph{all} encoder states
— attention — removes this bottleneck and is the subject of the next
chapter.
\end{remark}
