Recurrent Neural Networks

The Big Picture: Why Sequential Data Needs Special Architecture

Traditional feedforward neural networks process each input independently. They have no memory of previous inputs, making them unsuitable for sequential data where the order and history matter.

The Problem with Feedforward Networks

Consider predicting the next word in a sentence. A feedforward DNN treats each word in isolation, unable to capture the context of words that came before it. It cannot answer: "What did the user just click on?" or "What was the trend in their behavior?"

RNN Solution: Recurrence and Weight Sharing

Recurrent Neural Networks (RNNs) introduce a hidden state that persists across time steps. This hidden state acts as "memory," carrying information from past inputs forward.

Weight sharing means the same weights are used at every time step, drastically reducing parameters compared to unrolling a full feedforward network across a sequence.

Use Cases for RNNs

• Sequence Prediction: Language modeling, next-word prediction, stock price forecasting
• NLP: Machine translation, sentiment analysis, named entity recognition
• Time Series: Anomaly detection, forecasting, trend analysis
• AdTech: User click sequence prediction, conversion forecasting, contextual ad ranking

AdTech Example: Predicting User Actions with RNNs

In Bing Ads and similar ad platforms, understanding user behavior sequences is critical. Given a user's browsing and click history, we want to predict their next action to optimize ad placement and bidding.

The Scenario

A user visits several websites over time, interacting with ads. Each interaction is an event we can encode:

• Impression: An ad was shown (input code: 1)
• Click: The user clicked an ad (input code: 2)
• Conversion: The user purchased or completed a goal (input code: 3)
• Ignore: The user saw but ignored an ad (input code: 0)

Sequence Timeline Visualization

How RNN Helps

An RNN processes this sequence step by step. At each time step:

1. The current input (user action) and previous hidden state are combined
2. A new hidden state is computed, capturing information about all past actions
3. An output is predicted (next action probability)

The hidden state at step 4 contains information about all previous interactions. This allows the RNN to predict: "After seeing impressions and clicking ads, the user is likely to click again" or "The user is ready to convert."

RNN Architecture: The Recurrence Mechanism

The Recurrence Equation

At each time step t, the RNN computes a hidden state using the recurrence relation:

Where:

• h_t = hidden state at time step t
• h_{t-1} = hidden state from previous time step (the "memory")
• x_t = input at time step t
• W_hh = weights connecting hidden state to hidden state (recurrent weights)
• W_xh = weights connecting input to hidden state
• b_h = bias for hidden state
• tanh = activation function (squashes values to [-1, 1])

The output at each step is computed as:

Folded vs Unfolded Views

Weight Sharing: The Key Innovation

The same weight matrices (W_hh, W_xh, W_hy) are applied at every time step. This means:

• Parameter Efficiency: Instead of learning separate weights for each time step, we learn a single set of weights
• Generalization: The RNN can process sequences of any length without retraining
• Shared Pattern Learning: The same patterns (gates, computations) apply across the entire sequence

Information Flow

Input Layer → Hidden Layer (Recurrent) → Output Layer

The hidden layer is special: it receives input from both the current input and its own previous state, creating the recurrence.

Forward Pass Through Time: Step-by-Step Computation

Let's trace through a concrete example with actual numbers. We'll process a 4-step sequence through an RNN.

Setup

• Input dimension: 3 (e.g., one-hot encoded ad action: impression, click, conversion)
• Hidden dimension: 4 (arbitrary choice)
• Output dimension: 3 (probabilities for 3 possible actions)
• Initial hidden state: h_0 = [0, 0, 0, 0]

Forward Pass Walkthrough

Time Step 1 (t=1)

Time Step 2 (t=2)

Time Step 3 (t=3)

Time Step 4 (t=4)

Visualization

Matrix Dimensions

To be concrete about shapes:

• W_xh: (3 × 4) — maps input dimension 3 to hidden dimension 4
• W_hh: (4 × 4) — maps hidden to hidden (recurrent)
• W_hy: (4 × 3) — maps hidden dimension 4 to output dimension 3
• h_t: (4,) — hidden state vector
• y_t: (3,) — output vector (probabilities)

