Fabian M. Suchanek POS-Tagging 40
“Alizée wrote a really great song by herself” 2 Proper Name Verb Determiner Adverb Adjective Noun Preposition Pronoun Part-of-Speech  (also: POS, POS-tag, word class, lexical class, lexical category) is a set of words with the same grammatical role. Def: POS
Part of Speech Part-of-Speech  (also: POS, POS-tag, word class, lexical class, lexical category) is a set of words with the same grammatical role. • Proper nouns (PN): Alizée, Elvis, Obama... • Nouns (N): music, sand, ... • Adjectives (ADJ): fast, funny, ... • Adverbs (ADV): fast, well, ... • Verbs (V): run, jump, dance, ... 3 • Pronouns (PRON): he, she, it, this, ...   (what can replace a noun) • Determiners (DET): the, a, these, your,...   (what goes before a noun) • Prepositions (PREP): in, with, on, ...   (what goes before determiner + noun) • Subordinators (SUB): who, whose, that, which, because...   (what introduces a sub-sentence)
Def: POS-Tagging POS-Tagging  is the process of assigning to each word in a sentence its POS. 4 Alizée sings a wonderful song. PN V DET ADJ N © Ronny Martin Junnilainen Alizée, who has a wonderful voice, sang at the concert in Moscow.
Def: POS-Tagging POS-Tagging  is the process of assigning to each word in a sentence its POS. 5 Alizée sings a wonderful song. PN V DET ADJ N © Ronny Martin Junnilainen Alizée, who has a wonderful voice, sang at the concert in Moscow. PN PN V V ADJ N N DET DET PREP SUB PREP
Probabilistic POS-Tagging Probabilistic POS tagging is an algorithm for automatic POS tagging that works by introducing random variables for words and for POS-tags: 6 Alizée sings PN Adj Verb sings Alizée Prep PN runs Alizée W1 W2 T2 T1 ... ... Probability (visible) (hidden) World Verb
Probabilistic POS-Tagging Given a sentence  we want to find   . 7 sings PN Adj Verb sings Prep PN runs W1 W2 T2 T1 ... ... Probability (visible) (hidden) World Verb Alizée Alizée Alizée
Markov Assumption 1 8 Every word depends just on its tag:
Markov Assumption 1 The probability that the 4th word is “song” depends just on the tag of that word: 9 Every word depends just on its tag:
The probability that the 4th word is “song” depends just on the tag of that word: Markov Assumption 1 10 Every word depends just on its tag: Noun Elvis Verb PN ? sings Det a
The probability that the 4th word is “song” depends just on the tag of that word: Markov Assumption 1 11 Every word depends just on its tag: PN Noun Det sings Elvis Verb a ?
Markov Assumption 2 12 Every tag depends just on its predecessor
Markov Assumption 2 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 13 Every tag depends just on its predecessor
Markov Assumption 2 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 14 Every tag depends just on its predecessor Det PN ? song sings Verb Alizée a
Markov Assumption 2 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 15 Every tag depends just on its predecessor Alizée PN Verb Det ? sings a song
Homogeneity Assumption 1 16 The tag probabilities are the same at all positions
Homogeneity Assumption 1 The probability that a Det is followed by a Noun is the same at position 7 and 2: 17 The tag probabilities are the same at all positions
Homogeneity Assumption 1 The probability that a Det is followed by a Noun is the same at position 7 and 2: Let's denote this probability by 18 The tag probabilities are the same at all positions “Transition probability”
Homogeneity Assumption 2 19 The word probabilities are the same at all positions
Homogeneity Assumption 2 % The probability that a PN is “Elvis” is the same at position 7 and 2: 20 The word probabilities are the same at all positions
The probability that a PN is “Elvis” is the same at position 7 and 2: Homogeneity Assumption 2 % Let's denote this probability by 21 The word probabilities are the same at all positions “Emission probability”
Def: HMM A (homogeneous) Hidden Markov Model (also: HMM) is a sequence of random variables, such that  Emission probabilities Transition probabilities Words of the sentence POS-tags ... with  22
HMMs as graphs Transition probabilities  20% 23 80% End Verb 100% 100% Adj 50% Noun 50% Start
HMMs as graphs Emission probabilities 24 nice sound 50% sound 50% . sounds 100% 50% sounds 50% 50% 50% sound  20% 80% End Verb 100% 100% Adj 50% Noun 50% Start
HMMs as graphs P(nice, sounds, ., Adj, Noun, End) =    50%  *  50%  *  100%  *  50%  *  20%  *  100%  = 2.5% 25 nice sound 50% sound 50% . sounds 100% 50% sounds 50% 50% 50% sound  20% 80% End Verb 100% 100% Adj 50% Noun 50% Start
HMM Question What is the most likely tagging for “sound sounds .” ? 26 nice sound 50% sound 50% . sounds 100% 50% sounds 50% 50% 50% sound  20% 80% End Verb 100% 100% Adj 50% Noun 50% Start
POS tagging with HMMs Adj + Noun: 50%*50%*100%*50%*20%*100% = 2.5% Noun + Verb: 50%*50%*80%*50%*100% = 10% Finding the most likely sequence of tags that generated a sentence is POS tagging (hooray!). 27 What is the most likely tagging for “sound sounds .” ?
Where do we get the HMM? Elvis /PN  sings /Verb Elvis /PN  . /End Priscilla /PN  laughs /Verb Estimate probabilities from manually annotated corpus: 28 ... ... >Viterbi
The HMM as a Trellis Task: compute the probability of every possible path from left to right, find maximum. 29 Start Noun Verb End 50% Adj sound sounds . 0% 50% 0% 50% 50% 80% 100% 50% Noun Verb End Adj 50% 50% 50% Noun Verb End Adj 50% 50% 50%
The HMM as a Trellis Task: compute the probability of every possible path from left to right, find maximum. 30 Start Noun Verb End 50% Adj sound sounds . 0% 50% 0% 50% 50% 80% 100% 50% Noun Verb End Adj 50% 50% 50% Noun Verb End Adj 50% 50% 50% = 10% 50% * 50% •  80% * 50% •  100% * 100%
The HMM as a Trellis 31 Start Noun Verb End 50% Adj sound sounds . 0% 50% 0% 50% 50% 80% 100% 50% Noun Verb End Adj 50% 50% 50% Noun Verb End Adj 50% 50% b 50% * 50% •  80% * 50% •  a * b  a Complexity: 
The HMM as a Trellis 32 Start Noun Verb End 50% Adj sound sounds . 0% 50% 0% 50% 50% 80% 100% 50% Noun Verb End Adj 50% 50% 50% Noun Verb End Adj 50% 50% b 50% * 50% •  80% * 50% •  a * b  a Complexity:  same as before!
The HMM as a Trellis 33 Start Noun Verb End 50% Adj sound sounds . 0% 50% 0% 50% 50% 80% 100% 50% Noun V 10% End Adj 50% 50% 50% Noun Verb End Adj 50% 50% b 50% * 50% •  80% * 50% •  a * b  a Idea: Store at each node the probability of the maximal path that leads there.
Def: Viterbi Algorithm 34 Start Noun Verb End 50% Adj sound sounds 0% 50% 0% 50% 50% 80% 50% Noun V 10% End Adj 50% 50% 50% • For each word    • for each tag      • for each preceding tag        • compute      • store the maximal       probability at 
Viterbi Algorithm 35 Start N 25% V 0% E 0% 50% A 25% sound 0% 50% 0% 50% 50% 50% Start left to right, compute and store probability of arriving here.
Viterbi Algorithm 36 Start N 25% V 0% E 0% 50% A 25% sound 0% 50% 0% 50% 50% 50% Noun 50% Find  prev  that maximizes 25% * 0% * 50% 0% * 0% * 50% 0% * 0% * 50% 25% * 100% * 50% sounds 0% 0% 100% 0%
Viterbi Algorithm 37 Start N 25% V 0% E 0% 50% A 25% sound 0% 50% 0% 50% 50% 50% N 13% 50% Find  prev  that maximizes 25%*0%*50% 0%*0%*50% 0%*0%*50% 25% * 100% * 50% sounds 100%
38 Start 50% sound sounds . 0% 50% 0% 50% 50% 100% 50% V 10% E 0% A 0% 50% 50% 50% N 0% V 0% E 10% A 0% 50% 50% 50% Viterbi Algorithm N 25% V 0% E 0% A 25% N 13% 80% 100% Read best path by following arrows backwards: Start N V E
Def: Probabilistic POS Tagging Given a sentence and transition and emission probabilities, Probabilistic POS Tagging  computes the sequence of tags that has maximal probability (in an HMM).  Elvis sings 39 ... winner >end
Probabilistic POS Tagging • Probabilistic POS tagging uses Hidden Markov Models • General performance very good (>95% acc.) • Several POS taggers are available • Stanford POS tagger • SpaCy.io (open source) • NLTK (Pyhton library) • ... (HMMs and the Viterbi algorithm serve a wide variety of other tasks, in particular NLP at all levels of granularity, e.g., in speech processing) 40 >end
Research Questions How can we deal with • evil cases?         • unknown words? • new languages? • the word “blue” has 4 letters. • pre- and post-secondary • look it up • The Duchess was entertaining last night. [Wikipedia/POS tagging] 41 >end
POS Tagging helps pattern IE We can choose to match the placeholders with only nouns or proper nouns: Atkinson was born in the beautiful Consett. wasBornIn(Atkinson, the) wasBornIn(Atkinson,Consett) 42 “X was born in Y” Atkinson was born in Consett. >end
POS-tags can generalize patterns match 43 Atkinson was born in the beautiful Consett. Atkinson was born in the cold Consett. match “X was born in the ADJ X” >end
Phrase structure is a problem no match Atksinon, a famous actor, was born in Consett. no match 44 “X was born in the ADJ X” Atkinson was born in the very beautiful Consett.
References Daniel Ramage: HMM Fundamentals ”, CS229 Section Notes 45 ->dependency-parsing ->semantic-web ->ie-by-reasoning ->security