Introduction to Deep Learning
19. Recurrent Neural Networks
STAT 157, Spring 2019, UC Berkeley
Alex Smola and Mu Li
[Link]/berkeley-stat-157
© 2018, Amazon Web Services, Inc. or its Affiliates. All rights reserved.
Recurrent Neural Networks
[Link]/berkeley-stat-157
Latent Variable Autoregressive Models
Latent state summarizes all the relevant information about
the past. So we get ht = f(x1, …xt−1) = f(ht−1, xt−1)
p(ht | ht−1, xt−1) and p(xt | ht, xt−1)
h
[Link]/berkeley-stat-157
Recurrent Neural Networks (with hidden state)
Explanation
Action
[Link]/berkeley-stat-157
Recurrent Neural Networks (with hidden state)
Output o
Explanation h
Observation x
• Hidden State update
ht = ϕ(Whhht−1 + Whx xt−1 + bh)
• Observation update
ot = ϕ(Whoht + bo)
[Link]/berkeley-stat-157
Code …
[Link]/berkeley-stat-157
Implementing an RNN
Language Model
[Link]/berkeley-stat-157
Input Encoding
• Need to map input tokens to vectors
• Pick granularity (words, characters, subwords)
• Map to indicator vectors
• Multiply by embedding matrix W
[Link]/berkeley-stat-157
Input Encoding T H E _ T I M E
1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1
Canonical Vectors v 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
Embedding Matrix W
Embedded Vectors v′
[Link]/berkeley-stat-157
RNN with hidden state mechanics
• Input
vector sequence x1, …, xT
• Hidden States
vector sequence h1, …, hT where ht = f(ht−1, xt)
• Output
vector sequence o1, …, oT where ot = g(ht)
Read sequence to generate hidden states, then start
generating outputs. Often outputs (symbols) are used as
input for next hidden state (and thus output).
[Link]/berkeley-stat-157
Output Decoding
Output Vectors o
Decoding Matrix W′
p(y | o) ∝ exp (v⊤y o) = exp(o[y])
One-hot decoding
[Link]/berkeley-stat-157
Gradients
• Long chain of dependencies for backprop
• Need to keep a lot of intermediate values in memory
• Butterfly effect style dependencies
• Gradients can vanish or diverge (more on this later)
• Clipping to prevent divergence
( ∥g∥ )
θ
g ← min 1, g
rescales to gradient of size at most θ
[Link]/berkeley-stat-157
Perplexity
• Typically measure accuracy with log-likelihood
• This makes outputs of different length incomparable
(e.g. bad model on short output has higher likelihood
than excellent model on very long output)
• Normalize log-likelihood to sequence length
T
1 T
∑ ∑
− log p(yt | model) vs. π := − log p(yt | model)
t=1
T t=1
• Perplexity is exponentiated version exp(π)
(effectively number of possible choices on average)
[Link]/berkeley-stat-157
Code …
[Link]/berkeley-stat-157
Truncated Backprop Through Time
[Link]/berkeley-stat-157
Recurrent Neural Networks (with hidden state)
Output o
Explanation h
Observation x
• Hidden State update
ht = f(ht−1, xt−1, w)
• Observation update
ot = g(ht, w)
[Link]/berkeley-stat-157
Objective function
• RNN generates output which needs to be compared to
target labels
T
∑
L(x, y, w) = l(yt, ot)
t=1
• Gradient T
∑
∂w L = ∂wl(yt, ot)
t=1
T
∂otl(yt, ot)[∂wg(ht, w) + ∂ht g(ht, w)∂wht]
∑
=
t=1
[Link]/berkeley-stat-157
Latent State Gradient ∂wht
• Objective Function
T T
∂otl(yt, ot)[∂wg(ht, w) + ∂ht g(ht, w)∂wht]
∑ ∑
∂w L = ∂wl(yt, ot) =
t=1 t=1
• Gradient Recursion
∂wht = ∂w f(xt, ht−1, w) + ∂h f(xt, ht−1, w)∂wht−1
1 i
∑ ∏
= ∂h f(xj, hj−1, w) ∂w f(xi, hi−1, w)
i=t j=t
[Link]/berkeley-stat-157
Latent State Gradient ∂wht
• Gradient Recursion
1 i
∑ ∏
∂wht = ∂h f(xj, hj−1, w) ∂w f(xi, hi−1, w)
i=t j=t
Too Many
Terms expensive
Unstable
(divergence)
[Link]/berkeley-stat-157
Latent State Gradient ∂wht
• Gradient Recursion
1 i
∑ ∏
∂wht = ∂h f(xj, hj−1, w) ∂w f(xi, hi−1, w)
i=t j=t
Output o
Explanation h
Observation x
[Link]/berkeley-stat-157
Latent State Gradient ∂wht
• Gradient Recursion
1 i
∑ ∏
∂wht = ∂h f(xj, hj−1, w) ∂w f(xi, hi−1, w)
i=t j=t
Drop
gradients
Output
Explanation
Observation
[Link]/berkeley-stat-157
Truncated BPTT
• Don’t truncate (naive strategy, costly and divergent)
• Truncate at fixed intervals
(standard approach, is approximation but works well)
• Variable length (Tallec and Olivier, 2015)
(is exact after reweighting, doesn’t work better in practice)
[Link]/berkeley-stat-157
Truncated BPTT
• Random variable instead of simple truncation
zt = ∂w f(xt, ht−1, w) + ξt∂h f(xt, ht−1, w)∂wht−1
• Variable length (Tallec and Olivier, 2015)
(is exact after reweighting, doesn’t work better in practice)
[Link]/berkeley-stat-157
Computational Graph
[Link]/berkeley-stat-157
Example in detail
[Link]/berkeley-stat-157
Toy Model
• Linear RNN
ht = Whx xt + Whhht−1 and ot = Wohht
• Output gradient T
prod (∂otl(ot, yt), ht)
∑
∂Woh L =
t=1
• State update gradient
T
prod (∂otl(ot, yt), Woh, ∂Whhht)
∑
∂Whh L =
t=1
T
prod (∂otl(ot, yt), Woh, ∂Whxht)
∑
∂Whx L =
[Link]/berkeley-stat-157 t=1
Gradients … continued
• Linear RNN
ht = Whx xt + Whhht−1 and ot = Wohht
• Recursive update
∂ht ht+1 = W⊤hh and thus ∂ht hT = (W⊤hh)
T−t
• Full recursion
t
∑ ( hh)
⊤ t−j
∂Whhht = W hj
Drop j=1
t
gradients
∑ ( hh)
⊤ t−j
∂Whxht = W xj .
[Link]/berkeley-stat-157 j=1
Truncation in practice
• Compute forward pass across truncation boundaries
• Backprop only until truncation boundary
(typically mini batch boundary, too)
• In code
for s in state:
[Link]()
• Good reason for why sequential sampling is much more
accurate than random - state is carried through.
[Link]/berkeley-stat-157
Gated Recurrent Unit (GRU)
[Link]/berkeley-stat-157
Paying attention to a sequence
• Not all observations are equally relevant
• Only remember the relevant ones
• Need mechanism to pay attention (update gate)
• Need mechanism to forget (reset gate)
[Link]/berkeley-stat-157
Gating Rt = σ(XtWxr + Ht−1Whr + br),
Zt = σ(XtWxz + Ht−1Whz + bz)
[Link]/berkeley-stat-157
Candidate Hidden State
H̃t = tanh(XtWxh + (Rt ⊙ Ht−1) Whh + bh)
[Link]/berkeley-stat-157
Hidden State
Ht = Zt ⊙ Ht−1 + (1 − Zt) ⊙ H̃t
[Link]/berkeley-stat-157
Summary Rt = σ(XtWxr + Ht−1Whr + br),
Zt = σ(XtWxz + Ht−1Whz + bz)
H̃t = tanh(XtWxh + (Rt ⊙ Ht−1) Whh + bh)
Ht = Zt ⊙ Ht−1 + (1 − Zt) ⊙ H̃t
[Link]/berkeley-stat-157
Code …
[Link]/berkeley-stat-157
Long Short Term Memory
[Link]/berkeley-stat-157
Flashback to electronics
Output
gate
Input
gate
Reset
gate
[Link]/berkeley-stat-157
Long Short Term Memory
• Forget gate
Shrink values towards zero
• Input gate
Decide whether we should ignore the input data
• Output gate
Decide whether the hidden state is used for the output
generated by the LSTM
• Hidden state and Memory cell
[Link]/berkeley-stat-157
Gates It = σ(XtWxi + Ht−1Whi + bi)
Ft = σ(XtWxf + Ht−1Whf + bf )
Ot = σ(XtWxo + Ht−1Who + bo)
[Link]/berkeley-stat-157
Candidate Memory Cell
C̃t = tanh(XtWxc + Ht−1Whc + bc)
[Link]/berkeley-stat-157
Memory Cell
Ct = Ft ⊙ Ct−1 + It ⊙ C̃t
[Link]/berkeley-stat-157
Hidden State / Output
Ht = Ot ⊙ tanh(Ct)
[Link]/berkeley-stat-157
Hidden State / Output
It = σ(XtWxi + Ht−1Whi + bi)
Ft = σ(XtWxf + Ht−1Whf + bf )
Ot = σ(XtWxo + Ht−1Who + bo)
C̃t = tanh(XtWxc + Ht−1Whc + bc)
Ct = Ft ⊙ Ct−1 + It ⊙ C̃t
Ht = Ot ⊙ tanh(Ct)
[Link]/berkeley-stat-157
Code …
[Link]/berkeley-stat-157