Hidden Markov Models (Vaseghi - Advanced Digital Signal Processing and Noise Reduction), страница 2

The discrete models can also be used for themodelling of the space of a continuous-valued process quantised into anumber of discrete points. First, consider a discrete state observation densitymodel. Assume that associated with the ith state of an HMM there are Mdiscrete centroid vectors [µi1, ..., µiM] with a pmf [Pi1, ..., PiM].

Thesecentroid vectors and their probabilities are normally obtained throughclustering of a set of training signals associated with each state.151Hidden Markov Modelsx2x2x1x1(a)(b)Figure 5.6 Modelling a random signal space using (a) a discrete-valued pmfand (b) a continuous-valued mixture Gaussian density.For the modelling of a continuous-valued process, the signal spaceassociated with each state is partitioned into a number of clusters as inFigure 5.6. If the signals within each cluster are modelled by a uniformdistribution then each cluster is described by the centroid vector and thecluster probability, and the state observation model consists of M clustercentroids and the associated pmf {µik, Pik; i=1, ..., N, k=1, ..., M}.

In effect,this results in a discrete state observation HMM for a continuous-valuedprocess. Figure 5.6(a) shows a partitioning, and quantisation, of a signalspace into a number of centroids.Now if each cluster of the state observation space is modelled by acontinuous pdf, such as a Gaussian pdf, then a continuous density HMMresults. The most widely used state observation pdf for an HMM is themixture Gaussian density defined asMfXS ( x s = i ) = ∑ Pik N ( x , µ ik , Σ ik )(5.6)k =1where N ( x , µ ik , Σ ik ) is a Gaussian density with mean vector µik andcovariance matrix Σik, and Pik is a mixture weighting factor for the kthGaussian pdf of the state i.

