HMM Basic Problem 1 Probability of history o given n is sum over all state sequences Q=x,, X2, X3 X, PO|A)=∑PO|Q,)P(Q|A allo ∑(x)p(1|x)p(x2|x1,a)p(z2|x2)p(x3|x2,a2 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 X/2T HMM Basic Problem 1 1. nitialization ar(1)=x;p(z1|x) 2. Induction Repeat for t=1: T ()=∑a(0(x1x)m(x1x) 3. Termination: p(O|4)=∑a() Implementation of the computation of a ()in terms of a lattice of observations t, and statesHMM Basic Problem 1 Ɣ Probability of history O given O 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 ¦ ¦ , ,... 1 1 1 2 1 1 2 2 3 2 2 2 ( ) ( | ) ( | , ) ( | ) ( | , )... ( | ) ( | , ) ( | ) Q x x x x a Q all 1 all S O O O HMM Basic Problem 1 ( ) ( | ) 1 i 1 i D i S x ( ) ( ) ( | ) ( | ) 1 | | 1 1 t i X j t t j i a i j x x   » ¼ º « ¬ ª ¦D ¦ | | 1 ( | ) ( ) X i t O D i (j) j. 1 1 2 2 3 T N αt q q p z p x x a p z p x P O P O P Q 1. Initialization 2. Induction: Repeat for t=1:T 3. Termination: p z p x p z p O Implementation of the computation of in terms of a lattice of observations t, and states Observation, t State