Introduction to Hidden Markov Models

1 Introduction to Hidden Markov ModelsAlperen DegirmenciThis document contains derivations and algorithms for im-plementing Hidden Markov Models . The content presentedhere is a collection of my notes and personal insights fromtwo seminal papers on HMMs by Rabiner in 1989 [2] andGhahramani in 2001 [1], and also from Kevin Murphy s book[3]. This is an excerpt from my project report for the Machine Learning class taught in Fall HIDDENMARKOVMODELS(HMMS)HMMs have been widely used in many applications, suchas speech recognition, activity recognition from video, genefinding, gesture tracking. In this section, we will explain whatHMMs are, how they are used for machine learning, theiradvantages and disadvantages, and how we implemented ourown HMM DefinitionA Hidden Markov model is a tool for representing prob-ability distributions over sequences of observations [1]. Inthis model, an observationXtat timetis produced by astochastic process, but the stateZtof this process cannot bedirectly observed, it ishidden[2].

2 This Hidden processis assumed to satisfy the Markov property, where stateZtattimetdepends only on the previous state,Zt 1at timet is, in fact, called the first-order Markov model. Thenth-order Markov model depends on thenprevious states. Fig. 1shows a Bayesian network representing the first-order HMM,where the Hidden states are shaded in should note that even though we talk about time to indicate that observations occur at discrete time steps , time could also refer to locations within a sequence [3].The joint distribution of a sequence of states and observa-tions for the first-order HMM can be written as,P(Z1:N,X1:N) =P(Z1)P(X1|Z1)N t=2P(Zt|Zt 1)P(Xt|Zt)(1)where the notationZ1:Nis used as a shorthand forZ1,..,ZN. Notice that Eq. 1 can be also written as,P(X1:N,Z1:N) =P(Z1)N t=2P(Zt|Zt 1)N t=1P(Xt|Zt)(2)which is same as the expression given in the lecture are five elements that characterize a Hidden Markovmodel:The author is with the School of Engineering and This document is an excerptfrom a project report for the MIT Machine Learning class taught inFall Bayesian network representing a first-order HMM.

3 The hiddenstates are shaded in ) Number of states in the model,K:This is the numberof states that the underlying Hidden Markov process states often have some relation to the phenomena beingmodeled. For example, if a HMM is being used for gesturerecognition, each state may be a different gesture, or a partof the gesture. States are represented as integers1,.., will encode the stateZtat timetas aK 1vector ofbinary numbers, where the only non-zero element is thek-thelement ( 1), corresponding to statek Kat timet. While this may seem contrived, it will later on help us inour computations. (Note that [2] usesNinstead ofK).2) Number of distinct observations, :Observations arerepresented as integers1,.., . We will encode the observa-tionXtat timetas a 1vector of binary numbers, wherethe only non-zero element is thel-th element ( 1),corresponding to statel at timet. While this may seemcontrived, it will later on help us in our computations. (Notethat [2] usesMinstead of , and [1] usesD.

4 We decidedto use since this agrees with the lecture notes).3) State transition model,A:Also called the state transi-tion probability distribution [2] or the transition matrix [3],this is aK Kmatrix whose elementsAijdescribe theprobability of transitioning from stateZt 1,itoZt,jin onetime step wherei,j {1,..,K}. This can be written as,Aij=P(Zt,j= 1|Zt 1,i= 1).(3)Each row ofAsums to 1, jAij= 1, and therefore it iscalled a stochastic matrix. If any state can reach any otherstate in a single step (fully-connected), thenAij>0for121- 1- 1A1123A22A33A12A21A23A32(a)(b)Fig. 2. A state transition diagram for (a) a 2-state, and (b) a 3-state ergodicMarkov chain. For a chain to be ergodic, any state should be reachable fromany other state in a finite amount of 2014 Alperen Degirmencialli,j; otherwiseAwill have some zero-valued 2 shows two state transition diagrams for a 2-state and3-state first-order Markov chain. For these diagrams, the statetransition Models are,A(a)=[1 1 ],A(b)= A11A120A21A22A230A32A33.