Backpropagation Through Time (BPTT)

Training RNNs requires a variant of backpropagation called Backpropagation Through Time (BPTT). It's the same algorithm applied to the unrolled network across time steps.

The Core Idea

When we unroll an RNN across T time steps, we get a very deep feedforward network. Backpropagation must flow backward through all T time steps, computing gradients for the shared weights at each step, then summing them.

Gradient Flow in BPTT

The Chain Rule Across Time

To compute the gradient of loss with respect to a weight W_hh, we apply the chain rule across all time steps:

The Jacobian Product (Heart of BPTT)

The gradient of h_t with respect to h_k (where k < t) is a product of Jacobians:

Each factor is the Jacobian of the hidden state update at that step. If the RNN uses tanh activation:

Truncated BPTT

In practice, computing gradients over the entire sequence is often infeasible (very deep gradient path). Truncated BPTT limits how far back gradients flow:

Typical values: τ = 20 to 100 steps. You unroll the RNN for τ steps, compute loss, backprop, then move to the next τ steps, carrying the hidden state forward.

The Vanishing Gradient Problem in RNNs

RNNs suffer from a critical training challenge: gradients can shrink exponentially as they backpropagate through time steps. This is worse than in feedforward networks and makes learning long-range dependencies nearly impossible.

Why It Happens: The Jacobian Product

Recall the gradient chain across time steps:

Each Jacobian ∂h_i/∂h_{i-1} depends on W_hh and the activation function. For tanh activation:

The term (1 - tanh²(...)) is at most 1 (when the input is 0). The eigenvalues of W_hh typically determine the scaling. If the largest eigenvalue λ_max < 1:

This is exponential decay! Over many time steps, the gradient becomes vanishingly small.

Concrete Example: 50-Step Sequence

Suppose λ_max = 0.9. After 50 time steps:

This means the RNN essentially "forgets" information from early time steps. Weights that depend on early inputs receive tiny gradient updates and barely change.

Visualization of Gradient Decay

Consequences

• Difficulty Learning Long-Range Dependencies: The RNN forgets patterns that span many time steps
• Poor Performance on Long Sequences: Predictions depend mainly on recent inputs; distant past is ignored
• Training Stalls: Early-layer weights barely update, making the RNN stagnate
• Difficulty in NLP: Context words far from the prediction target are effectively ignored

Gradient Clipping (Quick Fix)

One technique to mitigate instability is gradient clipping: if the gradient norm exceeds a threshold, scale it down:

This prevents exploding gradients (when λ_max > 1) and helps stabilize training, but doesn't solve vanishing gradients directly.

The Motivation for LSTM and GRU

LSTM — Long Short-Term Memory

LSTM (Long Short-Term Memory) is designed to solve the vanishing gradient problem through a clever architecture that maintains a "cell state" acting as a conveyor belt carrying information across many time steps.

The LSTM Cell: Conceptual Overview

Unlike a simple RNN with one hidden state, LSTM has two state variables:

• Cell State (C_t): The long-term memory. Information can persist unchanged for many steps.
• Hidden State (h_t): The short-term output used for predictions.

Three Gates: Controlling Information Flow

An LSTM cell has three gates, each computed with sigmoid activation (output between 0 and 1) to control what information passes through:

1. Forget Gate (f_t)

2. Input Gate (i_t) & Candidate Values (C̃_t)

3. Output Gate (o_t)

Cell State Update (The Critical Step)

The cell state is updated additively, not multiplicatively:

Why Addition Helps: The gradient of addition is 1, so when backpropagating through the cell state, gradients don't decay multiplicatively. They flow through unchanged (modulo gate gradients).

Hidden State Output

LSTM Cell Diagram

Why LSTM Solves Vanishing Gradients

During backpropagation through the cell state, the gradient path has addition, not multiplication by weight matrices:

The gates still involve weight matrices, so some gradient decay still happens, but the cell state provides a "gradient highway" that preserves information across many time steps.

GRU — Gated Recurrent Unit

GRU (Gated Recurrent Unit) is a simplified version of LSTM with only 2 gates instead of 3. It often achieves comparable performance with fewer parameters and faster training.

