关于隐马尔可夫模型的更多信息

4.0MoreaboutHiddenMarkovModels关于隐马尔可夫模型的更多信息

数字语音处理概论IntroductiontoDigitalSpeechProcessingMarkovModelMarkovModel(MarkovChain)First-orderMarkovchainofNstatesisatriplet(S,A,

)SisasetofNstatesAistheN

Nmatrixofstatetransitionprobabilities

P(qt=j|qt-1=i,qt-2=k,……)=P(qt=j|qt-1=i)aij

isthevectorofinitialstateprobabilities

j=P(q0=j)Theoutputforanygivenstateisan

observableevent(deterministic)TheoutputoftheprocessisasequenceofobservableeventsAMarkovchainwith5states(labeledS1toS5)withstatetransitions.MarkovModelAnexample:a3-stateMarkovChainλState1generatessymbolAonly,

State2generatessymbolBonly,

andState3generatessymbolConlyGivenasequenceofobservedsymbolsO={CABBCABC},theonlyonecorrespondingstatesequenceis{S3S1S2S2S3S1S2S3},andthecorrespondingprobabilityis

P(O|λ)=P(q0=S3)P(S1|S3)P(S2|S1)P(S2|S2)P(S3|S2)P(S1|S3)P(S2|S1)P(S3|S2)

=0.1

0.3

0.3

0.7

0.2

0.3

0.3

0.2=0.00002268s2s3ABC0.60.70.30.30.20.20.10.30.7s1HiddenMarkovModelHMM,anextendedversionofMarkovModelTheobservationisaprobabilisticfunction(discreteorcontinuous)ofastateinsteadofanone-to-onecorrespondenceofastateThemodelisadoublyembeddedstochasticprocesswithanunderlyingstochasticprocessthatisnotdirectlyobservable(hidden)Whatishidden?TheStateSequence

Accordingtotheobservationsequence,weneverknowwhichstatesequencegeneratesitElementsofanHMM{S,A,B,}SisasetofNstatesAistheN

NmatrixofstatetransitionprobabilitiesBisasetofNprobabilityfunctions,eachdescribingtheobservationprobabilitywithrespecttoastate

isthevectorofinitialstateprobabilitiesSimplifiedHMMRGBGGBBGRRR……123HiddenMarkovModelTwotypesofHMM’saccordingtotheobservationfunctions

Discreteandfiniteobservations:

Theobservationsthatalldistinctstatesgeneratearefiniteinnumber

V={v1,v2,v3,……,vM},vk

RD

thesetofobservationprobabilitydistributionsB={bj(vk)}isdefinedasbj(vk)=P(ot=vk|qt=j),1

k

M,1

j

N

ot:

observationattimet,qt:stateattimet

forstatej,bj(vk)consistsofonlyMprobabilityvalues

Continuousandinfiniteobservations:Theobservationsthatalldistinctstatesgenerateareinfiniteandcontinuous,V={v|v

RD}thesetofobservationprobabilitydistributionsB={bj(v)}isdefinedasbj(v)=P

(ot=v|qt=j),1

j

N

bj(v)isacontinuousprobabilitydensityfunctionandisoftenassumedtobeamixtureofGaussiandistributionsHiddenMarkovModelAnexample:a3-statediscreteHMMλGivenasequenceofobservationsO={ABC},thereare27possiblecorrespondingstatesequences,andthereforethecorrespondingprobabilityiss2s1s3{A:.3,B:.2,C:.5}{A:.7,B:.1,C:.2}{A:.3,B:.6,C:.1}0.60.70.30.30.20.20.10.30.7HiddenMarkovModelThreeBasicProblemsforHMMsGivenanobservationsequenceO=(o1,o2,…..,oT),andanHMMλ=(A,B,)Problem1:

HowtoefficientlycomputeP(O|λ)?

EvaluationproblemProblem2:

Howtochooseanoptimalstatesequenceq=(q1,q2,……,qT)?

DecodingProblemProblem3:

GivensomeobservationsOfortheHMMλ,howtoadjustthemodelparameterλ=(A,B,)tomaximize

P(O|λ)?

Learning/TrainingProblem

BasicProblem1forHMM

l=(A,B,p)

