NLP Programming Tutorial 7 – Neural Networks

NLP Programming Tutorial 7 Neural Networks

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 7 – Neural Networks

Prediction Problems

Given x, predict y2

NLP Programming Tutorial 7 – Neural Networks

Example we will use:●

Given an introductory sentence from Wikipedia●Predict whether the article is about a person●Given sect priest (754-827)
Gonso was a Sanron

Predictin the late Nara and early Heian periods.

Yes!

Shichikuzan Chigogataki Fudomyoo isa historical site located at Magura, Maizuru
City, Kyoto Prefecture.

No!

This is binary classification (of course!)
3

NLP Programming Tutorial 7 – Neural Networks

Linear Classifiers
y = sign (w⋅ϕ(x))
I= sign ( ∑i=1 w i⋅ϕi ( x))●x: the input●

φ(x): vector of feature functions {φ1(x), φ2(x), …, φI(x)}●w: the weight vector {w1, w2, …, wI}●

y: the prediction, +1 if “yes”, -1 if “no”●

(sign(v) is +1 if v >= 0, -1 otherwise)

4

NLP Programming Tutorial 7 – Neural Networks

Example Feature Functions:Unigram Features●Equal to “number of times a particular word appears”

x = A site , located in Maizuru , Kyoto
φunigram “A”(x) = 1

φunigram “site”(x) = 1

φunigram “,”(x) = 2

φunigram “located”(x) = 1 φunigram “in”(x) = 1
φunigram “Maizuru”(x) = 1 φunigram “Kyoto”(x) = 1
φunigram “the”(x) = 0 φunigram “temple”(x) = 0…
●The rest
are all 0

For convenience, we use feature names (φunigram “A”)
instead of feature indexes (φ1)

5

NLP Programming Tutorial 7 – Neural NetworksCalculating the Weighted Sum
x = A site , located in Maizuru , Kyoto
φunigram “A”(x)φunigram “site”(x)φunigram “located”(x)

=1
=1
=1

φunigram “Maizuru”(x)φunigram “,”(x)φunigram “in”(x)φunigram “Kyoto”(x)φunigram “priest”(x)φunigram “black”(x)

=1
=2
=1
=1
=0
=0

wunigram “a”
wunigram “site”

*…

=0
= -3

wunigram “located” = 0
wunigram “Maizuru” = 0
wunigram “,”=0wunigram “in”
=0
wunigram “Kyoto” = 0
wunigram “priest” = 2
wunigram “black” = 0=0+-3+0 +0+00 ++0+0+0+…
=-3 → No!

6NLP Programming Tutorial 7 – Neural Networks

The Perceptron●Think of it as a “machine” to calculate a weighted sum
φ“A”=1
φ“site” = 1
φ“located” = 1
φ“Maizuru”= 1
φ“,”
=2
φ“in”
=1
φ“Kyoto” = 1
φ“priest” = 0
φ“black” = 00-300000
20

Isign( ∑ i=1 w i⋅ϕi ( x))-17

NLP Programming Tutorial 7 – Neural Networks

Perceptron in Numpy

8NLP Programming Tutorial 7 – Neural NetworksWhat is Numpy?
●A powerful computation library in Python●Vector and matrix multiplication is easy

●A part of SciPy (a more extensive scientific computinglibrary)

9

NLP Programming Tutorial 7 – Neural Networks

Example of Numpy (Vectors)

10

NLP Programming Tutorial 7 – Neural Networks

Example of Numpy (Matrices)11

NLP Programming Tutorial 7 – Neural Networks

Perceptron Prediction
predict_one(w, phi)score = 0
for each name, value in phi
if name exists in w
score += value * w[name]return (1 if score >= 0 else -1)# score = w*φ(x)numpy
predict_one(w, phi)score = np.dot( w, phi )return (1 if score[0] >= 0 else -1)
12

NLP Programming Tutorial 7 – Neural Networks

Converting Words to IDs●

numpy uses vectors, so we want to convert names intoindicesids = defaultdict(lambda: len(ids)) # A trick to convert to IDs
CREATE_FEATURES(x):create list phi
split x into words
for word in words
phi[ids[“UNI:”+word]] += 1
return phi

13

NLP Programming Tutorial 7 – Neural Networks

Initializing Vectors●

Create a vector as large as the number of features●With zeros

w = np.zeros(len(ids))●Or random between [-0.5,0.5]

w = np.random.rand(len(ids)) – 0.5

14NLP Programming Tutorial 7 – Neural Networks

Perceptron Training Pseudo-code# Count the features and initialize the weights
create map ids
for each labeled pair x, y in the data
create_features(x)w = np.zeros(len(ids))# Perform training
for I iterations
for each labeled pair x, y in the dataphi = create_features(x)y' = predict_one(w, phi)
if y' != yupdate_weights(w, phi, y)
print w to weight_file
print ids to id_file

15

NLP Programming Tutorial 7 – Neural Networks

16

NLP Programming Tutorial 7 – Neural Networks