GRU Gates: Simpler Than LSTM

1. Reset Gate (r_t)

2. Update Gate (z_t)

3. Candidate Hidden State (h̃_t)

First, apply the reset gate to the previous hidden state:

4. Hidden State Update

GRU Cell Diagram

The "Highway" Metaphor

Think of the update gate as a highway merge:

• When z_t ≈ 0: The old highway (h_{t-1}) is fully open; new traffic (h̃_t) is mostly blocked
• When z_t ≈ 1: The old highway is closed; new traffic flows through
• In between: Both old and new information merge

LSTM vs GRU: Detailed Comparison

Both LSTM and GRU solve the vanishing gradient problem, but they have different tradeoffs. Here's how they compare:

Practical Guidance

Empirical Findings

• Chung et al. (2014): Found GRU and LSTM perform comparably on several datasets
• Trend: GRU gaining popularity for its efficiency, though LSTM still preferred in deep stacks
• Attention Mechanism: Modern systems often layer attention with LSTM/GRU rather than relying solely on gating

Loss Functions for Sequences

Training RNNs requires defining loss over sequences. The choice of loss depends on the task structure: are we predicting at every time step or just at the end?

Many-to-One Prediction

Scenario: Sequence of inputs, single output at the end.

Loss Computation: Only compute loss at the final time step:

Many-to-Many Prediction

Scenario: Predict at every time step (e.g., output same length as input).

Loss Computation: Sum (or average) losses across all time steps:

Cross-Entropy Loss (Standard for Classification)

Mean Squared Error (For Regression)

If predicting continuous values (e.g., next price in a time series):

CTC Loss (Alignment-Free Sequences)

For tasks where output and input lengths don't match (e.g., speech recognition):

AdTech Loss Example

For predicting user conversion from a sequence of 10 ad actions:

Python Implementation: RNN, LSTM, and GRU from Scratch

Let's implement SimpleRNN, LSTM, and GRU using NumPy to solidify understanding. These implementations are educational and not optimized for production.

Complete Class-Based Implementation

import numpy as np

class SimpleRNN:
    """
    Simple RNN cell: h_t = tanh(W_hh @ h_{t-1} + W_xh @ x_t + b_h)
                     y_t = softmax(W_hy @ h_t + b_y)
    """
    def __init__(self, input_size, hidden_size, output_size):
        self.input_size = input_size
        self.hidden_size = hidden_size
        self.output_size = output_size

        # Initialize weights (small random values)
        self.W_xh = np.random.randn(input_size, hidden_size) * 0.01
        self.W_hh = np.random.randn(hidden_size, hidden_size) * 0.01
        self.W_hy = np.random.randn(hidden_size, output_size) * 0.01
        self.b_h = np.zeros((1, hidden_size))
        self.b_y = np.zeros((1, output_size))

    def forward(self, x_sequence):
        """
        x_sequence: list of T inputs, each of shape (batch_size, input_size)
        Returns: outputs (T, batch_size, output_size), hidden states
        """
        T = len(x_sequence)
        batch_size = x_sequence[0].shape[0]

        h = np.zeros((batch_size, self.hidden_size))
        outputs = []

        for t in range(T):
            x_t = x_sequence[t]  # (batch_size, input_size)
            h = np.tanh(x_t @ self.W_xh + h @ self.W_hh + self.b_h)
            y_t = self._softmax(h @ self.W_hy + self.b_y)
            outputs.append(y_t)

        return outputs, h

    def _softmax(self, x):
        exp_x = np.exp(x - np.max(x, axis=1, keepdims=True))
        return exp_x / np.sum(exp_x, axis=1, keepdims=True)


