RNNs & Sequences

Processing ordered data: language, time series, speech. From vanilla RNNs and their failure mode, through LSTM's gating solution, to the attention mechanism that replaced them.

Table of contents

1. Sequence modeling problem
2. Vanilla RNN
3. Backpropagation through time (BPTT)
4. Vanishing gradient in RNNs (formal)
5. LSTM (Long Short-Term Memory)
6. GRU (Gated Recurrent Unit)
7. Bidirectional RNNs
8. Seq2Seq (Encoder-Decoder)
9. Attention mechanism
10. Practical notes and code

1. Sequence modeling problem

Given a sequence $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_T$ (e.g., words, time-series values), we want to:

• Sequence classification: $(\mathbf{x}_1,\ldots,\mathbf{x}_T) \to y$ (e.g., sentiment, speaker ID).
• Sequence labeling: $(\mathbf{x}_1,\ldots,\mathbf{x}_T) \to (y_1,\ldots,y_T)$ (e.g., POS tagging, NER).
• Language modeling: $P(\mathbf{x}_T | \mathbf{x}_1,\ldots,\mathbf{x}_{T-1})$ (predict next token).
• Seq2Seq: $(x_1,\ldots,x_S) \to (y_1,\ldots,y_T)$ with different lengths (translation, summarization).

Key challenge: inputs/outputs can be of variable length; dependencies can span long distances (long-range dependencies).

2. Vanilla RNN

2.1 Architecture

Processes sequence one step at a time, maintaining a hidden state $\mathbf{h}_t$ (memory):

In matrix form (concat input and hidden):

Parameters: $\mathbf{W}_h \in \mathbb{R}^{H\times H}$, $\mathbf{W}_x \in \mathbb{R}^{H\times D}$, $\mathbf{W}_y \in \mathbb{R}^{K\times H}$, where $H$ = hidden size, $D$ = input size, $K$ = output size. Shared across all time steps — same weights at every $t$.

2.2 Unrolled RNN

The RNN is a deep feedforward network "unrolled" over time:

x₁ → [h₁] → ŷ₁
       ↓
x₂ → [h₂] → ŷ₂
       ↓
x₃ → [h₃] → ŷ₃

Depth = sequence length $T$. This creates the vanishing gradient problem for long sequences.

2.3 Initial hidden state

$\mathbf{h}_0 = \mathbf{0}$ (most common), or learned as a parameter, or set from a context encoder.

2.4 Training objectives

Many-to-many (language model):

Many-to-one (classification): use $\mathbf{h}_T$ as sequence representation, then linear classifier.

3. Backpropagation through time (BPTT)

3.1 Algorithm

Unroll the RNN for $T$ steps, then apply standard backpropagation through the unrolled graph.

Gradient of loss at time $t$ w.r.t. hidden state at time $\tau < t$:

Each Jacobian factor:

where $\text{diag}(1-\mathbf{h}_k^2)$ comes from $\tanh'(z) = 1 - \tanh^2(z)$.

Total gradient product over $t - \tau$ steps:

3.2 Truncated BPTT

Full BPTT for long sequences: $O(T)$ memory and time. Truncated BPTT: backpropagate through only the last $k$ steps. Trades accuracy for efficiency.

4. Vanishing gradient in RNNs (formal)

4.1 Analysis

The magnitude of the gradient product after $n = t - \tau$ steps:

where \lambda_\max is the largest singular value of $\mathbf{W}_h$.

Since $|\tanh'(z)| \leq 1$, if \lambda_\max(\mathbf{W}_h) < 1: gradients vanish exponentially as $n$ grows. If \lambda_\max(\mathbf{W}_h) > 1: gradients explode (fixed by gradient clipping).

Consequence: vanilla RNNs struggle to learn dependencies spanning > ~10 steps. The gradient carries essentially no information from time $t$ back to time $\tau$ when $t - \tau$ is large.

5. LSTM (Long Short-Term Memory)

5.1 Motivation (Hochreiter & Schmidhuber, 1997)

Replace the simple hidden state with a cell state $\mathbf{c}_t$ that flows mostly unchanged through time (like a "conveyor belt"), with gates controlling what information to add or remove.

5.2 LSTM equations

At each time step, with input $\mathbf{x}_t$ and previous states $(\mathbf{h}_{t-1}, \mathbf{c}_{t-1})$:

Forget gate (what to erase from cell state):

Input gate (what new information to write):

Candidate cell values (proposed update):

Cell state update:

Output gate (what to expose as hidden state):

Hidden state:

5.3 Gate intuitions

5.4 Why LSTM solves vanishing gradients

The gradient flows through $\mathbf{c}_t = \mathbf{f}_t \odot \mathbf{c}_{t-1} + \ldots$:

The Jacobian is diagonal with values $\mathbf{f}_t \in (0,1)$. If the forget gate is near 1, the gradient flows through the cell state mostly unchanged — no repeated matrix multiplication that would cause exponential decay.

This is the constant error carousel: the cell state provides a nearly unimpeded gradient pathway for long-range dependencies.

5.5 Parameters

