Understanding Recurrent Neural Networks
Understanding Recurrent Neural Networks
networks
Getting targets when modeling
• sequences
When applying machine learning to sequences, we often want to
turn an input sequence into an output sequence that lives in a
different domain.
– E. g. turn a sequence of sound pressures into a sequence of word
identities.
•
Memoryless models for sequences
• Autoregressive
models Predict the wt2 wt1
next term in a
input(t- input(t- input(
sequence from a fixed
2) 1) t)
number of previous terms
• using “delay taps”.
Feed-forward neural nets
These generalize hidde
n
autoregressive models by
using one or more layers of
input(t- input(t- input(t)
non-linear hidden units.
2) 1)
Beyond memoryless models
• If we give our generative model some hidden state, and
if we give this hidden state its own internal dynamics, we
get a much more interesting kind of model.
– It can store information in its hidden state for a long
time.
– If the dynamics is noisy and the way it generates
outputs from its hidden state is noisy, we can never
know its exact hidden state.
– The best we can do is to infer a probability
distribution over the space of hidden state vectors.
• This inference is only tractable for two types of hidden
state model.
Linear Dynamical Systems
• These are generative models. They have time
a real- valued hidden state that cannot be
ut
outp
ut
outp
ut
outp
observed directly.
– The hidden state has linear
dynamics with Gaussian noise and
produces the observations using a linear
n
hidde
n
hidde
n
hidde
model with Gaussian noise.
– There may also be driving inputs.
• To predict the next output (so that we can
shoot down the missile) we need to infer
input
g
drivin
input
g
drivin
input
g
drivin
the hidden state.
– A linearly transformed Gaussian is a
Gaussian. So the distribution over the hidden
state given the data so far is Gaussian. It can
Examples
•Kalman Filter: One of the most common applications of Linear-Gaussian models,
the Kalman Filter is used to estimate the state of a system over time (like the position
and velocity of a moving object) based on noisy measurements. For example, GPS
systems use Kalman filters to continuously estimate the location of a car based on
sensor data that may have small errors.
•Weather Forecasting: In this case, an LDS can model the hidden state of weather
systems based on past data, allowing for noise in the measurements and using a
linear approach to forecast future states.
Hidden Markov Models
• Hidden Markov Models have a discrete
ut
outp
ut
outp
ut
outp
one- of-N hidden state. Transitions
between states are stochastic and
controlled by a transition matrix. The
outputs produced by a state are
stochastic.
– We cannot be sure which state
produced a given output. So the state
is “hidden”.
–
• To predictItthe
is easy
next tooutput
represent
weaneed to
probability
infer distribution
the probability across N states
distribution over
with N numbers.
hidden states. time
– HMMs have efficient
algorithms for inference and
•Speech Recognition: In speech recognition, HMMs are used to model sequences
of sounds. Each hidden state in the model represents a different phoneme or sound,
and the transitions between states reflect the probabilistic nature of moving from
one sound to another in human speech.
•Biological Sequence Analysis: HMMs are widely used to identify patterns in
biological sequences, like DNA or protein sequences. Here, each hidden state
represents a type of structure in the sequence (e.g., coding vs. non-coding DNA
regions), and the model probabilistically “walks” through these hidden states based
on observed patterns in the data.
•POS Tagging in Natural Language Processing: In Part-of-Speech (POS)
tagging, an HMM can be used to assign parts of speech (like noun, verb, etc.) to
words in a sentence. Each hidden state corresponds to a part of speech, and the
observed data are words. The model transitions between tags based on the
likelihood of certain words following others in a language.
A fundamental limitation of
• HMMs
Consider what happens when a hidden Markov model
generates data.
– At each time step it must select one of its hidden
states. So with N hidden states it can only remember log(N)
bits about what it generated so far.
• Consider the information that the first half of an
utterance contains about the second half:
– The syntax needs to fit (e.g. number and tense agreement).
– The semantics needs to fit. The intonation needs to fit.
– The accent, rate, volume, and vocal tract characteristics
must all fit.
• All these aspects combined could be 100 bits of
information that the first half of an utterance needs to
Example
– Imagine an HMM is generating the phrase "The cat is..." followed
by the second half, "sleeping." For it to sound natural, the second
half of this phrase should match the grammar, meaning, and
style of the first half. However, if the HMM has limited memory
(just a few bits from the first half), it may produce a second half
that doesn’t fit well, like "playing," "jumping," or even something
nonsensical like "singing" if it doesn't remember enough context.
– The model can only hold onto a limited bit amount from earlier
states, so it might not "remember" whether it was dealing with
present tense, animals, or the specific action. This leads to output
that can easily break consistency or sound strange because it
lacks all the necessary information (syntax, semantics, and style).
To capture all this information, we’d need a lot more "memory,"
as in, about 100 bits worth to encode all the possibilities
Recurrent neural
• RNNs are verynetworks
powerful, because time
they
combine two properties:
ut
outp
ut
outp
ut
outp
– Distributed hidden state
that allows them to store a lot
of information about the past
efficiently.
n
hidde
n
hidde
n
hidde
– Non-linear dynamics that
allows them to update their
hidden state in complicated
t
inpu
t
inpu
t
inpu
ways.
• With enough neurons and time,
RNNs can compute anything that
can be computed by your
[Link]
Recurrent neural networks
• What kinds of behaviour can RNNs exhibit?
– They can oscillate. Good for motor control?
– They can settle to point attractors. Good for retrieving
memories?
– They can behave chaotically. Bad for information
processing?
– RNNs could potentially learn to implement lots of
small programs that each capture a nugget of
knowledge and run in parallel, interacting to produce
very complicated effects.
• But the computational power of RNNs makes them very
hard to train.
– For many years we could not exploit the
The equivalence between feedforward nets and
recurrent nets
w1 w4
time=
3 w1 w2 W3
w2 w3 W4
time=
Assume that there is a 2 w1 w2 W3
time delay of 1 in using W4
each connection. time=
The recurrent net is 1 w1 w2 W3
just a layered net that W4
keeps reusing the time=
same weights. 0
Reminder: Backpropagation with
weight constraints
• It is easy to modify the
algorithm to incorporate
backprop To constrain : w1
linear constraints we
w 2 need : w1
between the weights.
w2
• We compute the gradients
as usual, and then modify E E
compute : and
the gradients so that they w1 w2
satisfy the constraints.
– So if the
weights started off E E
satisfying the use for w1 and w2
w1 w2
constraints, they will
continue to satisfy
them.
Backpropagation through time
– Specify the initial tim
states of a subset of the w1 w2 W3 e
units. W4
– Specify the states of
the same subset of the
units at every time step.
w1 w2 W3
W4
• This is the natural way
to model most
sequential data.
Teaching signals for recurrent networks
• We can specify targets in
several ways:
– Specify desired final w1 w2 W3 W4
activities of all the units
– Specify desired
activities of all units for
the last few steps w1 w2 W3
• Good for learning W4
attractors
• It is easy to add in extra
error derivatives as we w1 w2 W3
backpropagate. W4
– Specify the desired
activity of a subset of the
units.
A good toy problem for a recurrent
• We cannetwork
train a feedforward net
binary
to do addition, but there are
obvious regularities that it 11001100
cannot capture efficiently.
– We must decide in
advance the maximum
number of digits in each
number. hidden units
– The processing applied to
the beginning of a long number
does
numbernotbecause
generalize
it to the end
uses
of the long
different weights.
• As a result, feedforward nets do
00100110 10100110
not generalize well on the binary
addition task.
The algorithm for binary addition
1 0 0 1
0 1 no carry 1
0
carry print
print 1 0 1
1 0 0 0 1 1 0
1
0 1 0 1 0 1
1
no carry carry
0 print 0 1 print 0 1
0 0 1 1 0
This is a finite state automaton. It decides what transition to make by looking
at the next column. It prints after making the transition. It moves from
right to left over the two input numbers.
A recurrent net for binary addition
• The network has two input
units and one output unit.
• It is given two input digits at
each time step. 0011010
• The desired output at each
time 0
step is the output for the 0100110
column
that was provided as input two 1
time steps ago. 1 0 0 0 0 00
– It takes one time step to
update 1
the hidden units based on
the two input digits. time
– It takes another time step
for the
hidden units to cause
the output.
The connectivity of the network
• The 3 hidden units are
fully interconnected in
both directions.
– This allows a
hidden activity
pattern at one time 3 fully interconnected hidden
step to vote for the
hidden activity units
pattern at the next
time step.
• The input units have
feedforward connections
that allow then to vote
for the next hidden
activity pattern.
What the network learns
• It learns four distinct • A recurrent network can
patterns of activity for the 3 emulate a finite state
hidden units. These patterns automaton, but it is
correspond to the nodes in exponentially more powerful.
the finite state automaton. With N hidden neurons it has
– Do not confuse units 2^N possible binary activity
in a neural network with vectors (but only N^2
nodes in a finite state weights)
automaton. Nodes are like – This is important
activity vectors. when the input stream
– The automaton is has two separate things
restricted to be in exactly going on at once.
one state at each time. – A finite state
The hidden units are automaton needs to
restricted to have exactly square its number of
A finite state machine (FSM) is a mathematical model that describes a system with a limited number of
oneandvector
states of activity
transitions between them. at states.
The backward pass is linear
• There is a big difference
between the forward and
backward passes.
• In the forward pass we use
squashing (activation) functions
(like the logistic) to prevent the
activity vectors from exploding.
• The backward pass, is completely
linear. If you double the error
derivatives at the final layer, all
the error derivatives will double.
– The forward pass
determines the slope of the linear
The problem of exploding or vanishing
gradients
• What happens to the magnitude • In an RNN trained on long
of the gradients as we sequences (e.g. 100 time steps)
backpropagate through many the gradients can easily explode
layers? or vanish.
– If the weights are – We can avoid this by
small, the gradients shrink initializing the weights very
exponentially. carefully.
– If the weights are big • Even with good initial weights,
the gradients grow its very hard to detect that the
exponentially. current target output depends on
• Typical feed-forward neural nets an input from many time-steps
can cope with these exponential ago.
effects because they only have – So RNNs have
a few hidden layers. difficulty dealing with long-
range dependencies.
Why the back-propagated gradient blows
up
1. 1. 1.
7 7 7
writ rea writ rea writ rea
e1 d0 e0 d0 e0 d1
1. 1.
time 7
7
Reading cursive handwriting
• This is a natural task • Graves & Schmidhuber
for an RNN. (2009) showed that
• The input is a sequence of RNNs with LSTM are
(x,y,p) coordinates of the currently the best systems
tip of the pen, where p for reading cursive
indicates whether the pen writing.
is up or down. – They used a
• The output is a sequence of small
sequence of characters. images as input
rather than pen
coordinates.
A demonstration of online handwriting
recognition by an RNN with Long Short Term
•
Memory (from Alex Graves)
The movie that follows shows several different things:
• Row 1: This shows when the characters are recognized.
– It never revises its output so difficult decisions are more
delayed.
• Row 2: This shows the states of a subset of the memory
cells.
– Notice how they get reset when it recognizes a character.
• Row 3: This shows the writing. The net sees the x and y
coordinates.
– Optical input actually works a bit better than pen
coordinates.
• Row 4: This shows the gradient backpropagated all the way
to the x and y inputs from the currently most active character.
SHOW ALEX GRAVES’
MOVIE
How much can we reduce the bett
er
error by moving in a given ratio
• direction?
If we choose a direction to move in and we
keep going in that direction, how much does
the error decrease before it starts rising
again? We
assume
the curvature is constant (i.e. it’s a quadratic
error surface).
– Assume the magnitude of the gradient
decreases as we move down the gradient (i.e.
the error surface is convex upward).
• The maximum error reduction depends on the ratio of
the gradient to the curvature. So a good direction to
move in is one with a high ratio of gradient to
curvature, even if the gradient itself is small.
Newton’s method
• The basic problem with steepest descent on a quadratic
error surface is that the gradient is not the direction we want
to go in.
– If the error surface has circular cross-sections, the
gradient is fine.
– So lets apply a linear transformation that turns ellipses
into circles. 1 dE
w H
• Newton’s method multiplies the gradient vector by the
(w) dw
inverse of the curvature matrix, H:
– On a real quadratic surface it jumps to the minimum in
one step.
– Unfortunately, with only a million weights, the
curvature matrix has a trillion terms and it is totally
infeasible to invert it.
Curvature
• Matrices
Each element in the curvature i j k
specifies how the gradient in
matrix
one direction changes as we ( )
E
wi
move in some other
direction. i w j
– The off-diagonal terms ( E
j )
correspond to twists in the
error surface. w j
• The reason steepest descent
goes wrong is that the gradient wi
for one weight gets messed up k 2 E
by the simultaneous changes to
all the other weights. w2
k
– The curvature matrix
How to avoid inverting a huge
•
matrix
The curvature matrix has too many terms to be of use in a big
network. – Maybe we can get some benefit from
just using the terms along the
leading diagonal (Le Cun). But the diagonal terms are only
a tiny
fraction of the interactions (they are the self-interactions).
• The curvature matrix can be approximated in many
different ways – Hessian-free methods, LBFGS, …
• In the HF method, we make an approximation to the curvature
matrix and then, assuming that approximation is correct, we
minimize the error using an efficient technique called
conjugate gradient. Then we
make another approximation to the curvature matrix and
minimize again.
– For RNNs its important to add a penalty for
Conjugate gradient
c softma
x
character: predicted distribution
1-of-
‐ 86
‐ for next character.
It’s a lot easier to predict 86 characters than 100,000 words.
A sub-tree in the tree of all character
There strings
are ...fi
exponentially i x e In an RNN, each
many nodes in node is a hidden
… … state vector. The
the tree of all
character strings n fixi fixe next character
of length N. … must transform
this to a new
fixin node.
• If the nodes are implemented as hidden states in an RNN,
different nodes can share structure because they use
distributed representations.
• The next hidden representation needs to depend on the
conjunction of the current character and the current hidden
representation.
Multiplicative connections
• Instead of using the inputs to the recurrent net to
provide additive extra input to the hidden units, we could
use the current input character to choose the whole
hidden-to-hidden weight matrix.
– But this requires 86x1500x1500 parameters
– This could make the net overfit.
• Can we achieve the same kind of multiplicative
interaction using fewer parameters?
– We want a different transition matrix for each
of the 86 characters, but we want these 86
character-specific weight matrices to share
parameters (the characters 9 and 8 should have
similar matrices).
Using factors to implement multiplicative
interactions
• We can get groups a and b to interact multiplicatively
by using “factors”.
– Each factor first computes a weighted sum for
each of its input groups.
–uThen it sendsvthe product of the weighted
f f c f bT
w f
sums toT its
a u f
Group
output group.
Group
f
vector v f scalar scalar
a
of input to f input to f
c
wf inputs from from
to group b group a
group c
Group b
Using factors to implement a set of basis
• matrices
We can think about
factors another way: cf b T
w f a T
uf v f
– Each factor
defines a rank 1
transition matrix from
to
uc.
af vf
cf bT w f u f v Tf a
scalar outer
Group
Group
f product
coefficie
nt transition
a
matrix with
c
wf
rank 1 T
c b T w u vf f a
f
Group b f
Using 3-way factors to allow a character to create
a whole transition matrix
uf vf
1500 f
1500
hidden hidden
units units
w kf
Each factor, f, k
rank onea matrix ,
defines predicted distribution
f v Tf character: 1-of-
‐ ‐ for next character
86
uEach character, k, determines a gain
for each of these
matrices.
wkf
Training the character model
• Ilya Sutskever used 5 million strings of 100 characters
taken from wikipedia. For each string he starts predicting
at the 11th character.
• Using the HF optimizer, it took a month on a GPU board
to get a really good model.
• Ilya’s current best RNN is probably the best single
model for character prediction (combinations of many
models do better).
• It works in a very different way from the best other
models.
– It can balance quotes and brackets over long
distances. Models that rely on matching previous
How to generate character strings from the
model
• Start the model with its default hidden state.
• Give it a “burn-in” sequence of characters and let it
update its hidden state after each character.
• Then look at the probability distribution it predicts for
the next character.
• Pick a character randomly from that distribution and tell
the net that this was the character that actually occurred.
– i.e. tell it that its guess was correct, whatever it
guessed.
• Continue to let it pick characters until bored.
• Look at the character strings it produces to see what it
“knows”.
He was elected President during the
Revolutionary War and forgave Opus Paul at
Rome. The regime of his crew of England, is
now Arab women's icons in and the
demons that use something between the
characters‘ sisters in lower coil trains were
always operated on the line of the
ephemerable street, respectively, the
graphic or other facility for deformation of a
given proportion of large segments at
RTUS). The B every chord was a "strongly
Some completions produced by the
model
• Sheila thrunges (most frequent)
• People thrunge (most frequent next character is
• Shiela, Thrungelini del Rey
space) (first
try)
• The meaning of life is literary recognition.
(6th try)
• The meaning of life is the tradition of the ancient human
reproduction: it is less favorable to the good boy for when to
remove her bigger.
(one of the first 10 tries for a model trained for longer).
What does it know?
• It knows a huge number of words and a lot about proper
names, dates, and numbers.
• It is good at balancing quotes and
brackets. – It can count
brackets: none, one, many
• It knows a lot about syntax but its very hard to pin
down exactly what form this knowledge has.
– Its syntactic knowledge is not modular.
• It knows a lot of weak semantic associations
– E.g. it knows Plato is associated with
Wittgenstein and cabbage is associated with
vegetable.
RNNs for predicting the next word
• Tomas Mikolov and his collaborators have recently trained
quite large RNNs on quite large training sets using BPTT.
– They do better than feed-forward neural nets.
– They do better than the best other models.
– They do even better when averaged with other models.
• RNNs require much less training data to reach the same
level of performance as other models.
• RNNs improve faster than other methods as the dataset
gets bigger.
– This is going to make them very hard to beat.
The key idea of echo state networks (perceptrons
again?)
• The equivalent idea for RNNs
• A very simple way to learn a is to fix the inputhidden
feedforward network is to connections and the
make the early layers random hiddenhidden connections
and fixed. at random values and only
• Then we just learn the last learn the hiddenoutput
layer which is a linear connections.
model that uses the – The learning is
transformed then very simple
inputs to predict (assuming linear
the target output units).
outputs. – Its important to set
– A big the random connections
random very carefully so the RNN
expansion of does not explode or die.
Setting the random connections in an Echo
State Network
• Set the hiddenhidden • Choose the scale of the
weights so that the length inputhidden connections
of the activity vector stays very carefully.
about the same after each – They need to
iteration. drive the loosely
– This allows the coupled oscillators
input to echo around the without wiping out the
network for a long time. information from the
• Use sparse connectivity (i.e. past that they already
set most of the weights to contain.
zero). • The learning is so fast that
– This creates lots we can try many different
of loosely coupled scales for the weights and
oscillators. sparsenesses.
A simple example of an echo state
network
INPUT SEQUENCE
A real-valued time-varying value that specifies the
frequency of a sine wave.
LEARNING METHOD
Fit a linear model that takes the states of the hidden
units as input and produces a single scalar output.
Example
from
Scholarpedi
a
The target and predicted outputs after
learning
Beyond echo state networks
• Good aspects of ESNs • Bad aspects of ESNs
Echo state networks can be They need many more
trained very fast because hidden units for a given
they just fit a linear model. task than an RNN that
• They demonstrate that its learns the hiddenhidden
very important to initialize weights.
weights sensibly.
• They can do impressive • Ilya Sutskever (2012)
modeling of one-dimensional has shown that if the
time-series. weights are initialized
– but they cannot using the ESN methods,
compete seriously for RNNs can be trained
high-dimensional data like very effectively.
pre-processed speech. – He uses
rmsprop with
momentum.
Gradient Decent:
[Link]
7cd3dfe#:~:text=III.-,Implementing%20Gradient%20Descent,function%20with%20respect%20to%20
w
.
RNN:
• [Link]
utm_source=google&utm_medium=paid_search&utm_campaignid=19589720824&utm_adgroupid=157156376071&utm_device=c&utm_keyword=&
utm_matchtype=&utm_network=g&utm_adpostion=&utm_creative=716160943432&utm_targetid=dsa-
2218886984380&utm_loc_interest_ms=&utm_loc_physical_ms=9077149&utm_content=&utm_campaign=230119_1-sea~dsa~tofu_2-b2c_3-row-
p2_4-prc_5-na_6-na_7-le_8-pdsh-go_9-nb-e_10-na_11-na-
oct24&gad_source=1&gclid=CjwKCAjwyfe4BhAWEiwAkIL8sBTaV119WO_nlTodapYMBfDF8Yp6LBFKIqjSt6uAo0kgdUH2vDodFRoCJMIQAvD_BwE
• [Link]