Note to other teachers and users of these slides Andrew would be delighted if you found this source material useful in giving your own lectures Feel free to use these slides verbatim or to modify them to fit your own needs PowerPoint originals are available If you make use of a significant portion of these slides in your own lecture please include this message or the following link to the source repository of Andrew s tutorials http www cs cmu edu awm tutorials Comments and corrections gratefully received Hidden Markov Models Andrew W Moore Professor School of Computer Science Carnegie Mellon University www cs cmu edu awm awm cs cmu edu 412 268 7599 Copyright 2001 2003 Andrew W Moore Nov 29th 2001 A Markov System Has N states called s1 s2 sN s2 s1 There are discrete timesteps t 0 t 1 s3 N 3 t 0 Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 2 A Markov System Has N states called s1 s2 sN s2 Current State s1 N 3 s3 There are discrete timesteps t 0 t 1 On the t th timestep the system is in exactly one of the available states Call it qt Note qt s1 s2 sN t 0 qt q0 s3 Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 3 A Markov System Has N states called s1 s2 sN Current State s2 s1 N 3 t 1 s3 There are discrete timesteps t 0 t 1 On the t th timestep the system is in exactly one of the available states Call it qt Note qt s1 s2 sN Between each timestep the next state is chosen randomly qt q1 s2 Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 4 P qt 1 s1 qt s2 1 2 P qt 1 s2 qt s2 1 2 A Markov System P qt 1 s3 qt s2 0 Has N states called s1 s2 sN P qt 1 s1 qt s1 0 P qt 1 s2 qt s1 0 s2 P qt 1 s3 qt s1 1 s1 s3 N 3 t 1 qt q1 s2 P qt 1 s1 qt s3 1 3 P qt 1 s2 qt s3 2 3 P qt 1 s3 qt s3 0 Copyright 2001 2003 Andrew W Moore There are discrete timesteps t 0 t 1 On the t th timestep the system is in exactly one of the available states Call it qt Note qt s1 s2 sN Between each timestep the next state is chosen randomly The current state determines the probability distribution for the next state Hidden Markov Models Slide 5 P qt 1 s1 qt s2 1 2 P qt 1 s2 qt s2 1 2 A Markov System P qt 1 s3 qt s2 0 Has N states called s1 s2 sN P qt 1 s1 qt s1 0 s2 P qt 1 s2 qt s1 0 1 2 P qt 1 s3 qt s1 1 2 3 1 2 s1 N 3 t 1 qt q1 s2 1 3 s3 1 P qt 1 s1 qt s3 1 3 P qt 1 s2 qt s3 2 3 P qt 1 s3 qt s3 0 Often notated with arcs between states Copyright 2001 2003 Andrew W Moore There are discrete timesteps t 0 t 1 On the t th timestep the system is in exactly one of the available states Call it qt Note qt s1 s2 sN Between each timestep the next state is chosen randomly The current state determines the probability distribution for the next state Hidden Markov Models Slide 6 P qt 1 s1 qt s2 1 2 P qt 1 s2 qt s2 1 2 Markov Property P qt 1 s3 qt s2 0 P qt 1 s1 qt s1 0 s2 P qt 1 s2 qt s1 0 1 2 P qt 1 s3 qt s1 1 2 3 1 2 s1 N 3 t 1 qt q1 s2 1 3 s3 1 qt 1 is conditionally independent of qt 1 qt 2 q1 q0 given qt In other words P qt 1 sj qt si P qt 1 sj qt si any earlier history P qt 1 s1 qt s3 1 3 P qt 1 s2 qt s3 2 3 P qt 1 s3 qt s3 0 Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 7 Markov Property Representation q0 q1 Copyright 2001 2003 Andrew W Moore q2 q3 q4 Hidden Markov Models Slide 8 A Blind Robot A human and a robot wander around randomly on a grid R H STATE q Copyright 2001 2003 Andrew W Moore Location of Robot Location of Human um n N Note 18 s state 24 18 3 Hidden Markov Models Slide 9 Dynamics of System q0 R H Each timestep the human moves randomly to an adjacent cell And Robot also moves randomly to an adjacent cell Typical Questions What s the expected time until the human is crushed like a bug What s the probability that the robot will hit the left wall before it hits the human What s the probability Robot crushes human on next time step Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 10 Example Question It s currently time t and human remains uncrushed What s the probability of crushing occurring at time t 1 If robot is blind We can compute this in advance If robot is omnipotent I E If robot knows state at time t can compute directly If robot has some sensors but incomplete state information We ll do this first Too Easy We won t do this Main Body of Lecture Hidden Markov Models are applicable Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 11 What is P qt s Too Slow Step 1 Work out how to compute P Q for any path Q q0 q1 q2 q3 qt Given we know the start state q0 P q0 q1 qt P q0 q1 qt 1 P qt q0 q1 qt 1 WHY P q0 q1 qt 1 P qt qt 1 P q1 q0 P q2 q1 P qt qt 1 Step 2 Use this knowledge to get P qt s mputation is t l in Co a i t n P qt s ne P Q expo Q Paths of length t that end in s Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 12 What is P qt s Clever Answer For each state si define pt i Prob state is si at time t P qt si Easy to do inductive definition i p0 i j pt 1 j P qt 1 s j Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 13 What is P qt s Clever answer For each state si define pt i Prob state is si at time t P qt si Easy to do inductive definition i 1 if si is the start state p0 i otherwise 0 j pt 1 j P qt 1 s j Copyright 2001 2003 Andrew W Moore Hidden Markov Models Slide 14 What …