Bidirectional RNNs

What Problem Does This Solve?

In vanilla RNNs, the hidden state $h_t$ at time $t$ only encodes information from inputs $x_1, x_2, \ldots, x_t$. This is perfect for causal tasks (predicting the next word) but terrible for tasks where the answer depends on the full context:

• Named Entity Recognition: "Paris" in "I live in Paris" (city) vs "Paris Hilton visited" (person) – you need words after "Paris"
• Machine Translation: Word order differs across languages; translating word 3 might require knowing word 7
• Speech Recognition: A phoneme's identity often depends on following phonemes
• Sentiment Analysis: "This movie is not bad" – "not" changes everything, but appears before "bad"

Standard RNNs are causally constrained – they can't "peek ahead." Bidirectional RNNs lift this constraint when the full sequence is available at inference time.

The Architecture: Two RNNs, One Forward, One Backward

Deriving the Forward Pass from First Principles

Let's build this step-by-step. Start with a standard RNN cell equation:

$h_t = \tanh(W_{h} h_{t-1} + W_{xh} x_t + b_h)$

Why this form? The hidden state is a nonlinear combination of (1) the previous hidden state $h_{t-1}$ (memory) and (2) the current input $x_t$ (new information). The tanh squashes to [-1, 1] to prevent exploding values.

Now, for a bidirectional architecture:

Forward RNN (processes left-to-right): $\overrightarrow{h}_t = \tanh(W_{\overrightarrow{h}} \overrightarrow{h}_{t-1} + W_{\overrightarrow{x}} x_t + b_{\overrightarrow{h}})$

• Starts with $\overrightarrow{h}_0 = \mathbf{0}$ (or learned initialization)
• At $t=1$: $\overrightarrow{h}_1$ depends only on $x_1$
• At $t=2$: $\overrightarrow{h}_2$ depends on $x_1, x_2$ (through $\overrightarrow{h}_1$)
• At $t=T$: $\overrightarrow{h}_T$ encodes the entire past sequence $x_1, \ldots, x_T$

Backward RNN (processes right-to-left): $\overleftarrow{h}_t = \tanh(W_{\overleftarrow{h}} \overleftarrow{h}_{t+1} + W_{\overleftarrow{x}} x_t + b_{\overleftarrow{h}})$

• Starts with $\overleftarrow{h}_{T+1} = \mathbf{0}$
• At $t=T$: $\overleftarrow{h}_T$ depends only on $x_T$
• At $t=T-1$: $\overleftarrow{h}_{T-1}$ depends on $x_T, x_{T-1}$ (through $\overleftarrow{h}_T$)
• At $t=1$: $\overleftarrow{h}_1$ encodes the entire future sequence $x_2, \ldots, x_T$

Why separate weight matrices? The forward and backward RNNs are learning different patterns (past vs. future dependencies), so they need independent parameters. Sharing weights would force both directions to learn a compromise representation.

Combining the outputs at each timestep:

The final output layer (for a task like NER or POS tagging): $y_t = \text{softmax}(W_y h_t + b_y) = \text{softmax}(W_y [\overrightarrow{h}_t; \overleftarrow{h}_t] + b_y)$

Why softmax here? We're making a classification decision (e.g., "is this word a PERSON or LOCATION?") at each timestep, so we need a probability distribution over classes.

The Full Forward Pass Algorithm

Given input sequence $\mathbf{x} = (x_1, x_2, \ldots, x_T)$:

1. Initialize: $\overrightarrow{h}_0 = \mathbf{0}$, $\overleftarrow{h}_{T+1} = \mathbf{0}$

2. Forward pass (left-to-right):

   for t = 1 to T:
       h⃗ₜ = tanh(W_h⃗ h⃗ₜ₋₁ + W_x⃗ xₜ + b_h⃗)
   

3. Backward pass (right-to-left):

   for t = T down to 1:
       h⃖ₜ = tanh(W_h⃖ h⃖ₜ₊₁ + W_x⃖ xₜ + b_h⃖)
   

4. Combine:

   for t = 1 to T:
       hₜ = [h⃗ₜ; h⃖ₜ]
       yₜ = softmax(Wᵧ hₜ + bᵧ)
   

Why two separate loops? The forward RNN must complete before we can compute backward RNN outputs because $\overleftarrow{h}_t$ depends on $\overleftarrow{h}_{t+1}$, which requires processing from right-to-left. In practice, frameworks vectorize this efficiently.

Worked Example: Named Entity Recognition

When to Use Bidirectional RNNs (and When Not To)

Use BiRNs when:

• The entire sequence is available at inference time (offline processing)
• The task is non-causal: the label/output at position $t$ can depend on inputs at positions $> t$
• Examples: NER, POS tagging, machine translation (encoder side), speech recognition (offline), sentiment analysis, question answering (encoding the question or passage)

Do NOT use BiRNNs when:

• The task is causal/autoregressive: predicting the next token (language modeling, text generation, online speech recognition)
• Why? At time $t$, you don't have access to $x_{t+1}, x_{t+2}, \ldots$ yet. Using a BiRNN here would be "cheating" – your model can't deploy in a real-time setting.
• Real-world constraint: If you need to make predictions as the sequence arrives (e.g., live captioning, chatbots), you can't wait for the full sequence to run the backward pass.

Computational Considerations

Time complexity:

• Unidirectional RNN: $O(T \cdot d_h^2)$ for a sequence of length $T$ with hidden dimension $d_h$
• Bidirectional RNN: $O(2 \cdot T \cdot d_h^2) = O(T \cdot d_h^2)$ (same order, but2× constants)

