Sequential Data Modeling – Conditional Random Fields

Sequential Data Modeling Conditional Random Fields

Graham Neubig
Nara Institute of Science and Technology (NAIST)

1

Sequential Data Modeling – Conditional Random Fields

Prediction Problems

Given x, predict y2Sequential Data Modeling – Conditional Random Fields

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 sentence
I read a bookIts parts-of-speech
NVBD DETNN

I read a book

StructuredPrediction(millions of choices)3Sequential Data Modeling – Conditional Random Fields

Logistic Regression

4Sequential Data Modeling – Conditional Random Fields

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!)
5Sequential Data Modeling – Conditional Random Fields

Review: Linear Prediction Model●

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” = -1For 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”

6Sequential Data Modeling – Conditional Random Fields

Review: 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)7

Sequential Data Modeling – Conditional Random Fields

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))In other words:p(y|x)P( y =1∣x)=1 if w⋅ϕ ( x )≥0
P( y =1∣x)=0 if w⋅ϕ (x)< 0

10.5-10-500w*phi(x)5108Sequential Data Modeling – Conditional Random Fields

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

Logistic Function
1p(y|x)p(y|x)

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

0.5-10-500510w*phi(x)9Sequential Data Modeling – Conditional Random Fields

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?

10Sequential Data Modeling – Conditional Random Fields

Review: Perceptron Training Algorithm
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' != yw += y * phi●

In other words
Try to classify each training example● Every time we make a mistake, update the weights●11Sequential Data Modeling – Conditional Random Fields

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Sequential Data Modeling – Conditional Random Fields

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.40.2-10-500510w*phi(x)w⋅ϕ (x)de(1−)w⋅ϕ (x)dw
1+ ew⋅ϕ (x)e= −ϕ (x )w⋅ϕ (x) 2(1+ e)

13Sequential Data Modeling – Conditional Random Fields

Example: Initial Update●

Set α=1, initialize w=0