class LSTMCell:
    """
    LSTM cell with forget, input, and output gates
    """
    def __init__(self, input_size, hidden_size):
        self.input_size = input_size
        self.hidden_size = hidden_size

        # Weight matrices for each gate
        self.W_f = np.random.randn(input_size + hidden_size, hidden_size) * 0.01
        self.W_i = np.random.randn(input_size + hidden_size, hidden_size) * 0.01
        self.W_C = np.random.randn(input_size + hidden_size, hidden_size) * 0.01
        self.W_o = np.random.randn(input_size + hidden_size, hidden_size) * 0.01

        self.b_f = np.zeros((1, hidden_size))
        self.b_i = np.zeros((1, hidden_size))
        self.b_C = np.zeros((1, hidden_size))
        self.b_o = np.zeros((1, hidden_size))

    def forward(self, x_t, h_prev, C_prev):
        """
        Single LSTM step
        x_t: (batch_size, input_size)
        h_prev: (batch_size, hidden_size)
        C_prev: (batch_size, hidden_size)
        """
        batch_size = x_t.shape[0]

        # Concatenate input and hidden state
        concat = np.hstack((h_prev, x_t))  # (batch_size, hidden_size + input_size)

        # Forget gate
        f_t = self._sigmoid(concat @ self.W_f + self.b_f)

        # Input gate and candidate
        i_t = self._sigmoid(concat @ self.W_i + self.b_i)
        C_tilde_t = np.tanh(concat @ self.W_C + self.b_C)

        # Cell state update
        C_t = f_t * C_prev + i_t * C_tilde_t

        # Output gate
        o_t = self._sigmoid(concat @ self.W_o + self.b_o)
        h_t = o_t * np.tanh(C_t)

        return h_t, C_t

    def _sigmoid(self, x):
        return 1 / (1 + np.exp(-np.clip(x, -500, 500)))


class GRUCell:
    """
    GRU cell with reset and update gates
    """
    def __init__(self, input_size, hidden_size):
        self.input_size = input_size
        self.hidden_size = hidden_size

        # Weight matrices
        self.W_r = np.random.randn(input_size + hidden_size, hidden_size) * 0.01
        self.W_z = np.random.randn(input_size + hidden_size, hidden_size) * 0.01
        self.W_h = np.random.randn(input_size + hidden_size, hidden_size) * 0.01

        self.b_r = np.zeros((1, hidden_size))
        self.b_z = np.zeros((1, hidden_size))
        self.b_h = np.zeros((1, hidden_size))

    def forward(self, x_t, h_prev):
        """
        Single GRU step
        x_t: (batch_size, input_size)
        h_prev: (batch_size, hidden_size)
        """
        concat = np.hstack((h_prev, x_t))

        # Reset and update gates
        r_t = self._sigmoid(concat @ self.W_r + self.b_r)
        z_t = self._sigmoid(concat @ self.W_z + self.b_z)

        # Candidate hidden state (with reset applied)
        concat_reset = np.hstack((r_t * h_prev, x_t))
        h_tilde_t = np.tanh(concat_reset @ self.W_h + self.b_h)

        # Hidden state update
        h_t = (1 - z_t) * h_prev + z_t * h_tilde_t

        return h_t

    def _sigmoid(self, x):
        return 1 / (1 + np.exp(-np.clip(x, -500, 500)))


# ===== Example: Character-Level Language Model =====

