NLP Programming Tutorial 11 – The Structured Perceptron

NLP Programming Tutorial 11 The Structured Perceptron

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 11 – 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 syntactic parse
SVPI read a bookNPN

VBD DETNN

I read a book

Structured
Prediction(millions of choices)
2NLP Programming Tutorial 11 – 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
EnglishJapanese

Multi-class
Prediction(several choices)A sentenceIts syntactic parse
SVP

I read a bookNPN

VBD DETNN

I read a book

Most NLP
Problems!
StructuredPrediction(millions of choices)3

NLP Programming Tutorial 11 – The Structured Perceptron

So Far, We Have Learned
Classifiers

Generative Models

Perceptron, SVM, Neural Net

HMM POS Tagging
CFG Parsing

Lots of features

Conditional probabilities

Binary prediction

Structured prediction

4

NLP Programming Tutorial 11 – The Structured Perceptron

Structured Perceptron
Classifiers

Generative Models

Perceptron, SVM, Neural Net

HMM POS Tagging
CFG Parsing

Lots of features

Conditional probabilities

Binary prediction

Structured prediction

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

5

NLP Programming Tutorial 11 – The Structured Perceptron

Uses of Structured Perceptron(or Variants)●POS Tagging with HMMs

Collins “Discriminative Training Methods for Hidden Markov Models:Theory and Experiments with Perceptron Algorithms” ACL02●Parsing

Huang+ “Forest Reranking: Discriminative Parsing with Non-LocalFeatures” ACL08●

Machine Translation

Liang+ “An End-to-End Discriminative Approach to MachineTranslation” ACL06(Neubig+ “Inducing a Discriminative Parser for Machine Translation
Reordering, EMNLP12”, Plug :) )●Discriminative Language Models

Roark+ “Discriminative Language Modeling with Conditional Random
Fields and the Perceptron Algorithm” ACL04
6

NLP Programming Tutorial 11 – The Structured Perceptron

Example: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 NN

NN

A type of structured prediction

7

NLP Programming Tutorial 11 – The Structured Perceptron

Hidden Markov Models (HMMs) forPOS 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)




JJ

NN

NN

…

LRB

NN

RRB

...

natural language processing (nlp)...

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

…




8

NLP Programming Tutorial 11 – 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?
●9NLP Programming Tutorial 11 – 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 )10NLP Programming Tutorial 11 – The Structured Perceptron

Restructuring HMM With Features
Normal HMM:

II +1

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

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

NLP Programming Tutorial 11 – The Structured Perceptron

Restructuring HMM With Features
Normal HMM:

II +1

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

II+1

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

12

NLP Programming Tutorial 11 – 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:

I

I+1Log Likelihood: logP ( X ,Y )=∑1 logP E ( x i∣y i ) ∑ i=1 logPT ( y i∣y i −1 )IS (X ,Y )=∑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)

13

NLP Programming Tutorial 11 – The Structured Perceptron

Exampleφ(IvisitedNara

PRP

VBDNNP)=

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

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

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

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

φCAPS,PRP(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

Ivisited

Nara

NNP

VBD

NNP)=

φ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) = 1

14

NLP Programming Tutorial 11 – The Structured Perceptron

Finding the Best Solution●

We must find the POS sequence that satisfies:Ŷ =argmax Y ∑ i w i ϕi (X ,Y )15

NLP Programming Tutorial 11 – 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 segmentation

16

NLP Programming Tutorial 11 – The Structured Perceptron

Forward Step: Part 1●First, calculate transition from <S> and emission of thefirst word for every POS
I

0:<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:PRP best_score[“1 PRP”] = -log PT(PRP|<S>) + -log PE(I | PRP)
1:NNP best_score[“1 NNP”] = -log PT(NNP|<S>) + -log PE(I | NNP)…

17

NLP Programming Tutorial 11 – The Structured Perceptron

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

visited

1:NN

2:NN

1:JJ

2:JJ

1:VB

2:VB

1:PRP

