Hidden Markov Models Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 1 Chains Introduction to probabilities
Hidden Markov Models Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 2 Chains Introduction to probabilities
3 Elvis sings PN Adj Verb sings Elvis Prep PN runs Elvis W1 W2 T2 T1 ... ... Probability (visible) (hidden) World Verb Usually, we observe the visible variables (here: the sentence) over time and we want to determine the hidden variables (here: the POS tags) over time. A HMM universe has “visible” and “hidden” random variables, with a set of “hidden” and “visible” values: Hidden Markov Models
Probabilistic POS-Tagging Given a sentence  we want to find   . 4 Elvis sings PN Adj Verb sings Elvis Prep PN runs Elvis W1 W2 T2 T1 ... ... Probability (visible) (hidden) World Verb
Markov Assumption 1 5 Every tag depends just on its predecessor
Markov Assumption 1 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 6 Every tag depends just on its predecessor
Markov Assumption 1 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 7 Every tag depends just on its predecessor Elvis Det PN ? song sings Verb Elvis a
Markov Assumption 1 The probability that PN, V, D is followed by a noun is the same as the probability that D is followed by a noun: 8 Every tag depends just on its predecessor Elvis PN Verb Det ? sings a song
Markov Assumption 2 9 Every word depends just on its tag:
Markov Assumption 2 The probability that the 4th word is “song” depends just on the tag of that word: 10 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 2 11 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 2 12 Every word depends just on its tag: PN Noun Det sings Elvis Verb a ?
Homogeneity Assumption 1 13 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: 14 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 15 The tag probabilities are the same at all positions “Transition probability”
Homogeneity Assumption 2 16 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: 17 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 18 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  19
HMMs as graphs Transition probabilities  20%   20 80% End Verb 100% 100% Adj 50% Noun 50% Start
HMMs as graphs Emission probabilities 21 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% 22 nice sound 50% sound 50% . sounds 100% 50% sounds 50% 50% 50% sound  20% 80% End Verb 100% 100% Adj 50% Noun 50% Start
Main questions: • Given   and  ,   what is the probability of a sentence with tags • Given   and  ,   what is the most likely sequence of    that generated a sentence • What are the    HMM questions 23