The Three Basic Problems for HMms 1)Given the history o=a1, Z1, a2, Z2 aT, ZT, and a model 2=(A, B, I), how do we efficiently compute P(on), the probability of the history, given the model? 2)Given the history O=a1, Z1, a2, Z2,. a, ZT and a model 2. how do we choose a corresponding state sequence X=X,X2,XT e, best""the observations/?se which is optimal in some meaningful sense 3)How do we adjust the model parameters 入=(A.B,) to maximize p(O|入)? HMM Basic Problem 1 Probability of history o given n is sum over all state sequences Q=X1, X2, X3 X, PO|)=∑POQ,PQ|) >I(x)P(=11xP(x21x, a,)P(=21x2)p(x3 1x2, a2) all 91, 92 Summing over all state sequences is 2T.XT Instead build lattice of states forward in time computing probabilities of each possible trajectory as lattice is built Forward algorithm is X2TThe Three Basic Problems for HMMs 1,z1,a2,z2,...,aT,zT, and a model λ=(A,B,π), how do we efficiently compute P(O|λ), the probability of the history, given the model? 1,z1,a2,z2,...,aT,zT and a model λ, how do we choose a corresponding state sequence X=x1,x2,...,xT which is optimal in some meaningful sense (i.e., best “explains” the observations)? λ=(A,B,π) to maximize P(O|λ)? HMM Basic Problem 1 ● Probability of history O given λ is sum over all state sequences Q=x1,x2,x3,...,xT,: ● Summing over all state sequences is 2T⋅|X|T ● Instead, build lattice of states forward in time, computing probabilities of each possible trajectory as lattice is built ● Forward algorithm is |X|2T ∑ ∑ = = ,..., 22322112111 2 )...,|()|(),|()|()( )|(),|()|( Q Q all 1 all π λ λλ 1) Given the history O=a 2) Given the history O=a 3) How do we adjust the model parameters q q a x x p x z p a x x p x z p x O P Q P O P