NLP Programming Tutorial 6 – Advanced Discriminative Learning

NLP Programming Tutorial 6 Advanced Discriminative Learning

Graham Neubig
Nara Institute of Science and Technology (NAIST)1NLP Programming Tutorial 6 – Advanced Discriminative Learning

Review: Classifiers and the Perceptron

2

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Prediction Problems

Given x, predict y3

NLP Programming Tutorial 6 – Advanced Discriminative Learning

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
4

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Mathematical Formulationy = 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)

5

NLP Programming Tutorial 6 – Advanced Discriminative Learning

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

6

NLP Programming Tutorial 6 – Advanced Discriminative Learning

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 * y7

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Stochastic Gradient Descent andLogistic Regression

8NLP Programming Tutorial 6 – Advanced Discriminative Learning

Perceptron and Probabilities●P( y∣x )Sometimes we want the probability
Estimating confidence in predictions● Combining with other systems●●However, perceptron only gives us a prediction

y =sign(w⋅ϕ( x))1P( y =1∣x)=1 if w⋅ϕ ( x )≥0
P( y =1∣x)=0 if w⋅ϕ (x)< 0p(y|x)

In other words:

0.5-10-500w*phi(x)5109

NLP Programming Tutorial 6 – Advanced Discriminative Learning

The Logistic Function●The logistic function is a “softened” version of thefunction used in the perceptronw⋅ϕ ( x)eP( y =1∣x)=w⋅ϕ (x)1+ePerceptron

Logistic1 Functionp(y|x)

p(y|x)

10.5-10-500510w*phi(x)●●Can account for uncertainty
Differentiable

0.5-10-500510w*phi(x)10NLP Programming Tutorial 6 – Advanced Discriminative Learning

Logistic Regression●●

Train based on conditional likelihood
Find the parameters w that maximize the conditional
likelihood of all answers yi given the example xî
w=argmax∏i P( y i∣x i ; w)
w

●How do we solve this?

11

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Stochastic Gradient Descent●Online training algorithm for probabilistic models(including logistic regression)
create map w
for I iterations
for each labeled pair x, y in the data
w += α * 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 α●12NLP Programming Tutorial 6 – Advanced Discriminative Learning

Gradient of the Logistic 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.4
0.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)

13

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Example: Initial Update●Set α=1, initialize w=0

y = -1x = A site , located in Maizuru , Kyoto
0deP ( y=−1∣x ) = −ϕ (x )w⋅ϕ(x)=00 2dw(1+e )=−0.25 ϕ (x)w← w +−0.25 ϕ ( x )wunigram “Maizuru” = -0.25
wunigram “,”= -0.5wunigram “in”
= -0.25
wunigram “Kyoto” = -0.25

wunigram “A”= -0.25
wunigram “site”= -0.25
wunigram “located” = -0.25

14

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Example: Second Update
y=1x = Shoken , monk born in Kyoto-0.5w⋅ϕ (x )=−1-0.25 -0.25

dP ( y=1∣x ) =dw=1eϕ (x)1 2(1+ e )0.196 ϕ (x )w← w +0.196 ϕ( x)wunigram “Maizuru” = -0.25
wunigram “,”= -0.304
wunigram “in”
= -0.054
wunigram “Kyoto” = -0.054

wunigram “A”= -0.25
wunigram “site”= -0.25
wunigram “located” = -0.25

wunigram “Shoken” = 0.196
wunigram “monk” = 0.196
wunigram “born” = 0.196
15

NLP Programming Tutorial 6 – Advanced Discriminative LearningSGD Learning Rate?
●How to set the learning rate α?

●

Usually decay over time:1
α=C+ tparameter●

number of samples

Or, use held-out data, and reduce the learning rate
when the likelihood rises
16

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Classification Margins

17

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Choosing between
Equally Accurate Classifiers●

Which classifier is better? Dotted or Dashed?
OX

OXOX

18

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Choosing between
Equally Accurate Classifiers●Which classifier is better? Dotted or Dashed?
OX

O
X

OX

●
●Answer: Probably the dashed line.
Why?: It has a larger margin.

19

NLP Programming Tutorial 6 – Advanced Discriminative Learning

What is a Margin?
●

The distance between the classification plane and thenearest example:
OX

OX

OX

20

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Support Vector Machines●

Most famous margin-based classifier
Hard Margin: Explicitly maximize the margin● Soft Margin: Allow for some mistakes●●Usually use batch learning
Batch learning: slightly higher accuracy, more stable● Online learning: simpler, less memory, fasterconvergence●●Learn more about SVMs:

