NLP Programming Tutorial 3 – The Perceptron Algorithm

NLP Programming Tutorial 3 The Perceptron Algorithm

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 3 – The Perceptron Algorithm

Prediction Problems

Given x, predict y2

NLP Programming Tutorial 3 – The Perceptron Algorithm

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

Is it positive?
yesnoBinary
Prediction(2 choices)

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

Its language
EnglishJapaneseMulti-classPrediction(several choices)A sentenceIts syntactic parseS
VPI read a bookNPN

VBD DETNN

I read a book

Structured
Prediction(millions of choices)3

NLP Programming Tutorial 3 – The Perceptron Algorithm

Example we will use:●

Given an introductory sentence from Wikipedia●Predict whether the article is about a person●

GivenPredict

Gonso was a Sanron sect priest (754-827)
in 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!)
4

NLP Programming Tutorial 3 – The Perceptron Algorithm

Performing Prediction

5

NLP Programming Tutorial 3 – The Perceptron Algorithm

How do We Predict?

Gonso was a Sanron sect priest ( 754 – 827 )in the late Nara and early Heian periods .

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

6

NLP Programming Tutorial 3 – The Perceptron Algorithm

How do We Predict?
Contains “priest” →probably person!

Contains “(<#>-<#>)” →probably person!

Gonso was a Sanron sect priest ( 754 – 827 )in the late Nara and early Heian periods .

Contains
Shichikuzan Chigogataki Fudomyoo is“site” →a historical site located at Magura , Maizuru
probably not person!
City , Kyoto Prefecture .
Contains“Kyoto Prefecture” →probably not person!

7

NLP Programming Tutorial 3 – The Perceptron Algorithm

Combining Pieces of Information●

Each element that helps us predict is a feature
contains “priest”
contains “(<#>-<#>)”
contains “site”
contains “Kyoto Prefecture”●

Each feature has a weight, positive if it indicates “yes”,
and negative if it indicates “no”
wcontains “priest” = 2
wcontains “site” = -3●

wcontains “(<#>-<#>)” = 1
wcontains “Kyoto Prefecture” = -1

For a new example, sum the weights
Kuya (903-972) was a priest
born in Kyoto Prefecture.

●

2 + -1 + 1 = 2

If the sum is at least 0: “yes”, otherwise: “no”

8

NLP Programming Tutorial 3 – The Perceptron Algorithm

Let me Say that in Math!
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)

9

NLP Programming Tutorial 3 – The Perceptron Algorithm

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)

10

NLP Programming Tutorial 3 – The Perceptron Algorithm

Calculating 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+0
0 ++0+0+0+…
=-3 → No!

11NLP Programming Tutorial 3 – The Perceptron Algorithm

Pseudo Code for Prediction
predict_all(model_file, input_file):load w from model_file # so w[name] = wname
for each x in input_filephi = create_features(x) # so phi[name] = φname(x)y' = predict_one(w, phi)print y'# calculate sign(w*φ(x))

12

NLP Programming Tutorial 3 – The Perceptron Algorithm

Pseudo Code forPredicting a Single Example
predict_one(w, phi)score = 0
for each name, value in phi
if name exists in w
score += value * w[name]if score >= 0
return 1
else
return -1# score = w*φ(x)13

NLP Programming Tutorial 3 – The Perceptron Algorithm

Pseudo Code for Feature Creation(Example: Unigram Features)
CREATE_FEATURES (x):create map phi
split x into words
for word in words
phi[“UNI:”+word] += 1
return phi●# We add “UNI:” to indicate unigrams

You can modify this function to use other features!
Bigrams?
● Other features?
●

14

NLP Programming Tutorial 3 – The Perceptron Algorithm

Learning Weights
Using the Perceptron Algorithm

15

NLP Programming Tutorial 3 – The Perceptron Algorithm

Learning Weights●

Manually creating weights is hard
Many many possible useful features● Changing weights changes results in unexpected ways●●Instead, we can learn from labeled datayx

1

FUJIWARA no Chikamori ( year of birth and death unknown ) was asamurai and poet who lived at the end of the Heian period .

1Ryonen ( 1646 - October 29 , 1711 ) was a Buddhist nun of the Obaku
Sect who lived from the early Edo period to the mid-Edo period .

-1-1

A moat settlement is a village surrounded by a moat .
Fushimi Momoyama Athletic Park is located in Momoyama-cho , Kyoto
City , Kyoto Prefecture .
16

NLP Programming Tutorial 3 – The Perceptron Algorithm

Online Learning
create map w
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)●In other words
Try to classify each training example● Every time we make a mistake, update the weights●●

Many different online learning algorithms●The most simple is the perceptron

17

NLP Programming Tutorial 3 – The Perceptron Algorithm

Perceptron Weight Updatew ← w + y ϕ(x)●In other words:●

If y=1, increase the weights for features in φ(x)–●Features for positive examples get a higher weightIf y=-1, decrease the weights for features in φ(x)–Features for negative examples get a lower weight→ Every time we update, our predictions get better!
update_weights(w, phi, y)
for name, value in phi:w[name] += value * y18

NLP Programming Tutorial 3 – The Perceptron Algorithm

Example: Initial Update●

Initialize w=0x = A site , located in Maizuru , Kyotow⋅ϕ(x)=0y = -1y ' =sign( w⋅ϕ( x))=1y '≠ yw ← w + y ϕ( x)wunigram “Maizuru” = -1 w
= -1
unigram “A”
wunigram “,”= -2 w= -1
unigram “site”
wunigram “in”
= -1 w= -1
unigram “located”
wunigram “Kyoto” = -1

19

NLP Programming Tutorial 3 – The Perceptron Algorithm

Example: Second Updatex = Shoken , monk born in Kyoto-2-1w⋅ϕ( x)=−4y=1-1

y ' =sign( w⋅ϕ( x))=−1y '≠ yw ← w + y ϕ( x)wunigram “Maizuru” = -1 w
= -1
unigram “A”wunigram “,”= -1 w= -1
unigram “site”
wunigram “in”
=0 w
= -1
unigram “located”
wunigram “Kyoto” = 0

wunigram “Shoken” = 1
wunigram “monk” = 1
wunigram “born” = 1

20

NLP Programming Tutorial 3 – The Perceptron Algorithm

Exercise21

NLP Programming Tutorial 3 – The Perceptron Algorithm

Exercise (1)●Write two programs
train-perceptron: Creates a perceptron model● test-perceptron: Reads a perceptron model and outputs
one prediction per line●●Test train-perceptron
Input: test/03-train-input.txt● Answer: test/03-train-answer.txt●

22

NLP Programming Tutorial 3 – The Perceptron Algorithm

Exercise (2)●Train a model on data-en/titles-en-train.labeled●Predict the labels of data-en/titles-en-test.word●

Grade your answers and report next week●●

script/grade-prediction.py data-en/titles-en-test.labeled your_answer

Extra challenge:
Find places where the model makes a mistake andanalyze why● Devise new features that could increase accuracy●

23

NLP Programming Tutorial 3 – The Perceptron Algorithm

Thank You!

24