Decoding: Best State Sequence O T Find the state sequence that best explains the observations Viterbi algorithm arg max P(XO) X 26
26 o1 ot-1 ot ot+1 oT Decoding: Best State Sequence • Find the state sequence that best explains the observations • Viterbi algorithm • arg max P(X | O) X
Ⅴ viterbi Algorithn t-1 O T 6()=maxP(x…x1,01.O1,x=j,) The state sequence which maximizes the probability of seeing the observations to time t-1, landing in state j, and seeing the observation at time t
27 o1 ot-1 ot ot+1 oT Viterbi Algorithm ( ) max ( ... , ... , , ) 1 1 1 1 ... 1 1 t t t t x x j t P x x o o x j o t = − − = − The state sequence which maximizes the probability of seeing the observations to time t-1, landing in state j, and seeing the observation at time t x1 xt-1 j
Ⅴ viterbi Algorithn t-1 x O T 6()=mxP(x…x11,O1.O1,x1=j,02) 6(+1)=max(b Recursive C y, (t+D)=arg max 0i(ta, bjo omputation 28
28 o1 ot-1 ot ot+1 oT Viterbi Algorithm ( ) max ( ... , ... , , ) 1 1 1 1 ... 1 1 t t t t x x j t P x x o o x j o t = − − = − 1 ( 1) max ( ) + + = t i i j j o i j t t a b 1 ( 1) arg max ( ) + + = t i i j j o i j t t a b Recursive Computation x1 xt-1 xt xt+1
Ⅴ viterbi Algorithn t-1 x T O T XT=arg max S, (T) Compute the most X1=V、(+1) likely state sequence by working backwards Xt+ P(X)=arg max S, T)
29 o1 ot-1 ot ot+1 oT Viterbi Algorithm arg max ( ) Xˆ i T i T = ( 1) ˆ 1 = ^ + + X t X t t ) arg max ( ) ˆ P(X i T i = Compute the most likely state sequence by working backwards x1 xt-1 xt xt+1 xT
Parameter estimation B B B B Given an observation sequence, find the model that is most likely to produce that sequence No analytic method=> an EM algorithm Baum-Welch) Given a model and observation sequence update the model parameters to better fit the observations
30 o1 ot-1 ot ot+1 oT Parameter Estimation • Given an observation sequence, find the model that is most likely to produce that sequence. • No analytic method => an EM algorithm (Baum-Welch) • Given a model and observation sequence, update the model parameters to better fit the observations. A B A A A B B B B