RNN & LSTM

Vanilla RNN

A recurrent neural network processes sequences by maintaining a hidden state updated at each time step:

Hidden state $\mathbf{h}_t$ 是 network 的「memory」— 它 encode 了所有 previous inputs 的資訊。Same weight matrices 在所有 time steps shared（parameter sharing）。

Key Properties

Backpropagation Through Time (BPTT)

To train an RNN, "unroll" it through time and apply backpropagation:

每個 term 涉及 Jacobians 的乘積：

Each factor $\frac{\partial \mathbf{h}_i}{\partial \mathbf{h}_{i-1}} = \text{diag}(\tanh'(\mathbf{z}_i)) \cdot \mathbf{W}_{hh}$ 涉及 weight matrix 和 activation derivative。

The Vanishing Gradient Problem

$|\tanh'(x)| \leq 1$ 且通常 $\|\mathbf{W}_{hh}\| < 1$ → gradient product shrinks exponentially:

Long sequences ($t - k \gg 1$) → gradient effectively vanishes → network cannot learn long-range dependencies。

Truncated BPTT: 實務中只 backpropagate fixed number of steps（例如 35）— 犧牲 long-range learning 換取 computational efficiency。

LSTM (Long Short-Term Memory)

LSTMs (Hochreiter & Schmidhuber, 1997) 用 cell state $\mathbf{c}_t$ — 一個 separate memory pathway with carefully controlled gates — 解決 vanishing gradient problem。

The Three Gates + Cell State

Forget Gate — decides what to erase from memory:

Input Gate — decides what new information to store:

Cell State Update — the critical equation:

Output Gate — decides what to expose from memory:

Gate Intuition

Sigmoid output 在 (0,1) → 控制 information flow 的「閥門」。Tanh 在 (-1,1) → 產出 candidate values。

Why LSTMs Solve Vanishing Gradients

Cell state update 是 additive（不是 multiplicative）:

When $\mathbf{f}_t \approx 1$（forget gate open）→ gradients flow through unchanged — no multiplicative shrinkage.

這和 ResNet 的 skip connections 是同一個原理 — additive path 讓 gradient 可以直接通過，不被 multiply/shrink。

Forget Gate Bias Initialization

GRU (Gated Recurrent Unit)

GRU (Cho et al., 2014) simplifies LSTM by merging forget + input gates into one update gate and combining cell + hidden state:

Update Gate: $\mathbf{z}_t = \sigma(\mathbf{W}_z[\mathbf{h}_{t-1}, \mathbf{x}_t])$

Reset Gate: $\mathbf{r}_t = \sigma(\mathbf{W}_r[\mathbf{h}_{t-1}, \mathbf{x}_t])$

Hidden State:

GRU vs LSTM

面試中被問「GRU vs LSTM？」— GRU 更簡單、更快，在大多數 tasks 上 performance comparable。LSTM 在非常長的 sequences 上可能略好（因為 separate cell state provides more memory capacity）。實務中先試 GRU，不夠再換 LSTM。

Bidirectional RNNs

Standard RNNs only use past context. Bidirectional RNNs run two separate RNNs — forward and backward — and concatenate:

每個 position 同時看到 past 和 future context → output dimension = 2 × hidden_size。

Sequence-to-Sequence (Seq2Seq)

Encoder-decoder architecture for tasks like machine translation:

1. Encoder: Process input sequence → final hidden state $\mathbf{c}$（context vector）
2. Decoder: Generate output sequence one token at a time, conditioned on $\mathbf{c}$

The Bottleneck Problem

把整個 input sequence 壓縮成 single fixed-size vector $\mathbf{c}$ → severe bottleneck — longer sequences 丟失更多 information。

Attention mechanism (Bahdanau et al., 2014) 解決了這個問題：decoder 在每個 step 可以 attend to all encoder hidden states，不只是最後一個。這是 Transformer 的前身。

每個 decoder step $t$ 有不同的 context vector $\mathbf{c}_t$ — dynamically focus on relevant parts of the input。

Practical Architecture Patterns

Stacking Layers

import torch.nn as nn

# Multi-layer LSTM (stacked)
lstm = nn.LSTM(
    input_size=128,
    hidden_size=256,
    num_layers=3,       # 3 stacked LSTM layers
    batch_first=True,
    dropout=0.3,        # dropout between layers (not on last)
    bidirectional=True,
)
# Output shape: [batch, seq_len, 2 × 256] (bidirectional)
# Hidden shape: [2 × 3, batch, 256] (2 directions × 3 layers)

Packing Variable-Length Sequences

Real-world sequences have different lengths. Padding + packing handles this efficiently:

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

# sequences: list of tensors with different lengths
# lengths: actual length of each sequence
packed = pack_padded_sequence(padded_input, lengths, batch_first=True, enforce_sorted=False)
output, (h_n, c_n) = lstm(packed)
output, _ = pad_packed_sequence(output, batch_first=True)
# Packing tells LSTM to ignore padded positions → correct gradients

不用 packing → LSTM 會在 padding tokens 上做無意義的計算 → 浪費 compute + potentially 汙染 hidden state。

Common Patterns

Why Transformers Replaced RNNs

When RNNs Still Win

Real-World Use Cases

Case 1: 信用卡詐欺偵測 — Transaction Sequences

Fraud patterns 常是 sequential 的 — 不是單筆交易有問題，而是一系列交易的 pattern 異常。

# Transaction sequence: [amount, merchant_cat, time_diff, is_international, ...]
# Each user has a variable-length sequence of recent transactions
class FraudLSTM(nn.Module):
    def __init__(self, input_dim, hidden_dim):
        super().__init__()
        self.lstm = nn.LSTM(input_dim, hidden_dim, batch_first=True)
        self.fc = nn.Linear(hidden_dim, 1)

    def forward(self, x, lengths):
        packed = pack_padded_sequence(x, lengths, batch_first=True, enforce_sorted=False)
        _, (h_n, _) = self.lstm(packed)
        return torch.sigmoid(self.fc(h_n.squeeze(0)))  # P(fraud)

面試 follow-up：「為什麼不用 Transformer？」— 可以用，但 fraud detection 的 sequence 通常較短（最近 50-100 筆交易）→ LSTM 足夠。而且 real-time scoring 需要 incremental processing（新交易來一筆就更新 hidden state），RNN 的 online inference 更自然。

Case 2: 推薦系統 — Session-Based Recommendation

用 user 的 browsing session（click sequence）預測下一個要點的 item：

GRU4Rec 是 session-based recommendation 的開山之作。Transformer-based methods（SASRec, BERT4Rec）在 longer sessions 上通常更好。

Case 3: 時間序列預測

LSTM 在 time series forecasting 中曾經是 standard（pre-Transformer era）：

class TimeSeriesLSTM(nn.Module):
    def __init__(self, input_dim, hidden_dim, forecast_horizon):
        super().__init__()
        self.lstm = nn.LSTM(input_dim, hidden_dim, num_layers=2, batch_first=True, dropout=0.2)
        self.fc = nn.Linear(hidden_dim, forecast_horizon)

    def forward(self, x):
        # x: [batch, lookback_window, features]
        output, (h_n, _) = self.lstm(x)
        return self.fc(h_n[-1])  # use last layer's hidden state

面試 follow-up：「LSTM 和 traditional time series 方法（ARIMA, Prophet）比？」— LSTM 可以 handle multivariate inputs 和 non-linear patterns。但 ARIMA/Prophet 在 univariate, well-structured time series 上通常更好且更 interpretable。現代 trend 是用 Temporal Fusion Transformer 或 N-BEATS。

Hands-on: RNN & LSTM in PyTorch

Basic LSTM

import torch
import torch.nn as nn

seq_len, batch, input_size, hidden_size = 50, 1, 3, 8

# Vanilla RNN
rnn = nn.RNN(input_size, hidden_size, batch_first=True)
x = torch.randn(batch, seq_len, input_size)
output_rnn, h_rnn = rnn(x)
# h_rnn: [1, 1, 8] — single hidden state

# LSTM
lstm = nn.LSTM(input_size, hidden_size, batch_first=True)
output_lstm, (h_lstm, c_lstm) = lstm(x)
# h_lstm: hidden state, c_lstm: cell state

# Bidirectional LSTM
bilstm = nn.LSTM(input_size, hidden_size, num_layers=2, batch_first=True, bidirectional=True)
output_bi, _ = bilstm(x)
# output: [1, 50, 16] — 2 × hidden_size

Text Classification with LSTM

class TextClassifier(nn.Module):
    def __init__(self, vocab_size, embed_dim, hidden_dim, num_classes):
        super().__init__()
        self.embedding = nn.Embedding(vocab_size, embed_dim, padding_idx=0)
        self.lstm = nn.LSTM(embed_dim, hidden_dim, batch_first=True, bidirectional=True)
        self.fc = nn.Sequential(
            nn.Dropout(0.5),
            nn.Linear(hidden_dim * 2, num_classes),  # 2x for bidirectional
        )

    def forward(self, x, lengths):
        emb = self.embedding(x)
        packed = pack_padded_sequence(emb, lengths, batch_first=True, enforce_sorted=False)
        _, (h_n, _) = self.lstm(packed)
        # h_n: [2, batch, hidden] for bidirectional
        # Concatenate forward and backward final hidden states
        h = torch.cat([h_n[0], h_n[1]], dim=1)  # [batch, hidden*2]
        return self.fc(h)

Interview Signals

What interviewers listen for:

• 你能解釋 vanishing gradient 的數學原因（Jacobian product → exponential shrinkage）
• 你知道 LSTM 的 additive cell state update 和 ResNet skip connections 的相似性
• 你能比較 LSTM 和 GRU 的 tradeoffs（不是只說「GRU 更快」）
• 你知道 Transformer 為什麼贏，但也知道 RNN 在什麼場景仍然有用
• 你理解 Bidirectional RNN 的限制（不能用於 autoregressive generation）

Practice

Flashcards

Quiz