Viterbi Decoding for HMM, Parameter Learning
EL
Pawan Goyal
PT
CSE, IIT Kharagpur
Week 4, Lecture 1
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 1/6
Walking through the states: best path
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 2/6
Walking through the states: best path
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 3/6
Finding the best path: Viterbi Algorithm
Intuition
Optimal path for each state can be recorded. We need
Cheapest cost to state j at step s: j (s)
EL
Backtrace from that state to best predecessor j (s)
Computing these values
j (s + 1)
j (s + 1)
PT
= max1iN i (s)p(tj |ti )p(ws+1 |tj )
= argmax1iN i (s)p(tj |ti )p(ws+1 |tj )
N
Best final state is argmax1iN i (|S|), we can backtrack from there
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 4/6
Practice Question
Suppose you want to use a HMM tagger to tag the phrase, “the light
book”, where we have the following probabilities:
P(the|Det) = 0.3, P(the|Noun) = 0.1, P(light|Noun) = 0.003, P(light|Adj) =
EL
0.002, P(light|Verb) = 0.06, P(book|Noun) = 0.003, P(book|Verb) = 0.01
P(Verb|Det) = 0.00001, P(Noun|Det) = 0.5, P(Adj|Det) = 0.3,
P(Noun|Noun) =0.2, P(Adj|Noun) = 0.002, P(Noun|Adj) = 0.2,
PT
P(Noun|Verb) = 0.3, P(Verb|Noun) = 0.3, P(Verb|Adj) = 0.001,
P(Verb|Verb) = 0.1
N
Work out in details the steps of the Viterbi algorithm. You can use a Table
to show the steps. Assume all other conditional probabilities, not
mentioned to be zero. Also, assume that all tags have the same
probabilities to appear in the beginning of a sentence.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 5/6
Learning the Parameters
Two Scenarios
A labeled dataset is available, with the POS category of individual words
in a corpus
EL
Only the corpus is available, but not labeled with the POS categories
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 6/6
Learning the Parameters
Two Scenarios
A labeled dataset is available, with the POS category of individual words
in a corpus
EL
Only the corpus is available, but not labeled with the POS categories
Methods for these scenarios
PT
For the first scenario, parameters can be directly estimated using
maximum likelihood estimate from the labeled dataset
N
For the second scenario, Baum-Welch Algorithm is used to estimate the
parameters of the hidden markov model.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 1 6/6
Baum Welch Algorithm
EL
Pawan Goyal
PT CSE, IIT Kharagpur
Week 4, Lecture 2
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 1/6
Baum Welch Algorithm
Uses the well-known EM algorithm to find the maximum likelihood estimate of
the parameters of a hidden markov model
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 2/6
Baum Welch Algorithm
Uses the well-known EM algorithm to find the maximum likelihood estimate of
the parameters of a hidden markov model
Parameters of HMM
EL
Let Xt be the random variable denoting hidden state at time t, and Yt be the
observation variable at time T . HMM parameters are given by ✓ = (A, B, ⇡)
where
A = {aij } = P(Xt = j|Xt
PT
1 = i) is the state transition matrix
⇡ = {⇡i } = P(X1 = i) is the initial state distribution
N
B = {bj (yt )} = P(Yt = yt |Xt = j) is the emission matrix
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 2/6
Baum Welch Algorithm
Uses the well-known EM algorithm to find the maximum likelihood estimate of
the parameters of a hidden markov model
Parameters of HMM
EL
Let Xt be the random variable denoting hidden state at time t, and Yt be the
observation variable at time T . HMM parameters are given by ✓ = (A, B, ⇡)
where
A = {aij } = P(Xt = j|Xt
PT
1 = i) is the state transition matrix
⇡ = {⇡i } = P(X1 = i) is the initial state distribution
N
B = {bj (yt )} = P(Yt = yt |Xt = j) is the emission matrix
Given observation sequences Y = (Y1 = y1 , Y2 = y2 , . . . , YT = yT ), the
algorithm tries to find the parameters ✓ that maximise the probability of the
observation.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 2/6
The Algorithm
The basic idea is to start with some random initial conditions on the
parameters ✓, estimate best values of state paths Xt using these, then
re-estimate the parameters ✓ using the just-computed values of Xt , iteratively.
EL
Intuition
Choose some initial values for ✓ = (A, B, ⇡).
Repeat the following step until convergence:
PT
Determine probable (state) paths . . . Xt 1 = i, Xt = j . . .
Count the expected number of transitions aij as well as the expected
N
number of times, various emissions bj (yt ) are made
Re-estimate ✓ = (A, B, ⇡) using aij and bj (yt )s.
A forward-backward algorithm is used for finding probable paths.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 3/6
Forward-Backward Algorithm
Forward Procedure
↵i (t) = P(Y1 = y1 , . . . , Yt = yt , Xt = i|✓) be the probability of seeing y1 , . . . , yt
and being in state i at time t. Found recursively using:
↵i (1) = ⇡i bi (y1 )
EL
N
X
↵j (t + 1) = bj (yt+1 ) ↵i (t)aij
i=1
Backward Procedure PT
i (t) = P(Yt+1 = yt+1 , . . . , YT = yT |Xt = i, ✓) be the probability of ending partial
N
sequence yt+1 , . . . , yT given starting state i at time t. i (t) is computed
recursively as:
i (T) =1
N
X
i (t) = j (t + 1)aij bj (yt+1 )
j=1
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 4/6
Finding probabilities of paths
We compute the following variables:
Probability of being in state i at time t given the observation Y and
parameters ✓
EL
↵i (t) i (t)
i (t) = P(Xt = i|Y, ✓) = PN
j=1 ↵j (t) j (t)
PT
Probability of being in state i and j at time t and t + 1 respectively given
the observation Y and parameters ✓
N
↵i (t)aij j (t + 1)bj (yt+1 )
⇣ij (t) = P(Xt = i, Xt+1 = j|Y, ✓) = PN PN
i=1 j=1 ↵i (t)aij j (t + 1)bj (yt+1 )
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 5/6
Updating the parameters
⇡i = i (1), expected number of times state i was seen at time 1
EL
PT
⇣ij (t)
aij = Pt=1
T , expected number of transitions from state i to state j,
t=1 i (t)
compared to the total number of transitions away from state i
PT
bi (vk ) = PT
t=1 i (t)
PT
t=1 1yt =vk i (t)
with 1yt =vk being an indicator function, is the
expected number of times the output observations are vk while being in
state i compared to the expected total number of times in state i.
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 2 6/6
Maximum Entropy Models
EL
Pawan Goyal
PT CSE, IIT Kharagpur
Week 4, Lecture 3
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 1 / 16
Issues with Markov Model Tagging
Unknown Words
We do not have the required probabilities.
Possible solutions:
EL
Use morphological cues (capitalization, suffix) to assign a more
calculated guess
Limited Context
PT
“is clearly marked” ! verb, past participle
N
“he clearly marked” ! verb, past tense
Possible solution: Use higher order model, combine various n-gram models to
avoid sparseness problem
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 2 / 16
Maximum Entropy Modeling: Discriminative Model
We may identify a heterogeneous set of features which contribute in some way
EL
to the choice of POS tag of the current word.
I Whether it is the first word in the article
Whether the next word is to
PT
I
I Whether one of the last 5 words is a preposition, etc.
MaxEnt combines these features in a probabilistic model
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 3 / 16
Maximum Entropy: The Model
0 1
1 BBBBX CCC
p (y|x) = exp B@ i fi (x, y)C CA
Z (x) i
where
EL
Z (x) is a normalizing constant given by
0 1
X BBBX CCC
Z (x) =
PT exp BB@
y
i fi (x, y)C
i
CA
N
i is a weight given to a feature fi
x denotes an observed datum and y denotes a class
What is the form of the features?
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 4 / 16
Features in Maximum Entropy Models
Features encode elements of the context x for predicting tag y
EL
Context x is taken around the word w, for which a tag y is to be predicted
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 5 / 16
Features in Maximum Entropy Models
Features encode elements of the context x for predicting tag y
EL
Context x is taken around the word w, for which a tag y is to be predicted
Features are binary values functions, e.g.,
PT
f (x, y) =
(
1 if isCapitalized(w)&y = NNP
0 otherwise
)
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 5 / 16
Example Features
Example: Named Entities
LOCATION (in Arcadia)
LOCATION (in Québec)
EL
DRUG (taking Zantac)
PERSON (saw Sue)
Example Features PT
f1 (x, y) = [y = LOCATION ^ w = “in” ^ isCapitalized(w)]
N
1
f2 (x, y) = [y = LOCATION ^ hasAccentedLatinChar(w)]
f3 (x, y) = [y = DRUG ^ ends(w, “c”)]
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 6 / 16
Tagging with Maximum Entropy Model
W = w1 . . . wn - words in the corpus (observed)
T = t1 . . . tn - the corresponding tags (unknown)
EL
Tag sequence candidate {t1 , . . . , tn } has conditional probability:
n
Y
PT
P(t1 , . . . , tn |w1 . . . , wn ) =
i=1
p(ti |xi )
N
The context xi also includes previously assigned tags for a fixed history.
Beam search is used to find the most probable sequence
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 7 / 16
Beam Inference
Beam Inference
EL
At each position, keep the top k complete sequences
Extend each sequence in each local way
The extensions compete for the k slots at the next position
But what is a MaxEnt model? PT
N
Let’s go to the basics now!
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 8 / 16
Maximum Entropy Model
EL
Intuitive Principle
Model all that is known and assume nothing about that which is unknown.
Given a collection of facts, choose a model which is consistent with all the
PT
facts, but otherwise as uniform as possible.
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 9 / 16
Maximum Entropy: Overview
Suppose we wish to model an expert translator’s decisions concerning
EL
the proper French rendering of the English word ‘in’.
Each French word or phrase f is assigned an estimate p(f ), probability
that the expert would choose f as a translation of ‘in’.
PT
Collect a large sample of instances of the expert’s decisions
Goal: extract a set of facts about the decision-making process (first task)
N
that will aid in constructing a model of this process (second task)
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 10 / 16
Maximum Entropy Model: Overview
First clue: list of allowed translations
Suppose the translator always chooses among {dans, en, á, au cours de,
pendant}.
EL
First constraint: p(dans)+p(en)+p(á)+p(au cours de)+p(pendant) = 1.
Infinite number of models p for which this identity holds, the most intuitive
model?
PT
allocate the total probability evenly among the five possible phrases !
most uniform model subject to our knowledge.
N
Is it the most uniform model overall?
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 11 / 16
Maximum Entropy Model: Overview
First clue: list of allowed translations
Suppose the translator always chooses among {dans, en, á, au cours de,
pendant}.
EL
First constraint: p(dans)+p(en)+p(á)+p(au cours de)+p(pendant) = 1.
Infinite number of models p for which this identity holds, the most intuitive
model?
PT
allocate the total probability evenly among the five possible phrases !
most uniform model subject to our knowledge.
N
Is it the most uniform model overall? ! No, that would grant an equal
probability to every possible French phrase.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 11 / 16
Maximum Entropy Model: Overview
More clues from the expert’s decision
Second clue: Suppose the expert chose either ‘dans’ or ‘en’ 30% of the
EL
time.
Third clue: In half of the cases, the expert chose either ‘dans’ or ‘á’
PT
How do we measure uniformity of a model?
As we add complexity to the model, we face two difficulties:
N
What exactly is meant by “uniform”?
How can one measure the uniformity of a model?
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 12 / 16
Maximum Entropy Modeling
Entropy: measures the uncertainty of a distribution.
Quantifying uncertainty (“surprise”)
Event x
EL
Probability px
Surprise: log(1/px )
"PT
Entropy: expected surprise (over p)
H(p) = Ep log2
1
# X
px log2 px
N
=
px x
Coin Tossing
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 13 / 16
Maximum Entropy Modeling
Distribution required
Minimize commitment = maximize entropy
Resemble some reference distribution
EL
Solution
Maximize entropy H , subject to feature-based constraints:
PT Ep [fi ] = Ep̃ [fi ]
N
Adding constraints
Lowers maximum entropy
Brings the distribution further from uniform and closer to data
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 14 / 16
Maximum Entropy Principle
Given n feature functions fi , we would like p to lie in the subset C of P defined
by
C = {p 2 P|p(fi ) = p̃(fi ), i 2 {1, 2, . . . , n}}
Empirical count (expectation) of a feature
EL
X
p̃(fi ) = p̃(x, y)fi (x, y)
x,y
Model expectation of a feature PT X
N
p(fi ) = p̃(x)p(y|x)fi (x, y)
x,y
Select the distribution which is most uniform (conditional probability):
X
p⇤ = argmaxp2C H(p) = H(Y|X) ⇡ p̃(x)p(y|x)logp(y|x)
x,y
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 15 / 16
Maximum Entropy Principle
p⇤ = argmaxp2C H(p)
Constraint Optimization
EL
Introduce a parameter i for each feature fi . Lagrangian is given by
X
^(p, ) = H(p) + i (p(fi ) p̃(fi ))
i
Solving, we get
PT
p (y|x) =
1
0
BBBX
exp BB@
1
CCC
i fi (x, y)C CA
N
Z (x) i
where Z (x) is a normalizing constant given by
0 1
X BBBX CCC
Z (x) = exp BB@ i fi (x, y)C CA
y i
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 3 16 / 16
Maximum Entropy Models
EL
Pawan Goyal
PT CSE, IIT Kharagpur
Week 4, Lecture 4
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 1/8
Practice Question
Consider the maximum entropy model for POS tagging, where you want to estimate P(tag|word). In a
hypothetical setting, assume that tag can take the values D, N and V (short forms for Determiner, Noun and
Verb). The variable word could be any member of a set V of possible words, where V contains the words a,
man, sleeps, as well as additional words. The distribution should give the following probabilities
P(D|a) = 0.9
P(N|man) = 0.9
P(V|sleeps) = 0.9
EL
P(D|word) = 0.6 for any word other than a, man or sleeps
P(N|word) = 0.3 for any word other than a, man or sleeps
P(V|word) = 0.1 for any word other than a, man or sleeps
It is assumed that all other probabilities, not defined above could take any values such that
P
PT
tag P(tag|word) = 1 is satisfied for any word in V .
Define the features of your maximum entropy model that can model this distribution. Mark your
features as f1 , f2 and so on. Each feature should have the same format as explained in the class.
[Hint: 6 Features should make the analysis easier]
N
For each feature fi , assume a weight i . Now, write expression for the following probabilities in terms
of your model parameters
I P(D|cat)
I P(N|laughs)
I P(D|man)
What value do the parameters in your model take to give the distribution as described above. (i.e.
P(D|a) = 0.9 and so on. You may leave the final answer in terms of equations)
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 2/8
Features for POS Tagging (Ratnaparakhi, 1996)
EL
The specific word and tag context available to a feature is
hi = {wi , wi+1 , wi+2 , wi 1 , wi 2 , ti 1 , ti 2 }
PT
Example: fj (hi , ti ) = 1 if suffix(wi ) = “ing00 &ti = VBG
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 3/8
Example Features
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 4/8
Example Features
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 5/8
Search Algorithm
Conditional Probability
Given a sentence {w1 , . . . , wn }, a tag sequence candidate {t1 , . . . , tn } has
EL
conditional probability:
n
Y
P(t1 , . . . , tn |w1 . . . , wn ) = p(ti |xi )
PT i=1
N
A Tag Dictionary is used, which, for each known word, lists the tags that it has
appeared with in the training set.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 6/8
Search Algorithm
Let W = {w1 , . . . , wn } be a test sentence, sij be the jth highest probability tag
sequence up to and including word wi .
Search description
Generate tags for w1 , find top N , set s1j , 1 j N , accordingly.
EL
Initialize i = 2
I Initialize j = 1
I
I
PT
Generate tags for wi , given s(i 1)j as previous tag context, and append
each tag to s(i 1)j to make a new sequence
j = j + 1, repeat if j N
N
Find N highest probability sequences generated by above loop, set sij
accordingly
i = i + 1, repeat if i n
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 7/8
Search Algorithm
Let W = {w1 , . . . , wn } be a test sentence, sij be the jth highest probability tag
sequence up to and including word wi .
Search description
Generate tags for w1 , find top N , set s1j , 1 j N , accordingly.
EL
Initialize i = 2
I Initialize j = 1
I
I
PT
Generate tags for wi , given s(i 1)j as previous tag context, and append
each tag to s(i 1)j to make a new sequence
j = j + 1, repeat if j N
N
Find N highest probability sequences generated by above loop, set sij
accordingly
i = i + 1, repeat if i n
Return highest probability sequence sn1
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 7/8
A Good Reference
EL
Berger et al., A Maximum Entropy Approach to Natural Language Processing,
Computational Linguistics, Vol. 22, No. 1.
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 4 8/8
Conditional Random Fields
EL
Pawan Goyal
PT CSE, IIT Kharagpur
Week 4, Lecture 5
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 1/8
Practice Question
Suppose you want to use a MaxEnt tagger to tag the sentence, “the light book”. We know that the top 2
POS tags for the words the, light and book are {Det, Noun}, {Verb, Adj} and {Verb, Noun}, respectively.
Assume that the MaxEnt model uses the following history hi (context) for a word wi :
hi = {wi , wi 1 , wi+1 , ti 1 }
EL
where wi 1 and wi+1 correspond to the previous and next words and ti 1 corresponds to the tag of the
previous word. Accordingly, the following features are being used by the MaxEnt model:
f1 : ti 1 = Det and ti = Adj
f2 : ti = Noun and ti = Verb
f3 : ti
f 4 : wi
f 5 : wi
1
1 = Adj and ti = Noun
1
1
= the and ti = Adj PT
= the&wi+1 = book and ti = Adj
N
f 6 : wi 1 = light and ti = Noun
f7 : wi+1 = light and ti = Det
f 8 : wi 1 = NULL and ti = Noun
Assume that each feature has a uniform weight of 1.0.
Use Beam search algorithm with a beam-size of 2 to identify the highest probability tag sequence for the
sentence.
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 2/8
Problem with Maximum Entropy Models
Per-state normalization
EL
All the mass that arrives at a state must be distributed among the possible
successor states
This gives a ‘label bias’ problem
PT
Let’s see the intuition (on paper)
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 3/8
Conditional Random Fields
EL
CRFs are conditionally trained, undirected graphical models.
Let’s look at the linear chain structure
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 4/8
Conditional Random Fields: Feature Functions
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 5/8
Feature Functions
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 6/8
Conditional Random Fields: Distribution
EL
PT
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 7/8
CRFs
EL
Have the advantages of MEMM but avoid the label bias problem
CRFs are globally normalized, whereas MEMMs are locally normalized.
PT
Widely used and applied. CRFs have been (close to) state-of-the-art in
many sequence labeling tasks.
N
Pawan Goyal (IIT Kharagpur) POS Tagging Week 4, Lecture 5 8/8