隐马尔科夫模型-英文课件.ppt

《隐马尔科夫模型-英文课件.ppt》由会员分享，可在线阅读，更多相关《隐马尔科夫模型-英文课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、隐马尔科夫模型Hidden Markov Model（HMM）Hidden Markov ModeluThe problems about the Template methoduHMM is a popular statistical tooluDiscrete-Time Markov ProcessuTheory of HMM:The three basic problems2Review template methodnKey ideaTo derive typical sequences of speech frames for a pattern via some averaging

2、 procedureRely on the use of local spectral distance measures to compare patternsDynamic programming,temporally align patternsProblems of Template methodu语音是一个随机信号u非严格意义上的统计方法Statistical techniques have been widely used in clustering to create reference patternsStatistical signal characterization in

3、herent in the template representation is only implicit and often inadequate:neglects the second-order statisticsu缺乏鲁棒性4HMM:popular toolnThe basic theory of HMM was published in a series of classic papers by Baum and his colleagues in the late 1960s and early 1970s nHMM was implemented for speech-pro

4、cessing applications by Baker at CMU,and by Jelinek and his colleagues at IBM in the 1970snHMM provides a natural and highly reliable way of recognizing speech for a wide range of applications5HMM:popular toolnThe underlying assumption of the HMMnthe speech signal can be well characterized as a para

5、metric random processnthe parameters of the stochastic process can be determined in a precise,well-defined manner6Discrete-Time Markov ProcessnA system with N discrete states indexed by 1,2,N.:The state at time t7Discrete-Time Markov Process8时不变系统？时不变系统？Observable Markov ModelnEach state corresponds

6、 to an observable eventExample:weatherState1:rain or snowState2:cloudyState3:sunny9The weather is observed once a dayCould it be used for what case?Extensions to Hidden Markov Models-The Urn-and-Ball ModelnN glass urns,each with M distinct color ballsnA urn is randomly selected first,and then a ball

7、 is chosen at random,whose color is recorded as the observationnThe ball is then replaced in the urn from which it was selectednThe procedure is repeated 102.2.The Urn-and-Ball Model11HMM for weather forecastnWhat Operations do you design to carry out the ball selection?nHow do you extend the Markov

8、 process to HMM to give more precise weather forecast?Theory of HMMnTopologynElementsnBi-hidden processesnThree basic problems13HMM Topology:Ergodic14HMM Topology:Left-right15Parallel path left-right HMM16Elements of HMM1.N-每个模型的状态数2.M-每个状态的可观察现象数3.状态转移概率分布,其中4.状态观察现象概率分布5.初始状态概率分布，其中n we use the co

9、mpact notation To indicate the complete parameter set of the model,this parameter set,of course,defines a probability measure for O,which we discuss later,we use the terminology HMM to indicate the parameter set and the associated probability measure interchangeably without ambiguity.Elements of HMM

10、18Bi-Hidden processesuThe statesuThe observations19The Three Basic ProblemsnEvaluation:Forward processnOptimal path:Viterbi AlgorithmnTraining:Baum-Welch Algorithm20Problem1:Given the observation sequence O=(o1,o2,oT),and a model how do we efficiently compute ,the probability of the observation sequ

11、ence,given the model?We can also view the problem as one of scoring how well a given model matches a given observation sequence.To solve the problem allows us to choose the model that best matches the observations.Evaluation21nProblem2 Given the observation sequence O=(o1,o2,oT),and the model how do

12、 we choose a corresponding static sequence q=(q1q2,qt)that is optimal in some sense.in this problem to find the correct state sequence.we usually use an optimality criterion to solve this problem as best as possible.Evaluation22nProblem3:How do we adjust the model parameters to maximize In this prob

13、lem we attempt to optimize the model parameters to best describe how a given observation sequence comes about.The observation sequence used to adjust the model parameters is called a training sequence because it is used to train the HMM.Evaluation23Probability EvaluationnWe wish to calculate the pro

14、bability of the observation sequence.Consider one such fixed-state sequencenWhere q1 is the initial state.The probability of the observation sequence O given the state sequence of q is nWhere we have assumed statistical independence of observation.Thus we get 24Probability EvaluationnThe probability

15、 of such a state sequence q can be written as nThe joint probability of O and q occur simultaneously,is simply the product of the above two terms25Probability EvaluationnThe probability of O is obtained by summing this joint probability over all possible state sequence q,giving26A.The Forward Proced

16、urenConsider the forward variable defined as nThat is,the probability of the partial observation sequence,o1o2ot,(until time t)and state i at time t,given the model .We can solve for inductively,as follows:27Forward Procedure1.initialization 2.induction 3.termination28B.The Backward ProcedurenIn a s

