NLP Programming Tutorial 8 – Recurrent Neural NetsNLP Programming Tutorial 8 Recurrent Neural Nets

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 8 – Recurrent Neural Nets

Feed Forward Neural Nets
●All connections point forwardϕ ( x)●

It is a directed acyclic graph (DAG)y2

NLP Programming Tutorial 8 – Recurrent Neural Nets

Recurrent Neural Nets (RNN)●

Part of the node outputs return as input

ht −1
ϕ t (x )●Why? It is possible to “memorize”

y3

NLP Programming Tutorial 8 – Recurrent Neural Nets

RNN in Sequence Modelingy1y2y3y4

NETNETNETNETx1x2x3x4

4

NLP Programming Tutorial 8 – Recurrent Neural Nets

Example: POS Tagging
JJNN

NNVBZ

NETNET

NETNET

naturallanguage processing

is5

NLP Programming Tutorial 8 – Recurrent Neural Nets

Multi-class Prediction with NeuralNetworks

6

NLP Programming Tutorial 8 – Recurrent Neural Nets

Review: Prediction Problems
Given x,predict y
A book review
Oh, man I love this book!
This book is so boring...

Is it positive?
yesnoBinaryPrediction(2 choices)

A tweetOn the way to the park!
公園に行くなう！

Its language
EnglishJapaneseMulti-classPrediction(several choices)A sentenceIts syntactic parse
SVP

I read a bookNPN

VBD DETNN

I read a book

StructuredPrediction(millions of choices)
7

NLP Programming Tutorial 8 – Recurrent Neural Nets

Review: Sigmoid Function●The sigmoid softens the step functionw⋅ϕ ( x)eP( y =1∣x)=w⋅ϕ (x)1+eSigmoid Function

Step Function

1p(y|x)p(y|x)

10.5-10-500w*phi(x)5100.5-10-500510w*phi(x)8NLP Programming Tutorial 8 – Recurrent Neural Nets

softmax Function●Sigmoid function for multiple classes

P( y∣x)=●ew⋅ϕ (x , y )∑~y eCurrent classw⋅ϕ ( x , ~y)Sum of other classes

Can be expressed using matrix/vector ops

r=exp (W⋅ϕ( x))p=r / ∑ ~r~r ∈r

9NLP Programming Tutorial 8 – Recurrent Neural Nets

Selecting the Best Value from a
Probability Distribution●Find the index y with the highest probability

find_best(p):y=0for each element i in 1 .. len(p)-1:if p[i] > p[y]:y=ireturn y10

NLP Programming Tutorial 8 – Recurrent Neural Nets

softmax Function Gradient●The difference between the true and estimatedprobability distributions−d err / d ϕ out = p '− p●

The true distribution p' is expressed with a vector with
only the y-th element 1 (a one-hot vector)

p '={0,0,…,1,…, 0}

11

NLP Programming Tutorial 8 – Recurrent Neural Nets

Creating a 1-hot Vector
create_one_hot(id, size):
vec = np.zeros(size)
vec[id] = 1
return vec

12

NLP Programming Tutorial 8 – Recurrent Neural Nets

Forward Propagation in Recurrent Nets

13

NLP Programming Tutorial 8 – Recurrent Neural Nets

Review: Forward Propagation Codeforward_nn(network, φ0)
φ= [ φ0 ] # Output of each layer
for each layer i in 1 .. len(network):w, b = network[i-1]# Calculate the value based on previous layer
φ[i] = np.tanh( np.dot( w, φ[i-1] ) + b )return φ # Return the values of all layers

14

NLP Programming Tutorial 8 – Recurrent Neural Nets

RNN Calculation
pt1wr,hht-1wr,xbosoftmaxwo,htanh

pt+11wr,hht
wr,x

xt br

xt+1 b11bosoftmax

wo,hht+1tanhr

ht =tanh (w r , h⋅ht −1+ w r , x⋅xt +b r )pt =softmax (w o , h⋅ht +b o)

15

NLP Programming Tutorial 8 – Recurrent Neural Nets

RNN Forward Calculation
forward_rnn(wr,x, wr,h, br, wo,h, bo, x)h = [ ] # Hidden layers (at time t)
p = [ ] # Output probability distributions (at time t)y = [ ] # Output values (at time t)
for each time t in 0 .. len(x)-1:
if t > 0:h[t] = tanh(wr,xx[t] + wr,hh[t-1] + br)else:
h[t] = tanh(wr,xx[t] + br)
p[t] = tanh(wo,hh[t] + bo)
y[t] = find_max(p[t])return h, p, y16

NLP Programming Tutorial 8 – Recurrent Neural Nets

Review:
Back Propagation in Feed-forward Nets

17

NLP Programming Tutorial 8 – Recurrent Neural Nets

Stochastic Gradient Descent●Online training algorithm for probabilistic models(including logistic regression)
w=0for I iterations
for each labeled pair x, y in the dataw += α * dP(y|x)/dw●In other words
For every training example, calculate the gradient(the direction that will increase the probability of y)● Move in that direction, multiplied by learning rate α●18

NLP Programming Tutorial 8 – Recurrent Neural Nets

Gradient of the Sigmoid Function
Take the derivative of the probabilityw⋅ϕ ( x)dP ( y=1∣x ) =dw

d ed w 1+e w⋅ϕ (x)w⋅ϕ (x)e= ϕ (x )w⋅ϕ (x) 2(1+e)
dP ( y=−1∣x ) =dw

dp(y|x)/dw*phi(x)●0.40.3
0.2
0.1-10-500510w*phi(x)w⋅ϕ (x)de(1−)w⋅ϕ (x)dw
1+ ew⋅ϕ (x)e= −ϕ (x )w⋅ϕ (x) 2(1+ e)