http://disi.unitn.it/moschitti/material/Interspeech2010-Tutorial.Moschitti.pdf●Batch learning libraries:
LIBSVM, LIBLINEAR, SVMLite

21

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Online Learning with a Margin●Penalize not only mistakes, but also correct answers
under a margin

create map w
for I iterations
for each labeled pair x, y in the dataphi = create_features(x)val = w * phi * y★
if val <= margin
update_weights(w, phi, y)(A correct classifier will always make w * phi * y > 0)If margin = 0, this is the perceptron algorithm
22

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Regularization

23

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Cannot Distinguish Between
Large and Small Classifiers●

For these examples:-1 he saw a bird in the park
+1 he saw a robbery in the park●

Which classifier is better?
Classifier 1he +3
saw -5a +0.5bird -1
robbery +1
in +5
the -3
park -2

Classifier 2
bird -1
robbery +1

24

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Cannot Distinguish Between
Large and Small Classifiers●For these examples:-1 he saw a bird in the park
+1 he saw a robbery in the park●

Which classifier is better?
Classifier 1
he +3
saw -5a +0.5bird -1
robbery +1
in +5
the -3
park -2

Classifier 2
bird -1
robbery +1

Probably classifier 2!
It doesn't use
irrelevant information.
25

NLP Programming Tutorial 6 – Advanced Discriminative LearningRegularization●A penalty on adding extra weights●L2 regularization:

5Big penalty on large weights,small penalty on small weights● High accuracy
●

●

43

L1 regularization:

2Uniform increase whether largeor small-2● Will cause many weights tobecome zero → small model

1

●

-1

0

L2
L1

0

1

2

26

NLP Programming Tutorial 6 – Advanced Discriminative Learning

L1 Regularization in Online Learning●

After update, reduce the weight by a constant c

update_weights(w, phi, y, c)★ for name, value in w:
if abs(value) < c:★
w[name] = 0
★
else:
★
w[name] -= sign(value) * c★
for name, value in phi:w[name] += value * y

If abs. value < c,set weight to zeroIf value > 0,decrease by c
If value < 0,increase by c

27

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Example●Every turn, we Regularize, Update, Regularize, Update

Regularization: c=0.1
Updates:{1, 0} on 1st and 5th turns{0, -1} on 3rd turn
R1

U1

R2

U2

R3

U3

Change: {0, 0}{1, 0}{-0.1, 0}{0, 0}{-0.1, 0}{0, -1}{0, 0}{1, 0}{0.9, 0}{0.9, 0}{0.8, 0} {0.8, -1}

R4

U4R5U5w:

Change:{-0.1, 0.1} {0, 0} {-0.1, 0.1}
w:

R6

U6

{1, 0} {-0.1, 0.1} {0, 0}{0.7, -0.9} {0.7, -0.9} {0.6, -0.8} {1.6, -0.8} {1.5, -0.7}{1.5, -0.7}
28

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Efficiency Problems●Typical number of features:
Each sentence (phi): 10~1000● Overall (w): 1,000,000~100,000,000●

update_weights(w, phi, y, c)
for name, value in w:
if abs(value) <= c:w[name] = 0else:w[name] -= sign(value) * c
for name, value in phi:w[name] += value * yThis loop isVERY SLOW!

29

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Efficiency Trick●●

Regularize only when the value is used!
getw(w, name, c, iter, last)
if iter != last[name]:# regularize several times
c_size = c * (iter - last[name])
if abs(w[name]) <= c_size:
w[name] = 0else:w[name] -= sign(w[name]) * c_size
last[name] = iter
return w[name]
This is called “lazy evaluation”, used in many
applications

30

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Choosing the Regularization Constant●

The regularization constant c has a large effect●Large value
small model● lower score on training set● less overfitting●●

Small value
large model● higher score on training set● more overfitting●●

Choose best regularization value on development set●e.g. 0.0001, 0.001, 0.01, 0.1, 1.031NLP Programming Tutorial 6 – Advanced Discriminative Learning

Exercise32

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Exercise●

Write program:●train-svm/train-lr: Create an svm or LR model with L2
regularization constant 0.001●

Train a model on data-en/titles-en-train.labeled●

Predict the labels of data-en/titles-en-test.word●

Grade your answers and compare them with theperceptron●●

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

Extra challenge:
Try many different regularization constants● Implement the efficiency trick●33

NLP Programming Tutorial 6 – Advanced Discriminative Learning

Thank You!

34