Four gates, each with weight matrices $\mathbf{W} \in \mathbb{R}^{H \times (H+D)}$ and bias $\mathbf{b} \in \mathbb{R}^H$. Total: $4 \times (H(H+D) + H) = 4H(H+D+1)$ parameters.

For $H=512, D=256$: $\approx 1.6M$ parameters per layer.

6. GRU (Gated Recurrent Unit)

6.1 Equations (Cho et al., 2014)

Simpler than LSTM: merges cell state and hidden state, uses only two gates.

Reset gate (how much past to forget):

Update gate (interpolation between old and new):

Candidate hidden state:

Hidden state update (linear interpolation):

When $\mathbf{z}_t \approx 0$: copy old hidden state (remember long-term). When $\mathbf{z}_t \approx 1$: replace with new candidate (update quickly).

6.2 GRU vs LSTM

Rule of thumb: try both; GRU is often preferred for smaller datasets due to fewer parameters.

7. Bidirectional RNNs

7.1 Motivation

A standard RNN at time $t$ can only use past context $\mathbf{x}_1, \ldots, \mathbf{x}_t$. For tasks where the full sequence is available (e.g., NER, POS tagging, text classification), future context can also help.

7.2 Architecture

Run two RNNs: one forward (left to right), one backward (right to left):

Concatenate: $\mathbf{h}_t = [\overrightarrow{\mathbf{h}}_t; \overleftarrow{\mathbf{h}}_t] \in \mathbb{R}^{2H}$.

Limitation: cannot be used for autoregressive generation (future tokens unknown at time $t$). BERT uses bidirectional transformers for encoding; GPT uses unidirectional for generation.

8. Seq2Seq (Encoder-Decoder)

8.1 Architecture (Sutskever et al., 2014)

Problem: input sequence length $S$ ≠ output sequence length $T$.

Encoder: RNN reads input, compresses to fixed context vector:

Decoder: RNN generates output autoregressively, conditioned on $\mathbf{c}$:

Training: teacher forcing — feed ground-truth $y_{t-1}$ as decoder input (even if previous prediction was wrong). Faster convergence.

Inference: use predicted $\hat{y}_{t-1}$ as decoder input (autoregressive decoding). Exposure bias: mismatch between training (ground-truth inputs) and inference (own predictions).

8.2 Bottleneck problem

The entire input sequence must be compressed into a single fixed-size vector $\mathbf{c}$. For long sequences, this is information-lossy. Solution: attention mechanism.

8.3 Beam search

Greedy decoding: at each step, pick most probable token. Suboptimal (misses high-probability sequences).

Beam search: maintain top-$B$ partial sequences at each step:

1. Expand each beam by all vocabulary tokens.
2. Score each extension by accumulated log-prob.
3. Keep top-$B$.

Beam size $B=5$ is common. Increases quality significantly over greedy, at $B\times$ cost.

9. Attention mechanism

9.1 Bahdanau attention (Bahdanau et al., 2015)

Allow the decoder to attend to different encoder positions at each decoding step, instead of using one fixed context vector.

Alignment scores: score how relevant encoder hidden state $\mathbf{h}_s^\text{enc}$ is for decoder step $t$:

Attention weights:

Context vector (weighted sum of encoder states):

Decoder uses $\mathbf{c}_t$ (dynamic, per-step) instead of a fixed $\mathbf{c}$.

9.2 Luong attention (Luong et al., 2015)

Computes alignment after computing current decoder hidden state:

Three variants: dot ($\mathbf{h}_t^\top\mathbf{h}_s$), general ($\mathbf{h}_t^\top\mathbf{W}\mathbf{h}_s$), concat (Bahdanau style). Dot product is simplest and scales to the transformer.

9.3 Interpretability

Attention weights $\alpha_{ts}$ can be visualized: which source words did the decoder focus on when producing target word $t$? In practice these are interpretable for NMT (e.g., diagonal pattern for monotone alignment).

Caveat: attention weights ≠ feature importance. They influence the context vector but are not directly a complete explanation of model behavior.

10. Practical notes and code

10.1 Sequence padding and packing

Batching variable-length sequences: pad shorter sequences to the batch maximum length.

import torch
import torch.nn as nn
from torch.nn.utils.rnn import pack_padded_sequence, pad_packed_sequence

# Packing: skip padded positions (efficient computation)
packed = pack_padded_sequence(padded_input, lengths, batch_first=True, enforce_sorted=False)
output_packed, (h_n, c_n) = lstm(packed)
output, _ = pad_packed_sequence(output_packed, batch_first=True)

10.2 PyTorch LSTM / GRU

lstm = nn.LSTM(
    input_size=128,
    hidden_size=256,
    num_layers=2,
    batch_first=True,
    dropout=0.3,
    bidirectional=True
)
gru = nn.GRU(input_size=128, hidden_size=256, num_layers=2, batch_first=True)

# Input: (batch, seq_len, input_size)
output, (h_n, c_n) = lstm(x)         # LSTM
output, h_n        = gru(x)          # GRU
# output: (batch, seq_len, 2*hidden) for bidirectional
# h_n:    (num_layers*num_dir, batch, hidden)

10.3 When RNNs vs Transformers

*File: notes/14_rnns_and_sequences.md — next: notes/15_transformers.md*