y = -1x = A site , located in Maizuru , Kyoto
0de
P ( 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Sequential Data Modeling – Conditional Random Fields

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Sequential Data Modeling – Conditional Random Fields

Calculating Optimal Sequences,
Probabilities

16Sequential Data Modeling – Conditional Random Fields

Sequence Likelihood●Logistic regression considered probability of y ∈{−1,+ 1}P( y∣x )●What if we want to consider probability of a sequence?
XiIvisitedNaraYiPRN

VBD

NNPP(Y∣X )17

Sequential Data Modeling – Conditional Random Fields

Calculating Multi-class Probabilities●●

Each sequence has it's own feature vector
time flies φT,<S>,N=1 φT,N,V=1 φT,V,</S>=1 φE,N,time=1 φE,V,flies=1φ( N V )time flies φT,<S>,V=1 φT,V,N=1 φT,N,</S>=1 φE,V,time=1 φE,N,flies=1φ( V N )time flies φT,<S>,N=1 φT,N,N=1 φT,N,</S>=1 φE,N,time=1 φE,N,flies=1φ( N N )time flies φT,<S>,V=1 φT,V,V=1 φT,V,</S>=1 φE,V,time=1 φE,V,flies=1φ( V V )Use weights for each feature to calculate scores
wT,<S>,N=1 wT,V,</S>=1 wE,N,time=1φ( time flies )*w=3
N Vφ( time flies )*w=2
N N

φ( time flies )*w=0
V Nφ( time flies )*w=1V V18

Sequential Data Modeling – Conditional Random Fields

The Softmax Function●Turn into probabilities by taking exponent andnormalizing (the Softmax function)

P(Y∣X )=ew⋅ϕ (Y , X )∑Ỹ ew⋅ϕ ( Ỹ , X )Take the exponent and normalize
exp(φ( time flies )*w)=20.08 exp(φ(time flies )*w)=1.00
N VV Nexp(φ( time flies )*w)=7.39exp(φ(time flies )*w)=2.72
N NV V●P(N V | time flies)=.6437

P(V N | time flies)=0.0320

P(N N | time flies)=.2369

P(V V | time flies)=0.0872

19Sequential Data Modeling – Conditional Random Fields

Calculating Edge Features●Like perceptron, can calculate features for each edgetime
φE,N,time=1
φT,<S>,N=1N

φE,N,flies=1
φT,N,N=1N

φE,N,flies=1
φT,V,N=1<S>
φE,V,time=1
φT,<S>,V=1flies

φE,V,flies=1
φT,N,V=1

V

φE,V,flies=1
φT,V,V=1

V

φT,N,</S>=1</S>
φT,V,</S>=120

Sequential Data Modeling – Conditional Random Fields

Calculating Edge Probabilities●Calculate scores, and take exponenttimeew*φ=7.39
P=.881

New*φ=1.00
P=.237●New*φ=1.00
P=.032ew*φ=1.00
P=.644<S>ew*φ=1.00
P=.119flies

Vw*φe =1.00
P=.087V

ew*φ=1.00
P=.269</S>
ew*φ=2.72
P=.731This is now the same form as the HMM
Can use the Viterbi algorithm● Calculate probabilities using forward-backward●

21Sequential Data Modeling – Conditional Random Fields

Conditional Random Fields

22Sequential Data Modeling – Conditional Random Fields

Maximizing CRF Likelihood●Want to maximize the likelihood for sequenceŝw=argmax∏i P(Y i∣X i ; w )P(Y∣X )=w●e∑Ỹ ew⋅ϕ ( Ỹ , X )For convenience, we consider the log likelihood

log P(Y∣X )=w⋅ϕ(Y , X)−log ∑Ỹ e●w⋅ϕ (Y , X )w⋅ϕ ( Ỹ , X )Want to find gradient for stochastic gradient descentdlog P (Y∣X )dw

23

Sequential Data Modeling – Conditional Random Fields

Deriving a CRF Gradient:log P( Y∣X )dlog P (Y∣X )dw=w⋅ϕ (Y , X )−log ∑ Ỹ e=w⋅ϕ (Y , X )−log Z====w⋅ϕ (Ỹ , X )dw⋅ϕ (Ỹ , X )ϕ( Y , X )−log ∑ Ỹ edw
1d w⋅ϕ ( Ỹ , X )ϕ( Y , X )− ∑ ỸeZdww⋅ϕ ( Ỹ , X )eϕ( Y , X )−∑Ỹ
ϕ ( Ỹ , X )Z̃ )ϕ ( Ỹ , X 24)
ϕ( Y , X )−∑Ỹ P ( Y∣X

Sequential Data Modeling – Conditional Random Fields

In Other Words...
●To get the gradient we:d̃ )ϕ ( Ỹ , X )log P (Y∣X )=ϕ (Y , X )−∑Ỹ P ( Y∣X
dw
add the correct feature vector
subtract the expectation of the features25

Sequential Data Modeling – Conditional Random Fields

Exampletime flies φT,<S>,N=1 φT,N,V=1 φT,V,</S>=1 φE,N,time=1 φE,V,flies=1φ( N V )time flies φT,<S>,V=1 φT,V,N=1 φT,N,</S>=1 φE,V,time=1 φE,N,flies=1φ( V N )time flies φT,<S>,N=1 φT,N,N=1 φT,N,</S>=1 φE,N,time=1 φE,N,flies=1φ( N N )time flies φT,<S>,V=1 φT,V,V=1 φT,V,</S>=1 φE,V,time=1 φE,V,flies=1φ( V V )P=.644
P=.032
P=.237
P=.087

φT,<S>,N, φE,N,time = 1-.644-.237 = .119

φT,N,V = 1-.644 = .356

φT,<S>,V, φE,V,time = 0-.032-.087 = -.119

φT,V,N = 0-.032 = -.032

φT,V,</S>, φE,V,flies = 1-.644-.087 = .269

φT,N,N = 0-.237 = -.237

φT,N,</S>, φE,V,flies = 0-.032-.237 = -.269

φT,V,V = 0-.087 = -.087
26

Sequential Data Modeling – Conditional Random Fields

Combinatorial Explosion●Problem!: The number of hypotheses is exponential.

d̃ )ϕ ( Ỹ , X )log P (Y∣X )=ϕ (Y , X )−∑Ỹ P ( Y∣Xdw
O(T|X|)
T = number of tags

27Sequential Data Modeling – Conditional Random Fields

Calculate Feature Expectations
using Edge Probabilities!
●If we know the edge probabilities, just multiply them!

ew*φ=7.39 φE,N,time=1
P=.881 φT,<S>,N=1time
N…

<S>
ew*φ=1.00 φE,V,time=1
P=.119 φT,<S>,V=1V

φT,<S>,N, φE,N,time = 1-.881 = .119
φT,<S>,V, φE,V,time = 0-.119 = -.119

Same answer as when we
explicitly expand all Y!
φT,<S>,N, φE,N,time = 1-.644-.237 = .119
φT,<S>,V, φE,V,time = 0-.032-.087 = -.11928

Sequential Data Modeling – Conditional Random Fields

CRF Training Procedure
Can perform stochastic gradient descent, like logistic
regression
create map w
for I iterations
for each labeled pair X, Y in the data
gradient = φ(Y,X)
calculate eφ(y,x)*w for each edge
run forward-backward algorithm to get P(edge)
for each edge
gradient -= P(edge)*φ(edge)
w += α * gradient● Only major difference is gradient calculation●●Learning rate α29Sequential Data Modeling – Conditional Random Fields

Learning Algorithms

30Sequential Data Modeling – Conditional Random Fields

Batch Learning●Online Learning: Update after each example
Online Stochastic Gradient Descentcreate map w
for I iterations
for each labeled pair x, y in the data
w += α * dP(y|x)/dw●

Batch Learning: Update after all examples
Batch Stochastic Gradient Descentcreate map w
for I iterations
for each labeled pair x, y in the data
gradient += α * dP(y|x)/dw
w += gradient31Sequential Data Modeling – Conditional Random Fields

Batch Learning Algorithms:
Newton/Quasi-Newton Methods●Newton-Raphson Method:
Choose how far to update using the second-orderderivatives (the Hessian matrix)● Faster convergence, but |w|*|w| time and memory●●

Limited Memory Broyden-Fletcher-Goldfarb-Shanno
algorithm (L-BFGS):
Guesses second-order derivatives from first-order● Most widely used?
● Library: http://www.chokkan.org/software/liblbfgs/●●More information:
http://homes.cs.washington.edu/~galen/files/quasinewton-notes.pdf

32Sequential Data Modeling – Conditional Random Fields

Online Learning vs. Batch Learning●

Online:In general, simpler mathematical derivation● Often converges faster●●Batch:More stable (does not change based on order)● Trivially parallelizable●

33Sequential Data Modeling – Conditional Random Fields

Regularization

34

Sequential Data Modeling – Conditional Random Fields

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

35Sequential Data Modeling – Conditional Random Fields

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.
36

Sequential Data Modeling – Conditional Random FieldsRegularization●A penalty on adding extra weights●L2 regularization:
Big penalty on large weights,small penalty on small weights● High accuracy

5L1 regularization:

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

1

●

●

43

●-2-1

0

L2L101237

Sequential Data Modeling – Conditional Random Fields

Regularization in LogisticRegression/CRF●To do so in logistic regression/CRF, we add thepenalty to the log likelihood (for the whole corpus)
L2 Regularization2
̂w=argmax( ∏i P (Y i∣X i ; w))−c ∑ w∈ w ww

●c adjusts the strength of the regularization
smaller: more freedom to fit the data
● larger: less freedom to fit the data, better generalization●●

L1 also used, slightly more difficult to optimize
38Sequential Data Modeling – Conditional Random Fields

Conclusion

39Sequential Data Modeling – Conditional Random Fields

Conclusion●●●

Logistic regression is a probabilistic classifier
Conditional random fields are probabilistic structured
discriminative prediction modelsCan be trained using
Online stochastic gradient descent (like peceptron)● Batch learning using a method such as L-BFGS●●Regularization can help solve problems of overfitting40Sequential Data Modeling – Conditional Random Fields

Thank You!

41