17、imilar manner,we can consider a backward variable defined as nThat is,the probability of the partial observation sequence from t+1 to the end,given state i at time t and the model nAgain we can solve for inductively,as Follows:29Backward Procedure1.initialization 2.Induction30Backward procedurenThe

18、initialization step 1 arbitrarily define to be 1 for all i.nStep 2,which is illustrated in next figure,which shows that in order to have been in state i at time t,and to account for the observation sequence from time t+1 on,you have to consider all possible state j at time t+1 31naccording for the t

19、ransition from i to j,as well as the observation ot+1 in state j.And then account for the remaining partial observation sequence from state j.We will see alter how the backward as well as the forward calculation are used to help solve fundamental problem 2 and 3 of HMMsBackward procedure32ai3ai2ai1a

20、iNs1s2s3sNt+1tsiBackward procedure33nThere are several possible ways of solving problem 2,finding the“optimal”state sequence associated with the given observation sequence.To implement this problem 2,we can define that a posteriori probability variableBackward procedure34 That is,the probability of

21、being in state i at time t,given the observation sequence O,and the model,we can express in several forms,including Backward procedure35nSince is equal to we can write as Backward procedure36nWhere we see that accounts for the partial observation sequence and state i at t,while account for the remai

22、nder of the observation sequence ,given state Using ,we can solve for the individually most likely state at time t,as Backward procedure37A.The Viterbi AlgorithmnTo find the single best state sequence,q=(q1q2qT),for the given observation sequence O=(o1o2oT),we need to define the quantity38Viterbi Al

23、gorithmnThat is,is the best score along a single path,at time t,which accounts for the first t observations and ends in state i,by induction we have39Viterbi AlgorithmnThe complete procedure for finding the best state sequence can now be stated as follows:1.Initialization40Viterbi Algorithm2.Recursi

24、on3.Termination41Viterbi Algorithm4.Path(state sequence)backtrackingnIt should be noted that the Viterbi algorithm is similar in implementation to the forward calculation.42B.Alternative Viterbi ImplementationnBy taking logarithms of the model parameters,the Viterbi algorithm of the preceding sectio

25、n can be implemented without the need for any multiplications,thus:43Viterbi Algorithm0.Preprocessing44Viterbi Algorithm1.Initialization2.Recursion 45Viterbi Algorithm3.Termination4.Backtracking 46time-series modeling-声学统计模型（语音识别）语言模型通信系统生物信号处理手写字符识别面部识别Feature extraction(Ferdinando Samaria etc.at O

26、livetti Research,Ltd)手势识别一、一、HMM应用领域应用领域HMM的应用的应用471.1HMM在生物信号处理中的应用在生物信号处理中的应用For protein and nucleic acid sequence analysis(Washington University)The recognition of Human Genes in DNA(University of California)Detecting Remote Protein Homologies(UCSC)Estimating amino acid distributions481.2 HMM应用与手

27、势识别应用与手势识别nHand motion is an effective means of human communications in real world49二、二、HMM的训练标准的训练标准ML-Maximum LikelihoodMMI-Minimum discrimination informationMDIMaximum mutual informationMMDMaximum model distanceCT Corrective TrainingMCE Minimum classification Error50nThe standard ML design criter

28、ion is to use a training sequence of observations O to derive the set of model parameters ,yieldingnAny of the reestimation algorithms discussed previously provides a solution to this optimization problem.ML-Maximum Likelihood51nThe minimum discrimination information(MDI)is a measure of closeness be

29、tween two probability measures under the given constraint R is defined by nWhere MDIMaximum mutual information52nThe standard ML criterion is to use to estimate model parameters ,yieldingnThe mutual information between an observation sequence and the word v,parameterized by n ,isnThe MMI criterion i

30、s to find the entire model set such that the mutual information is maximized,MMI Minimum discrimination information53三、三、HMM的应用问题的应用问题1.Scaling2.Multiple Observation Sequences3.Initial Estimates of HMM parameters.4.Effects of Insufficient Training Data5.Choice of Model54nInitially,for t=1,we setnFor

31、 each t,in terms of the previously scalednThat is,nWe determine the scaling coefficient asnGiving 3.1 Scaling55nEach nEach nSo in terms of the scaled variables,we getnFinally the term can be seen to be of the form3.1 Scaling56nThe only real change to the HMM procedure because of scaling is the proce

32、dure for computing .We cannot merely sum up the terms,because these are scaled already.However,we can use the property thatnThus we haven orn or3.1 Scaling57nThe major problem with left-right models is hat one cannot use a single observation sequence to train the model.This is because the transient

33、nature of the states within the model allows only a small number of observations for any state.nHence,to have sufficient data to make reliable estimates of all model parameters,one has to use multiple observation sequences.3.2 Multiple Observation Sequences58nHow do we choose initial estimates of th

