23-204-0603 DEEP LEARNING

CUSAT Scheme 2023

MODULE IV: RNNs, LSTMs & Recursive Networks — Complete Exam-
Ready Notes

MODULE IV: RECURRENT & RECURSIVE NEURAL

NETWORKS
This module covers sequence modeling with Recurrent Neural Networks (RNNs), the powerful
LSTM architecture that solves long-term dependency problems, and Recursive Neural Networks for
tree-structured data. These architectures are essential for NLP, time-series, and speech processing.

1. RECURRENT NEURAL NETWORKS (RNNs)

Definition
A Recurrent Neural Network (RNN) is a class of neural network designed to process sequential
data. Unlike feedforward networks that process each input independently, RNNs maintain a hidden
state (memory) that captures information from previous time steps. This makes them suitable for
tasks where context from earlier in the sequence matters (e.g., language, speech, time series).

Modeling the Time Dimension

Real-world data is often sequential — words in a sentence, stock prices over time, audio samples,
video frames. The key challenge is: How do we incorporate information from previous time steps
into the current prediction?
• Fixed-length inputs in MLPs ignore temporal order — previous timesteps have no influence
on current prediction.
• RNNs solve this by passing a hidden state h(t) from one time step to the next, acting as a
running memory of the sequence.

General RNN Architecture

At each time step t, the RNN takes:
• x(t): Current input (e.g., current word vector or stock price)
• h(t-1): Hidden state from the previous time step (memory)
And produces:
• h(t): New hidden state (updated memory)
• y(t): Output at current time step (optional)

RNN Equations
h(t) = tanh(W_hh * h(t-1) + W_xh * x(t) + b_h)
y(t) = W_hy * h(t) + b_y
Where:
• W_hh: Weight matrix for hidden-to-hidden connections (recurrent weights)
 • W_xh: Weight matrix for input-to-hidden connections
• W_hy: Weight matrix for hidden-to-output connections
• b_h, b_y: Bias vectors
• tanh: Activation function (or ReLU in some variants)
Key property: The SAME weights W_hh, W_xh, W_hy are used at EVERY time step (weight sharing
over time).

Diagram Description (Draw in Exam)

[DIAGRAM — UNROLLED RNN]: Draw a horizontal sequence of identical boxes:
• Draw 4 boxes horizontally, each labeled 'RNN Cell'
• Below each box: arrow pointing up labeled 'x(t-1)', 'x(t)', 'x(t+1)', 'x(t+2)' (inputs)
• Above each box: arrow pointing up labeled 'y(t-1)', 'y(t)', 'y(t+1)', 'y(t+2)' (outputs)
• Horizontal arrows between boxes: 'h(t-1) -> h(t) -> h(t+1) -> h(t+2)' (hidden state flow)
• Label: 'Unrolled RNN: Same weights W at every time step'
• Option: Also draw the 'folded' version — a single box with a loop arrow on hidden state

3D Volumetric Input
When input data has a 3D structure (e.g., video frames, volumetric medical scans), the input x(t) at
each time step is itself a 3D tensor (H x W x C), not just a vector. This requires specialized
processing:
• CNN+RNN: Use a CNN to extract spatial features from each frame, then feed the feature
vector into an RNN for temporal modeling.
• 3D CNNs: Treat time as a third spatial dimension. Filter moves in H, W, and T dimensions
simultaneously. Used for action recognition in videos.
• ConvLSTM: An LSTM variant where matrix multiplications are replaced by convolutions.
Processes spatiotemporal data directly.

Why Not Markov Models?

