CSE 150 Lecture Notes - Lecture 13: Arg Max, Product Rule, Subsequence

HW 5.3

Z z = {1,2,...,k} type of “movie-goer”

/ | \ \

R1R2… R61

Review of Hidden Markov Models (HMMs)

Assumptions

P(St|S1,...,St-1) = P(St|St-1)

| | |

O1O2… OT

Joint Distribution

P(S1,...,ST, O1,...,OT) = P(S1) Πt = 2

T

P(St|St-1) Πt = 1

T

P(Ot|St)

S’ O’

Parameters:

aij = P(St+1 = j|St = i) transition matrix (nxn)

Arg max S’ [P(S1,...,ST|O1,...,OT)] nT possible hidden state sequences

3) How to update beliefs for real time monitoring? How to compute (St = i|O1,...,Ot) ?

4) How to learn HMM from data? How to estimate {πi, aij, bik } from sequences of observations to

maximize P(O1,...,OT) ?

Note: 1-3 are problems in “inference”, 4 is estimating CPTs

1) How to compute likelihood P(O1,...,OT) ?

P(O1,...,OT) = Σs’ P(S1,...,ST,O1,...,OT) [marginalization]

= Σs’ P(S1) Πt = 2

T

= Σi = 1

= Σi = 1