期望传播算法及其推导

1、期望传播算法及其推导个人博客：Notations:Diag(a):adiagonalmatrixwithabeingitsdiagonalelement.diag(A):avectorfromthediagonalelementoAf.ab：componentwisemultiply.a0b：componentwisedivide.RecapofVariationalInferenceAsmentionedin1,wehaveintroducedvariationalinferenceanditsapplicationinBayesianlinearregression.Inthisblog,

2、wefocusonavariationalinferenceperspectiveonexpectationpropagation.Insignalprocessingregime,theposteriordistributionisinterested.However,itisdifficulttoobtainowingtomanyhigh-dimensionintegral.Forexample,weconsiderlinearGaussianmodely=Hx+wItsposteriordistributiondenotedby(y|x)(x)p(x|y)=Jp(y|x)p(x)dxwh

3、erep(y|x)=pw(yHx).Unlessbothp(y|x)andp(x)areGaussian,wecantobtaintheclose-formofp(x|y)directly.Forthat,someapproximationsarenecessary.Tothidend,weuseq(x)toapproximatetheposteriordistributionandKL-divergencetomeasurethedifferencebetweenq(x)andp(x|y).Forsimplification,wegenerallyrestricttheformofq(x)f

4、romthedistributionfamilyS,i.e.,argminq(x)=g(x)GSDKL(P|q)Obviously,adistributionfamilywithexcellentpropertieswillgreatlyreducetheamountofcomputation.Fortunately,exponentialfamilyisoneofthat.ExponentialFamilyTheexponentialfamilyoverxparameteredbynisdefinedbyp(x；n)=h(x)g(n)exp(nTu(x)whereg(n)isnormaliz

5、ationconstant=1g(n)(/h(x)exp(nTu(x)dx)Takingthegradientofbothsideoftheabovew.r.t.n,wegetg(n)/h(x)exp(nTu(x)dx+g(n)/h(x)俗吩)U(x)dx=Rearrangingyields1一g(n)g(n)=g(n)/u(x)h(x)exp(nTu(x)dxfu(x)h(x)exp(nTu(x)dx=fh(x)exp(nTu(x)dx=Eu(x)UsingthefactSgg(n)=g(n)Vg(n),wehavelogg(n)=Eu(x)(*1)AVariationalInference

6、PerspectiveonEPForthedistributionofq(x)invariationalinference,Wetakeexponentialfamilydistributionintoaccountq(x)=h(x)g(n)exp(nTu(x)wethenwriteDKl(pIIq)asDKL(p|q)=logg(n)-nTEP(x)u(x)+constTakingthegradientofthebothsideofabovew.r.t.ntozeroyieldslogg(n)=Ep(x)u(x)Asmentionedin(*1),wethengetEq(x)u(x)=Ep(

7、x)u(x)Notethatifq(x)isGaussianN(x|”,S),wethenminimizetheKL-divergencebysettingMequaltothemeanofp(x)and乞equaltothevarianceofp(x).Weexploitthisresulttoobtainapraticalalgorithmforapproximateinference.Formanyprobabilitymodels,thejointdistributionofdataD=y，yNandhiddenvariables(mayincludingparameters)comp

8、risesaproductoffactorsintheformnp(d,&)=ifi(e)wheref0(6)=p(e)and九(&)=P(yn|。)，(n!=0).Theposteriordistributionisgivenbyp(d,e)1nP(e|D)=p(D)=p(D)ifi(e)wherep(D)ispartitionfunctionorevidencefunction.rnP(D)=/ifi(e)deAswedeterminetheformofq(x)inq(e)=Ziqi(e)Thenq(e)isupdatedbyminimizingqi(e)argmin1=qi(e)DKL(

9、p(D)ninifi(e)llziqi(e)Actually,theapproximationispoorsinceeachfactorisindividuallyapproximated.Toremedythissituation,expectationpropagationmakesamuchbetterapproximationbyoptimizingeachfactorinturninthecontextofalloftheremainingfactors2.Below,wehavegiventhedetaileddescriptionsofEPstep-by-step.Stepi:I

10、nitializeallfactorsqi(e)fromdistributionfamilyS.inq(e)=Ziqi(e)Step2:Computeqj(e)denotedbyq(e)qj(e)=Cqj(e)whereCisnormalizationconstant.Step3:Updateqnewp)=Dkl(Zjfj(e)qj(e)|q(e)whereqnew(e)istheupdateofq(0).Step4：Updateqj(6)qnew(e)%=cqjwhereCisanormalizationconstant.Step5：_、step2.ApplicationinCommunic

11、ationWeconsiderstandardlinearGaussianmodel(SLM)y=Hx+wwherexWCNgeneratedfromM-QAMconstellationwithdistributionp(x)=ni=1p(xi).PassingthechannelHeCMxN(estimatedperfeetbeforhand)andaddingthewhiteGaussiannoisewNc(w|0,2I),theobservedsignalyisthenobtained.Weaimatdesigninganhigh-efficientsignaldetectorusing

12、EP.Basedonaboveknowledge,wewritetheposteriordistributionofthismodelasp(y|x)p(x)p(x|y)=p(y)gp(y|x)p(x)Noticethatsinceyisgiven,thenp(y)isregardedasaconstant.Wefurtherassumetheeachobserveddataareindependentofothers,i.e.,nMp(y|x)=Q=1p(a|x)Step1:Initializeq(x),theapproximationofq(x).Sincep(y|x)isGaussian

13、,wethenapproximatep(x)byGaussian,oneofexponentialfamily.q(x)=Nc(x|m,Diag(v)Itsmarginaldistributionisq(xj=Nc(xilmi,vi).Notethatq(xjhereisq/。)mentionedinsection3.Step2:Calculatethejointdistributionq(x,y)q(x,y)=q(x)p(y|x)=Nc(x|m,Diag(v)Nc(y|Hx,b2I)aNc(x|m,Diag(v)Nc(x|(HH)-1Hy,(-2HH)-1)xNc(xM，s)wherethe

14、lastequaitoncanbeobtainedbyGaussianproductlemmamentionedin2,andfollowingequations乞=(b-1HHH+Diag(10v)-1M=S(a2HHy+Diag(m0v)Here,wefurtherexploitNc(xj(ijQjj)toapproximatep(xj,y).Thisoperationignoresthecorrelationofxjandxj,sowewriteitasq(叼,y)=”上叼仏，Ejj).Step3：Computeqj(叼)q(叼,y)M(叼bjQjj)qj(xj)=q(xj)=Nc(xj

15、|mj,vj)xNc(xj|mjem,vjem)temtemwhere(mj,vj)canbeobtainedbyGaussianproductlemmatemvj=11(%Vj)temmj=/Pjvt叫j-1mjvjStep4：Updateq(xi,y)byminimizingKL-divergenceargmin1qnew(xj,y)=q(Xj,y)Sdkl(Cp(xj)qj(xj)|q(xj,y)丿Thisstepcanbewrittenastemtemxj=xj|mj，vjtemtemvj=Varxj|mj,vjtemtemP(xj)Nc(xjmj,vj),wheretheexpect

16、ationistakenoverfp(叼)Nc(叼mtem，vm)dxj.ItmeansthatXjandVjisthemeanandvarianeeofC1p(xj)qj(xj),respectively.Withmomentmatch,thereisqnew(叼,y)=Nc(xj|Xj,Vj)Notethatthemarginalposteriordistributionisapproximatedbyp(xj|y)Cp(xj)qj(xj).Step5:Updateq(xj),wethenupdateq(xj)byUsingtheGaussianproductlemma,wegetqnew(xj,y)q(xj)x(qj(xj)vj=1tem-vj-1mj=vj(temmjtemxjVj-vjStep6：step2.Totally,Withabovedescription,wesummarytheEPalgorithmasfollowing乞=(b-1HHH+Diag(10v