Markov models (like Hidden Markov Models - HMMs) are traditional sequence models. They are
based on the Markov assumption:
P(x(t) | x(1),...,x(t-1)) = P(x(t) | x(t-1)) [1st Order Markov]
This means: the current state depends ONLY on the immediately preceding state.
• Problem 1: Limited Context. In language, 'The bank of the river...' — understanding 'bank'
requires long-range context. Markov models can't capture this.
• Problem 2: State Space Explosion. Higher-order Markov models (considering k previous
states) have exponentially growing state spaces.
• Problem 3: No Feature Learning. HMMs require hand-crafted features; they don't learn
representations.
• RNNs overcome these: Hidden state h(t) theoretically captures the ENTIRE history of the
sequence, not just the last k steps.
EXAM COMPARISON: HMM uses fixed Markov assumption (1-step memory). RNN has
theoretically unlimited memory via hidden state. In practice, RNNs have vanishing
gradient issues for long sequences, which LSTMs solve.
2. TRAINING RNNs: BACKPROPAGATION THROUGH TIME (BPTT)
Definition
RNNs are trained using Backpropagation Through Time (BPTT). The RNN is 'unrolled' through time
steps, creating a deep feedforward network where depth = sequence length. Standard
backpropagation is then applied to this unrolled network.

Problems with BPTT

• Vanishing Gradient: Gradients shrink exponentially as they propagate back through long
sequences. Early time steps receive nearly zero gradient -> network fails to learn long-range
dependencies.
• Exploding Gradient: Gradients grow exponentially -> unstable training. Solution: Gradient
clipping (clip gradients to a maximum norm).
• Truncated BPTT: In practice, backpropagate only through the last k time steps (k=20-50) to
save computation and mitigate vanishing gradients.

3. LONG SHORT-TERM MEMORY (LSTM) NETWORKS

Definition
Long Short-Term Memory (LSTM) is a type of RNN architecture designed specifically to solve the
vanishing gradient problem and capture long-range dependencies in sequences. Introduced by
Hochreiter and Schmidhuber in 1997, LSTMs use a gating mechanism to control what information is
remembered, forgotten, and output at each time step.

Motivation: The Problem with Vanilla RNNs

In a standard RNN, information from many steps ago is largely forgotten due to vanishing gradients.
For example, in 'I grew up in France... I speak ___', the network needs to remember 'France' from
many steps back to predict 'French'. Vanilla RNNs fail at this.

Key Innovation: The Cell State

LSTMs introduce a cell state c(t) — a separate, protected memory line that runs through the entire
sequence with only minor linear interactions. This 'highway' allows gradients to flow more easily
through many time steps, enabling learning of long-range dependencies.

LSTM Architecture: The Four Gates

Each LSTM cell has four main components:

Gate 1: Forget Gate

Decides what information to ERASE from the cell state. Output is a vector of values between 0 and
1 (0 = completely forget, 1 = completely keep).
f(t) = sigmoid(W_f * [h(t-1), x(t)] + b_f)
• W_f: Weight matrix for forget gate
• [h(t-1), x(t)]: Concatenation of previous hidden state and current input
• f(t) near 0: Forget most of cell state. f(t) near 1: Keep most of cell state.

Gate 2: Input Gate (and Candidate Cell State)

Decides what NEW information to ADD to the cell state. Two parts:
i(t) = sigmoid(W_i * [h(t-1), x(t)] + b_i) [Input gate]
g(t) = tanh(W_g * [h(t-1), x(t)] + b_g) [Candidate cell state]
 • i(t): How much of the new candidate to add (0 to 1).
• g(t): New candidate values (new content to potentially write to cell state, range -1 to 1).

Cell State Update

Combine forget gate (what to erase) and input gate (what to write):
c(t) = f(t) * c(t-1) + i(t) * g(t)
• f(t) * c(t-1): Forget part of old cell state.
• i(t) * g(t): Add selected portion of new candidate.
• This is the KEY equation — element-wise operations, no matrix multiplication. Gradient can
flow back through this addition without vanishing!

Gate 3: Output Gate

Decides what to OUTPUT from the cell state as the hidden state h(t):
o(t) = sigmoid(W_o * [h(t-1), x(t)] + b_o) [Output gate]
h(t) = o(t) * tanh(c(t)) [Hidden state]
• o(t): What parts of the cell state to expose as output.
• tanh(c(t)): Normalized cell state (range -1 to 1).
• h(t): Output/hidden state passed to next time step and to prediction layer.

Diagram Description (Draw in Exam)