2:PRP

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(language | NN),
best_score[“1 VB”] + -log PT(NN|VB) + -log PE(language | NN),
best_score[“1 PRP”] + -log PT(NN|PRP) + -log PE(language | NN),
best_score[“1 NNP”] + -log PT(NN|NNP) + -log PE(language | NN),...
)
best_score[“2 JJ”] = min(best_score[“1 NN”] + -log PT(JJ|NN) + -log PE(language | JJ),
best_score[“1 JJ”] + -log PT(JJ|JJ) + -log PE(language | JJ),
best_score[“1 VB”] + -log PT(JJ|VB) + -log PE(language | JJ), 18...

NLP Programming Tutorial 11 – 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:PRP best_score[“1 PRP”] = wT,<S>,PRP + wE,PRP,I
1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I…

19

NLP Programming Tutorial 11 – The Structured Perceptron

HMM Viterbi with Features●Can add additional features
I0:<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:PRP best_score[“1 PRP”] = wT,<S>,PRP + wE,PRP,I + wCAPS,PRP
1:NNP best_score[“1 NNP”] = wT,<S>,NNP + wE,NNP,I + wCAPS,NNP…

20

NLP Programming Tutorial 11 – 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?

21

NLP Programming Tutorial 11 – The Structured Perceptron

Learning in the Structured Perceptron●

Positive example, correct feature vector:φ(●Ivisited

Nara

PRP

VBD

NNP)

Negative example, incorrect feature vector:

φ(Ivisited

Nara

NNP

VBD

NNP)
22

NLP Programming Tutorial 11 – The Structured Perceptron

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

Nara

NNPVBD

NNPφ(Ivisited

Nara

PRP

VBDNNvisitedφ(●Which do we use?

)
IPRPVB)
Nara
NNP)
23

NLP Programming Tutorial 11 – 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
24

NLP Programming Tutorial 11 – 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

25

NLP Programming Tutorial 11 – The Structured Perceptron

Creating HMM Features●Make “create features” for each transition, emission

create_trans( NNP,VBD)

create_emit( NNP,Nara )φ[“T,NNP,VBD”] = 1

φ[“E,NNP,Nara”] = 1
φ[“CAPS,NNP”] = 126

NLP Programming Tutorial 11 – The Structured Perceptron

Creating HMM Features●The create_features function does for all words
create_features(X, Y):
create map phi
for i in 0 .. |Y|:
if i == 0: first_tag = “
”else:first_tag = Y[i-1]
if i == |Y|: next_tag = “
”else:
next_tag = Y[i]phi += create_trans(first_tag, next_tag)
for i in 0 .. |Y|-1:
phi += create_emit(Y[i], X[i])return phi27NLP Programming Tutorial 11 – The Structured Perceptron

Viterbi Algorithm Forward Step
split line into words
I = length(words)
make maps best_score, best_edge
best_score[“0 
”] = 0 # Start with 
best_edge[“0 
”] = NULL
for i in 0 … I-1:
for each prev in keys of possible_tags
for each next in keys of possible_tags
if best_score[“i prev”] and transition[“prev next”] exist
score = best_score[“i prev”] +-log PT(next|prev) + -log PE(word[i]|next)
w*(create_t(prev,next)+create_e(next,word[i]))if best_score[“i+1 next”] is new or < score
best_score[“i+1 next”] = score
best_edge[“i+1 next”] = “i prev”
28# Finally, do the same for 


NLP Programming Tutorial 11 – The Structured Perceptron

Exercise29

NLP Programming Tutorial 11 – The Structured Perceptron

Exercise●

Write train-hmm-percep and test-hmm-percep●

Test the program

●

●

●

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

Answer: test/05­{train,test}­answer.txt

Train an HMM model on data/wiki­en­train.norm_posand run the program on data/wiki­en­test.norm

Measure the accuracy of your tagging withscript/gradepos.pl data/wiki­en­test.pos my_answer.pos●●

Report the accuracy (compare to standard HMM)
Challenge:
create new features
use training with margin or regularization

30

NLP Programming Tutorial 11 – The Structured Perceptron

Thank You!

31