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

隐马尔科夫模型

HiddenMarkovModel（HMM）HiddenMarkovModelTheproblemsabouttheTemplatemethodHMMisapopularstatisticaltoolDiscrete-TimeMarkovProcessTheoryofHMM:Thethreebasicproblems2ReviewtemplatemethodKeyideaToderivetypicalsequencesofspeechframesforapatternviasomeaveragingprocedureRelyontheuseoflocalspectraldistancemeasurestocomparepatternsDynamicprogramming,temporallyalignpatternsProblemsofTemplatemethod语音是一个随机信号非严格意义上的统计方法StatisticaltechniqueshavebeenwidelyusedinclusteringtocreatereferencepatternsStatisticalsignalcharacterizationinherentinthetemplaterepresentationisonlyimplicitandofteninadequate:neglectsthesecond-orderstatistics缺乏鲁棒性4HMM:populartoolThebasictheoryofHMMwaspublishedinaseriesofclassicpapersbyBaumandhiscolleaguesinthelate1960sandearly1970sHMMwasimplementedforspeech-processingapplicationsbyBakeratCMU,andbyJelinekandhiscolleaguesatIBMinthe1970sHMMprovidesanaturalandhighlyreliablewayofrecognizingspeechforawiderangeofapplications5HMM:populartoolTheunderlyingassumptionoftheHMMthespeechsignalcanbewellcharacterizedasaparametricrandomprocesstheparametersofthestochasticprocesscanbedeterminedinaprecise,well-definedmanner6Discrete-TimeMarkovProcessAsystemwithNdiscretestatesindexedby{1,2,…N}.:Thestateattimet7Discrete-TimeMarkovProcess8时不变系统？ObservableMarkovModelEachstatecorrespondstoanobservableeventExample:weatherState1:rainorsnowState2:cloudyState3:sunny9TheweatherisobservedonceadayCoulditbeusedforwhatcase?ExtensionstoHiddenMarkovModels

--TheUrn-and-BallModelNglassurns,eachwithMdistinctcolorballsAurnisrandomlyselectedfirst,andthenaballischosenatrandom,whosecolorisrecordedastheobservationTheballisthenreplacedintheurnfromwhichitwasselectedTheprocedureisrepeated10……2.2.TheUrn-and-BallModel11HMMforweatherforecastWhatOperationsdoyoudesigntocarryouttheballselection?HowdoyouextendtheMarkovprocesstoHMMtogivemorepreciseweatherforecast?TheoryofHMMTopologyElementsBi-hiddenprocessesThreebasicproblems13HMMTopology:Ergodic14HMMTopology:Left-right15Parallelpathleft-rightHMM16ElementsofHMMN每个模型的状态数M每个状态的可观察现象数状态转移概率分布,其中状态观察现象概率分布初始状态概率分布，其中weusethecompactnotationToindicatethecompleteparametersetofthemodel,thisparameterset,ofcourse,definesaprobabilitymeasureforO,,whichwediscusslater,weusetheterminologyHMMtoindicatetheparametersetandtheassociatedprobabilitymeasureinterchangeablywithoutambiguity.ElementsofHMM18Bi-HiddenprocessesThestatesTheobservations19TheThreeBasicProblemsEvaluation:ForwardprocessOptimalpath:ViterbiAlgorithmTraining:Baum-WelchAlgorithm20Problem1:GiventheobservationsequenceO=(o1,o2…,oT),andamodelhowdoweefficientlycompute,theprobabilityoftheobservationsequence,giventhemodel?Wecanalsoviewtheproblemasoneofscoringhowwellagivenmodelmatchesagivenobservationsequence.Tosolvetheproblemallowsustochoosethemodelthatbestmatchestheobservations.Evaluation21Problem2GiventheobservationsequenceO=(o1,o2,…,oT),andthemodelhowdowechooseacorrespondingstaticsequenceq=(q1q2,…,qt)thatisoptimalinsomesense.inthisproblemtofindthecorrectstatesequence.weusuallyuseanoptimalitycriteriontosolvethisproblemasbestaspossible.Evaluation22Problem3:Howdoweadjustthemodelparameterstomaximize

Inthisproblemweattempttooptimizethemodelparameterstobestdescribehowagivenobservationsequencecomesabout.TheobservationsequenceusedtoadjustthemodelparametersiscalledatrainingsequencebecauseitisusedtotraintheHMM.Evaluation23ProbabilityEvaluationWewishtocalculatetheprobabilityoftheobservationsequence.Consideronesuchfixed-statesequenceWhereq1istheinitialstate.TheprobabilityoftheobservationsequenceOgiventhestatesequenceofqisWherewehaveassumedstatisticalindependenceofobservation.Thusweget

24ProbabilityEvaluationTheprobabilityofsuchastatesequenceqcanbewrittenasThejointprobabilityofOandqoccursimultaneously,issimplytheproductoftheabovetwoterms25ProbabilityEvaluationTheprobabilityofOisobtainedbysummingthisjointprobabilityoverallpossiblestatesequenceq,giving26A.TheForwardProcedureConsidertheforwardvariable

