Sequential Data Modeling – The Structured Perceptron

Sequential Data Modeling The Structured Perceptron

Graham Neubig
Nara Institute of Science and Technology (NAIST)

1

Sequential Data Modeling – The Structured Perceptron

Prediction Problems

Given x, predict y2Sequential Data Modeling – The Structured Perceptron

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-class
Prediction(several choices)A sentenceIts parts-of-speech

I read a bookN

VBD DETNN

I read a book

StructuredPrediction(millions of choices)

Sequential prediction is a subset3

Sequential Data Modeling – The Structured Perceptron

Simple Prediction:
The Perceptron Model4

Sequential Data Modeling – The Structured Perceptron

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 is
a historical site located at Magura, Maizuru
City, Kyoto Prefecture.

No!

This is binary classification (of course!)
5Sequential Data Modeling – The Structured Perceptron

How do We Predict?

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

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

6

Sequential Data Modeling – The Structured Perceptron

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Sequential Data Modeling – The Structured Perceptron

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Sequential Data Modeling – The Structured Perceptron

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

Sequential Data Modeling – The Structured Perceptron

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Sequential Data Modeling – The Structured Perceptron

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

Sequential Data Modeling – The Structured Perceptron

Learning Weights
Using the Perceptron Algorithm

12Sequential Data Modeling – The Structured Perceptron

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 .

1

Ryonen ( 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 .
13

Sequential Data Modeling – The Structured Perceptron

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

14Sequential Data Modeling – The Structured Perceptron

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!

15

Sequential Data Modeling – The Structured Perceptron

Example: Initial Update●Initialize w=0

x = 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

16

Sequential Data Modeling – The Structured Perceptron

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= -1unigram “site”
wunigram “in”
=0 w
= -1
unigram “located”
wunigram “Kyoto” = 0

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

17Sequential Data Modeling – The Structured Perceptron

Review:
The HMM Model18

Sequential Data Modeling – The Structured Perceptron

Part of Speech (POS) Tagging●Given a sentence X, predict its part of speech
sequence Y

Natural language processing ( NLP ) is a field of computer science
JJ

NN

NN -LRB- NN -RRB- VBZ DT NN IN NNNN

●A type of “structured” prediction, from two weeks ago●How can we do this? Any ideas?

19Sequential Data Modeling – The Structured Perceptron

Probabilistic Model for Tagging●“Find the most probable tag sequence, given thesentence”

Natural language processing ( NLP ) is a field of computer science
JJ

NN

NN LRB NN RRB VBZ DT NN IN NN

NN

argmax P (Y∣X )Y●Any ideas?
20Sequential Data Modeling – The Structured Perceptron

Generative Sequence Model●First decompose probability using Bayes' law

P ( X∣Y ) P(Y )argmax P (Y∣X )=argmaxP (X )YY=argmax P ( X∣Y ) P(Y )Y

Model of word/POS interactions“natural” is probably a JJ●

Model of POS/POS interactions
NN comes after DET

Also sometimes called the “noisy-channel model”
21Sequential Data Modeling – The Structured Perceptron

Hidden Markov Models (HMMs) for
POS Tagging●●POS→POS transition probabilities
I+ 1● Like a bigram model!
P (Y )≈ ∏ i=1 PT (y i∣y i−1 )POS→Word emission probabilities
IP (X∣Y )≈ ∏1 P E ( x i∣y i )PT(JJ|
) * PT(NN|JJ) * PT(NN|NN)




JJNN

NN…

LRB

NN

RRB

...

natural language processing (nlp)...

PE(natural|JJ) * PE(language|NN) * PE(processing|NN)

…




22

Sequential Data Modeling – The Structured Perceptron

Learning Markov Models (with tags)●Count the number of occurrences in the corpus andnatural language processing ( nlp )c(JJ→natural)++
c(
 JJ)++●c(NN→language)++

JJ

NN

NN

c(JJ NN)++

…

is …

…

LRB NN RRB VB … 


Divide by context to get probability
PT(LRB|NN) = c(NN LRB)/c(NN) = 1/3
PE(language|NN) = c(NN → language)/c(NN) = 1/3
23Sequential Data Modeling – The Structured Perceptron

Remember: HMM Viterbi Algorithm●

Forward step, calculate the best path to a node●●

Find the path to each node with the lowest negative log
probability

Backward step, reproduce the path●

This is easy, almost the same as word segmentation24

Sequential Data Modeling – The Structured Perceptron

Forward Step: Part 1●

First, calculate transition from <S> and emission of thefirst word for every POS
I0:<S>

1:NN best_score[“1 NN”] = -log PT(NN|<S>) + -log PE(I | NN)
1:JJ best_score[“1 JJ”] = -log PT(JJ|<S>) + -log PE(I | JJ)
1:VB best_score[“1 VB”] = -log PT(VB|<S>) + -log PE(I | VB)
1:PRN best_score[“1 PRN”] = -log PT(PRN|<S>) + -log PE(I | PRN)
1:NNP best_score[“1 NNP”] = -log PT(NNP|<S>) + -log PE(I | NNP)…

25

Sequential Data Modeling – The Structured Perceptron

Forward Step: Middle Parts●For middle words, calculate the minimum score for all
possible previous POS tags

Ivisited

1:NN

2:NN

1:JJ

2:JJ

1:VB

2:VB

1:PRN

2:PRN

1:NNP

2:NNP

…

…

best_score[“2 NN”] = min(best_score[“1 NN”] + -log PT(NN|NN) + -log PE(visited | NN),
best_score[“1 JJ”] + -log PT(NN|JJ) + -log PE(visited | NN),
best_score[“1 VB”] + -log PT(NN|VB) + -log PE(visited | NN),
best_score[“1 PRN”] + -log PT(NN|PRN) + -log PE(visited | NN),
best_score[“1 NNP”] + -log PT(NN|NNP) + -log PE(visited | NN),...
)
best_score[“2 JJ”] = min(best_score[“1 NN”] + -log PT(JJ|NN) + -log PE(visited | JJ),
best_score[“1 JJ”] + -log PT(JJ|JJ) + -log PE(visited | JJ),
26
best_score[“1 VB”] + -log PT(JJ|VB) + -log PE(visited | JJ),...

Sequential Data Modeling – The Structured Perceptron

The Structured Perceptron27Sequential Data Modeling – The Structured Perceptron

So Far, We Have Learned
Classifiers

Generative Models

Perceptron

HMM

Lots of features

Conditional probabilities

Binary prediction

Structured prediction28

Sequential Data Modeling – The Structured Perceptron

Structured PerceptronClassifiers

Generative Models

Perceptron

HMM

Lots of features

Conditional probabilities

Binary prediction

Structured prediction

Structured perceptron →Classification with lots of features
over structured models!

29Sequential Data Modeling – The Structured Perceptron

Why are Features Good?
●Can easily try many different ideas
Are capital letters usually nouns?
● Are words that end with -ed usually verbs? -ing?
●30

Sequential Data Modeling – The Structured Perceptron

Restructuring HMM With Features
Normal HMM:

II+ 1P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )31Sequential Data Modeling – The Structured Perceptron

Restructuring HMM With Features
Normal HMM:

I

I+ 1P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )I

