Natural Language Processing
with Deep Learning
CS224N/Ling284
Christopher Manning
Lecture 6: Simple and LSTM Recurrent Neural Networks
Lecture Plan
1. RNN Language Models (25 mins)
2. Other uses of RNNs (8 mins)
3. Exploding and vanishing gradients (15 mins)
4. LSTMs (20 mins)
5. Bidirectional and multi-layer RNNs (12 mins)
• Projects
• Next Thursday: a lecture about choosing final projects
• It’s fine to delay thinking about projects until next week
• But if you’re already thinking about projects, you can view some info/inspiration on
the website. It’s still last year’s information at present!
• It’s great if you can line up your own mentor; we also lining up some mentors
2
Overview
3
• Last lecture we learned:
• Language models, n-gram language models, and Recurrent Neural Networks (RNNs)
• Today we’ll learn how to get RNNs to work for you
• Training RNNs
• Uses of RNNs
• Problems with RNNs (exploding and vanishing gradients) and how to fix them
• These problems motivate a more sophisticated RNN architecture: LSTMs
• And other more complex RNN options: bidirectional RNNs and multi-layer RNNs
• Next lecture we’ll learn:
• How we can do Neural Machine Translation (NMT) using an RNN-based architecture
called sequence-to-sequence with attention
1. The Simple RNN Language Model
4
the students opened theirwords / one-hot vectors
books
laptops
word embeddings
a zoo
output distribution
Note: this input sequence could be much
longer now!
hidden states
is the initial hidden state
Training an RNN Language Model
• Get a big corpus of text which is a sequence of words
• Feed into RNN-LM; compute output distribution for every step t.
• i.e., predict probability dist of every word, given words so far
• Loss function on step t is cross-entropy between predicted probability
distribution , and the true next word (one-hot for ):
• Average this to get overall loss for entire training set:
5
Training an RNN Language Model
= negative log prob
of “students”
the students opened their …
examsCorpus
Loss
…
6
Predicted
prob dists
Training an RNN Language Model
the students opened their …
examsCorpus
Loss
…
7
Predicted
prob dists
= negative log prob
of “opened”
Training an RNN Language Model
the students opened their …
examsCorpus
Loss
…
8
Predicted
prob dists
= negative log prob
of “their”
Training an RNN Language Model
the students opened their …
examsCorpus
Loss
…
9
Predicted
prob dists
= negative log prob
of “exams”
Training an RNN Language Model
+ + + + … =
the students opened their …
exams
…
10
Corpus
Loss
Predicted
prob dists
“Teacher forcing”
Training a RNN Language Model
• However: Computing loss and gradients across entire corpus is too
expensive!
• In practice, consider as a sentence (or a document)
• Recall: Stochastic Gradient Descent allows us to compute loss and gradients for small
chunk of data, and update.
• Compute loss for a sentence (actually, a batch of sentences), compute gradients
and update weights. Repeat.
11
Training the parameters of RNNs: Backpropagation for RNNs
12
……
Question: What’s the derivative of w.r.t. the repeated weight matrix ?
Answer:
“The gradient w.r.t. a repeated weight
is the sum of the gradient
w.r.t. each time it appears”
Why?
Multivariable Chain Rule
13
Source:
https://www.khanacademy.org/math/multivariable-calculus/multivariable-derivatives/differentiating-vector-valued-functions/a/multivariable-chain-rule-simple-version
Gradients sum at
outward branches!
(lecture 3)
Backpropagation for RNNs: Proof sketch
14
…
In our example:
equalsequals
equals
Apply the multivariable chain rule:
= 1
Source:
https://www.khanacademy.org/math/multivariable-calculus/multivariable-derivatives/differentiating-vector-valued-functions/a/multivariable-chain-rule-simple-version
Backpropagation for RNNs
……
Question: How do we
calculate this?
Answer: Backpropagate over timesteps
i=t,…,0, summing gradients as you go.
This algorithm is called “backpropagation
through time” [Werbos, P.G., 1988, Neural
Networks 1, and others]
15
Generating text with a RNN Language Model
Just like a n-gram Language Model, you can use an RNN Language Model to
generate text by repeated sampling. Sampled output becomes next step’s input.
my favorite season is
…
sample
favorite
sample
season
sample
is
sample
spring
spring16
Generating text with an RNN Language Model
Let’s have some fun!
• You can train an RNN-LM on any kind of text, then generate text in that style.
• RNN-LM trained on Harry Potter:
Source: https://medium.com/deep-writing/harry-potter-written-by-artificial-intelligence-8a9431803da6
17
Generating text with an RNN Language Model
Let’s have some fun!
• You can train an RNN-LM on any kind of text, then generate text in that style.
• RNN-LM trained on recipes:
Source: https://gist.github.com/nylki/1efbaa36635956d35bcc
18
Evaluating Language Models
• The standard evaluation metric for Language Models is perplexity.
• This is equal to the exponential of the cross-entropy loss :
19
Inverse probability of corpus, according to Language Model
Normalized by
number of words
Lower perplexity is better!
RNNs have greatly improved perplexity
n-gram model
Increasingly
complex RNNs
Perplexity improves
(lower is better)
Source: https://research.fb.com/building-an-efficient-neural-language-model-over-a-billion-words/
20
Why should we care about Language Modeling?
21
• Language Modeling is a benchmark task that helps us
measure our progress on understanding language
• Language Modeling is a subcomponent of many NLP tasks, especially those involving
generating text or estimating the probability of text:
• Predictive typing
• Speech recognition
• Handwriting recognition
• Spelling/grammar correction
• Authorship identification
• Machine translation
• Summarization
• Dialogue
• etc.
Recap
• Language Model: A system that predicts the next word
• Recurrent Neural Network: A family of neural networks that:
• Take sequential input of any length
• Apply the same weights on each step
• Can optionally produce output on each step
• Recurrent Neural Network ≠ Language Model
• We’ve shown that RNNs are a great way to build a LM
• But RNNs are useful for much more!
22
2. Other RNN uses: RNNs can be used for sequence tagging
e.g., part-of-speech tagging, named entity recognition
knocked over the vasethe startled cat
VBN IN DT NNDT JJ NN
23
RNNs can be used for sentence classification
the movie a lotoverall I enjoyed
positive
Sentence
encoding
How to compute
sentence encoding?
e.g., sentiment classification
24
RNNs can be used for sentence classification
the movie a lotoverall I enjoyed
positive
Sentence
encoding
equals
How to compute
sentence encoding?
Basic way:
Use final hidden
state
e.g., sentiment classification
25
RNNs can be used for sentence classification
the movie a lotoverall I enjoyed
positive
Sentence
encoding
How to compute
sentence encoding?
Usually better:
Take element-wise
max or mean of all
hidden states
e.g., sentiment classification
26
RNNs can be used as a language encoder module
e.g., question answering, machine translation, many other tasks!
Context: Ludwig
van Beethoven was
a German
composer and
pianist. A crucial
figure …
Beethoven ?what nationality wasQuestion:
Here the RNN acts as an
encoder for the Question (the
hidden states represent the
Question). The encoder is part
of a larger neural system.
Answer: German
lots of neural
architecture
lotsofneural
architecture
27
RNN-LMs can be used to generate text
e.g., speech recognition, machine translation, summarization
what’s the
weatherthewhat’s
This is an example of a conditional language model.
We’ll see Machine Translation in much more detail next class.
28
Input (audio)
<START>
conditioning
RNN-LM
3. Problems with Vanishing and Exploding Gradients
29
Vanishing gradient intuition
30
?
Vanishing gradient intuition
chain rule!
31
Vanishing gradient intuition
chain rule!
32
Vanishing gradient intuition
chain rule!
33
Vanishing gradient intuition
What happens if these are small?
Vanishing gradient problem:
When these are small, the gradient
signal gets smaller and smaller as it
backpropagates further
34
Vanishing gradient proof sketch (linear case)
• Recall:
• What if were the identity function, ?
• Consider the gradient of the loss on step , with respect
to the hidden state on some previous step . Let
35
(chain rule)
Source: “On the difficulty of training recurrent neural networks”, Pascanu et al, 2013. http://proceedings.mlr.press/v28/pascanu13.pdf
(and supplemental materials), at http://proceedings.mlr.press/v28/pascanu13-supp.pdf
(chain rule)
If Wh is “small”, then this term gets
exponentially problematic as becomes large
(value of )
Vanishing gradient proof sketch (linear case)
• What’s wrong with ?
• Consider if the eigenvalues of are all less than 1:
• We can write using the eigenvectors of as a basis:
• What about nonlinear activations (i.e., what we use?)
• Pretty much the same thing, except the proof requires
for some dependent on dimensionality and
36
Source: “On the difficulty of training recurrent neural networks”, Pascanu et al, 2013. http://proceedings.mlr.press/v28/pascanu13.pdf
(and supplemental materials), at http://proceedings.mlr.press/v28/pascanu13-supp.pdf
(eigenvectors)
Approaches 0 as grows, so gradient vanishes
sufficient but
not necessary
Why is vanishing gradient a problem?
Gradient signal from far away is lost because it’s much smaller than gradient signal from close-by.
So, model weights are updated only with respect to near effects, not long-term effects.
37
Effect of vanishing gradient on RNN-LM
• LM task: When she tried to print her tickets, she found that the printer was out of toner.
She went to the stationery store to buy more toner. It was very overpriced. After
installing the toner into the printer, she finally printed her ________
• To learn from this training example, the RNN-LM needs to model the dependency
between “tickets” on the 7th step and the target word “tickets” at the end.
• But if gradient is small, the model can’t learn this dependency
• So, the model is unable to predict similar long-distance dependencies at test time
38
Why is exploding gradient a problem?
• If the gradient becomes too big, then the SGD update step becomes too big:
• This can cause bad updates: we take too large a step and reach a weird and bad
parameter configuration (with large loss)
• You think you’ve found a hill to climb, but suddenly you’re in Iowa
• In the worst case, this will result in Inf or NaN in your network
(then you have to restart training from an earlier checkpoint)
39
learning rate
gradient
Gradient clipping: solution for exploding gradient
40
• Gradient clipping: if the norm of the gradient is greater than some threshold, scale it
down before applying SGD update
• Intuition: take a step in the same direction, but a smaller step
• In practice, remembering to clip gradients is important, but exploding gradients are an
easy problem to solve
Source: “On the difficulty of training recurrent neural networks”, Pascanu et al, 2013. http://proceedings.mlr.press/v28/pascanu13.pdf
How to fix the vanishing gradient problem?
• The main problem is that it’s too difficult for the RNN to learn to preserve information
over many timesteps.
• In a vanilla RNN, the hidden state is constantly being rewritten
• How about a RNN with separate memory?
41
4. Long Short-Term Memory RNNs (LSTMs)
• A type of RNN proposed by Hochreiter and Schmidhuber in 1997 as a solution to the vanishing gradients
problem.
• Everyone cites that paper but really a crucial part of the modern LSTM is from Gers et al. (2000) 💜
• On step t, there is a hidden state and a cell state
• Both are vectors length n
• The cell stores long-term information
• The LSTM can read, erase, and write information from the cell
• The cell becomes conceptually rather like RAM in a computer
• The selection of which information is erased/written/read is controlled by three corresponding gates
• The gates are also vectors length n
• On each timestep, each element of the gates can be open (1), closed (0), or somewhere in-between
• The gates are dynamic: their value is computed based on the current context
42
“Long short-term memory”, Hochreiter and Schmidhuber, 1997. https://www.bioinf.jku.at/publications/older/2604.pdf
“Learning to Forget: Continual Prediction with LSTM”, Gers, Schmidhuber, and Cummins, 2000. https://dl.acm.org/doi/10.1162/089976600300015015
We have a sequence of inputs 𝑥("), and we will compute a sequence of hidden states ℎ(") and cell states
𝑐("). On timestep t:
Long Short-Term Memory (LSTM)
Allthesearevectorsofsamelengthn
Forget gate: controls what is kept vs
forgotten, from previous cell state
Input gate: controls what parts of the
new cell content are written to cell
Output gate: controls what parts of
cell are output to hidden state
New cell content: this is the new
content to be written to the cell
Cell state: erase (“forget”) some
content from last cell state, and write
(“input”) some new cell content
Hidden state: read (“output”) some
content from the cell
Sigmoid function: all gate
values are between 0 and 1
43
Gates are applied using element-wise
(or Hadamard) product: ⊙
Long Short-Term Memory (LSTM)
44
You can think of the LSTM equations visually like this:
Source: http://colah.github.io/posts/2015-08-Understanding-LSTMs/
ct-1
ht-1
ct
ht
ft
it ot
ct
ct
~
Long Short-Term Memory (LSTM)
45
You can think of the LSTM equations visually like this:
Source: http://colah.github.io/posts/2015-08-Understanding-LSTMs/
Compute the
forget gate
Forget some
cell content
Compute the
input gate
Compute the
new cell content
Compute the
output gate
Write some new cell content
Output some cell content
to the hidden state
The + sign is the secret!
How does LSTM solve vanishing gradients?
• The LSTM architecture makes it easier for the RNN to
preserve information over many timesteps
• e.g., if the forget gate is set to 1 for a cell dimension and the input
gate set to 0, then the information of that cell is preserved
indefinitely.
• In contrast, it’s harder for a vanilla RNN to learn a recurrent
weight matrix Wh that preserves info in the hidden state
• In practice, you get about 100 timesteps rather than about 7
• LSTM doesn’t guarantee that there is no vanishing/exploding
gradient, but it does provide an easier way for the model to learn
long-distance dependencies
46
LSTMs: real-world success
• In 2013–2015, LSTMs started achieving state-of-the-art results
• Successful tasks include handwriting recognition, speech recognition, machine
translation, parsing, and image captioning, as well as language models
• LSTMs became the dominant approach for most NLP tasks
• Now (2021), other approaches (e.g., Transformers) have become dominant for many
tasks
• For example, in WMT (a Machine Translation conference + competition):
• In WMT 2016, the summary report contains “RNN” 44 times
• In WMT 2019: “RNN” 7 times, ”Transformer” 105 times
47
Source: "Findings of the 2016 Conference on Machine Translation (WMT16)", Bojar et al. 2016, http://www.statmt.org/wmt16/pdf/W16-2301.pdf
Source: "Findings of the 2018 Conference on Machine Translation (WMT18)", Bojar et al. 2018, http://www.statmt.org/wmt18/pdf/WMT028.pdf
Source: "Findings of the 2019Conference on Machine Translation (WMT19)", Barrault et al. 2019, http://www.statmt.org/wmt18/pdf/WMT028.pdf
Is vanishing/exploding gradient just a RNN problem?
48
• No! It can be a problem for all neural architectures (including feed-forward and
convolutional), especially very deep ones.
• Due to chain rule / choice of nonlinearity function, gradient can become vanishingly small as it
backpropagates
• Thus, lower layers are learned very slowly (hard to train)
• Solution: lots of new deep feedforward/convolutional architectures that add more
direct connections (thus allowing the gradient to flow)
For example:
• Residual connections aka “ResNet”
• Also known as skip-connections
• The identity connection
preserves information by default
• This makes deep networks much
easier to train
"Deep Residual Learning for Image Recognition", He et al, 2015. https://arxiv.org/pdf/1512.03385.pdf
Is vanishing/exploding gradient just a RNN problem?
49
• Solution: lots of new deep feedforward/convolutional architectures that add more
direct connections (thus allowing the gradient to flow)
Other methods:
• Dense connections aka “DenseNet”
• Directly connect each layer to all future layers!
”Densely Connected Convolutional Networks", Huang et al, 2017. https://arxiv.org/pdf/1608.06993.pdf
• Highway connections aka “HighwayNet”
• Similar to residual connections, but the identity
connection vs the transformation layer is
controlled by a dynamic gate
• Inspired by LSTMs, but applied to deep
feedforward/convolutional networks
”Highway Networks", Srivastava et al, 2015. https://arxiv.org/pdf/1505.00387.pdf
Is vanishing/exploding gradient just a RNN problem?
50
• No! It can be a problem for all neural architectures (including feed-forward and
convolutional), especially very deep ones.
• Due to chain rule / choice of nonlinearity function, gradient can become vanishingly small as it
backpropagates
• Thus, lower layers are learned very slowly (hard to train)
• Solution: lots of new deep feedforward/convolutional architectures that add more
direct connections (thus allowing the gradient to flow)
• Conclusion: Though vanishing/exploding gradients are a general problem, RNNs are
particularly unstable due to the repeated multiplication by the same weight matrix
[Bengio et al, 1994]
”Learning Long-Term Dependencies with Gradient Descent is Difficult", Bengio et al. 1994, http://ai.dinfo.unifi.it/paolo//ps/tnn-94-gradient.pdf
5. Bidirectional and Multi-layer RNNs: motivation
51
terribly exciting !the movie was
positive
Sentence
encoding
element-wise mean/max element-wise mean/max
We can regard this hidden state as a
representation of the word “terribly” in the
context of this sentence. We call this a
contextual representation.
These contextual
representations only
contain information
about the left context
(e.g. “the movie
was”).
What about right
context?
In this example,
“exciting” is in the
right context and this
modifies the meaning
of “terribly” (from
negative to positive)
Task: Sentiment Classification
Bidirectional RNNs
52
terribly exciting !the movie was
Forward RNN
Backward RNN
Concatenated
hidden states
This contextual representation of “terribly”
has both left and right context!
Bidirectional RNNs
53
Forward RNN
Backward RNN
Concatenated hidden states
This is a general notation to mean
“compute one forward step of the
RNN” – it could be a vanilla, LSTM
or GRU computation.
We regard this as “the hidden
state” of a bidirectional RNN.
This is what we pass on to the
next parts of the network.
Generally, these
two RNNs have
separate weights
On timestep t:
Bidirectional RNNs: simplified diagram
54
terribly exciting !the movie was
The two-way arrows indicate bidirectionality and
the depicted hidden states are assumed to be the
concatenated forwards+backwards states
Bidirectional RNNs
• Note: bidirectional RNNs are only applicable if you have access to the entire input
sequence
• They are not applicable to Language Modeling, because in LM you only have left
context available.
• If you do have entire input sequence (e.g., any kind of encoding), bidirectionality is
powerful (you should use it by default).
• For example, BERT (Bidirectional Encoder Representations from Transformers) is a
powerful pretrained contextual representation system built on bidirectionality.
• You will learn more about transformers include BERT in a couple of weeks!
55
Multi-layer RNNs
• RNNs are already “deep” on one dimension (they unroll over many timesteps)
• We can also make them “deep” in another dimension by
applying multiple RNNs – this is a multi-layer RNN.
• This allows the network to compute more complex representations
• The lower RNNs should compute lower-level features and the higher RNNs should
compute higher-level features.
• Multi-layer RNNs are also called stacked RNNs.
56
Multi-layer RNNs
57
terribly exciting !the movie was
RNN layer 1
RNN layer 2
RNN layer 3
The hidden states from RNN layer i
are the inputs to RNN layer i+1
Multi-layer RNNs in practice
• High-performing RNNs are often multi-layer (but aren’t as deep as convolutional or
feed-forward networks)
• For example: In a 2017 paper, Britz et al find that for Neural Machine Translation, 2 to 4
layers is best for the encoder RNN, and 4 layers is best for the decoder RNN
• Usually, skip-connections/dense-connections are needed to train deeper RNNs (e.g., 8 layers)
• Transformer-based networks (e.g., BERT) are usually deeper, like 12 or 24 layers.
• You will learn about Transformers later; they have a lot of
skipping-like connections
58
“Massive Exploration of Neural Machine Translation Architecutres”, Britz et al, 2017. https://arxiv.org/pdf/1703.03906.pdf
In summary
59
Lots of new information today! What are some of the practical takeaways?
1. LSTMs are powerful 2. Clip your gradients
3. Use bidirectionality
when possible
4. Multi-layer RNNs are more powerful, but
you might need skip connections if it’s deep