17

NLP Programming Tutorial 7 – Neural Networks

Perceptron Prediction Coderead ids from id_file
read w from weights_file
for each example x in the dataphi = create_features(x)y' = predict_one(w, phi)

18

NLP Programming Tutorial 7 – Neural Networks

Neural Networks

19

NLP Programming Tutorial 7 – Neural Networks

Problem: Only Linear Classification●Cannot achieve high accuracy on non-linear functions

XOO

X

20

NLP Programming Tutorial 7 – Neural Networks

Neural Networks●

Connect together multiple perceptrons
φ“A”=1
φ“site” = 1
φ“located” = 1
φ“Maizuru”= 1
φ“,”
=2
φ“in”
=1
φ“Kyoto” = 1
φ“priest” = 0
φ“black” = 0●-1

Motivation: Can represent non-linear functions!

21

NLP Programming Tutorial 7 – Neural Networks

Example●Create two classifiers

φ0(x1) = {-1, 1} φ0(x2) = {1, 1}

X

φ0[1]

O

φ0[0]

X

φ0(x3) = {-1, -1} φ0(x4) = {1, -1}1

φ0[1]

11-1

φ0[0]

Ow0,0

step

φ1[0]

step

φ1[1]

b0,0
w0,1

φ0[0] -1
φ0[1] -1
1-1
b0,122

NLP Programming Tutorial 7 – Neural Networks

Example●These classifiers map to a new space
φ1(x3) = {-1, 1}

φ0(x1) = {-1, 1} φ0(x2) = {1, 1}

X

φ2OO

φ1[1]

φ1

O

φ1[0]

XX

φ0(x3) = {-1, -1} φ0(x4) = {1, -1}

φ1(x1) = {-1, -1}
φ1(x4) = {-1, -1}

11-1

φ1[0]-1-1-1

φ1[1]Oφ1(x2) = {1, -1}

23

NLP Programming Tutorial 7 – Neural Networks

Example●In the new space, the examples are linearly separable!

φ0(x1) = {-1, 1} φ0(x2) = {1, 1}
φ0[1]

XO
φ0[0]

OX

1
1
1

φ2[0] = yφ0(x3) = {-1, -1} φ0(x4) = {1, -1}1
1-1-1-1-1

φ1[0]
φ1[1]

φ1(x3) = {-1, 1} O
φ1(x1) = {-1, -1}
X
φ1(x4) = {-1, -1}

φ1[1]
φ1[0]
O φ1(x2) = {1, -1}

24

NLP Programming Tutorial 7 – Neural Networks

Example●The final net
φ0[0]

1

φ0[1]

1

1-1

φ0[0]

-1

φ0[1]

-1

1-1tanh φ1[0]11tanhφ2[0]tanh φ [1]11 125NLP Programming Tutorial 7 – Neural Networks

Calculating a Net (with Vectors)
Input

φ0 = np.array( [1, -1] )φ0[0] 1
φ0[1] 11tanh φ1[0]1-1

φ0[0] -1
φ [1] -1 tanh φ [1]
01 -1

1

1

1 1

tanh

φ2[0]

First Layer Output

w0,0 = np.array( [1, 1] )b0,0 = np.array( [-1] )w0,1 = np.array( [-1, -1] )b0,1 = np.array( [-1] )φ1 = np.zeros( 2 )φ1[0] = np.tanh( w0,0φ0 + b0,0 )[0]φ1[1] = np.tanh( w0,1φ0 + b0,1 )[0]Second Layer Output

w1,0 = np.array( [1, 1] )b1,0 = np.array( [-1] )φ2 = np.zeros( 1 )26
φ2[0] = np.tanh( w1,0φ1 + b1,0 )[0]

NLP Programming Tutorial 7 – Neural Networks

Calculating a Net (with Matrices)
Input

φ0 = np.array( [1, -1] )φ0[0] 1
φ0[1] 11

w0 = np.array( [[1, 1], [-1,-1]] )b0 = np.array( [-1, -1] )φ1 = np.tanh( np.dot(w0, φ0) + b0 )tanh φ1[0]Second Layer Output

1-1

φ0[0] -1
φ0[1] -1 tanh φ1[1]1 -1First Layer Output

1tanh

φ2[0]

w1 = np.array( [[1, 1]] )b1 = np.array( [-1] )φ2 = np.tanh( np.dot(w1, φ1) + b1 )1 127

NLP Programming Tutorial 7 – Neural Networks

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

28

NLP Programming Tutorial 7 – Neural Networks