[DIAGRAM — LSTM CELL]: Draw a rectangular box with the following internal structure:
• Inputs entering from left: h(t-1) and x(t) concatenated
• Four sigmoid/tanh boxes inside: labeled 'f(t) [Forget]', 'i(t) [Input]', 'g(t) [Cell candidate, tanh]',
'o(t) [Output]'
• Top horizontal line: 'Cell State c(t-1) -> * f(t) -> + i(t)*g(t) -> c(t)' (cell state highway)
• From c(t): tanh -> * o(t) -> h(t) (output computation)
• Outputs: h(t) exits right and upward
• Symbols: * = element-wise multiply, + = element-wise add
• Labels on gates with their formulas

Why LSTMs Solve Vanishing Gradient

• The cell state update c(t) = f(t)*c(t-1) + i(t)*g(t) involves addition, not multiplication by a
weight matrix. Gradients flow through addition with little change.
• The forget gate f(t) can be set close to 1, meaning the cell state passes through almost
unchanged over many steps, allowing gradients to flow back.
• The gating mechanism (learned during training) allows the network to decide when to
remember and when to forget.
EXAM KEY: LSTM has 4 equations: Forget gate (f), Input gate (i), Candidate (g), Output
gate (o), plus Cell state update (c) and hidden state (h). Total = 6 key equations. Cell state
= long-term memory. Hidden state = short-term memory/output.

GRU: Gated Recurrent Unit (Simplified LSTM)

GRU is a simplified version of LSTM with only 2 gates (Reset gate and Update gate) and no
separate cell state. Fewer parameters, similar performance on many tasks.
z(t) = sigmoid(W_z * [h(t-1), x(t)]) [Update gate]
r(t) = sigmoid(W_r * [h(t-1), x(t)]) [Reset gate]
h_tilde(t) = tanh(W * [r(t)*h(t-1), x(t)]) [Candidate]
 h(t) = (1-z(t)) * h(t-1) + z(t) * h_tilde(t) [Output]
• Update gate z(t): Controls how much of the previous hidden state to keep.
• Reset gate r(t): Controls how much of the past to forget when computing candidate.

RNN vs LSTM Comparison

Feature Vanilla RNN LSTM
Memory Hidden state h(t) only Cell state c(t) + hidden state h(t)
Gates None Forget, Input, Output gates
Long-term Dependencies Fails (vanishing gradient) Handles effectively
Parameters Fewer 4x more than vanilla RNN
Training Faster (simpler) Slower (more computation)
Gradient Flow Multiplicative (vanishes) Additive (stable)
Use Case Short sequences only Long sequences, NLP, speech

4. DOMAIN SPECIFIC APPLICATIONS AND BLENDED NETWORKS

Domain-Specific RNN/LSTM Applications
• Natural Language Processing (NLP): Language modeling (predict next word), machine
translation, text generation, question answering, sentiment analysis.
• Speech Recognition: Convert audio sequences to text. Input: Spectrogram frames. Output:
Characters or words.
• Time Series Forecasting: Predict stock prices, weather, energy consumption.
• Music Generation: Generate music notes/sequences.
• Video Captioning: Describe video content in words.
• Handwriting Recognition: Process stroke sequences.

Blended Networks (Hybrid Architectures)

Modern deep learning combines different network types to leverage the strengths of each:
• CNN + RNN: CNN extracts spatial features from images/frames; RNN models temporal
dependencies. Used in: Video captioning, action recognition, image captioning.
Example — Image Captioning: CNN encodes image -> feature vector. LSTM decodes feature
vector -> sequence of words.
• CNN + LSTM for Video: CNN processes each video frame independently -> frame features
fed into LSTM -> sequence-level understanding.
• Transformer (Attention-based): Modern NLP uses self-attention instead of recurrence.
BERT, GPT — no RNN, but learned from RNN/LSTM ideas.
• Seq2Seq (Encoder-Decoder): RNN encoder compresses input sequence to context vector.
RNN decoder generates output sequence from context vector. Used in machine translation,
summarization.

