Transcript savechapter5part1

Word classes and part of
speech tagging
Chapter 5
Outline
Why part of speech tagging?
Word classes
Tag sets and problem definition
Automatic approaches 1: rule-based tagging
Automatic approaches 2: stochastic tagging
On Part 2: finish stochastic tagging, and continue on to:
Automatic approaches 3: transformation-based tagging
Other issues: tagging unknown words, evaluation
Slide 1
Definition
“The process of assigning a part-of-speech or
other lexical class marker to each word in a
corpus” (Jurafsky and Martin)
WORDS
the
girl
kissed
the
boy
on
the
cheek
TAGS
N
V
P
DET
Slide 2
An Example
WORD
the
girl
kissed
the
boy
on
the
cheek
LEMMA
the
girl
kiss
the
boy
on
the
cheek
TAG
+DET
+NOUN
+VPAST
+DET
+NOUN
+PREP
+DET
+NOUN
Slide 3
Motivation
Speech synthesis — pronunciation
Speech recognition — class-based N-grams
Information retrieval — stemming, selection high-content
words
Word-sense disambiguation
Corpus analysis of language & lexicography
Slide 4
Outline
Why part of speech tagging?
Word classes
Tag sets and problem definition
Automatic approaches 1: rule-based tagging
Automatic approaches 2: stochastic tagging
Automatic approaches 3: transformation-based tagging
Other issues: tagging unknown words, evaluation
Slide 5
Word Classes
Basic word classes: Noun, Verb, Adjective, Adverb,
Preposition, …
Open vs. Closed classes
Open:
Nouns, Verbs, Adjectives, Adverbs.
Why “open”?
Closed:
determiners: a, an, the
pronouns: she, he, I
prepositions: on, under, over, near, by, …
Slide 6
Open Class Words
Every known human language has nouns and verbs
Nouns: people, places, things
Classes of nouns
proper vs. common
count vs. mass
Verbs: actions and processes
Adjectives: properties, qualities
Adverbs: hodgepodge!
Unfortunately, John walked home extremely slowly yesterday
Numerals: one, two, three, third, …
Slide 7
Closed Class Words
Differ more from language to language than open 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, …
Slide 8
Prepositions from CELEX
Slide 9
English Single-Word Particles
Slide 10
Pronouns in CELEX
Slide 11
Conjunctions
Slide 12
Auxiliaries
Slide 13
Outline
Why part of speech tagging?
Word classes
Tag sets and problem definition
Automatic approaches 1: rule-based tagging
Automatic approaches 2: stochastic tagging
Automatic approaches 3: transformation-based tagging
Other issues: tagging unknown words, evaluation
Slide 14
Word Classes: Tag Sets
• Vary in number of tags: a dozen to over 200
• Size of tag sets depends on language, objectives and
purpose
– Some tagging approaches (e.g., constraint grammar based) make
fewer distinctions e.g., conflating prepositions, conjunctions,
particles
– Simple morphology = more ambiguity = fewer tags
Slide 15
Word Classes: Tag set example
PRP
PRP$
Slide 16
Example of Penn Treebank Tagging of
Brown Corpus Sentence
The/DT grand/JJ jury/NN commented/VBD on/IN a/DT
number/NN of/IN other/JJ topics/NNS ./.
VB DT NN .
Book that flight .
VBZ DT NN VB NN ?
Does that flight serve dinner ?
See http://www.infogistics.com/posdemo.htm
Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo
Slide 17
The Problem
Words often have more than one word class: this
This is a nice day = PRP
This day is nice = DT
You can go this far = RB
Slide 18
Word Class Ambiguity
(in the Brown Corpus)
Unambiguous (1 tag): 35,340
Ambiguous (2-7 tags): 4,100
2 tags
3,760
3 tags
264
4 tags
61
5 tags
12
6 tags
2
7 tags
1
(Derose, 1988)
Slide 19
Part-of-Speech Tagging
• Rule-Based Tagger: ENGTWOL (ENGlish TWO Level
analysis)
• Stochastic Tagger: HMM-based
• Transformation-Based Tagger (Brill)
Slide 20
Outline
Why part of speech tagging?
Word classes
Tag sets and problem definition
Automatic approaches 1: rule-based tagging
Automatic approaches 2: stochastic tagging
Automatic approaches 3: transformation-based tagging
Other issues: tagging unknown words, evaluation
Slide 21
Rule-Based Tagging
• Basic Idea:
– Assign all possible tags to words
– Remove tags according to set of rules of type: if word+1 is an
adj, adv, or quantifier and the following is a sentence boundary
and word-1 is not a verb like “consider” then eliminate non-adv
else eliminate adv.
– Typically more than 1000 hand-written rules
Slide 22
Sample ENGTWOL Lexicon
Demo: http://www2.lingsoft.fi/cgi-bin/engtwol
Slide 23
Stage 1 of ENGTWOL Tagging
First Stage: Run words through a morphological analyzer to get all
parts of speech.
Example: Pavlov had shown that salivation …
Pavlov
had
shown
that
salivation
PAVLOV N NOM SG PROPER
HAVE V PAST VFIN SVO
HAVE PCP2 SVO
SHOW PCP2 SVOO SVO SV
ADV
PRON DEM SG
DET CENTRAL DEM SG
CS
N NOM SG
Slide 24
Stage 2 of ENGTWOL Tagging
Second Stage: Apply constraints.
Constraints used in negative way.
Example: Adverbial “that” rule
Given input: “that”
If
(+1 A/ADV/QUANT)
(+2 SENT-LIM)
(NOT -1 SVOC/A)
Then eliminate non-ADV tags
Else eliminate ADV
Slide 25
Outline
Why part of speech tagging?
Word classes
Tag sets and problem definition
Automatic approaches 1: rule-based tagging
Automatic approaches 2: stochastic tagging
Automatic approaches 3: transformation-based tagging
Other issues: tagging unknown words, evaluation
Slide 26
Stochastic Tagging
• Based on probability of certain tag occurring given
various possibilities
• Requires a training corpus
• No probabilities for words not in corpus.
• Training corpus may be different from test corpus.
Slide 27
Stochastic Tagging (cont.)
•Simple Method: Choose most frequent tag in training text
for each word!
–
–
–
–
Result: 90% accuracy
Baseline
Others will do better
HMM is an example
Slide 28
HMM Tagger
• Intuition: Pick the most likely tag for this word.
• HMM Taggers choose tag sequence that maximizes this
formula:
– P(word|tag) × P(tag|previous n tags)
• Let T = t1,t2,…,tn
Let W = w1,w2,…,wn
• Find POS tags that generate a sequence of words, i.e.,
look for most probable sequence of tags T underlying the
observed words W.
Slide 29
Start with Bigram-HMM Tagger
argmaxT P(T|W)
argmaxTP(T)P(W|T)
argmaxtP(t1…tn)P(w1…wn|t1…tn)
argmaxt[P(t1)P(t2|t1)…P(tn|tn-1)][P(w1|t1)P(w2|t2)…P(wn|tn)]
To tag a single word: ti = argmaxj P(tj|ti-1)P(wi|tj)
How do we compute P(ti|ti-1)?
c(ti-1ti)/c(ti-1)
How do we compute P(wi|ti)?
c(wi,ti)/c(ti)
How do we compute the most probable tag sequence?
Viterbi
Slide 30
An Example
Secretariat/NNP is/VBZ expected/VBN to/TO race/VB
tomorrow/NN
People/NNS continue/VBP to/TO inquire/VB the DT
reason/NN for/IN the/DT race/NN for/IN outer/JJ
space/NN
to/TO race/???
Slide 31