O=o1o2o3……ot……oT

observationsequence

q=

q1q2q3……qt……qT

statesequence

12N․Problem1:

GivenlandO,

findP(O|l)=Prob[observingOgivenl]

․DirectEvaluation:consideringallpossiblestatesequenceq

P(O|l)=å([bq1(o1)·bq2(o2)

·

……bqT(oT)]

·

[pq1·

aq1q2·aq2q3

·……aqT-1qT])P(q|l)totalnumberofdifferentq:NThugecomputationrequirementsP(O

|

q,

l)allq

allq

allq

BasicProblem1

123

BasicProblem1αt(i)tti

t(i)=P(o1o2……ot,qt=i|

)

BasicProblem1ForwardAlgorithmαt(i)αt+1(j)jit+1t

t+1(j)=[

t(i)aij]bj(ot+1)

1

j

N 1

t

T

1Ni=1BasicProblem2βt(i)t+1tTi

t(i)

=P(ot+1,ot+2,…,oT|qt=i,

)BasicProblem2BackwardAlgorithmβt(i)βt+1(j)jit+1tT

t(i)=

aijbj(ot+1)

t+1(j)t=T

1,T

2,…,2,1,

1

i

NNj=1BasicProblem2βt(i)αt(i)it

P(O,qt=i|

)=Prob[observingo1,o2,…,ot,…,oT,qt=i|

]=

t(i)

t(i)

BasicProblem2P(Ō|λ)αt(i)βt(i)tiP(O|

)=

T(i)Ni=1P(O|

)=

P(O,qt=i|

)=

[

t(i)

t(i)]Ni=1Ni=1BasicProblem2forHMM

․Approach1–Choosingstateqt*

individuallyasthemostlikelystateattimet-

Defineanewvariablegt(i)=P(qt=i|O,l)

gt(i)=¾¾¾¾¾=¾¾¾¾¾

at(i)bt(i)

å

at(i)bt(i)

N

i=1

P(O,qt=i|l)

P(O|l)

-Problemmaximizingtheprobabilityateachtimetindividuallyq*=q1*q2*…qT*maynotbeavalidsequence(e.g.aqt*qt+1*=0)

-

Solution

gt(i)],1£t£T