Calculating Error with tanh
●Error function: Squared error
err = (y' – y)2 /2
Correct Answer●Net Output

Gradient of the error:
err' = δ = y' - y●Update of weights:w ← w + λ⋅δ⋅ϕ( x )●λ is the learning rate29

NLP Programming Tutorial 7 – Neural Networks

Problem:Don't know error for hidden layers!
●The NN only gets the correct label for the final layer
φ“A”=1
φ“site” = 1
φ“located” = 1
φ“Maizuru”= 1
φ“,”
=2
φ“in”
=1
φ“Kyoto” = 1
φ“priest” = 0
φ“black” = 00y' = ?
y=1

y' = ?
1 y=1

2

3y' = 1y = -1y' = ?
y=130

NLP Programming Tutorial 7 – Neural Networks

Solution: Back Propagation●Propagate the error backwards through the layers
w=0.1

δ = -0.9w=1

δ = 0.2

w=-0.3

δ = 0.4j

Also consider the gradient of the non-linear functiony●∑i δ i w j ,i-4-3-2-101234

2d tanh (ϕ (x)∗w)=1−tanh (ϕ (x )∗w) =1− y●2jTogether:δ j=(1− y ) ∑i δi w j ,i2j

31

NLP Programming Tutorial 7 – Neural Networks

Back Propagation
Error of the Output

Error of the First Layerδ2 = np.array( [y'-y] )δ'2 = δ2 * (1-φ22)
δ1 = np.dot(δ'2, w1)

φ0[0] 1
φ0[1] 11tanh φ1[0]Error of the 0th Layer1

δ'1 = δ1 * (1-φ12)
δ0 = np.dot(δ'1, w0)-1

φ0[0] -1
φ0[1] -1 tanh φ1[1]
1 -1

1

1 1

tanh

φ2[0]

32

NLP Programming Tutorial 7 – Neural Networks

Back Propagation Codebackward_nn(net, φ, y')J = len(net)create array δ = [ 0, 0, …, np.array([y' – φ[J][0]]) ] # length J+1
create array δ' = [ 0, 0, …, 0 ]for i in J-1 .. 0:
δ'[i+1] = δ[i+1] * (1 – φ[i+1]2)
w, b = net[i]δ[i] = np.dot(δ'[i+1], w)
return δ'33

NLP Programming Tutorial 7 – Neural Networks

Updating Weights●

Finally, use the error to update weights●

Grad. of weight w is outer prod. of next δ' and prev φ-derr/dwi = np.outer( δ'i+1, φi )●Multiply by learning rate and update weights
wi += λ * -derr/dwi●

For the bias, input is 1, so simply δ'-derr/dbi = δ'i+1
bi += λ * -derr/dbi
34

NLP Programming Tutorial 7 – Neural Networks

Weight Update Codeupdate_weights(net, φ, δ', λ)for i in 0 .. len(net)-1:w, b = net[i]w += λ * np.outer( δ'[i+1], φ[i] )b += λ * δ'[i+1]35NLP Programming Tutorial 7 – Neural Networks

Overall View of Learning# Create features, initialize weights randomly
create map ids, array feat_lab
for each labeled pair x, y in the data
add (create_features(x), y ) to feat_lab
initialize net randomly# Perform training
for I iterations
for each labeled pair φ0, y in the feat_lab
φ= forward_nn(net, φ0)
δ'= backward_nn(net, φ, y)update_weights(net, φ, δ', λ)print net to weight_file
print ids to id_file36

NLP Programming Tutorial 7 – Neural Networks

Tricks to Learning Neural Nets

37

NLP Programming Tutorial 7 – Neural Networks

Stabilizing Training●●

NNs have many parameters, objective is non-convex→ training is less stable
Initializing Weights:●●

Randomly, e.g. uniform distribution between -0.1-0.1

Learning Rate:
Often start at 0.1● Compare error with previous iteration, and reduce rate alittle if error has increased ( *= 0.9 or *= 0.5)●

●Hidden Layer Size:●

Usually just try several sizes and pick the best one
38

NLP Programming Tutorial 7 – Neural Networks

Testing Neural Nets●

●Easy Way: Print the error and make sure it is more orless decreasing everty iteration
Better Way: Use the finite differences method

Idea:

When updating weights, calculate grad. for wi: derr/dwi
If we change that weight by a small amount (ω):
wi = xwi = x + ωIfthen↓↓err = yerr ≈ y + ω * derr/dwi
In the finite differences method, we change wi by ω and checkto make sure that the error changes by the expected amount39
Details: http://cs231n.github.io/neural-networks-3/

NLP Programming Tutorial 7 – Neural Networks

Exercise40

NLP Programming Tutorial 7 – Neural Networks

Exercise (1)●Implement
train-nn: A program to learn a NN
● test-nn: A program to test the learned NN●●Test
Input: test/03-train-input.txt● One iteration, one hidden layer, to hidden nodes● Check the update by hand●

41

NLP Programming Tutorial 7 – Neural Networks

Exercise (2)●Train data/titles-en-train.labeled●Predict data/titles-en-test.word●Measure Accuracy●●script/grade-prediction.py data-en/titles-en-test.labeled your_answer

CompareSimple perceptron, SVM, or logistic regression● Numbers of nodes, learning rates, initialization ranges● Challenge●Implement nets with multiple hidden layers● Implement method to decrease learning rate when error
42increases●

NLP Programming Tutorial 7 – Neural Networks

Thank You!

43