Note that Pik is the prior probability of the kthmode of the mixture pdf for the state i. Figure 5.6(b) shows the space of amixture Gaussian model of an observation signal space. A 5-mode mixtureGaussian pdf is shown in Figure 5.7.152Hidden Markov Modelsf (x)µ1µ2µ3µ4µ5xFigure 5.7 A mixture Gaussian probability density function.5.2.5 State Transition ProbabilitiesThe first-order Markovian property of an HMM entails that the transitionprobability to any state s(t) at time t depends only on the state of the processat time t–1, s(t–1), and is independent of the previous states of the HMM.This can be expressed as, s(t − N ) = l )Prob(s (t ) = j s (t − 1) = i, s (t − 2) = k ,= Prob(s (t ) = j s (t − 1) = i ) = aij(5.7)where s(t) denotes the state of HMM at time t. The transition probabilitiesprovide a probabilistic mechanism for connecting the states of an HMM,and for modelling the variations in the duration of the signals associatedwith each state.

The probability of occupancy of a state i for d consecutivetime units, Pi(d), can be expressed in terms of the state self-loop transitionprobabilities aii asPi (d ) = aiid −1 (1 − aii )(5.8)From Equation (5.8), using the geometric series conversion formula, themean occupancy duration for each state of an HMM can be derived asMean occupancy of state i =∞1∑ d Pi (d ) = 1−ad =0(5.9)ii153Hidden Markov Modelsa 11a 22a 12s1a 33a 44a 23s2s3a 13a 34s4a 24(a)Statess1s2s3s4Time(b)Figure 5.8 (a) A 4-state left–right HMM, and (b) its state–time trellis diagram.5.2.6 State–Time Trellis DiagramA state–time trellis diagram shows the HMM states together with all thedifferent paths that can be taken through various states as time unfolds.Figure 5.8(a) and 5.8(b) illustrate a 4-state HMM and its state–timediagram.

Since the number of states and the state parameters of an HMM aretime-invariant, a state-time diagram is a repetitive and regular trellisstructure. Note that in Figure 5.8 for a left–right HMM the state–time trellishas to diverge from the first state and converge into the last state. In general,there are many different state sequences that start from the initial state andend in the final state.

Each state sequence has a prior probability that can beobtained by multiplication of the state transition probabilities of thesequence. For example, the probability of the state sequences =[ S1 ,S1 ,S 2 ,S 2 ,S 3 ,S 3 ,S 4 ] is P(s)=π1a11a12a22a23a33a34. Since each state hasa different set of prototype observation vectors, different state sequencesmodel different observation sequences. In general an N-state HMM canreproduce NT different realisations of the random process that it is trained tomodel.154Hidden Markov Models5.3 Training Hidden Markov ModelsThe first step in training the parameters of an HMM is to collect a trainingdatabase of a sufficiently large number of different examples of the randomprocess to be modelled.

Assume that the examples in a training databaseconsist of L vector-valued sequences [X]=[Xk; k=0, ..., L–1], with eachsequence Xk=[x(t); t=0, ..., Tk–1] having a variable number of Tk vectors.The objective is to train the parameters of an HMM to model the statistics ofthe signals in the training data set. In a probabilistic sense, the fitness of amodel is measured by the posterior probability PM|X(M|X) of the model Mgiven the training data X. The training process aims to maximise theposterior probability of the model M and the training data [X], expressedusing Bayes’ rule asPM | X (M X ) =1f X (X )f X |M ( X M )PM (M )(5.10)where the denominator fX(X) on the right-hand side of Equation (5.10) hasonly a normalising effect and PM(M) is the prior probability of the model M.For a given training data set [X] and a given model M, maximising Equation(5.10) is equivalent to maximising the likelihood function PX|M(X|M).

Thelikelihood of an observation vector sequence X given a model M can beexpressed asf X |M ( X M )= ∑ f X |S ,M ( X s , M ) Ps|M ( s M )(5.11)swhere fX|S,M(X(t)|s(t),M), the pdf of the signal sequence X along the statesequence s =[ s (0) ,s (1) , ,s (T − 1)] of the model M, is given byf X |S ,M ( X s, M ) = f X |S ( x (0) s (0) ) f X |S ( x (1) s (1) ) f X |S ( x (T − 1) s (T − 1) )(5.12)where s(t), the state at time t, can be one of N states, and fX|S(X(t)|s(t)), ashorthand for fX|S,M(X(t)|s(t),M), is the pdf of x(t) given the state s(t) of themodel M. The Markovian probability of the state sequence s is given byPS |M ( s M ) = π s (0) a s (0) s (1) a s (1) s (2) a s ( T −2) s(T −1)(5.13)155Training Hidden Markov ModelsSubstituting Equations (5.12) and (5.13) in Equation (5.11) yieldsf X |M ( X | M ) = ∑ f X | S ,M ( X | s, M )Ps|M ( s | M )s= ∑ π s (0) f X | S ( x (0) s (0) ) a s (0) s (1) f X | S ( x (1) s (1) )sas (T − 2) s (T −1)f X | S ( x (T − 1) s (T − 1) )(5.14)where the summation is taken over all state sequences s.

In the trainingprocess, the transition probabilities and the parameters of the observationpdfs are estimated to maximise the model likelihood of Equation (5.14).Direct maximisation of Equation (5.14) with respect to the modelparameters is a non-trivial task. Furthermore, for an observation sequence oflength T vectors, the computational load of Equation (5.14) is O(NT). This isan impractically large load, even for such modest values as N=6 and T=30.However, the repetitive structure of the trellis state–time diagram of anHMM implies that there is a large amount of repeated computation inEquation (5.14) that can be avoided in an efficient implementation. In thenext section we consider the forward-backward method of model likelihoodcalculation, and then proceed to describe an iterative maximum-likelihoodmodel optimisation method.5.3.1 Forward–Backward Probability ComputationAn efficient recursive algorithm for the computation of the likelihoodfunction fX|M(X|M) is the forward–backward algorithm.

The forward–backward computation method exploits the highly regular and repetitivestructure of the state–time trellis diagram of Figure 5.8.In this method, a forward probability variable αt(i) is defined as thejoint probability of the partial observation sequence X=[x(0), x(1), ..., x(t)]and the state i at time t, of the model M:α t (i )= f X , S|M ( x (0), x (1), , x (t ), s (t ) = i M )(5.15)The forward probability variable αt(i) of Equation (5.15) can be expressedin a recursive form in terms of the forward probabilities at time t–1, αt–1(i):156Hidden Markov Models{aij }f X |S ( x (t ) s(t ) = i )f X |S ( x(t + 1) s(t + 1) = i ){aij }×States i×αt-1(i)+××+××+×+×++α t (i)α t+1(i)Time tFigure 5.9 A network for computation of forward probabilities for a left-right HMM., x(t ), s(t ) = i M )(x (0), x(1), , x (t − 1), s(t − 1) = j M ) aα t (i ) = f X , S |M (x (0), x (1), N=  ∑ f X , S |M j =1N(jif(x(t ) s(t ) = i, M ) X | S ,M)= ∑ α t −1 ( j ) a ji f X | S ,M (x (t ) s (t ) = i, M )j =1(5.16)Figure 5.9 illustrates, a network for computation of the forward probabilitiesfor the 4-state left–right HMM of Figure 5.8.