Seq2Seq Architecture
[DIAGRAM Description]:
• Left section: 'Encoder RNN' — processes input sequence word by word, produces context
vector c at the end
• Right section: 'Decoder RNN' — takes context vector c as initial hidden state, generates
output sequence word by word
• Arrow: 'Context Vector c' connecting encoder output to decoder input
• Example: Input: 'Je mange' -> Context c -> Output: 'I eat'
5. RECURSIVE NEURAL NETWORKS
Definition
Recursive Neural Networks (RecNNs or TreeNNs) are a generalization of RNNs that operate on
tree-structured data rather than sequences. They process inputs with hierarchical (tree/graph)
structures by recursively applying the same neural network module at each node of the tree, from
leaves to root.
Key distinction: RNN processes LINEAR sequences (left to right). Recursive NN processes TREE
STRUCTURES (bottom-up, leaf to root).

Motivation
Many data structures in the real world are hierarchical rather than sequential:
• Parse trees (grammatical structure of sentences)
• Abstract syntax trees (program code structure)
• Knowledge graphs and semantic hierarchies
• Molecular structures in chemistry
• Organizational hierarchies
Recursive NNs exploit this hierarchical structure to build compositional representations.

Network Architecture
A Recursive NN processes a tree by:
• Leaf nodes: Receive input vectors (e.g., word embeddings at leaf nodes in a parse tree).
• Internal nodes: Combine children's representations using a shared neural network function.
• Root node: Produces the final representation of the entire tree.
h(parent) = f(W * [h(left_child); h(right_child)] + b)
Where f is a non-linear activation function, W is the weight matrix (SAME for all internal nodes), [;]
denotes concatenation, and h is the vector representation at each node.

Diagram Description (Draw in Exam)

[DIAGRAM — Recursive NN on Binary Tree]:
• Draw a tree with root at top, leaves at bottom
• Leaves (bottom): 'x1', 'x2', 'x3', 'x4' — word vectors
• Level 2 (internal nodes): 'h(1,2) = f(W*[x1;x2]+b)' and 'h(3,4) = f(W*[x3;x4]+b)'
• Root (top): 'h(root) = f(W*[h(1,2);h(3,4)]+b)' — sentence representation
• Arrows point upward (leaf to root)
• Note: Same W used at every internal node

Training Recursive NNs

• The tree structure must be known in advance (e.g., from a parser for sentences).
• Backpropagation Through Structure (BPTS): Analogous to BPTT, but gradients propagate
through the tree structure.
• Loss can be applied at root (sentence-level) or at multiple nodes (phrase-level).

6. VARIETIES OF RECURSIVE NEURAL NETWORKS

Standard Recursive NN (Vanilla RecNN)
• Uses same weight matrix at all nodes.
 • Simple but doesn't distinguish different types of compositions (subject-verb vs noun-
adjective).

Matrix-Vector Recursive NN (MV-RNN)

• Each word/phrase has both a vector (meaning) and a matrix (how it modifies other
meanings).
• Allows capturing more complex compositional semantics.
• Example: 'very good' — 'very' modifies 'good' differently than 'not good'.

Recursive Neural Tensor Network (RNTN)

Proposed by Socher et al. (2013). Uses a tensor instead of a matrix for composition:
h = f([left; right]^T * V * [left; right] + W * [left; right] + b)
• V is a 3D tensor — allows more expressive interactions between children.
• Achieves state-of-the-art sentiment analysis (Stanford Sentiment Treebank).

Tree LSTM
• Combines LSTM gating mechanisms with tree-structured recursion.
• Each node has its own cell state and hidden state, like LSTM.
• Children's cell states and hidden states are gated before combining at parent.
• Two variants: Child-Sum Tree LSTM (variable number of children) and N-ary Tree LSTM
(fixed number of children).
h(parent) = LSTM-style composition of h(children) with gates

Graph Neural Networks (GNNs) — Extension

• Recursive NNs handle trees. GNNs generalize to arbitrary graph structures.
• Each node aggregates information from its neighbors iteratively.
• Used for molecular property prediction, social networks, knowledge graphs.

7. APPLICATIONS OF RECURSIVE NEURAL NETWORKS

