This document introduces hidden Markov models (HMMs) and discusses three main problems in HMMs: evaluation, decoding, and learning.
The evaluation problem involves computing the probability of an observed sequence given the HMM parameters. The forward algorithm solves this problem recursively in linear time.
The decoding problem involves either finding the most likely hidden state at a time or the most likely full state sequence. The forward-backward and Viterbi algorithms solve these problems respectively in linear time.
The learning problem involves estimating HMM parameters to maximize the likelihood of observed data. The EM algorithm iteratively solves this by doing expectation and maximization steps in linear time.
This document introduces hidden Markov models (HMMs) and discusses three main problems in HMMs: evaluation, decoding, and learning.
The evaluation problem involves computing the probability of an observed sequence given the HMM parameters. The forward algorithm solves this problem recursively in linear time.
The decoding problem involves either finding the most likely hidden state at a time or the most likely full state sequence. The forward-backward and Viterbi algorithms solve these problems respectively in linear time.
The learning problem involves estimating HMM parameters to maximize the likelihood of observed data. The EM algorithm iteratively solves this by doing expectation and maximization steps in linear time.
This document introduces hidden Markov models (HMMs) and discusses three main problems in HMMs: evaluation, decoding, and learning.
The evaluation problem involves computing the probability of an observed sequence given the HMM parameters. The forward algorithm solves this problem recursively in linear time.
The decoding problem involves either finding the most likely hidden state at a time or the most likely full state sequence. The forward-backward and Viterbi algorithms solve these problems respectively in linear time.
The learning problem involves estimating HMM parameters to maximize the likelihood of observed data. The EM algorithm iteratively solves this by doing expectation and maximization steps in linear time.
This document introduces hidden Markov models (HMMs) and discusses three main problems in HMMs: evaluation, decoding, and learning.
The evaluation problem involves computing the probability of an observed sequence given the HMM parameters. The forward algorithm solves this problem recursively in linear time.
The decoding problem involves either finding the most likely hidden state at a time or the most likely full state sequence. The forward-backward and Viterbi algorithms solve these problems respectively in linear time.
The learning problem involves estimating HMM parameters to maximize the likelihood of observed data. The EM algorithm iteratively solves this by doing expectation and maximization steps in linear time.
• Decoding – Given HMM parameters & observation seqn
find most probable sequence of hidden states
• Learning – Given HMM with unknown parameters and
observation sequence find parameters that maximize likelihood of observed data 13 HMM Algorithms
• Evaluation – What is the probability of the observed
sequence? Forward Algorithm
• Decoding – What is the probability that the third roll was
loaded given the observed sequence? Forward-Backward Algorithm – What is the most likely die sequence given the observed sequence? Viterbi Algorithm
• Learning – Under what parameterization is the observed
sequence most probable? Baum-Welch Algorithm (EM) 14 Evaluation Problem • Given HMM parameters & observation sequence S1 S2 ST-1 ST find probability of observed sequence O1 O2 OT-1 OT
requires summing over all possible hidden state values at all
times – KT exponential # terms! Instead:
αkT Compute recursively 15
Forward Probability
Compute forward probability αkt recursively over t
16 Forward Algorithm Can compute αtk for all k, t using dynamic programming:
• Initialize: α1k = p(O1|S1 = k) p(S1 = k) for all k
• Iterate: for t = 2, …, T αtk = p(Ot|St = k) ∑ αit-1 p(St = k|St-1 = i) for all k i
• Termination: = ∑ αkT k
17 Decoding Problem 1 • Given HMM parameters & observation sequence find probability that hidden state at time t was k
Compute recursively αkt βtk
S1 St-1 St St+1 ST-1 ST
O1 Ot-1 Ot Ot+1 OT-1 OT
18 Backward Probability
Compute forward probability βtk recursively over t
St St+1 St+2 ST
Ot Ot+1 Ot+2 OT Introduce St+1 . . Chain rule . Markov assumption
19 Backward Algorithm Can compute βtk for all k, t using dynamic programming:
• Initialize: βTk = 1 for all k
• Iterate: for t = T-1, …, 1
for all k
• Termination:
20 Most likely state vs. Most likely sequence Most likely state assignment at time t
E.g. Which die was most likely used by the casino in the third roll given the observed sequence?
Most likely assignment of state sequence
E.g. What was the most likely sequence of die rolls used by the casino given the observed sequence? MLA of x? Not the same solution ! MLA of (x,y)? 21 Decoding Problem 2 • Given HMM parameters & observation sequence find most likely assignment of state sequence
VkT Compute recursively VkT - probability of most likely sequence of states ending at state ST = k 22 Viterbi Decoding
Compute probability Vkt recursively over t
S1 St-1 St . Bayes rule . Ot-1 Markov assumption O1 Ot .
23 Viterbi Algorithm Can compute Vtk for all k, t using dynamic programming:
• Initialize: V1k = p(O1|S1=k)p(S1 = k) for all k
• Iterate: for t = 2, …, T for all k
• Termination:
Traceback:
24 Computational complexity • What is the running time for Forward, Backward, Viterbi?
O(K2T) linear in T instead of O(KT) exponential in T!
25 Learning Problem • Given HMM with unknown parameters and observation sequence find parameters that maximize likelihood of observed data But likelihood doesn’t factorize since observations not i.i.d.
hidden variables – state sequence
EM (Baum-Welch) Algorithm: E-step – Fix parameters, find expected state assignments M-step – Fix expected state assignments, update parameters
26 Baum-Welch (EM) Algorithm • Start with random initialization of parameters • E-step – Fix parameters, find expected state assignments
Forward-Backward algorithm
27 Baum-Welch (EM) Algorithm • Start with random initialization of parameters • E-step = expected # times in state i -1 = expected # transitions from state i
= expected # transitions from state i to j • M-step
28 Some connections • HMM vs Linear Dynamical Systems (Kalman Filters)
HMM: States are Discrete
Observations Discrete or Continuous
Linear Dynamical Systems: Observations and States are multi-
variate Gaussians whose means are linear functions of their parent states (see Bishop: Sec 13.3)
29 HMMs.. What you should know • Useful for modeling sequential data with few parameters using discrete hidden states that satisfy Markov assumption • Representation - initial prob, transition prob, emission prob, State space representation • Algorithms for inference and learning in HMMs – Computing marginal likelihood of the observed sequence: forward algorithm – Predicting a single hidden state: forward-backward – Predicting an entire sequence of hidden states: viterbi – Learning HMM parameters: an EM algorithm known as Baum- Welch
