Part-of-Speech Tagging and HMM in Text Mining
POS TAGGING AND
HMM
Tim Teks Mining
Adapted from Heng Ji
Outline
•
POS Tagging and HMM
3
/
3
9
What is Part-of-Speech (POS)
•
Generally speaking, Word Classes (=POS) :
•
Verb, Noun, Adjective, Adverb, Article,
…
•
We can also include inflection:
•
Verbs: Tense, number,
…
•
Nouns: Number, proper/common,
…
•
Adjectives: comparative, superlative,
…
•
…
4
/
3
9
Parts of Speech
•
8 (ish) traditional parts of speech
•
Noun, verb, adjective, preposition, adverb, article, interjection,
pronoun, conjunction, etc
•
Called: parts-of-speech, lexical categories, word classes,
morphological classes, lexical tags...
•
Lots of debate within linguistics about the number, nature, and
universality of these
•
We’ll completely ignore this debate.
5
/
3
9
7 Traditional POS Categories
•
N
noun
chair, bandwidth, pacing
•
V
verb
study, debate, munch
•
ADJ
adj
purple, tall, ridiculous
•
ADV
adverb
unfortunately, slowly,
•
P
preposition
of, by, to
•
PRO
pronoun
I, me, mine
•
DET
determiner
the, a, that, those
6
/
3
9
POS Tagging
•
The process of assigning a part-of-speech or lexical
class marker to each word in a collection.
WORD
tag
t
h
e
D
E
T
k
o
a
l
a
N
p
u
t
V
t
h
e
D
E
T
k
e
y
s
N
o
n
P
t
h
e
D
E
T
t
a
b
l
e
N
7
/
3
9
Penn TreeBank POS Tag Set
•
Penn Treebank: hand-annotated corpus of
Wall Street
Journal
, 1M words
•
46 tags
•
Some particularities:
•
to
/TO not disambiguated
•
Auxiliaries and verbs not distinguished
8
/
3
9
Penn Treebank Tagset
9
/
3
9
Why POS tagging is useful?
•
Speech synthesis:
•
How to pronounce
“
lead
”
?
•
INsult
inSULT
•
OBject
obJECT
•
OVERflow
overFLOW
•
DIScount
disCOUNT
•
CONtent
conTENT
•
Stemming for information retrieval
•
Can search for “aardvarks” get “aardvark”
•
Parsing and speech recognition and etc
•
Possessive pronouns (my, your, her) followed by nouns
•
Personal pronouns (I, you, he) likely to be followed by verbs
•
Need to know if a word is an N or V before you can parse
•
Information extraction
•
Finding names, relations, etc.
•
Machine Translation
10
10
/
3
9
Open and Closed Classes
•
Closed class: a small fixed membership
•
Prepositions: of, in, by, …
•
Auxiliaries: may, can, will had, been, …
•
Pronouns: I, you, she, mine, his, them, …
•
Usually
function words
(short common words which play a
role in grammar)
•
Open class: new ones can be created all the time
•
English has 4: Nouns, Verbs, Adjectives, Adverbs
•
Many languages have these 4, but not all!
11
11
/
3
9
Open Class Words
•
Nouns
•
Proper nouns (Boulder, Granby, Eli Manning)
•
English capitalizes these.
•
Common nouns (the rest).
•
Count nouns and mass nouns
•
Count: have plurals, get counted: goat/goats, one goat, two goats
•
Mass: don’t get counted (snow, salt, communism) (*two snows)
•
Adverbs: tend to modify things
•
Unfortunately,
John
walked home
extremely slowly yesterday
•
Directional/locative adverbs (here,home, downhill)
•
Degree adverbs (extremely, very, somewhat)
•
Manner adverbs (slowly, slinkily, delicately)
•
Verbs
•
In English, have morphological affixes (eat/eats/eaten)
12
12
/
3
9
Closed Class Words
Examples
:
•
prepositions:
on, under, over,
…
•
particles:
up, down, on, off, …
•
determiners:
a, an, the, …
•
pronouns:
she, who, I, ..
•
conjunctions:
and, but, or, …
•
auxiliary verbs:
can, may should, …
•
numerals:
one, two, three, third, …
13
13
/
3
9
Prepositions from CELEX
14
14
/
3
9
English Particles
15
15
/
3
9
Conjunctions
16
16
/
3
9
POS Tagging
Choosing a Tagset
•
There are so many parts of speech, potential distinctions we can
draw
•
To do POS tagging, we need to choose a standard set of tags to
work with
•
Could pick very coarse tagsets
•
N, V, Adj, Adv.
•
More commonly used set is finer grained, the “Penn TreeBank
tagset”, 45 tags
•
PRP$, WRB, WP$, VBG
•
Even more fine-grained tagsets exist
17
17
/
3
9
Using the Penn Tagset
•
The/DT grand/JJ jury/NN commmented/VBD on/IN a/DT
number/NN of/IN other/JJ topics/NNS ./.
•
Prepositions and subordinating conjunctions marked IN
(“although/IN I/PRP..”)
•
Except the preposition/complementizer “to” is just marked
“TO”.
18
18
/
3
9
POS Tagging
•
Words often have more than one POS:
back
•
The
back
door = JJ
•
On my
back
= NN
•
Win the voters
back
= RB
•
Promised to
back
the bill = VB
•
The POS tagging problem is to determine the POS tag for
a particular instance of a word.
These examples from Dekang Lin
19
19
/
3
9
How Hard is POS Tagging? Measuring
Ambiguity
20
20
/
3
9
Current Performance
•
How many tags are correct?
•
About 97% currently
•
But baseline is already 90%
•
Baseline algorithm:
•
Tag every word with its most frequent tag
•
Tag unknown words as nouns
•
How well do people do?
21
21
/
3
9
Quick Test: Agreement?
•
the students went to class
•
plays well with others
•
fruit flies like a banana
DT: the, this, that
NN: noun
VB: verb
P: prepostion
ADV: adverb
22
22
/
3
9
Quick Test
•
the students went to class
DT NN VB P NN
•
plays well with others
VB ADV P NN
NN NN P DT
•
fruit flies like a banana
NN NN VB DT NN
NN VB P DT NN
NN NN P DT NN
NN VB VB DT NN
23
23
/
3
9
How to do it? History
B
r
o
w
n
C
o
r
p
u
s
C
r
e
a
t
e
d
(
E
N
-
U
S
)
1
M
i
l
l
i
o
n
W
o
r
d
s
B
r
o
w
n
C
o
r
p
u
s
T
a
g
g
e
d
H
M
M
T
a
g
g
i
n
g
(
C
L
A
W
S
)
9
3
%
-
9
5
%
G
r
e
e
n
e
a
n
d
R
u
b
i
n
R
u
l
e
B
a
s
e
d
-
7
0
%
L
O
B
C
o
r
p
u
s
C
r
e
a
t
e
d
(
E
N
-
U
K
)
1
M
i
l
l
i
o
n
W
o
r
d
s
D
e
R
o
s
e
/
C
h
u
r
c
h
E
f
f
i
c
i
e
n
t
H
M
M
S
p
a
r
s
e
D
a
t
a
9
5
%
+
B
r
i
t
i
s
h
N
a
t
i
o
n
a
l
C
o
r
p
u
s
(
t
a
g
g
e
d
b
y
C
L
A
W
S
)
P
O
S
T
a
g
g
i
n
g
s
e
p
a
r
a
t
e
d
f
r
o
m
o
t
h
e
r
N
L
P
T
r
a
n
s
f
o
r
m
a
t
i
o
n
B
a
s
e
d
T
a
g
g
i
n
g
(
E
r
i
c
B
r
i
l
l
)
R
u
l
e
B
a
s
e
d
–
9
5
%
+
T
r
e
e
-
B
a
s
e
d
S
t
a
t
i
s
t
i
c
s
(
H
e
l
m
u
t
S
h
m
i
d
)
R
u
l
e
B
a
s
e
d
–
9
6
%
+
N
e
u
r
a
l
N
e
t
w
o
r
k
9
6
%
+
T
r
i
g
r
a
m
T
a
g
g
e
r
(
K
e
m
p
e
)
9
6
%
+
C
o
m
b
i
n
e
d
M
e
t
h
o
d
s
9
8
%
+
P
e
n
n
T
r
e
e
b
a
n
k
C
o
r
p
u
s
(
W
S
J
,
4
.
5
M
)
L
O
B
C
o
r
p
u
s
T
a
g
g
e
d
24
24
/
3
9
Two Methods for POS Tagging
1.
Rule-based tagging
•
(ENGTWOL)
2.
Stochastic
1.
Probabilistic sequence models
•
HMM (Hidden Markov Model) tagging
•
MEMMs (Maximum Entropy Markov Models)
25
25
/
3
9
Rule-Based Tagging
•
Start with a dictionary
•
Assign all possible tags to words from the dictionary
•
Write rules by hand to selectively remove tags
•
Leaving the correct tag for each word.
26
26
/
3
9
Rule-based taggers
•
Early POS taggers all hand-coded
•
Most of these (Harris, 1962; Greene and Rubin, 1971)
and the best of the recent ones, ENGTWOL (Voutilainen,
1995) based on a two-stage architecture
•
Stage 1: look up word in lexicon to give list of potential POSs
•
Stage 2: Apply rules which certify or disallow tag sequences
•
Rules originally handwritten; more recently Machine
Learning methods can be used
27
27
/
3
9
Start With a Dictionary
•
she:
PRP
•
promised:
VBN,VBD
•
to
TO
•
back:
VB, JJ, RB, NN
•
the:
DT
•
bill:
NN, VB
•
Etc… for the ~100,000 words of English with more than 1
tag
28
28
/
3
9
Assign Every Possible Tag
NN
RB
VBN
JJ VB
PRP
VBD
TO
VB DT
NN
S
h
e
p
r
o
m
i
s
e
d
t
o
b
a
c
k
t
h
e
b
i
l
l
29
29
/
3
9
Write Rules to Eliminate Tags
Eliminate VBN if VBD is an option when VBN|VBD follows
“<start> PRP”
NN
RB
JJ
VB
PRP
VBD
TO VB
DT
NN
S
h
e
p
r
o
m
i
s
e
d
t
o
b
a
c
k
t
h
e
b
i
l
l
VBN
30
30
/
3
9
POS tagging
The involvement of ion channels in B and T lymphocyte activation is
DT NN IN NN NNS IN NN CC NN NN NN VBZ
supported by many reports of changes in ion fluxes and membrane
VBN IN JJ NNS IN NNS IN NN NNS CC NN
…………………………………………………………………………………….
…………………………………………………………………………………….
Machine Learning
Algorithm
training
We demonstrate
that …
Unseen text
We demonstrate
PRP VBP
that …
IN
31
31
/
3
9
Goal of POS Tagging
We want the best set of tags for a sequence of words (a
sentence)
W — a sequence of words
T — a sequence of tags
Example:
P(
(NN NN P DET ADJ NN)
|
(
heat oil in a large pot
)
)
O
u
r
G
o
a
l
32
32
/
3
9
But, the Sparse Data Problem …
•
Rich Models often require vast amounts of data
•
Count up instances of the string "heat oil in a large pot" in
the training corpus, and pick the most common tag
assignment to the string..
•
Too many possible combinations
33
33
/
3
9
POS Tagging as Sequence Classification
•
We are given a sentence (an “observation” or “sequence of
observations”)
•
Secretariat is expected to race tomorrow
•
What is the best sequence of tags that corresponds to this
sequence of observations?
•
Probabilistic view:
•
Consider all possible sequences of tags
•
Out of this universe of sequences, choose the tag sequence which is
most probable given the observation sequence of n words w
1
…w
n
.
34
34
/
3
9
Getting to HMMs
•
We want, out of all sequences of n tags t
1
…t
n
the single tag sequence
such that P(t
1
…t
n
|w
1
…w
n
) is highest.
•
Hat ^ means “our estimate of the best one”
•
Argmax
x
f(x) means “the x such that f(x) is maximized”
35
35
/
3
9
Getting to HMMs
•
This equation is guaranteed to give us the best tag
sequence
•
But how to make it operational? How to compute this
value?
•
Intuition of Bayesian classification:
•
Use Bayes rule to transform this equation into a set of other
probabilities that are easier to compute
36
36
/
3
9
Reminder: Apply
Bayes’ Theorem (1763)
Reverend Thomas Bayes
—
Presbyterian minister (1702-1761)
Our Goal: To
maximize it!
37
37
/
3
9
How to Count
P(W|T) and P(T) can be counted from a large
hand-tagged corpus; and smooth them to get rid of the zeroes
38
38
/
3
9
Count P(W|T) and P(T)
Assume each word in the sequence depends only on
its corresponding tag:
39
39
/
3
9
Make a Markov assumption and use N-grams over
tags ...
P(T) is a product of the probability of N-grams that make
it up
Count P(T)
40
40
/
3
9
Part-of-speech tagging with Hidden Markov
Models
words
tags
output probability
transition probability
41
41
/
3
9
Analyzing
Fish sleep.
42
42
/
3
9
A Simple POS HMM
43
43
/
3
9
Word Emission Probabilities
P ( word | state )
•
A two-word language:
“
fish
”
and
“
sleep
”
•
Suppose in our training corpus,
•
“
fish
”
appears 8 times as a noun and 5 times as a verb
•
“
sleep
”
appears twice as a noun and 5 times as a verb
•
Emission probabilities:
•
Noun
•
P(fish | noun) :
0.8
•
P(sleep | noun) :
0.2
•
Verb
•
P(fish | verb) :
0.5
•
P(sleep | verb) :
0.5
44
44
/
3
9
Viterbi Probabilities
45
45
/
3
9
46
46
/
3
9
Token 1: fish
47
47
/
3
9
Token 1: fish
48
48
/
3
9
Token 2: sleep
(if ‘fish’ is verb)
49
49
/
3
9
Token 2: sleep
(if ‘fish’ is verb)
50
50
/
3
9
Token 2: sleep
(if ‘fish’ is a noun)
51
51
/
3
9
Token 2: sleep
(if ‘fish’ is a noun)
52
52
/
3
9
Token 2: sleep
take maximum,
set back pointers
53
53
/
3
9
Token 2: sleep
take maximum,
set back pointers
54
54
/
3
9
Token 3: end
55
55
/
3
9
Token 3: end
take maximum,
set back pointers
56
56
/
3
9
Decode:
fish = noun
sleep = verb
Markov Chain for a Simple Name Tagger
START
END
PER
X
0.3
0.2
0.2
0.2
0.3
0.6
0.5
George:0.3
W.:0.3
W.:0.3
discussed:0.7
$:1.0
LOC
0.5
0.2
0.1
0.3
0.3
0.1
0.2
Bush:0.3
Iraq:0.1
George:0.2
Iraq:0.8
T
r
a
n
s
i
t
i
o
n
P
r
o
b
a
b
i
l
i
t
y
E
m
i
s
s
i
o
n
P
r
o
b
a
b
i
l
i
t
y
58
58
/
3
9
Exercise
•
Tag names in the followin
g sentence:
•
George. W. Bush discussed Iraq.
59
59
/
3
9
POS taggers
•
Brill
’
s tagger
•
http://www.cs.jhu.edu/~brill/
•
TnT tagger
•
http://www.coli.uni-saarland.de/~thorsten/tnt/
•
Stanford tagger
•
http://nlp.stanford.edu/software/tagger.shtml
•
SVMTool
•
http://www.lsi.upc.es/~nlp/SVMTool/
•
GENIA tagger
•
http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/tagger/
•
More complete list at:
http://www-nlp.stanford.edu/links/statnlp.html#Taggers
Part-of-Speech (POS) tagging plays a crucial role in natural language processing by assigning lexical class markers to words. This process helps in speech synthesis, information retrieval, parsing, and machine translation. With the use of Hidden Markov Models (HMM), we can enhance the accuracy of POS tagging for various applications in text mining and language analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
POS TAGGING AND HMM Tim Teks Mining Adapted from Heng Ji
Outline POS Tagging and HMM
3/39 What is Part-of-Speech (POS) Generally speaking, Word Classes (=POS) : Verb, Noun, Adjective, Adverb, Article, We can also include inflection: Verbs: Tense, number, Nouns: Number, proper/common, Adjectives: comparative, superlative,
4/39 Parts of Speech 8 (ish) traditional parts of speech Noun, verb, adjective, preposition, adverb, article, interjection, pronoun, conjunction, etc Called: parts-of-speech, lexical categories, word classes, morphological classes, lexical tags... Lots of debate within linguistics about the number, nature, and universality of these We ll completely ignore this debate.
5/39 7 Traditional POS Categories N V ADJ adj ADV adverb P PRO pronoun DET determiner noun verb chair, bandwidth, pacing study, debate, munch purple, tall, ridiculous unfortunately, slowly, preposition of, by, to I, me, mine the, a, that, those
6/39 POS Tagging The process of assigning a part-of-speech or lexical class marker to each word in a collection. WORD tag the koala put the keys on the table DET N V DET N P DET N
7/39 Penn TreeBank POS Tag Set Penn Treebank: hand-annotated corpus of Wall Street Journal, 1M words 46 tags Some particularities: to /TO not disambiguated Auxiliaries and verbs not distinguished
8/39 Penn Treebank Tagset
9/39 Why POS tagging is useful? Speech synthesis: How to pronounce lead ? INsult OBject OVERflow overFLOW DIScount CONtent Stemming for information retrieval Can search for aardvarks get aardvark Parsing and speech recognition and etc Possessive pronouns (my, your, her) followed by nouns Personal pronouns (I, you, he) likely to be followed by verbs Need to know if a word is an N or V before you can parse Information extraction Finding names, relations, etc. Machine Translation inSULT obJECT disCOUNT conTENT
10/39 Open and Closed Classes Closed class: a small fixed membership Prepositions: of, in, by, Auxiliaries: may, can, will had, been, Pronouns: I, you, she, mine, his, them, Usually function words (short common words which play a role in grammar) Open class: new ones can be created all the time English has 4: Nouns, Verbs, Adjectives, Adverbs Many languages have these 4, but not all!
11/39 Open Class Words Nouns Proper nouns (Boulder, Granby, Eli Manning) English capitalizes these. Common nouns (the rest). Count nouns and mass nouns Count: have plurals, get counted: goat/goats, one goat, two goats Mass: don t get counted (snow, salt, communism) (*two snows) Adverbs: tend to modify things Unfortunately, John walked home extremely slowly yesterday Directional/locative adverbs (here,home, downhill) Degree adverbs (extremely, very, somewhat) Manner adverbs (slowly, slinkily, delicately) Verbs In English, have morphological affixes (eat/eats/eaten)
12/39 Closed Class Words Examples: prepositions: on, under, over, particles: up, down, on, off, determiners: a, an, the, pronouns: she, who, I, .. conjunctions: and, but, or, auxiliary verbs: can, may should, numerals: one, two, three, third,
13/39 Prepositions from CELEX
14/39 English Particles
15/39 Conjunctions
16/39 POS Tagging Choosing a Tagset There are so many parts of speech, potential distinctions we can draw To do POS tagging, we need to choose a standard set of tags to work with Could pick very coarse tagsets N, V, Adj, Adv. More commonly used set is finer grained, the Penn TreeBank tagset , 45 tags PRP$, WRB, WP$, VBG Even more fine-grained tagsets exist
17/39 Using the Penn Tagset The/DT grand/JJ jury/NN commmented/VBD on/IN a/DT number/NN of/IN other/JJ topics/NNS ./. Prepositions and subordinating conjunctions marked IN ( although/IN I/PRP.. ) Except the preposition/complementizer to is just marked TO .
18/39 POS Tagging Words often have more than one POS: back The back door = JJ On my back = NN Win the voters back = RB Promised to back the bill = VB The POS tagging problem is to determine the POS tag for a particular instance of a word. These examples from Dekang Lin
19/39 How Hard is POS Tagging? Measuring Ambiguity
20/39 Current Performance How many tags are correct? About 97% currently But baseline is already 90% Baseline algorithm: Tag every word with its most frequent tag Tag unknown words as nouns How well do people do?
21/39 Quick Test: Agreement? the students went to class plays well with others fruit flies like a banana DT: the, this, that NN: noun VB: verb P: prepostion ADV: adverb
22/39 Quick Test the students went to class DT NN VB P NN plays well with others VB ADV P NN NN NN P DT fruit flies like a banana NN NN VB DT NN NN VB P DT NN NN NN P DT NN NN VB VB DT NN
23/39 How to do it? History Combined Methods 98%+ Trigram Tagger (Kempe) 96%+ DeRose/Church Efficient HMM Sparse Data 95%+ Tree-Based Statistics (Helmut Shmid) Rule Based 96%+ Transformation Based Tagging (Eric Brill) Rule Based 95%+ Greene and Rubin Rule Based - 70% HMM Tagging (CLAWS) 93%-95% Neural Network 96%+ 1960 1970 1980 1990 2000 LOB Corpus Tagged Brown Corpus Created (EN-US) 1 Million Words Brown Corpus Tagged British National Corpus (tagged by CLAWS) POS Tagging separated from other NLP LOB Corpus Created (EN-UK) 1 Million Words Penn Treebank Corpus (WSJ, 4.5M)
24/39 Two Methods for POS Tagging Rule-based tagging (ENGTWOL) Stochastic 1. Probabilistic sequence models HMM (Hidden Markov Model) tagging MEMMs (Maximum Entropy Markov Models) 1. 2.
25/39 Rule-Based Tagging Start with a dictionary Assign all possible tags to words from the dictionary Write rules by hand to selectively remove tags Leaving the correct tag for each word.
26/39 Rule-based taggers Early POS taggers all hand-coded Most of these (Harris, 1962; Greene and Rubin, 1971) and the best of the recent ones, ENGTWOL (Voutilainen, 1995) based on a two-stage architecture Stage 1: look up word in lexicon to give list of potential POSs Stage 2: Apply rules which certify or disallow tag sequences Rules originally handwritten; more recently Machine Learning methods can be used
27/39 Start With a Dictionary she: PRP promised: VBN,VBD to back: VB, JJ, RB, NN the: DT bill: NN, VB TO Etc for the ~100,000 words of English with more than 1 tag
28/39 Assign Every Possible Tag PRP VBD She promised to back the VBN TO NN RB JJ VB VB DT NN bill
29/39 Write Rules to Eliminate Tags Eliminate VBN if VBD is an option when VBN|VBD follows <start> PRP NN RB JJ PRP VBD TO VB DT She promised to back the NN bill VB VBN
30/39 POS tagging The involvement of ion channels in B and T lymphocyte activation is DT NN IN NN NNS IN NN CC NN NN NN VBZ supported by many reports of changes in ion fluxes and membrane VBN IN JJ NNS IN NNS IN NN NNS CC NN . . training Unseen text We demonstrate PRP VBP that IN We demonstrate that Machine Learning Algorithm
Goal of POS Tagging We want the best set of tags for a sequence of words (a sentence) W a sequence of words T a sequence of tags ^ = arg T max ( | ) T P T W Our Goal Example: P((NN NN P DET ADJ NN) | (heat oil in a large pot)) 31/39
32/39 But, the Sparse Data Problem Rich Models often require vast amounts of data Count up instances of the string "heat oil in a large pot" in the training corpus, and pick the most common tag assignment to the string.. Too many possible combinations
33/39 POS Tagging as Sequence Classification We are given a sentence (an observation or sequence of observations ) Secretariat is expected to race tomorrow What is the best sequence of tags that corresponds to this sequence of observations? Probabilistic view: Consider all possible sequences of tags Out of this universe of sequences, choose the tag sequence which is most probable given the observation sequence of n words w1 wn.
34/39 Getting to HMMs We want, out of all sequences of n tags t1 tn the single tag sequence such that P(t1 tn|w1 wn) is highest. Hat ^ means our estimate of the best one Argmaxxf(x) means the x such that f(x) is maximized
35/39 Getting to HMMs This equation is guaranteed to give us the best tag sequence But how to make it operational? How to compute this value? Intuition of Bayesian classification: Use Bayes rule to transform this equation into a set of other probabilities that are easier to compute
Reminder: Apply Bayes Theorem (1763) likelihood prior posterior ( | ) ( ) P W T P T = ( | ) P T W ( ) P W Our Goal: To maximize it! marginal likelihood Reverend Thomas Bayes Presbyterian minister (1702-1761) 36/39
How to Count ^ = arg T max ( | ) T P T W ( | ) ( ) P W T P T = arg max T ( ) P W = arg max T ( | ) ( ) P W T P T P(W|T) and P(T) can be counted from a large hand-tagged corpus; and smooth them to get rid of the zeroes 37/39
Count P(W|T) and P(T) Assume each word in the sequence depends only on its corresponding tag: n = i W ( | ) ( i t | ) P T P w i 1 38/39
39/39 Count P(T) = ( ,..., ) P t t history 1 n ( ) ( | ) ( | ) ... ( | ,..., ) P t P t t P t t t P t t t 1 2 1 3 1 2 1 1 n n Make a Markov assumption and use N-grams over tags ... P(T) is a product of the probability of N-grams that make it up n = i = ( ,..., ) ( ) ( | ) P t t P t P t t 1 i i 1 1 n 2
40/39 Part-of-speech tagging with Hidden Markov Models ( ) ( ) ) ( P ) ... | ... ... P w w t t P t t ( ) = 1 1 1 ... | ... n n n P t t w w ( 1 tags 1 n n ... P w | w 1 words n ( ) ... ... ... P w w t t t t 1 1 1 n n n n ( ) ( P ) = i | | P w t t t 1 i i i i 1 transition probability output probability
41/39 Analyzing Fish sleep.
42/39 A Simple POS HMM 0.2 0.1 0.8 0.7 end 0.8 start noun verb 0.2 0.1 0.1
43/39 Word Emission Probabilities P ( word | state ) A two-word language: fish and sleep Suppose in our training corpus, fish appears 8 times as a noun and 5 times as a verb sleep appears twice as a noun and 5 times as a verb Emission probabilities: Noun P(fish | noun) : 0.8 P(sleep | noun) : 0.2 Verb P(fish | verb) : 0.5 P(sleep | verb) : 0.5
44/39 Viterbi Probabilities 0 1 2 3 start verb noun end
45/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 0 1 2 3 start 1 verb 0 noun 0 end 0
46/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 Token 1: fish 0 1 2 3 start 1 0 verb 0 .2 * .5 noun 0 .8 * .8 end 0 0
47/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 Token 1: fish 0 1 2 3 start 1 0 verb 0 .1 noun 0 .64 end 0 0
48/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 Token 2: sleep 0 1 2 3 (if fish is verb) start 1 0 0 verb 0 .1 .1*.1*.5 noun 0 .64 .1*.2*.2 end 0 0 -
49/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 Token 2: sleep 0 1 2 3 (if fish is verb) start 1 0 0 verb 0 .1 .005 noun 0 .64 .004 end 0 0 -
50/39 0.2 0.1 0.8 0.7 0.8 end start noun verb 0.2 0.1 0.1 Token 2: sleep 0 1 2 3 (if fish is a noun) start 1 0 0 verb 0 .1 .005 .64*.8*.5 .004 .64*.1*.2 - noun 0 .64 end 0 0