I+ 1

Log Likelihood: logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )32Sequential Data Modeling – The Structured Perceptron

Restructuring HMM With Features
Normal HMM:

I

I+ 1P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )I

I+ 1

Log Likelihood: logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )Score

II+ 1S (X ,Y )=∑1 w E , y , x ∑ i=1 w T , yiii −1, yi33

Sequential Data Modeling – The Structured Perceptron

Restructuring HMM With Features
II+ 1

P (X ,Y )=∏ 1 P E ( x i∣y i ) ∏i=1 PT ( y i∣y i−1 )Normal HMM:

Log Likelihood:I
I +1logP ( X ,Y )=∑ i=1 logP E (x i∣y i )+ ∑ i=1 logP T (y i∣y i−1 )IS (X ,Y )=∑i =1 w E , y , x + ∑i =1 w E , yScore
When:

I +1iw E , y , x =log P E (x i∣y i )iiwT ,yii−1, yii −1,yi=logP T ( y i∣y i−1 )log P(X,Y) = S(X,Y)

34

Sequential Data Modeling – The Structured Perceptron

Exampleφ(IvisitedNara

PRN

VBDNNP)=

φT,<S>,PRN(X,Y1) = 1

φT,PRN,VBD(X,Y1) = 1

φE,PRN,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1φCAPS,PRN(X,Y1) = 1

φCAPS,NNP(X,Y1) = 1

φ(φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1

φSUF,VBD,”...ed”(X,Y1) = 1

IvisitedNara

NNP

VBDNNP)=

φT,<S>,NNP(X,Y1) = 1

φT,NNP,VBD(X,Y1) = 1

