EM算法的一些基本原理

16.0SomeFundamentalPrinciples:EMAlgorithmEM算法的一些基本原理

数字语音处理概论IntroductiontoDigitalSpeechProcessingReferences:1.4.3.2,4.4.2ofHuang,or9.1-9.3ofJelinek2.6.4.3ofRabinerandJuang3.http://www.stanford.edu/class/cs229/materials.html4./people/bilmes/mypapers/em.pdf5./2785880/A_note_on_EM_algorithm_for_probabilistic_latent_semantic_analysisEM(ExpectationandMaximization)Algorithm

Goal

estimatingtheparametersforsomeprobabilisticmodelsbasedonsomecriteriaParameterEstimationPrinciplesgivensomeobservations

X=[x1,x2,……,xN]:MaximumLikelihood(ML)Principle

findthemodelparameterset

suchthatthelikelihoodfunctionismaximized,P(X|

)=max.Forexample,if

={,}istheparametersofanormaldistribution,andXisi.i.d,thentheMLestimateof

={,}canbeshowntobe

theMaximumAPosteriori(MAP)PrincipleFindthemodelparameter

sothattheAPosteriorprobabilityismaximized

i.e.P(

|X)=P(X|

)P(

)/P(X)=max

P(X|

)P(

)=maxParameterEstimation

EM(ExpectationandMaximization)AlgorithmWhyEM?Insomecasestheevaluationoftheobjectivefunction(e.g.likelihoodfunction)dependsonsomeintermediatevariables(latentdata)whicharenotobservable(e.g.

thestatesequence

forHMMparametertraining)directestimationofthedesiredparameterswithoutsuchlatentdataisimpossibleordifficult

e.g.toestimate{A,B,

}forHMMwithoutknowingthestatesequence

EM(ExpectationandMaximization)AlgorithmIteractiveProcedurewithTwoStepsinEachIteration:E(Expectation):expectationoftheobjectivefunctionwithrespecttoadistribution(valuesandprobabilities)ofthelatentdatabasedonthecurrentestimatesofthedesiredparametersconditionedonthegivenobservationsM(Maximization):generatinganewsetofestimatesofthedesiredparametersbymaximizingtheobjectivefunction(e.g.accordingtoMLorMAP)theobjectivefunctionincreasedaftereachiteration,eventuallyconvergedX：availabledata

(k)：k-thestimateoftheparameterset

z：latentdataP(X|)：objectivefunction(X,

(k))Pz(k)(z|X,

(k))Ez(k)[P(X|

)]

(k+1)=argmax

{Maximization(M)}Expectation(E)EMAlgorithm:AnexampleParametertobeestimated:λ={P(A),P(B),P(R|A),P(G|A),P(R|B),P(G|B)}ABoutputObserveddata:O:“ballsequence”:RGGLatentdata:q:“bottlesequence”:AAB(RGG)First,randomlyassignedλ(0)={P(0)(A),P(0)(B),P(0)(R|A),P(0)(G|A),P(0)(R|B),P(0)(G|B)}

forexample:{P(0)(A)=0.4,P(0)(B)=0.6,P(0)(R|A)=0.5,P(0)(G|A)=0.5,P(0)(R|B)=0.5,P(0)(G|B)=0.5}ExpectationStep:findtheexpectationoflogP(O|λ)

8possiblestatesequencesqi:{AAA},{BBB},{AAB},{BBA},{ABA},{BAB},{ABB},{BAA}MaximizationStep:findλ(1)tomaximizetheexpectationfunctionEq(logP(O|λ))Iterations:λ(0)

λ(1)

λ(2)....Forexample,whenqi={AAB}EMAlgorithmInEachIteration(assuminglogP(x

|)istheobjectivefunction)

Estep:expressingthelog-likelihoodlogP(x|

)intermsofthedistributionofthelatentdataconditionedon[x,

(k)]Mstep:findawaytomaximizedtheabovefunction,suchthattheabovefunctionincreasesmonotonically,i.e.,logP(x|

(k+1))logP(x|

(k))TheConditionsforeachIterationtoProceedbasedontheCriterionx:observed(incomplete)data,z:latentdata,{x,z}:completedataEMAlgorithmFortheEMIterationstoProceedbasedontheCriterion:tomakesurelogP(x|

[k+1])logP(x|

[k])H(

[k+1],

[k])H(

[k],

[k])duetoJenson’sInequality

theonlyrequirementistohave

[k+1]suchthat

Q(

[k+1],

[k])-Q(

[k],

[k])0

E-step:toestimate

Q(

,

[k]):auxiliaryfunction(increaseinthisfunctionmeansincreaseinobjectivefunction,maximizingthisfunctionmaybeeasier),theexpectationoftheobjectivefunctionintermsofthedistributionofthelatentdataconditionedon(x,

[k])M-step:

[k+1]=Q(

,

[k])argmax

Example:UseofEMAlgorithminSolvingProblem3ofHMMObserveddata:observationsO,latentdata:statesequenceqTheprobabilityofthecompletedatais

P(O,q|λ)=P(O|q,λ)P(q|λ)E-Step:

Q(λ,λ[k])=E[logP(O,q|λ)|O,λ[k]]=Σq

P(q|O,λ[k])log[P(O,q|λ)]λ[k]:k-thestimateofλ(known),λ:unknownparam