Natural Language Processing
• Sentiment Analysis: Parse tree of sentence -> recursive composition from words to phrases
to full sentence sentiment. Stanford Sentiment Treebank uses RNTN.
• Semantic Compositionality: Learn that 'not good' is not the same as 'good'. Recursive
structure captures nested negation, modification.
• Relation Classification: Identify semantic relationships between entities in sentences.
• Sentence Similarity: Compare two sentences using their tree-structured representations.
• Natural Language Inference (NLI): Determine if one sentence entails, contradicts, or is
neutral to another.

Code Analysis
• Abstract Syntax Trees (ASTs) of programs have natural tree structure.
• Code classification, bug detection, code similarity using RecNNs on ASTs.

Image Scene Graphs

• Describe spatial and semantic relationships between objects in images using tree/graph
structures.
 • Recursive NN processes the scene graph to understand complex scene descriptions.

Drug Discovery and Chemistry

• Molecular graphs have tree-like substructure.
• Recursive/Graph NNs predict molecular properties (binding affinity, toxicity).
EXAM TIP: Recursive NN = Same network applied recursively on a TREE. RNN = Same
network applied on a LINEAR SEQUENCE. Both share weights across applications. Key
difference: structure (tree vs sequence).

Summary Comparison: RNN vs LSTM vs Recursive NN

Feature Vanilla RNN LSTM Recursive NN
Input Structure Linear sequence Linear sequence Tree / hierarchical
Long-term Memory Poor (vanishing) Excellent (cell state) N/A (tree depth)
Weight Sharing Over time steps Over time steps Over tree nodes
Handles Order Yes (sequential) Yes (sequential) Yes (via tree structure)
Best For Short sequences Long sequences, NLP Parse trees, code,
molecules
Training Method BPTT BPTT BPTS (Backprop
through structure)

MODULE IV: KEY SUMMARY FOR EXAM

Topic Key Concept / Formula
RNN Equations h(t) = tanh(W_hh*h(t-1) + W_xh*x(t) + b_h); y(t) = W_hy*h(t) + b_y
Why not Markov Models Limited context (only k steps). State space explosion. No feature
learning.
BPTT Unroll RNN through time -> apply backprop. Suffers vanishing/exploding
gradients.
LSTM - Forget Gate f(t) = sigmoid(W_f * [h(t-1), x(t)] + b_f)
LSTM - Input Gate i(t) = sigmoid(W_i * [h(t-1), x(t)] + b_i)
LSTM - Candidate g(t) = tanh(W_g * [h(t-1), x(t)] + b_g)
LSTM - Cell Update c(t) = f(t)*c(t-1) + i(t)*g(t) [Key equation - additive!]
LSTM - Output Gate o(t) = sigmoid(W_o*[h(t-1),x(t)]+b_o); h(t) = o(t)*tanh(c(t))
GRU Simplified LSTM: 2 gates (update z, reset r). No separate cell state.
Seq2Seq Encoder RNN -> context vector c -> Decoder RNN. For
translation/summarization.
Recursive NN h(parent) = f(W*[h(left);h(right)]+b). Same weights at all tree nodes.
Tree LSTM LSTM gating at each tree node. Combines LSTM + Recursive NN.
RecNN Applications Sentiment analysis (RNTN), code analysis, molecular property
prediction

MASTER SUMMARY: ALL MODULES

Module Key Architectures Core Ideas
Module I Perceptron, MLP, Backprop Biological neuron -> Perceptron -> MLP. Backprop
= chain rule. Activation functions. Loss functions.
Hyperparameters.
Module II RBM, Autoencoder, VAE Deep learning principles. RBM = undirected
graphical model. AE = compress + reconstruct.
VAE = probabilistic AE + reparameterization.
Module III DBN, GAN, CNN DBN = stacked RBMs. GAN = Generator vs
Discriminator. CNN = local filters + pooling + FC
layers.
Module IV RNN, LSTM, Recursive NN RNN for sequences. LSTM solves vanishing
gradient (4 gates + cell state). Recursive NN for
trees.

END OF MODULE IV AND COMPLETE NOTES

These notes cover ALL topics in the CUSAT 23-204-0603 Deep Learning syllabus. Good luck!