definedasThatis,theprobabilityofthepartialobservationsequence,o1o2…ot,(untiltimet)andstateiattimet,giventhemodel.Wecansolveforinductively,asfollows:27ForwardProcedure1.initialization2.induction3.termination28B.TheBackwardProcedureInasimilarmanner,wecanconsiderabackwardvariabledefinedasThatis,theprobabilityofthepartialobservationsequencefromt+1totheend,givenstateiattimetandthemodelAgainwecansolveforinductively,asFollows:29BackwardProcedure1.initialization2.Induction30BackwardprocedureTheinitializationstep1arbitrarilydefinetobe1foralli.Step2,whichisillustratedinnextfigure,whichshowsthatinordertohavebeeninstateiattimet,andtoaccountfortheobservationsequencefromtimet+1on,youhavetoconsiderallpossiblestatejattimet+131accordingforthetransitionfromitoj,aswellastheobservationot+1instatej.Andthenaccountfortheremainingpartialobservationsequencefromstatej.Wewillseealterhowthebackwardaswellastheforwardcalculationareusedtohelpsolvefundamentalproblem2and3ofHMMsBackwardprocedure32……ai3ai2ai1aiNs1s2s3sNt+1tsiBackwardprocedure33Thereareseveralpossiblewaysofsolvingproblem2,findingthe“optimal”statesequenceassociatedwiththegivenobservationsequence.Toimplementthisproblem2,wecandefinethataposterioriprobabilityvariableBackwardprocedure34Thatis,theprobabilityofbeinginstateiattimet,giventheobservationsequenceO,andthemodel,wecanexpressinseveralforms,includingBackwardprocedure35SinceisequaltowecanwriteasBackwardprocedure36Whereweseethataccountsforthepartialobservationsequenceandstateiatt,whileaccountfortheremainderoftheobservationsequence,givenstateUsing,wecansolvefortheindividuallymostlikelystateattimet,asBackwardprocedure37A.The

ViterbiAlgorithmTofindthesinglebeststatesequence,q=(q1q2…qT),forthegivenobservationsequenceO=(o1o2…oT),weneedtodefinethequantity38ViterbiAlgorithmThatis,isthebestscorealongasinglepath,attimet,whichaccountsforthefirsttobservationsandendsinstatei,byinductionwehave39ViterbiAlgorithmThecompleteprocedureforfindingthebeststatesequencecannowbestatedasfollows:1.Initialization40ViterbiAlgorithm2.Recursion3.Termination41ViterbiAlgorithm4.Path(statesequence)backtrackingItshouldbenotedthattheViterbialgorithmissimilarinimplementationtotheforwardcalculation.42B.Alternative

ViterbiImplementationBytakinglogarithmsofthemodelparameters,theViterbialgorithmoftheprecedingsectioncanbeimplementedwithouttheneedforanymultiplications,thus:43ViterbiAlgorithm0.Preprocessing44ViterbiAlgorithm1.Initialization2.Recursion