34、e HMM parameters so that the local maximum is equal to or as close as possible to the global maximum of the likelihood function?nExperience has shown that either random or uniform initial estimates of the and A parameters are adequate for giving useful reestimates of these parameters in almost all c

35、ases.nHowever,for the B experiences has shown that Good initial estimates are helpful in the discrete symbol case and are essential in the continuous-distribution case.3.3 Initial Estimates of HMM parameters594.HMM system for Isolated Word Recognition1.Choice of Model Parameters2.Segmental k-means s

36、egmentation with clustering.3.Incorporation of Sate Duration into the HMM4.HMM Isolated-Digit Performance60To do isolated word speech recognition,we must perform the following:1.For each word v in the vocabulary,we must build an HMM -that is,we must estimate the model parameter(A,B,)that optimize th

37、e likelihood of the training set observation vectors for the vth word.2.For each unknown word to be recognized,the processing shown in Figure4.1 must be carried out,namely,measurement of the observation sequence ,via a feature analysis of the speech corresponding to the word;followed by calculation

38、of model likelihoods for all possible models,;followed by selection of the word whose model likelihood is highestthat is,4.1 HMM Recognizer of Isolated Words61Block diagram of an isolated word HMM recognizer62nThe figure shows a plot of average word error rate versus N,for the case of recognition of

39、 isolated digits.It can be seen that the error is somewhat insensitive to N,achieving a local minimum at N=6;however,differences in error rate for values of N close to 6 are small.4.2 Choice of Model ParametersAverage word error rate(for a digits vocabulary)versus the number of states N in the HMM(a

40、fter Rabiner et al.18)63nThe figure shows a comparison of marginal distributions against a histogram of the actual observations within a state.The observation vectors are ninth order,and the model density uses M=5 mixtures.The covariancematrices are constrained to be diagonal for each individual mix

41、ture.The results of the figure are for the first model state of the word“zero.”4.2 Choice of Model Parameters64 nfigure shows a curve of average word error rate versus the parameter (on a log scale)for a standard word-recognition experiment.It can be seen that over a very broad range()the average er

42、ror rate remains at about a constant value;however,when is set to 0(i.e.,),then the error rate increases sharply.nSimilarly,for continuous densities it is important to constrain the mixture gains as well as the diagonal covariance coefficients to be greater than or equal to some minimum values.4.2 C

43、hoice of Model Parameters65nThe Figure(next page)shows a log-energy plot,an accumulated log-likelihood plot,and a state segmentation for one occurrence of the word“six.”The states correspond roughly to the sounds in the spoken word“six.”nThe result of segmenting each of the training sequences is,for

44、 each of the N state j according to the current model.nThe resulting model reestimation procedure is used to reestimate all model parameters.The resulting model is then compared to the previous model(by computing a distance score that reflects the statistical similarity of the HMMs).4.3 K-means trai

45、ning procedure664.3 K-means training procedureThe segmental k-means training procedure used to estimate parameter values for the optimal continuous mixture density fit to a finite number of observation sequences.67nA typical set of histograms of for a five-state model of the word“six”is shown in the

46、 Figure.the first two states account for the initial/s/in“six”;the third state accounts for the transition to the vowel/i/;the fourth state accounts for the vowel;and the fifth state accounts for the stop and the final/s/sound.4.4 Incorporation of Sate Duration into the HMM68nFirst the normal Viterb

47、i algorithm is used to give the best segmentation of the observation sequence of the unknown word into states via a backtracking procedure.The duration of each state is then measured from the state segmentation.nA postprocessor then increments the log-likelihood score of the Viterbi algorithm,by the

48、 quantity4.4 Incorporation of Sate Duration into the HMM69nThe results of the recognition tests are given in the table(next page).The recognizers are the following:nLPC/DTW Conventional template-based recognizer using dynamic time warping(DTW)alignmentnLPC/DTW/VQ Conventional recognizer with vector

49、quantization of the feature vectors(M=64)nHMM/VQ HMM recognizer with M=64 codebooknHMM/CD HMM recognizer using continuous density model with M=5 mixtures per statenHMM/AR HMM recognizer using autoregressive observation density4.5 HMM Isolated-Digit Performance70Average Digit Error Rates for Several

50、Recognizers and Evaluation SetsEvaluation SetOriginal TrainingTS2TS3TS4RecognizerTypeLPC/DTW0.10.22.01.1LPC/DTW/VQ-3.5-HMM/VQ-3.7-HMM/CD00.21.31.8HMM/AR0.31.83.44.14.5 HMM Isolated-Digit Performance71五、五、HMM的缺陷的缺陷n状态独立假设n基于帧的特征提取n粗糙的状态时长模型：指数分布模型n训练方法的不完善性：非判决性、非全局最优72一些大公司对一些大公司对HMM的研究及应用的研究及应用1.HM