class CharLevelLSTM:
    """
    Character-level language model using LSTM
    """
    def __init__(self, hidden_size=128):
        self.hidden_size = hidden_size
        self.chars = set()
        self.char_to_idx = {}
        self.idx_to_char = {}
        self.lstm_cell = None
        self.W_hy = None
        self.b_y = None

    def build_vocab(self, text):
        """Build character vocabulary from text"""
        self.chars = sorted(list(set(text)))
        self.char_to_idx = {c: i for i, c in enumerate(self.chars)}
        self.idx_to_char = {i: c for i, c in enumerate(self.chars)}

        vocab_size = len(self.chars)
        self.lstm_cell = LSTMCell(vocab_size, self.hidden_size)
        self.W_hy = np.random.randn(self.hidden_size, vocab_size) * 0.01
        self.b_y = np.zeros((1, vocab_size))

    def forward_sequence(self, sequence_chars):
        """
        Forward pass through sequence of characters
        sequence_chars: list of characters
        Returns: outputs, final_h, final_C
        """
        batch_size = 1
        h = np.zeros((batch_size, self.hidden_size))
        C = np.zeros((batch_size, self.hidden_size))
        outputs = []

        for char in sequence_chars:
            char_idx = self.char_to_idx[char]
            x_t = np.zeros((1, len(self.chars)))
            x_t[0, char_idx] = 1  # one-hot encode

            h, C = self.lstm_cell.forward(x_t, h, C)
            y_t = self._softmax(h @ self.W_hy + self.b_y)
            outputs.append(y_t)

        return outputs, h, C

    def compute_loss(self, sequence_chars):
        """
        Compute cross-entropy loss for predicting next character
        """
        outputs, _, _ = self.forward_sequence(sequence_chars[:-1])
        targets = sequence_chars[1:]

        loss = 0
        for output, target_char in zip(outputs, targets):
            target_idx = self.char_to_idx[target_char]
            loss -= np.log(output[0, target_idx] + 1e-8)

        return loss / len(targets)

    def generate(self, seed_char, length=100):
        """
        Generate text given a seed character
        """
        h = np.zeros((1, self.hidden_size))
        C = np.zeros((1, self.hidden_size))
        generated = seed_char

        char = seed_char
        for _ in range(length):
            char_idx = self.char_to_idx[char]
            x_t = np.zeros((1, len(self.chars)))
            x_t[0, char_idx] = 1

            h, C = self.lstm_cell.forward(x_t, h, C)
            y_t = self._softmax(h @ self.W_hy + self.b_y)

            # Sample next character
            next_idx = np.random.choice(len(self.chars), p=y_t[0])
            char = self.idx_to_char[next_idx]
            generated += char

        return generated

    def _softmax(self, x):
        exp_x = np.exp(x - np.max(x))
        return exp_x / np.sum(exp_x)


# ===== Example Training =====

if __name__ == "__main__":
    # Simple character dataset
    text = "hello world hello world" * 10

    # Create and train model
    model = CharLevelLSTM(hidden_size=32)
    model.build_vocab(text)

    # Training loop (simplified)
    for epoch in range(100):
        loss = model.compute_loss(text[:20])
        if (epoch + 1) % 10 == 0:
            print(f"Epoch {epoch+1}, Loss: {loss:.4f}")

    # Generate text
    generated = model.generate('h', length=50)
    print(f"Generated: {generated}")
            

Usage Guide

For SimpleRNN:

# Create RNN
rnn = SimpleRNN(input_size=10, hidden_size=20, output_size=3)

# Prepare sequence (list of T arrays, each shape (batch_size, input_size))
sequence = [np.random.randn(32, 10) for _ in range(15)]  # 15 steps, batch size 32

# Forward pass
outputs, final_h = rnn.forward(sequence)

# outputs is list of 15 arrays, each (32, 3) — probabilities at each step
# final_h is (32, 20) — final hidden state
            

For CharLevelLSTM:

# Initialize model
model = CharLevelLSTM(hidden_size=128)
model.build_vocab("your text data here")

# Compute loss on a sequence
loss = model.compute_loss("hello")

# Generate new text
generated_text = model.generate('h', length=200)
            

Key Implementation Details

• Weight Initialization: Small random values (×0.01) to start in a stable region
• Sigmoid Clipping: np.clip prevents overflow in exponential
• One-Hot Encoding: Characters represented as one-hot vectors before input
• Softmax: Subtracting max for numerical stability (prevents overflow)
• Loss: Cross-entropy: -log(predicted probability of true class)

Loading Real Data (Optional)

To train on actual text data, download a dataset:

import urllib.request

# Download Penn Treebank dataset
url = "https://s3.amazonaws.com/research.metamind.io/wikitext/wikitext-2-v1.zip"
urllib.request.urlretrieve(url, "wikitext-2.zip")

# Extract and use:
with open("wikitext-2/train.txt", "r") as f:
    text = f.read()

model = CharLevelLSTM(hidden_size=256)
model.build_vocab(text)

# Training loop (with gradient updates omitted for brevity)
for epoch in range(10):
    # Divide text into sequences of length 50
    for i in range(0, len(text) - 50, 50):
        sequence = text[i:i+50]
        loss = model.compute_loss(sequence)
        # In practice, use gradient descent to update weights