5 (4)The conditional probability can be written asP(Zt|Zt 1) =K i=1K j=1 AZt 1,iZt,jij.(5)Taking the logarithm, we can write this aslogP(Zt|Zt 1) =K i=1K j=1Zt 1,iZt,jlogAij(6)=Z>tlog (A)Zt 1.(7)4) Observation model,B:Also called the emission prob-abilities,Bis a Kmatrix whose elementsBkjdescribethe probability of making observationXt,kgiven stateZt, can be written as,Bkj=P(Xt=k|Zt=j).(8)The conditional probability can be written asP(Xt|Zt) =K j=1 k=1 BZt,jXt,kkj.(9)Taking the logarithm, we can write this aslogP(Xt|Zt) =K j=1 k=1Zt,jXt,klogBkj(10)=X>tlog (B)Zt.(11)5) Initial state distribution, :This is aK 1vectorof probabilities i=P(Z1i=1). The conditional probabilitycan be written as,P(Z1| ) =K i=1 Z1ii.(12)Given these five parameters presented above, an HMMcan be completely specified. In literature, this often getsabbreviated as = (A,B, ).(13)B. Three Problems of InterestIn [2] Rabiner states that for the HMM to be useful inreal-world applications, the following three problems mustbe solved: Problem 1:Given observationsX1.

6 ,XNand amodel = (A,B, ), how do we efficiently computeP(X1:N| ), the probability of the observations giventhe model? This is a part of theexact inferenceproblempresented in the lecture notes, and can be solved usingforward Zt-1,Zt Zt,Zt+1 Xt,ZtZt+1Xt ZtZt-1 ,Zt Zt Zt ,Zt+1 Zt+1Zt ,Zt+1 ZtXt ,Zt Xt Xt ,Zt ZtZt ,Zt+1 Zt Zt-1 ,Zt Zt+1 Zt-1 ,Zt Zt Xt ,Zt XtXt ,ZtFig. graph for a slice of the HMM at timet. Problem 2:Given observationsX1,..,XNand themodel , how do we find the correct Hidden statesequenceZ1,..,ZNthat best explains the observa-tions? This corresponds to finding the most probablesequence of Hidden states from the lecture notes, andcan be solved using the Viterbi algorithm. A relatedproblem is calculating the probability of being in stateZtkgiven the observations,P(Zt=k|X1:N), whichcan be calculated using the forward-backward algo-rithm. Problem 3:How do we adjust the model parameters =(A,B, )to maximizeP(X1:N| )?

7 This correspondsto the learning problem presented in the lecture notes,and can be solved using the Expectation-Maximization(EM) algorithm (in the case of HMMs, this is called theBaum-Welch algorithm).C. The Forward-Backward AlgorithmThe forward-backward algorithm is a dynamic program-ming algorithm that makes use of message passing (be-lief propagation). It allows us to compute the filtered andsmoothed marginals, which can be then used to performinference, MAP estimation, sequence classification, anomalydetection, and model-based clustering. We will follow thederivation presented in Murphy [3].1) The Forward Algorithm:In this part , we computethe filtered marginals,P(Zt|X1:T)using thepredict-updatecycle. The prediction step calculates theone-step-aheadpredictive density,P(Zt=j|X1:t 1) = K i=1=P(Zt=j|Zt 1=i)P(Zt 1=i|X1:t 1)(14)which acts as the new prior for timet. In the update state,the observed data from timetis absorbed using Bayes rule: t(j),P(Zt=j|X1:t)=P(Zt=j|Xt,X1:t 1)=P(Xt|Zt=j, X1:t 1)P(Zt=j|X1:t 1) jP(Xt|Zt=j, X1:t 1)P(Zt=j|X1:t 1)=1 CtP(Xt|Zt=j)P(Zt=j|X1:t 1)(15)2c 2014 Alperen DegirmenciAlgorithm 1 Forward algorithm1:Input:A, 1:N, 2:[ 1,C1] = normalize( 1 );3:fort= 2 :Ndo4:[ t,Ct] = normalize( t (A> t 1));5:Return 1:NandlogP(X1:N) = tlogCt6:Sub: [ ,C] = normalize(u):C= juj; j=uj/C;where the observationsX1:t 1cancel out because they the normalization constant (toavoid confusion, we usedCtas opposed toZtfrom [3])given by,Ct,P(Xt|X1:t 1) =K j=1=P(Xt|Zt=j)P(Zt=j|X1:t 1).

