A Revealing Introduction to Hidden Markov Models

1 A Revealing Introduction to Hidden Markov ModelsMark Stamp Department of Computer ScienceSan Jose State UniversityOctober 17, 20181 A simple exampleSuppose we want to determine the average annual temperature at a particular location onearth over a series of years. To make it interesting, suppose the years we are concerned withlie in the distant past, before thermometers were invented. Since we can t go back in time,we instead look for indirect evidence of the simplify the problem, we only consider two annual temperatures, hot and cold .Suppose that modern evidence indicates that the probability of a hot year followed by anotherhot year is and the probability that a cold year is followed by another cold year is ll assume that these probabilities held in the distant past as well.

2 The information sofar can be summarized asH CHC[ ](1)whereHis hot andCis cold .Also suppose that current research indicates a correlation between the size of tree growthrings and temperature. For simplicity, we only consider three different tree ring sizes, small,medium and large, orS,MandL, respectively. Finally, suppose that based on availableevidence, the probabilistic relationship between annual temperature and tree ring sizes isgiven byS M LHC[ ].(2) Email: This tutorial was originally published online in 2004. Minor correctionsand additions have been made over time, with new (and improved!) exercises added. This current versionis suspiciously similar to Chapter 2 of my book, Introduction to Machine Learning with Applications inInformation Security[5].

3 1 For this system, thestateis the average annual temperature eitherHorC. The tran-sition from one state to the next is aMarkov process(of order one1), since the next statedepends only on the current state and the fixed probabilities in (1). However, the actualstates are Hidden since we can t directly observe the temperature in the we can t observe the state (temperature) in the past, we can observe the sizeof tree rings. From (2), tree rings provide us with probabilistic information regarding thetemperature. Since the states are Hidden , this type of system is known as aHidden MarkovModel(HMM). Our goal is to make effective and efficient use of the observable informationso as to gain insight into various aspects of the Markov state transition matrixA=[ ](3)comes from (1) and the observation matrixB=[ ].

4 (4)is from (2). In this example, suppose that the initial state distribution, denoted by , is =[ ].(5)The matrices ,AandBarerow stochastic, meaning that each element is a probability andthe elements of each row sum to 1, that is, each row is a probability consider a particular four-year period of interest from the distant past, for whichwe observe the series of tree ringsS,M,S,L. Letting 0 representS, 1 representMand 2representL, this observation sequence isO= (0,1,0,2).(6)We might want to determine the most likely state sequence of the Markov process giventhe observations (6). That is, we might want to know the most likely average annual temper-atures over the four-year period of interest.

5 This is not quite as clear-cut as it seems, sincethere are different possible interpretations of most likely. On the one hand, we could rea-sonably define most likely as the state sequence with the highest probability from amongall possible state sequences of length four. Dynamic programming (DP) can be used to effi-ciently finds this particular solution. On the other hand, we might reasonably define mostlikely as the state sequence that maximizes the expected number of correct states. HMMscan be used to find this DP solution and the HMM solution are not necessarily the same. For example, theDP solution must have valid state transitions, while this is not necessarily the case for theHMMs.

6 And even if all state transitions are valid, the HMM solution can still differ fromthe DP solution as illustrated in the example , we present one of the most challenging aspects of HMMs, namely, the we discuss the three fundamental problems related to HMMs and give algorithms1A Markov process of order two would depend on the two preceding states, a Markov process of orderthree would depend on the three preceding states, and so on. In any case, the memory is their efficient solutions. We also consider some critical computational issue that mustbe addressed when writing any HMM computer program. We conclude with a substantialexample that does not require any specialized knowledge, yet nicely illustrates the strengthof the HMM approach.

7 Rabiner [3] is the best source for further introductory informationon NotationLetT= length of the observation sequenceN= number of states in the modelM= number of observation symbolsQ={q0,q1,..,qN 1}= distinct states of the Markov processV={0,1,..,M 1}= set of possible observationsA= state transition probabilitiesB= observation probability matrix = initial state distributionO= (O0,O1,..,OT 1) = observation observations are always denoted by{0,1,..,M 1}, since this simplifies the notationwith no loss of generality. That is,Oi Vfori= 0,1,..,T generic Hidden Markov model is illustrated in Figure 1, where theXirepresent thehidden state sequence and all other notation is as given above.

8 The Markov process whichis Hidden behind the dashed line is determined by the current state and are only able to observe theOi, which are related to the ( Hidden ) states of the Markovprocess by the process:X0X1X2 XT 1-A-A-A-A?B?B?B?BObservations:O0O1O2 OT 1 Figure 1: Hidden Markov ModelFor the temperature example of the previous section with the observations sequencegiven in (6) we haveT= 4,N= 2,M= 3,Q={H,C},V={0,1,2}(where welet 0,1,2 represent small , medium and large tree rings, respectively). In this case, thematricesA,Band are given by (3), (4) and (5), matrixA={aij}isN Nwithaij=P(stateqjatt+ 1|stateqiatt)3andAis row stochastic. Note that the probabilitiesaijare independent oft.

9 The matrixB={bj(k)}is anN Mwithbj(k) =P(observationkatt|stateqjatt).As withA, the matrixBis row stochastic and the probabilitiesbj(k) are independent unusual notationbj(k) is standard in the HMM HMM is defined byA,Band (and, implicitly, by the dimensionsNandM). TheHMM is denoted by = (A,B, ).Consider a generic state sequence of length fourX= (x0,x1,x2,x3)with corresponding observationsO= (O0,O1,O2,O3).Then x0is the probability of starting in statex0. Also,bx0(O0) is the probability of initiallyobservingO0andax0,x1is the probability of transiting from statex0to statex1. Continuing,we see that the probability of the state sequenceXis given byP(X,O) = x0bx0(O0)ax0,x1bx1(O1)ax1,x2bx2(O2)ax2,x 3bx3(O3).

10 (7)Consider again the temperature example in Section 1 with observation sequenceO=(0,1,0,2), as given in (6). Using (7) we can compute, say,P(HHCC) = ( )( )( )( )( )( )( ) = , we can directly compute the probability of each possible state sequence of lengthfour, assuming the given observation sequence (6). We have listed these results in Table 1,where the probabilities in the last column are normalized so that they sum to find the optimal state sequence in the dynamic programming (DP) sense, we simplychoose the sequence with the highest probability, namely,CCCH. To find the optimalsequence in the HMM sense, we choose the most probable symbol at each position. To thisend we sum the probabilities in Table 1 that have anHin the first position.