Why? You're running two RNNs, each with $T$ timesteps and $O(d_h^2)$ work per step (matrix multiply $W_{hh} h_{t-1}$).

Space complexity:

• Must store both $\overrightarrow{h}_1, \ldots, \overrightarrow{h}_T$ and $\overleftarrow{h}_1, \ldots, \overleftarrow{h}_T$ for backpropagation
• Total: $O(2 \cdot T \cdot d_h)$ memory

Paralelization:

• Forward and backward passes are not paralelizable within themselves (sequential dependency: $h_t$ depends on $h_{t-1}$)
• But forward and backward RNNs are independent, so you can compute them in parallel if you have multiple GPUs or batch-process multiple sequences
• Contrast with Transformers: Transformers process all timesteps in parallel (self-attention), making them much faster on modern hardware

Backpropagation Through Time (BPTT) for BiRNNs

During training, we need gradients with respect to all parameters: $W_{\overrightarrow{h}}, W_{\overrightarrow{x}}, W_{\overleftarrow{h}}, W_{\overleftarrow{x}}, W_y$.

Loss function (e.g., for sequence tagging): $\mathcal{L} = \sum_{t=1}^T \text{CrossEntropy}(y_t, \hat{y}_t)$

Gradient flow:

1. Compute $\frac{\partial \mathcal{L}}{\partial h_t}$ (gradient w.r.t. combined hidden state)
2. Since $h_t = [\overrightarrow{h}_t; \overleftarrow{h}_t]$, split into $\frac{\partial \mathcal{L}}{\partial \overrightarrow{h}_t}$ and $\frac{\partial \mathcal{L}}{\partial \overleftarrow{h}_t}$
3. Forward RNN gradients flow backward in time (right-to-left through the forward chain): $\frac{\partial \mathcal{L}}{\partial \overrightarrow{h}_{t-1}} = \frac{\partial \mathcal{L}}{\partial \overrightarrow{h}_t} \cdot \frac{\partial \overrightarrow{h}_t}{\partial \overrightarrow{h}_{t-1}} = \frac{\partial \mathcal{L}}{\partial \overrightarrow{h}_t} \cdot W_{\overrightarrow{h}}^T \cdot \text{tanh}'(\cdots)$
4. Backward RNN gradients flow forward in time (left-to-right through the backward chain): $\frac{\partial \mathcal{L}}{\partial \overleftarrow{h}_{t+1}} = \frac{\partial \mathcal{L}}{\partial \overleftarrow{h}_t} \cdot \frac{\partial \overleftarrow{h}_t}{\partial \overleftarrow{h}_{t+1}} = \frac{\partial \mathcal{L}}{\partial \overleftarrow{h}_t} \cdot W_{\overleftarrow{h}}^T \cdot \text{tanh}'(\cdots)$

Why this is tricky: You have two vanishing/exploding gradient problems (one per RNN). The same solutions apply: use LSTMs/GRUs, gradient clipping, careful initialization.

Bidirectional LSTMs (BiLSTMs)

In practice, vanilla BiRNNs are rarely used because of vanishing gradients. Instead, we use Bidirectional LSTMs (BiLSTMs) or Bidirectional GRUs (BiGRUs).

The architecture is identical, but each RNN cell is replaced with an LSTM/GRU cell:

$\overrightarrow{h}_t, \overrightarrow{c}_t = \text{LSTM}_{\text{forward}}(x_t, \overrightarrow{h}_{t-1}, \overrightarrow{c}_{t-1})$ $\overleftarrow{h}_t, \overleftarrow{c}_t = \text{LSTM}_{\text{backward}}(x_t, \overleftarrow{h}_{t+1}, \overleftarrow{c}_{t+1})$ $h_t = [\overrightarrow{h}_t; \overleftarrow{h}_t]$

Why LSTMs? The cell state $c_t$ provides a "highway" for gradients, mitigating vanishing gradients over long sequences. This is crucial for NLP tasks where dependencies can span20+ words.

Example task: Sentiment analysis on "The movie was not particularly bad, but the acting was terrible."

• Forward LSTM at "not": encodes "The movie was not"
• Backward LSTM at "not": encodes "not particularly bad, but the acting was terrible"
• Combined: the model learns that "not...bad" is a negation, but "acting was terrible" dominates the sentiment

Connections

• Recurrent Neural Networks (RNNs): Bidirectional RNNs are built from two unidirectional RNNs
• LSTM and GRU Cells: BiLSTMs and BiGRUs solve vanishing gradients in BiRNNs
• Encoder-Decoder Architecture: BiRNNs are commonly used in the encoder (encode full source sentence) but never the decoder (autoregressive generation)
• Attention Mechanism: Often applied on top of BiRNN outputs to weigh timesteps differently
• Transformers: Replace BiRNNs with self-attention for better parallelization, but the intuition (full-sequence context) is similar
• Named Entity Recognition: Canonical application of BiRNNs/BiLSTMs
• Part-of-Speech Tagging: Another sequence labeling task where BiRNNs excel
• Sequence-to-Sequence Models: BiRNNs in the encoder allow decoder to attend over full input context

#flashcards/ai-ml

What is the key difference between a unidirectional RNN and a Bidirectional RNN? :: A unidirectional RNN processes the sequence in one direction (left-to-right), so $h_t$ only depends on past inputs $x_1, \ldots, x_t$. A Bidirectional RNN has two RNNs: one processes left-to-right ($\overrightarrow{h}_t$), one processes right-to-left ($\overleftarrow{h}_t$), and at each timestep $h_t = [\overrightarrow{h}_t; \overleftarrow{h}_t]$, giving access to both past and future context.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)