8 (16)TheK 1vector t=P(Zt|X1:T)is called the (filtered)belief stateat matrix notation, we can write the recursive update as: t t (A> t 1)(17)where t= [ t1, t2,.., tK] ={P(Xt|Zt=i)}1 i Kisthe local evidence at timetwhich can be calculated usingEq. 9,Ais the transition matrix, and is the Hadamardproduct, representing elementwise vector multiplication. Thepseudo-code in Algorithm 1 outlines the steps of the of the evidence can be computed aslogP(X1:N| ) =N t=1logP(Xt|X1:t 1) =N t=1logCt(18)This, in fact, is the solution forProblem 1stated by Rabiner[2]. Working in thelogdomain allows us to avoid numericalunderflow during ) The Forward-Backward Algorithm:Now that we havethe filtered belief states from the forward messages, wecan compute the backward messages to get the smoothedmarginals:P(Zt=j|X1:N) P(Zt= +1:N|X1:t)(19) P(Zt=j|X1:t)P(Xt+1:N|Zt=j, X1:t).which is the probability of being in stateZtj. Given that thehidden state at timetisj, define the conditional likelihoodof future evidence as t(j),P(Xt+1:N|Zt=j).

9 (20)Also define the desired smoothed posterior marginal as t(j),P(Zt=j|X1:N).(21)Then we can rewrite Eq. 19 as t(j) t(j) t(j)(22)We can now compute the s recursively from right to left:Algorithm 2 Backward algorithm1:Input:A, 1:N, 2: N= 1;3:fort=N 1 : 1do4: t=normalize(A( t+1 t+1);5: =normalize( ,1)6:Return 1:N t 1(i) =P(Xt:N|Zt 1=i)= jP(Zt=j,Xt,Xt+1:N|Zt 1=i)= jP(Xt+1:N|Zt=j, Xt, Zt 1=j) P(Zt=j,Xt|Zt 1=i)= jP(Xt+1:N|Zt=j)P(Xt|Zt=j, Zt 1=i) P(Zt=j|Zt 1=i)= j t(j) t(j)A(i,j)(23)This can be written as t 1=A( t t)(24)The base case for Nis N(i) =P(XN+1:N|ZN=i) =P( |ZN=i) = 1(25)Finally, the smoothed posterior is then i= i i j( i(j) i(j))(26)where the denominator ensures that each column of sumsto 1 to ensure it is a stochastic matrix. The pseudo-code inAlgorithm 2 outlines the steps of the The Viterbi AlgorithmIn order to compute the most probable sequence of hiddenstates (Problem 2), we will use the Viterbi algorithm. Thisalgorithm computes the shortest path through the trellisdiagram of the HMM.)

10 The trellis diagram shows how eachstate in the model at one time step connects to the statesin the next time step. In this section, we again follow thederivation presented in Murphy [3].The Viterbi algorithm also has a forward and backwardpass. In the forward pass, instead of the sum-product algo-rithm, we utilize the max-product algorithm. The backwardpass recovers the most probable path through the trellisdiagram using a traceback procedure, propagating the mostlikelystateat timetback in time to recursively find the mostlikelysequencebetween times1 :t. This can be expressedas, t(j),maxZ1,..,Zt 1P(Z1:t 1,Zt=j|X1:t).(27)This probability can be expressed as a combination of thetransition from the previous stateiat timet 1and the most3c 2014 Alperen DegirmenciAlgorithm 3 Viterbi algorithm1:Input:X1:N,K,A,B, 2:Initialize: 1= BX1,a1=0;3:fort= 2 :Ndo4:forj= 1 :Kdo5:[at(j), t(j)] =maxi(log t 1(:) + logAij+logBXt(j));6:Z N= arg max( N);7:fort=N 1 : 1do8:Z t=at+1Z t+1;9:ReturnZ 1:Nprobable path leading toi, t(j) = max1 i K t 1(i)AijBXt(j).