HMM Tagging
PA154 Language Modeling (5.2)
Pavel Rychly
pary@fi.muni.cz March 16,2023
Source: Introduction to Natural Language Processing (600.465) Jan Hajic, CS Dept.Johns Hopkins Univ. www.cs.jhu.edu/~hajic
Review
■ Recall:
■ tagging ~ morphological disambiguation
■ tagset Vj c (Q, C2,... Cn)
■ C, - morphological categories, such as POS, NUMBER, CASE, PERSON, TENSE, GENDER,...
■ mapping w —>► {t e Vj] exists
■ restriction of Morphological Analysis: A+    2(LC2C2' Cn) where A is the language alphabet, L is the set of lemmas
■ extension of punctuation, sentence boundaries (treated as words)
Pavel Rychly • HMM Tagging • March 16,2023
2/12
The Setting
Noisy Channel setting:
Input (tags)
NNP VBZDT.
The channel
(adds "noise")
Output (words)
John drinks the..
Goal (as usual): discover "input" to the channel (T,the tag seq.) given the "output" (W, the word sequence)
■ p{T\W) = p{W\T)p{T)/p{W)
■ p(W) fixed (W given)... argmaxTp(T\W) = argmaxTp(W\T)p(T)
Pavel Rychly • HMM Tagging • March 16,2023
3/12
The Model
Two models (d = \ W\ = |7"| word sequence Length):
■ p{W\T) = n/=1...cyp(^/|^1, . . . ti, ... ,£</)
■ p(t) = n/=i...£/p(t/|tiJ..., t/_i)
Too much parameters (as always) Approximation using the following assumptions:
■ words do not depend on the context
■ tag depends on limited history:
p(f/|fl,. . . , £/_i) = p(£/|£/_„+i,..., f/_i) ■ n-gram tag "Language" model
■ word depends on tag only: p(wi\w1,..., W/_i, fi,..., U) = p(w/|f/)
Pavel Rychly • HMM Tagging • March 16,2023
4/12
The HMM Model Definition
■ (Almost) general HMM:
■ output (words) emitted by states (not arcs)
■ states: (n-l)-tuples of tags if n-gram tag model used
■ five-tuple (S, s0, /, Ps, Py) where:
■ 5 = {s0,si,... ,sr} is the set of states, s0 is the initial state, m Y = {yi,/2,...,»} is the output alphabet (the words),
■ Ps{Sj\si) is the set of prob. distributions of transitions
~Ps(s/|S/) = p(£/|£/_n+i,..., £/-i); Sj = (t/_n+2, • • •, t/)? =
(t/ —A7+1 j • • • 5 f/'-l)
■ Pr(y/f|5/) is the set of output (emission) probability distributions
-another simplification: Py(yk\Sj) if s, and sy contain the same tag as the rightmost element: Py(yk\Sj) = p(w/|t/)
Pavel Rychly • HMM Tagging • March 16,2023
5/12
Supervised Learning (Manually Annotated Data Available)
Use MLE
■ p(Wj\tj) = C^(f/,^/)/Q(f/)
Q/7(f/-/7+lj • • • 5 f/'-lj f/)/Q(/7-l)(f/-/7+lj • • • 5 f/'-l)
Smooth(bothl)
■ p(wj\tj) : "Add l"for all possible tag, word pairs using a predefined dictionary (thus some 0 kept!)
■ p(£,-|£/_„+i,..., t/_i) : linear interpolation:
■ e.g. for trigram model:
p'x(ti\ti-2, t/-i) = A3p(t/|t/-2, f/-i) + A2p(t/|t/-i) + Aip(t/) + A0/| W|
Pavel Rychly • HMM Tagging • March 16,2023
6/12
Unsupervised Learning
■ Completely unsupervised Learning impossible
■ at least if we have the tagset given- how would we associate words with tags?
■ Assumed (minimal) setting:
■ tagset known
■ dictionary/morph. analysis available (providing possible tags for any word)
■ Use: Baum-Welch algorithm (see Lecture 5.1)
■ "tying": output (state-emitting only, same dist. from two states with same "final" tag)
Pavel Rychly • HMM Tagging • March 16,2023
7/12
Comments on Unsupervised Learning
■ Initialization of Baum-WeLch
■ is some annotated data available, use them
■ keep 0 for impossible output probabilities
■ Beware of:
■ degradation of accuracy (Baum-Welch criterion: entropy, not accuracy!)
■ use heldout data for cross-checking
■ Supervised almost always better
Pavel Rychly • HMM Tagging • March 16,2023
8/12
Unknown Words
■ "00V" words (out-of-vocabuLary)
■ we do not have list of possible tags for them
■ and we certainly have no output probabilities
■ Solutions:
■ try all tags (uniform distribution)
■ try open-class tags (uniform, unigram distribution)
■ try to "guess" possible tags (based on suffix/ending) - use different output distribution based on the ending (and/or other factors, such as capitalization)
Pavel Rychly • HMM Tagging • March 16,2023
9/12
Running the Tagger
■ Use Viterbi
■ remember to handle unknown words
■ single-best, n-best possible
■ Another option
■ assign always the best tag at each word, but consider all possibilities for previous tags (no back pointers nor a path-backpass)
■ introduces random errors, implausible sequences, but might get higher accuracy (less secondary errors)
Pavel Rychly • HMM Tagging • March 16,2023
10/12
(Tagger) Evaluation
■ A must. Test data (S), previously unseen (in training)
■ change test data often if at all possible! ("feedback cheating")
■ Error-rate based
■ Formally:
■ Out(w) = set of output "items" for an input "item" w
■ True(w) = single correct output (annotation) for w
■ Errors(S) = J2i=i \s\ $ (Out(w,) ^ True(w/))
■ Correct(S) = J2i=i \s\ $ (True(w,) e Out(w,))
■ Generated(S) = J2i=i \s\ 5|0ut(w/)|
Pavel Rychly • HMM Tagging • March 16,2023
11/12
Evaluation Metrics
■ Accuracy: Single output (tagging: each word gets a single tag)
■ Error rate: Err(S) = Errors(S)/|S|
■ Accuracy: Acc(S) = l-(Errors(S)/|S|) = 1- Err(S)
■ What if multiple (or no) output?
■ Recall: R(S) = Correct(S)/|S|
■ Precision: P(S) = Correct(S)/Generated(S)
■ Combination: F measure: F = XjiajP + (1 - a)/R)
■ a is a weight given to precision vs. recall; for
a = .5,F = 2PR/{R + P)
Pavel Rychly • HMM Tagging • March 16,2023
12/12