Hidden Markov Models (779805), страница 3
Текст из файла (страница 3)
The likelihood of anobservation sequence X=[x(0), x(1), ..., x(T–1)] given a model M can beexpressed in terms of the forward probabilities asf X |M ( x (0), x (1),, x(T −1) M ) = ∑ fNi =1NX , S |M ( x (0),x (1),, x(T −1), s(T −1) = i M )= ∑ α T −1 (i )i =1(5.17)Similar to the definition of the forward probability concept, a backwardprobability is defined as the probability of the state i at time t followed bythe partial observation sequence [x(t+1), x(t+2), ..., x(T–1)] as157Training Hidden Markov Models, x(T − 1) M )(s (t + 1) = j , x (t + 2), x (t + 3), , x (T − 1) )β t (i ) = f X , S M (s (t ) = i, x (t + 1), x (t + 2),N= ∑ a ij f X , S Mj =1(5.18)× f X |S ( x (t + 1) s (t + 1) = j , M )N= ∑ a ij β t +1 ( j ) f X | S,M ( x (t + 1) s (t + 1) = j , M )j =1In the next section, forward and backward probabilities are used to developa method for the training of HMM parameters.5.3.2 Baum–Welch Model Re-EstimationThe HMM training problem is the estimation of the model parametersM=(π, A, F) for a given data set.
These parameters are the initial stateprobabilities π, the state transition probability matrix A and the continuous(or discrete) density state observation pdfs. The HMM parameters areestimated from a set of training examples {X=[x(0), ..., x(T–1)]}, with theobjective of maximising fX|M(X|M), the likelihood of the model and thetraining data. The Baum–Welch method of training HMMs is an iterativelikelihood maximisation method based on the forward–backwardprobabilities defined in the preceding section.
The Baum–Welch method isan instance of the EM algorithm described in Chapter 4. For an HMM M,the posterior probability of a transition at time t from state i to state j of themodel M, given an observation sequence X, can be expressed asγ t (i, j ) = PS| X ,M (s (t ) = i, s (t + 1) = j X , M )==f S, X |M (s (t ) = i, s (t + 1) = j , X M )f X |M (X M )(5.19)α t (i )aij f X |S ,M (x (t + 1) s (t + 1) = j , M )β t +1 ( j )N∑αi =1T −1(i )where f S, X |M (s (t ) = i, s (t + 1) = j , X M ) is the joint pdf of the states s(t) and158Hidden Markov Modelss(t+1) and the observation sequence X, and f X |S ( x (t + 1) s (t + 1) = i ) is thestate observation pdf for the state i. Note that for a discrete observationdensity HMM the state observation pdf in Equation (5.19) is replaced withthe discrete state observation pmf PX |S ( x (t + 1) s (t + 1) = i ) . The posteriorprobability of state i at time t given the model M and the observation X isγ t (i ) = PS | X ,M (s (t ) = i X , M )==f S, X |M (s (t ) = i, X M )f X |M (X M )(5.20)α t (i ) β t (i )N∑αj =1T −1( j)Now the state transition probability aij can be interpreted asaij =expected number of transitions from state i to state jexpected number of transitions from state i(5.21)From Equations (5.19)–(5.21), the state transition probability can be reestimated as the ratioT −2aij =∑ γ t (i , j )t =0T −2∑ γ t (i )(5.22)t =0Note that for an observation sequence [x(0), ..., x(T–1)] of length T, the lasttransition occurs at time T–2 as indicated in the upper limits of thesummations in Equation (5.22).
The initial-state probabilities are estimatedasπ i =γ 0 (i )(5.23)Training Hidden Markov Models1595.3.3 Training HMMs with Discrete Density Observation ModelsIn a discrete density HMM, the observation signal space for each state ismodelled by a set of discrete symbols or vectors. Assume that a set of Mvectors [µi1,µi2, ..., µiM] model the space of the signal associated with the ithstate.
These vectors may be obtained from a clustering process as thecentroids of the clusters of the training signals associated with each state.The objective in training discrete density HMMs is to compute the statetransition probabilities and the state observation probabilities. The forward–backward equations for discrete density HMMs are the same as those forcontinuous density HMMs, derived in the previous sections, with thedifference that the probability density functions such as f X |S ( x (t ) s (t ) = i )are substituted with probability mass functions PX |S ( x (t ) s (t ) = i ) definedasPX |S ( x (t ) s (t ) = i )= PX |S (Q[ x (t )] s (t ) = i )(5.24)where the function Q[x(t)] quantises the observation vector x(t) to thenearest discrete vector in the set [µi1,µi2, ..., µiM]. For discrete densityHMMs, the probability of a state vector µik can be defined as the ratio of thenumber of occurrences of µik (or vectors quantised to µik ) in the state i,divided by the total number of occurrences of all other vectors in the state i:Pik ( µ ik ) =expected number of times in state i and observing µ ikexpected number of times in state iT −1∑=γ t (i )t∈x (t )→ µ ikT −1(5.25)∑ γ t (i)t =0In Equation (5.25) the summation in the numerator is taken over those timeinstants t where the kth symbol µik is observed in the state i.For statistically reliable results, an HMM must be trained on a largedata set X consisting of a sufficient number of independent realisations ofthe process to be modelled.
Assume that the training data set consists of Lrealisations X=[X(0), X(1), ..., X(L–1)], where X(k)=[x(0), x(1), ..., x(Tk–1)]. The re-estimation formula can be averaged over the entire data set as160Hidden Markov Modelsπˆ i =1 L −1 l∑ γ (i )L l =0 0(5.26)L −1 Tl −2∑ ∑ γ tl (i , j )aˆ ij =l=0 t=0L −1 Tl − 2∑∑(5.27)γ tl(i )l =0 t = 0andL −1Pˆi ( µ ik ) =∑Tl −1∑ γ tl (i )l = 0 t∈x ( t )→µ ikL −1 Tl −1γ tl ( i )l=0 t=0(5.28)∑∑The parameter estimates of Equations (5.26)–(5.28) can be used in furtheriterations of the estimation process until the model converges.5.3.4 HMMs with Continuous Density Observation ModelsIn continuous density HMMs, continuous probability density functions(pdfs) are used to model the space of the observation signals associated witheach state.
Baum et al. generalised the parameter re-estimation method toHMMs with concave continuous pdfs such a Gaussian pdf. A continuous Pvariate Gaussian pdf for the state i of an HMM can be defined asfXS( x(t ) s (t ) = i ) =1(2π )P/2Σi1/ 2exp{[ x (t ) − µ i ]T Σ i−1 [ x (t ) − µ i ] }(5.29)where µi and Σi are the mean vector and the covariance matrix associatedwith the state i. The re-estimation formula for the mean vector of the stateGaussian pdf can be derived as161Training Hidden Markov ModelsT −1µi =∑ γ t (i ) x (t )t =0T −1(5.30)∑ γ t (i )t =0Similarly, the covariance matrix is estimated asT −1Σi =∑ γ t (i)( x (t ) − µ i )( x(t ) − µ i )Tt =0(5.31)T −1∑ γ t (i)t =0The proof that the Baum–Welch re-estimation algorithm leads tomaximisation of the likelihood function fX|M(X|M) can be found in Baum.5.3.5 HMMs with Mixture Gaussian pdfsThe modelling of the space of a signal process with a mixture of Gaussianpdfs is considered in Section 4.5.
In HMMs with mixture Gaussian pdf statemodels, the signal space associated with the ith state is modelled with amixtures of M Gaussian densities asMf X |S ( x (t ) s (t ) = i )= ∑ Pik N ( x (t ), µ ik , Σ ik )(5.32)k =1where Pik is the prior probability of the kth component of the mixture. Theposterior probability of state i at time t and state j at time t+1 of the modelM, given an observation sequence X=[x(0), ..., x(T–1)], can be expressed asγ t (i, j ) = PS | X ,M (s(t ) = i, s (t + 1) = j | X , M )Mαt (i )aij ∑ Pjk N x( t + 1 ), µ jk , Σ jk βt +1( j )k =1=(N∑ αT −1(i)i =1)(5.33)162Hidden Markov Modelsand the posterior probability of state i at time t given the model M and theobservation X is given byγ t (i ) = PS | X ,M (s( t ) = i X , M )=α t (i ) β t (i )N∑ α T −1 ( j )(5.34)j =1Now we define the joint posterior probability of the state i and the kthGaussian mixture component pdf model of the state i at time t asζt (i, k ) = PS , K | X ,M (s (t ) = i, m(t ) = k X , M )N=∑ αt −1( j)a ji Pik N (x (t ), µik , Σ ik )βt (i)j =1(5.35)N∑ αT −1( j )j =1where m(t) is the Gaussian mixture component at time t.
Equations (5.33) to(5.35) are used to derive the re-estimation formula for the mixturecoefficients, the mean vectors and the covariance matrices of the statemixture Gaussian pdfs asPik =expected number of times in state i and observing mixture kexpected number of times in state iT −1=∑ ξ t (i , k )(5.36)t =0T −1∑ γ t (i )t =0andT −1µ ik =∑ξ t (i , k ) x (t )t=0T −1∑ ξ t (i , k )t=0(5.37)163Decoding of Signals Using Hidden Markov ModelsSimilarly the covariance matrix is estimated asT −1Σ ik =∑ ξ t (i, k )[x (t ) − µ ik ][x(t ) − µ ik ]Tt =0(5.38)T −1∑ ξ t (i, k )t =05.4 Decoding of Signals Using Hidden Markov ModelsHidden Markov models are used in applications such as speech recognition,image recognition and signal restoration, and for the decoding of theunderlying states of a signal.
For example, in speech recognition, HMMs aretrained to model the statistical variations of the acoustic realisations of thewords in a vocabulary of say size V words. In the word recognition phase,an utterance is classified and labelled with the most likely of the V+1candidate HMMs (including an HMM for silence) as illustrated in Figure5.10. In Chapter 12 on the modelling and detection of impulsive noise, abinary–state HMM is used to model the impulsive noise process.Consider the decoding of an unlabelled sequence of T signal vectorsX=[x(0), x(1), ..., X(T–1)] given a set of V candidate HMMs [M1 ,..., MV].The probability score for the observation vector sequence X and the modelMk can be calculated as the likelihood:f X |M ( X M k )= ∑ π s (0) f X S ( x (0) s (0) )as (0) s (1) f X S ( x (1) s (1) ) as (T − 2) s (T −1) f X S ( x(T − 1 ) s (T − 1) )s(5.39)where the likelihood of the observation sequence X is summed over allpossible state sequences of the model M.
Equation (5.39) can be efficientlycalculated using the forward–backward method described in Section 5.3.1.The observation sequence X is labelled with the HMM that scores thehighest likelihood asLabel ( X )= arg max( f X |M ( X M k )),kk=1, ..., V+1(5.40)In decoding applications often the likelihood of an observation sequence Xand a model Mk is obtained along the single most likely state sequence of164Hidden Markov ModelsWord ModelM1likelihoodof M 1fY|M (Y| M 1 )SpeechSignalFeatureExtractorFeaturesequenceYM2likelihoodof M 2fY|M (Y| M 2 )...Word Model MVlikelihoodof M vfY|M (Y| MV )Most likely word selectorWord ModelM MLSilence Model MsilfY|M (Y| Msil )likelihoodof M silFigure 5.10 Illustration of the use of HMMs in speech recognition.model Mk, instead of being summed over all sequences, so Equation (5.40)becomesLabel ( X )= arg max max f X , S M ( X , s M k ) sk(5.41)In Section 5.5, on the use of HMMs for noise reduction, the most likely statesequence is used to obtain the maximum-likelihood estimate of theunderlying statistics of the signal process.165Decoding of Signals Using Hidden Markov Modelsf X|S(x(t+1)|s(t+1)=i)fX|S (x(t)|s(t)=i)States i{aij}Maxδt(i–1){aij}×ψt(i)××Maxδt(i)Max×ψt+1(i)MaxMax×Max×δt(i+1)×x×Time tFigure 5.11 A network illustration of the Viterbi algorithm.5.4.1 Viterbi Decoding AlgorithmIn this section, we consider the decoding of a signal to obtain the maximuma posterior (MAP) estimate of the underlying state sequence.
The MAP statesequence sMAP of a model M given an observation signal sequence X=[x(0),..., x(T–1)] is obtained ass MAP = arg max f X , S M ( X ,s M )s= arg max ( f XsS ,M ( Xs,M )PS M ( s M ))(5.42)The MAP state sequence estimate is used in such applications as thecalculation of a similarity score between a signal sequence X and an HMMM, segmentation of a non-stationary signal into a number of distinct quasistationary segments, and implementation of state-based Wiener filters forrestoration of noisy signals as described in the next section.For an N-state HMM and an observation sequence of length T, there arealtogether NT state sequences. Even for moderate values of N and T say(N=6 and T=30), an exhaustive search of the state–time trellis for the beststate sequence is a computationally prohibitive exercise. The Viterbialgorithm is an efficient method for the estimation of the most likely statesequence of an HMM.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