φT,VBD,NNP(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1

φE,NNP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,NNP(X,Y1) = 2

φSUF,VBD,”...ed”(X,Y1) = 135

Sequential Data Modeling – The Structured Perceptron

Finding the Best Solution●We must find the POS sequence that satisfies:Ŷ =argmax Y ∑ i w i ϕi (X ,Y )36

Sequential Data Modeling – The Structured Perceptron

HMM Viterbi with Features●Same as probabilities, use feature weights
I

0:<S>

1:NN best_score[“1 NN”] = wT,<S>,NN + wE,NN,I
1:JJ best_score[“1 JJ”] = wT,<S>,JJ + wE,JJ,I
1:VB best_score[“1 VB”] = wT,<S>,VB + wE,VB,I
1:PRN best_score[“1 PRN”] = wT,<S>,PRN + wE,PRN,I1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I…

37

Sequential Data Modeling – The Structured Perceptron

HMM Viterbi with Features●Can add additional features
I

0:<S>

1:NN best_score[“1 NN”] = wT,<S>,NN + wE,NN,I + wCAPS,NN
1:JJ best_score[“1 JJ”] = wT,<S>,JJ + wE,JJ,I + wCAPS,JJ
1:VB best_score[“1 VB”] = wT,<S>,VB + wE,VB,I + wCAPS,VB
1:PRN best_score[“1 PRN”] = wT,<S>,PRN + wE,PRN,I + wCAPS,PRN
1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I + wCAPS,NNP…

38

Sequential Data Modeling – The Structured Perceptron

Learning In the Structured Perceptron●

Remember the perceptron algorithm●If there is a mistake:w ← w + y ϕ(x)●●Update weights to:increase score of positive examples
decrease score of negative examples
What is positive/negative in structured perceptron?

39Sequential Data Modeling – The Structured Perceptron

Learning in the Structured Perceptron●

Positive example, correct feature vector:φ(●IvisitedNaraPRNVBDNNP)

Negative example, incorrect feature vector:

φ(Ivisited

Nara

NNP

VBDNNP)40

Sequential Data Modeling – The Structured Perceptron

Choosing an Incorrect Feature Vector●φ(There are too many incorrect feature vectors!
I

visited

Nara

NNP

VBD

NNP

φ(Ivisited

Nara

PRN

VBD

NN
visitedφ(●Which do we use?

)
I

PRN

VB)
Nara
NNP)
41

Sequential Data Modeling – The Structured Perceptron

Choosing an Incorrect Feature Vector●Answer: We update using the incorrect answer withthe highest score:Ŷ =argmax Y ∑ i w i ϕi (X ,Y )●Our update rule becomes:w ← w + ϕ(X , Y ' )−ϕ( X , Ŷ )●●(Y' is the correct answer)

Note: If highest scoring answer is correct, no change
42Sequential Data Modeling – The Structured Perceptron

ExampleφT,<S>,PRN(X,Y1) = 1

φT,PRN,VBD(X,Y1) = 1

φT,VBD,NNP(X,Y1) = 1

φE,PRN,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,PRN(X,Y1) = 1

φCAPS,NNP(X,Y1) = 1

φSUF,VBD,”...ed”(X,Y1) = 1φT,<S>,NNP(X,Y1) = 1

φT,NNP,VBD(X,Y1) = 1

φT,VBD,NNP(X,Y1) = 1

φE,NNP,”I”(X,Y1) = 1

φE,VBD,”visited”(X,Y1) = 1 φE,NNP,”Nara”(X,Y1) = 1

φCAPS,NNP(X,Y1) = 2

φSUF,VBD,”...ed”(X,Y1) = 1-φT,NNP,</S>(X,Y1) = 1

φT,NNP,</S>(X,Y1) = 1=φT,<S>,PRN(X,Y1) = 1 φT,PRN,VBD(X,Y1) = 1
φT,VBD,NNP(X,Y1) = 0 φT,NNP,</S>(X,Y1) = 0
φT,<S>,NNP(X,Y1) = -1 φ(X,Y1) = -1
T,NNP,VBD
φE,PRN,”I”(X,Y1) = 1
φE,VBD,”visited”(X,Y1) = 0 φE,NNP,”Nara”(X,Y1) = 0
φE,NNP,”I”(X,Y1) = -1
43
φCAPS,NNP(X,Y1) = -1 φCAPS,PRN(X,Y1) = 1
φSUF,VBD,”...ed”(X,Y1) = 0

Sequential Data Modeling – The Structured Perceptron

Structured Perceptron Algorithm
create map w
for I iterations
for each labeled pair X, Y_prime in the data
Y_hat = hmm_viterbi(w, X)
phi_prime = create_features(X, Y_prime)
phi_hat = create_features(X, Y_hat)w += phi_prime - phi_hat

44Sequential Data Modeling – The Structured Perceptron

Conclusion●The structured perceptron is a discriminative
structured prediction model
HMM: generative structured prediction● Perceptron: discriminative binary prediction●●

It can be used for many problems●Prediction of45

Sequential Data Modeling – The Structured Perceptron

Thank You!

46