CS 416 Artificial Intelligence Lecture Lecture 25 25 Hidden Hidden Markov Markov Models Models Chapter Chapter 15 15 Hidden Markov Models An An attempt attempt to to understand understand Markov Markov Processes Processes We We know know the the state state of of the the system system at at an an instant instant state state x 1 x 2 x 1 x 2 x n x n at at times times t 1 t 1 t 2 t 2 t n t n transitions transitions to to new new states states are are only only dependent dependent on on the the current current state state Use Use aa matrix matrix A A to to represent represent transitions transitions the the transitions transitions between between states states are are well well understood understood all all elements elements of of jj are are 0 0 and and 1 1 parameters parameters are are time time independent independent Transition model A A matrix matrix called called A A a i j a i j P P system system in in state state jj system system was was in in state state i i Transition Model Weather Weather Transition Matrix What What ifif states states aren t aren t observable observable b j k b j k Probability Probability k k is is observed observed system system in in state state j j Use Use seaweed seaweed as as an an indicator indicator of of weather weather seaweed seaweed is is dry dry dryish dryish damp damp soggy soggy new new matrix matrix is is What s the hidden part There There is is aa disconnect disconnect between between the the states states you ve you ve created created and and the the true true states states you you are are modeling modeling The The state state of of seaweed seaweed may may or or may may not not be be well well correlated correlated to to tomorrow s tomorrow s weather weather IfIf itit works works itit works works HMM questions given given aa model model and and aa sequence sequence of of observations observations what what is is the the probability probability that that the the model model actually actually generated generated those those observations observations ifif we we had had two two models models lambda 1 lambda 1 pi 1 pi 1 A 1 A 1 B 1 B 1 and and lambda 2 lambda 2 pi 2 pi 2 A 2 A 2 B 2 B 2 which which one one better better describes describes aa sequence sequence of of given given observations observations Can Can we we automatically automatically improve improve aa model model to to better better fit fit observations observations adjust adjust model model parameters parameters lamba lamba pi pi A A B B to to maximize maximize P P O O lambda lambda Speech Recognition Understanding Understanding Spoken Spoken Language Language Input Input is is aa signal signal frequency frequency over over time time Output Output is is aa sequence sequence of of words words HMM for speech Words Words are are made made of of phonemes phonemes Well defined Well defined categorization categorization of of sounds sounds English English has has 45 45 44 phonemes phonemes English English has has 600 600 ways ways to to spell spell these these 45 45 sounds sounds Could Could these these be be the the hidden hidden states states behind behind predicting predicting what what words words are are pronounced pronounced An HMM for each word Build Build aa sequence sequence of of states states that that model model aa transition transition from from saying saying nothing nothing to to saying saying had had your your Segmentation Segmentation is is aa tough tough issue issue silence silence end beginning end beginning of of words words end beginning end beginning of of phonemes phonemes