45ViterbiAlgorithm3.Termination4.Backtracking46time-seriesmodeling声学统计模型（语音识别）语言模型通信系统生物信号处理手写字符识别面部识别—Featureextraction(FerdinandoSamariaetc.atOlivettiResearch,Ltd)手势识别一、HMM应用领域HMM的应用471.1HMM在生物信号处理中的应用Forproteinandnucleicacidsequenceanalysis(WashingtonUniversity)TherecognitionofHumanGenesinDNA(UniversityofCalifornia)DetectingRemoteProteinHomologies(UCSC)Estimatingaminoaciddistributions481.2HMM应用与手势识别Handmotionisaneffectivemeansofhumancommunicationsinrealworld49二、HMM的训练标准ML--MaximumLikelihoodMMI--MinimumdiscriminationinformationMDI—MaximummutualinformationMMD—MaximummodeldistanceCT–CorrectiveTrainingMCE–MinimumclassificationError50ThestandardMLdesigncriterionistouseatrainingsequenceofobservationsOtoderivethesetofmodelparameters,yieldingAnyofthereestimationalgorithmsdiscussedpreviouslyprovidesasolutiontothisoptimizationproblem.ML--MaximumLikelihood51Theminimumdiscriminationinformation(MDI)isameasureofclosenessbetweentwoprobabilitymeasuresunderthegivenconstraintRisdefinedbyWhereMDI—Maximummutualinformation52ThestandardMLcriterionistousetoestimatemodelparameters,yieldingThemutualinformationbetweenanobservationsequenceandthewordv,parameterizedby,isTheMMIcriterionistofindtheentiremodelsetsuchthatthemutualinformationismaximized,MMI–Minimumdiscriminationinformation53三、HMM的应用问题1.Scaling2.MultipleObservationSequences3.InitialEstimatesofHMMparameters.4.EffectsofInsufficientTrainingData5.ChoiceofModel54Initially,fort=1,wesetForeacht,,intermsofthepreviouslyscaledThatis,WedeterminethescalingcoefficientasGiving3.1Scaling55EachEachSointermsofthescaledvariables,wegetFinallythetermcanbeseentobeoftheform3.1Scaling56TheonlyrealchangetotheHMMprocedurebecauseofscalingistheprocedureforcomputing.Wecannotmerelysumuptheterms,becausethesearescaledalready.However,wecanusethepropertythatThuswehaveoror3.1Scaling57Themajorproblemwithleft-rightmodelsishatonecannotuseasingleobservationsequencetotrainthemodel.Thisisbecausethetransientnatureofthestateswithinthemodelallowsonlyasmallnumberofobservationsforanystate.Hence,tohavesufficientdatatomakereliableestimatesofallmodelparameters,onehastousemultipleobservationsequences.3.2MultipleObservationSequences58HowdowechooseinitialestimatesoftheHMMparameterssothatthelocalmaximumisequaltoorascloseaspossibletotheglobalmaximumofthelikelihoodfunction?ExperiencehasshownthateitherrandomoruniforminitialestimatesoftheandAparametersareadequateforgivingusefulreestimatesoftheseparametersinalmostallcases.However,fortheBexperienceshasshownthatGoodinitialestimatesarehelpfulinthediscretesymbolcaseandareessentialinthecontinuous-distributioncase.3.3InitialEstimatesofHMMparameters594.HMMsystemforIsolatedWordRecognition1.ChoiceofModelParameters2.Segmentalk-meanssegmentationwithclustering.3.IncorporationofSateDurationintotheHMM4.HMMIsolated-DigitPerformance60Todoisolatedwordspeechrecognition,wemustperformthefollowing:1.Foreachwordvinthevocabulary,wemustbuildanHMM--thatis,wemustestimatethemodelparameter(A,B,)thatoptimizethelikelihoodofthetrainingsetobservationvectorsforthevthword.2.Foreachunknownwordtoberecognized,theprocessingshowninFigure4.1mustbecarriedout,namely,measurementoftheobservationsequence,viaafeatureanalysisofthespeechcorrespondingtotheword;followedbycalculationofmodellikelihoodsforallpossiblemodels,;followedbyselectionofthewordwhosemodellikelihoodishighest—thatis,4.1HMMRecognizerofIsolatedWords61BlockdiagramofanisolatedwordHMMrecognizer62ThefigureshowsaplotofaverageworderrorrateversusN,forthecaseofrecognitionofisolateddigits.ItcanbeseenthattheerrorissomewhatinsensitivetoN,achievingalocalminimumatN=6;however,differencesinerrorrateforvaluesofNcloseto6aresmall.4.2ChoiceofModelParametersAverageworderrorrate(foradigitsvocabulary)versusthenumberofstatesNintheHMM(afterRabineretal.[18])63Thefigureshowsacomparisonofmarginaldistributionsagainstahistogramoftheactualobservationswithinastate.Theobservationvectorsareninthorder,andthemodeldensityuses M=5mixtures.Thecovariance matricesareconstrainedtobe diagonalforeachindividual mixture.Theresultsofthe figureareforthefirstmodel stateoftheword“zero.”4.2ChoiceofModelParameters64

figureshowsacurveofaverageworderrorrateversustheparameter(onalogscale)forastandardword-recognitionexperiment.Itcanbeseenthatoveraverybroadrange()theaverageerrorrateremainsataboutaconstantvalue;however,whenissetto0(i.e.,),thentheerrorrateincreasessharply.Similarly,forcontinuousdensitiesitisimportanttoconstrainthemixturegainsaswellasthediagonalcovariancecoefficientstobegreaterthanorequaltosomeminimumvalues.4.2ChoiceofModelParameters65TheFigure(nextpage)showsalog-energyplot,anaccumulatedlog-likelihoodplot,andastatesegmentationforoneoccurrenceoftheword“six.”Thestatescorrespondroughlytothesoundsinthespokenword“six.”Theresultofsegmentingeachofthetrainingsequencesis,foreachoftheNstatejaccordingtothecurrentmodel.Theresultingmodelreestimationprocedureisusedtoreestimateallmodelparameters.Theresultingmodelisthencomparedtothepreviousmodel(bycomputingadistancescorethatreflectsthestatisticalsimilarityoftheHMMs).4.3K-meanstrainingprocedure664.3K-meanstrainingprocedureThesegmentalk-meanstrainingprocedureusedtoestimateparametervaluesfortheoptimalcontinuousmixturedensityfittoafinitenumberofobservationsequences.67Atypicalsetofhistogramsofforafive-statemodeloftheword“six”isshownintheFigure.thefirsttwostatesaccountfortheinitial/s/in“six”;thethirdstateaccountsforthetransitiontothevowel/i/;thefourthstateaccountsforthevowel;andthefifthstateaccountsforthestopandthefinal/s/sound.4.4IncorporationofSateDurationintotheHM