qt*=argmax[1£i£N

infact

qt*=argmax[1£i£N

P(O,qt=i|l)

]=argmax[1£i£N

at(i)t(i)

b]ViterbiAlgorithmδt(i)δt+1(j)δt(i)ittt+111ij

t+1(j)=max[

t(i)aij]

bj(ot+1)i

t(i)

=max

P[q1,q2,…qt-1,qt=i,o1,o2,…,ot|

]q1,q2,…qt-1ViterbiAlgorithmPathbacktrackingBasicProblem2forHMM․ApplicationExampleofViterbiAlgorithm-Isolatedwordrecognition...Themodelwiththehighestprobabilityforthemostprobablepathusuallyalsohasthehighestprobabilityforallpossiblepaths.observation1£i£n

1£i£nBasicProblem1ForwardAlgorithm(forallpaths)BasicProblem2ViterbiAlgorithm(forasinglebestpath)BasicProblem3βt+1(j)αt(i)tt+1ij

t(i)aijbj(ot+1)

t+1(j)αt(i)aijbj(ot+1)βt+1(j)βt+1(j)αt(i)ijtt+1BasicProblem3BasicProblem3

BasicProblem3aij=

T-1

t=1

t(i,j)/(T-1)T-1

t=1

t(i)/(T-1)

BasicProblem3

BasicProblem3

Noclosed-formsolution,butapproximatediterativelyAninitialmodelisneeded-modelinitializationMayconvergetolocaloptimalpointsratherthanglobaloptimalpoint-heavilydependingontheinitializationModeltrainingBasicProblem3forHMMModelInitialization:SegmentalK-meansModelRe-estimation:Baum-WelchBasicProblem3GlobaloptimumLocaloptimumPP(O|λ)

jknVectorQuantization(VQ)AnEfficientApproachforDataCompressionreplacingasetofrealnumbersbyafinitenumberofbitsAnEfficientApproachforClusteringLargeNumberofSampleVectorsgroupingsamplevectorsintoclusters,eachrepresentedbyasinglevector(codeword)ScalarQuantizationreplacingasinglerealnumberbyanR-bitpatternamappingrelationJk

-A=m0

vk

A=mLS=Jk

,

V={v1

,v2

,…,vL}Q:S

VQ(x[n])=vkifx[n]

JkL=2REachvkrepresentedbyanR-bitpatternQuantizationcharacteristics(codebook){J1

,J2

,…,JL}and{v1

,v2

,…,vL}designedconsideringatleasterrorsensitivityprobabilitydistributionofx[n]

ScalarQuantization

：PulseCodedModulation(PCM)VectorQuantizationquantizationerror000001010011100101110111

100100101110VectorQuantizationPx(x)VectorQuantization(VQ)Considerationserrorsensitivitymaydependonx[n],x[n+1]jointlydistributionofx[n],x[n+1]maybecorrelatedstatisticallymoreflexiblechoiceofJkQuantizationCharacteristics(codebook){J1

,J2

,…,JL}and{v1

,v2

,…,vL}

2-dimVectorQuantization(VQ)Example:xn=(x[n],x[n+1])S={xn=(x[n],x[n+1]);|x[n]|<A,|x[n+1]|<A}VQSdividedintoL2-dimregions {J1

,J2

,…,Jk

,…JL}

eachwitharepresentativevectorvk

Jk,

V={v1

,v2

,…,vL}Q:S

VQ(xn)=vkifxn

JkL=2R

eachvkrepresentedbyanR-bitpattern

VectorQuantization

(256)2=(28)2=2161024=210JkvkVectorQuantizationVectorQuantizationJkvkVectorQuantization(VQ)N-dimVectorQuantization

x=(x1

,x2

,…,xN)S={x=(x1

,x2

,…,xN),|xk|<A,k=1,2,…N}V={v1

,v2

,…,vL}Q:S

VQ(x)=vkifx

JkL=2R,eachvk

representedbyanR-bitpattern

CodebookTrainedbyaLargeTrainingSet˙Definedistancemeasurebetweentwovectorsx,y

d(x,y):S

S

R+(non-negativerealnumbers)-desiredpropertiesd(x,y)

0d(x,x)=0d(x,y)=d(y,x)d(x,y)+d(y,z)

d(x,z)examples:d(x,y)=

(xi

yi)2d(x,y)=

|xi

yi|d(x,y)=(x-y)t

-1(x-y)MahalanobisDistance:Co-varianceMatrixiiDistanceMeasures

cityblockdistance

Mahalanobisdistance

VectorQuantization(VQ)K-MeansAlgorithm/Lloyd-MaxAlgorithmIterativeProceduretoObtainCodebookfromaLargeTrainingSet(1)Fixed{v1,v2,…,vL}findbestsetof{J1,J2,…,JL}(2)Fixed{J1,J2,…,JL}findbestsetof{v1,v2,…,vL}(1)Jk={x|d(x,vk

)<d(x,vj),j

k}

D=d(x

,Q(x))=minnearestneighborcondition(2)Foreachk

Dk=d(x,vk)=mincentroidcondition(3)ConvergenceconditionD=

DkaftereachiterationDisreduced,butD

0|D(m+1)

D(m)|<

,m:iteration

Lk=1VectorQuantizationVectorQuantization(VQ)K-meansAlgorithmmayConvergetoLocalOptimalSolutionsdependingoninitialconditions,notuniqueingeneralTrainingVQCodebookinStages―LBGAlgorithmstep1:Initialization.L=1,traina1-vectorVQcodebookstep2:Splitting. SplittingtheLcodewordsinto2Lcodewords,L=2Lexample1

step3:k-meansAlgorithm:toobtainL-vectorcodebookstep4:Termination.Otherwisegotostep2UsuallyConvergestoBetterCodebook‧example2:thevectormostfarapartLBGAlgorithmInitializationinHMMTrainingAnOftenUsedApproach―SegmentalK-MeansAssumeaninitialestimateofallmodelparameters(e.g.estimatedbysegmentationoftrainingutterancesintostateswithequallength)FordiscretedensityHMMForcontinuousdensityHMM(MGaussianmixtu