19

NLP Programming Tutorial 8 – Recurrent Neural Nets

Learning:
Don't Know Derivative for Hidden Units!
●For NNs, only know correct tag for last layerh( x)w1d P( y=1∣x)=?
d w1d P( y=1∣x)e w ⋅h(x )=h (x)w ⋅h( x) 2dw(1+ e)
4w
4ϕ ( x)

w2w3

4

4

y=1d P( y=1∣x)=?
d w2d P( y=1∣x)=?
d w320NLP Programming Tutorial 8 – Recurrent Neural Nets

Answer: Back-Propogation●

Calculate derivative w/ chain ruled P( y=1∣x) d P( y=1∣x ) d w 4 h(x ) d h1 (x )=d w1d w 4 h( x) d h1 (x) d w 1w 4⋅h( x )ew ⋅h( x) 2(1+e)

w 1,44

Error ofnext unit (δ4)
In General
Calculate i basedon next units j:

Weight Gradient of
this unitd P( y=1∣x) d hi ( x)=δw∑ji, jjwid wi21

NLP Programming Tutorial 8 – Recurrent Neural Nets

Conceptual Picture●Send errors back through the netw1ϕ ( x)

δ1w2w4δ2δ4yw3

δ3
22

NLP Programming Tutorial 8 – Recurrent Neural Nets

Back Propagation in Recurrent Nets

23

NLP Programming Tutorial 8 – Recurrent Neural Nets

What Errors do we Know?
y1 δNETx1o,1δr,1y2 δo,2NETx2

δr,2y3 δo,3

NETx3

δr,3

y4 δo,4

NETx4

We know the output errors δo● Must use back-prop to find recurrent errors δr●24

NLP Programming Tutorial 8 – Recurrent Neural Nets

How to Back-Propagate?
●Standard back propagation through time (BPTT)●●For each δo, calculate n steps of δr

Full gradient calculation●

Use dynamic programming to calculate the wholesequence

25

NLP Programming Tutorial 8 – Recurrent Neural Nets

Back Propagation through Timeδδy1

δo,1 y2 δo,2y3 δNETδ
δ

NETx1

NETx2

δ
δo,3y4δo,4NETδx3

Use only one output error● Stop after n steps (here, n=2)x4●26NLP Programming Tutorial 8 – Recurrent Neural Nets

Full Gradient Calculationy1δ

δo,1y2δδo,2y3δ

δo,3y4δo,4δ

NETNETNETNETx1x2x3x4

First, calculate whole net result forward● Then, calculate result backwards●

27

NLP Programming Tutorial 8 – Recurrent Neural Nets

BPTT? Full Gradient?
●

Full gradient:+ Faster, no time limit● - Must save the result of the whole sequence in memory●●BPTT:+ Only remember the results in the past few steps● - Slower, less accurate for long dependencies●28NLP Programming Tutorial 8 – Recurrent Neural Nets

Vanishing Gradient in Neural Netsy1

●y2y3y4verytinytiny

smallmed.

δδ

δ

δ

NETNETNETNETx1

x2x3

x4

δo,4

“Long Short Term Memory” is designed to solve this29

NLP Programming Tutorial 8 – Recurrent Neural Nets

RNN Full Gradient Calculation
gradient_rnn(wr,x, wr,h, br, wo,h, bo, x, h, p, y')initialize Δwr,x, Δwr,h, Δbr, Δwo,h, Δboδr' = np.zeros(len(br)) # Error from the following time stepfor each time t in len(x)-1 .. 0:p' = create_one_hot(y'[t])δo' = p' – p[t]# Output error
Δwo,h += np.outer(h[t], δo');Δbo += δo' # Output gradientδr = np.dot(δ'r, wr,h) + np.dot(δ'o, wo,h)# Backprop
δ'r = δr * (1 – h[t]2)# tanh gradientΔwr,x += np.outer(x[t], δr');
Δbr += δr'# Hidden gradientif t != 0:
Δwr,h += np.outer(h[t-1], δr');
return Δwr,x, Δwr,h, Δbr, Δwo,h, Δbo30NLP Programming Tutorial 8 – Recurrent Neural Nets

Weight Update
update_weights(wr,x, wr,h, br, wo,h, bo, Δwr,x, Δwr,h, Δbr, Δwo,h, Δbo, λ)wr,x += λ * Δwr,xwr,h += λ * Δwr,hbr += λ * Δbr
wo,h += λ * Δwo,hbo += λ * Δbo

31

NLP Programming Tutorial 8 – Recurrent Neural Nets

Overall Training Algorithm# Create features
create map x_ids, y_ids, array data
for each labeled pair x, y in the dataadd (create_ids(x, x_ids), create_ids(y, y_ids) ) to data

initialize net randomly# Perform training
for I iterations
for each labeled pair x, y' in the feat_lab
h, p, y = forward_rnn(net, φ0)
Δ= gradient_rnn(net, x, h, y')update_weights(net, Δ, λ)print net to weight_file
print x_ids, y_ids to id_file32

NLP Programming Tutorial 8 – Recurrent Neural Nets

Exercise33

NLP Programming Tutorial 8 – Recurrent Neural Nets

Exercise●Create an RNN for sequence labeling●Training train-rnn and testing test-rnn●

Test: Same data as POS tagging●●●

Input: test/05-{train,test}-input.txt●

Reference: test/05-{train,test}-answer.txt

Train a model with data/wiki-en-train.norm_pos and predict for
data/wiki-en-test.norm

Evaluate the POS performance, and compare with HMM:
script/gradepos.pl data/wiki-en-test.pos my_answer.pos

34