基于贝叶斯网络的各种抽样方法比较

1基于贝叶斯网络的各种抽样方法实现与比较王秀琳14S003051计算机2班英国学者T.贝叶斯1763年在《论有关机遇问题的求解》中提出一种归纳推理的理论,后被一些统计学者发展为一种系统的统计推断方法,称为贝叶斯方法．采用这种方法作统计推断所得的全部结果,构成贝叶斯统计的内容．认为贝叶斯方法是唯一合理的统计推断方法的统计学者,组成数理统计学中的贝叶斯学派,其形成可追溯到20世纪30年代．到50～60年代,已发展为一个有影响的学派．Zhang和Poole首先提出了变量消元法,其原理自关于不定序动态规划的研究（BerteleandBrioschi,1972）．相近的工作包括D`Ambrosio（1991）、Shachter（1994）、Shenoy（1992）等人的研究．近期关于变量消元法的研究可参见有关文献【1】由于变量消元法不考虑步骤共享,故引进了团树传播法,如Hugin方法．在实际应用中,网络节点往往是众多的,精确推理算法是不适用的,因而近似推理有了进一步的发展.重要性抽样法（Rubinstein,1981）是蒙特尔洛积分中降低方差的一种手段,Henrion（1988）提出了逻辑抽样,它是最简单也是最先被用于贝叶斯网近似推理的重要性抽样算法.Fung和Chang（1989）、Shachter和Peot（1989）同时提出了似然加权算法.Shachter和Peot（1989）还提出了自重要性抽样和启发式重要性抽样算法.Fung和Favero（1994）提出了逆序抽样（backwardsam-pling）,它也是重要性抽样的一个特例.Cheng和Druzdzel（2000）提出了自适应重要性抽样算法,同时也给出了重要性抽样算法的通用框架,这就是各种抽样方法的发展状况.本文就近似推理阐述了两种重要的抽样方法即逻辑抽样方法和似然加权法,并比较了它们的优缺点．2.基本概念2.1贝叶斯网络的基本概念贝叶斯网络是一种概率网络,用来表示变量之间的依赖关系,是带有概率分布标注的有向无环图,能够图形化地表示一组变量间的联合概率分布函数．贝叶斯网络模型结构由随机变量（可以是离散或连续）集组成的网络节点,具有因果关系的网络节点对的有向边集合和用条件概率分布表示节点之间的影响等组成．其中节点表示了随机变量,是对过程、事件、状态等实体的某些特征的描述;边则表示变量间的概率依赖关系．起因的假设和结果的数据均用节点表示,各变量之间的因果关系由节点之间的有向边表示,一个变量影响到另一个变量的程度用数字编码形式描述．因此贝叶斯网络可以将现实世界的各种状态或变量画成各种比例,进行建模．2.2重要性抽样法基本理论设()fX是一组变量X在其定义域nXR上的可积函数．考虑积分2()()XIfXdX(2.2.1)为了近似计算这一积分,重要性抽样方法将上式改写为如下形式:()()()()XfXIPXdXPX(2.2.2)这里,X被看成是一组随机变量,()PX是X的一个联合分布,称为重要性分布,它满足以下条件:对X的任意取值x,如果()0fXx,那么()0PXx.接下来,重要性抽样方法()PX从独立地抽取m个样本12,,...,,mDDD并基于这些样本来对积分I进行估计:1()1.()mimiifDImPD（2.2.3）可以证明,mI是I的一个无偏估计,且根据强大数定律,当样本量m趋于无穷时,mI几乎收敛于I.重要性抽样法的性能主要从两个方面来衡量:一个是算法复杂度,另一个是近似解的精度．因此,人们用计算mI所需的时间t和mI的方差var()mI之积var()mtI来度量重要性抽样法的效率:var()mtI越小,算法的效率越高,收敛速度也就越快,从而获得高精度近似所需的样本量不大．这里,方差可用下式计算:221()var()()()XmfXIdXImPX（2.2.4）重要性分布的选择是提高算法效率的关键．由于重要性分布的选择对时间复杂度的影响不大,因此为了提高算法的效率,应该选用使得方差var()mI尽可能小的重要性分布．根据式(2.2.4),若被积函数()0fx,则最优重要性分布为*()()/PXfXI.此时var()0mI,样本被集中在()fX值较大的＂重要＂区域．由于I本身是未知的,在实际中很少能够从*()PX抽样,只能寻找与*()PX尽量接近的分布．重要性分布与最优分布*()PX越接近,方差var()mI就越小．2.3重要性抽样法的概率推理考虑一个贝叶斯网,用X记其中所有变量的集合,()PX记所表示的联合概率分布．设观测到证据Ee.下面将讨论如何近似计算一组查询变量Q取某值q的后验概率(|)PQqEe.设W是一些变量的集合,Y是的W一个子集合,\ZWY,并设y为Y的一个取值．定义函数1,()(,)0,YyYyYyWYZ若若Yy（2.3.1）按条件概率的定义,有(,)(|)()PQqEePQqEePEe.（2.3.2）根据式（2.3.1）(,)PQqEe和()PEe可以分别表示成如下形式:3(,)()()(),QqEeXPQqEeXXPX（2.3.3）()()()EeXPEeXPX.（2.3.4）于是可以利用重要性抽样法来对它们进行近似．对于近似的一般性质,有一点需要注意．根据以上讨论,利用重要性抽样法获得的对(,)PQqEe和()PEe的估计是无偏的．3.重要性抽样方法3.1逻辑抽样法要用重要性抽样法解决式（2.3.3）和式（2.3.4）的问题,首先需要选择一个重要性分布．一个很自然的想法就是选用联合分布()PX本身来作为重要性分布,其中12,,...,nXXXX,这样就得到了逻辑抽样．逻辑抽样法首先从()PX分布中抽取样本．注意到()PX分解为()(|()),XXXXPXP其中()X表示那些在拓扑序排列中那些在节点X之前的节点12,,...,iXXX的一个集合.因此可以按照贝叶斯网的拓扑序对其中的变量逐个进行抽样:对待抽样变量iX,若它是根节点,则按分布()iPX进行抽样;若是非根节点,则按分布是(|())iiPXXr进行抽样,这里()iXr是父节点的抽样结果,在对iX抽样时是已知的,为顺序抽样,此过程需要从一些单变量概率分布随即抽样．（图1）对图1所示的贝叶斯网,用逻辑抽样法计算(|E)PQqe,逻辑抽样法生成一个样本的过程如下:假设对()PX顺序抽样过程获得了m个独立样本12,DD…mD,其中满足Ee的有em个,而在这em个样本中,进一步满足Qq的有,qem个．根据式（2.2.3）和式（2.3.3）,有Cloudy(C)WetGrass(W)Sprinkler(S)Rain(R)41()()()1(,)()mQqiEeiiiiDDPDPQqEemPD11()()mQqiEeiiDDm,.qemm类似地,根据式（2.2.3）和（2.3.4）可得11()()mEeiiPEeDm=emm.将上面两式代入式（2.3.2）,可得,(|)qeemPQqEem,（4.1.1）这就是通过逻辑抽样法获得的对后验概率的近似,它是在所有满足Ee的样本中,进一步满足Qq的样本比例．逻辑抽样法所产生与证据Ee不一致的那些样本相当于被舍弃．因此,逻辑抽样有时也称为舍选抽样．3.2似然加权法似然加权法是重要性抽样的一个特例,提出它的一个主要目的是避免逻辑抽样因舍弃样本而造成浪费．在抽样过程中,它按拓扑序对每个变量进iX行抽样:当iX不是证据变量时,抽样方法与逻辑方法一致;而当是iX证据变量时,则以的iX观测值作为抽样结果．这样保证了每一个样本都与证据Ee一致,从而可以利用,不必舍弃．对图1所示的贝叶斯网,用似然加权法计算(|)PRtSt,似然加权法生成一个样本的过程如下:（1）对根节点C,从()PC抽样,假设得到Ct;（2）对节点S,因为SE是证据变量,所以抽样结果被视为它的观测值t;（3）对节点R,抽样分布为(|)PRCt,假设得到Rt;（4）最后对叶节点W抽样,抽样分布为(|,)PWRtSt,假设得到Wt.最后产生的样本为D={,,,CtRtStWt}.设12,DD,…mD是通过上述过程抽得的m个样本．下面讨论怎样基于它们对(,)PQqEe和()PEe进行近似．设Y是X的一个子集．对任一Y的函数()hY,用()|iDhY表示当变量Y取iD中的值时,这个函数的函数值．对任一XX,(|())XXP是X中一些变量的函数．于是,(|())|iDXXP是当变量取iD中的值时,这个函数的函数值．用Z记所有非证据变量的集合,即\ZXE,设'()PX是似然加权法所使用的重要性分布．不难看出,'()()EePEE,而5'(|)(|)(|())XXXXPZEPZEP于是有''()(,)PXPZE''()(|)PEPZE()(|())XEeXXXEP注意()(,)()EeEeEeXEZE.于是有'()()(|())XEeXXXPXXP对每个i=1,2,…,m,样本iD与证据Ee一致,因此对一函数()hX,有()()()|iEeiiDDhDhX.所以,.'(X)=(|())|XiDZXXPP()()(|())|XiEeiiDZXXDPDP.根据式(2.2.3)和式(2.3.3),可得'1()()()1(,)()mQqiEeiiiiDDPDPQqEemPD1(|())|1()(|())|XXiiDmXQqiiDZXXXXPDmP11()(|())|XimQqiDiEXXDPm11()(),mQqiiiDwDm(4.1.2)其中()(|())|XiiDEXXwDP.类似地,根据式（2.2.3）和式（2.3.4）,可得'1()()1()()mEeiiiiDPDPEemPD11()miiwDm.（4.1.3）6将式(4.1.2)和式(4.1.3)代入式(2.3.2),得11()()(|)()mQqiiimiiDwDPQqEewD.（4.1.4）4.两种抽样方法的优缺点逻辑抽样的优点是简单易行,缺点是当概率()PEe很小时,算法效率低,收敛速度慢．事实上,问题的最优重要性分布是()()()EeXPXPEe,而抽样使用的是分布()PX,两者差别显著:前者的概率质量集中在X的与Ee一致的那些取值处,而后者在这些区域的概率值却很小,随着()PEe的减小,所抽得的与Ee一致的样本个数将会减少,因此大量样本被舍弃,造成了计算资源的浪费．与逻辑抽样相比,似然加权法相当于为每个样本iD都赋予一个权重()iwD.设iz为iD中Z的取值,则iD可以写成iD(,)iZzEe．当所有证据变量都是叶节点时,权重是()iwD,即给定Ee时iZz的似然度．似然加权法的优点是每个样本都被利用,效率比逻辑抽样有很大提高.当所有证据变量都位于网络顶端时,重要性分布'()PX正好就是最优分布,似然加权的效率达到最优．在其它情况下,重要性分布与最优分布可能差别显著,尤其是当概率()PEe很小时．这时,算法的收敛会很慢,即要获得高精度的近似所需的样本量会增加．参考文献[2]BerteleU,BrioschiF.Nonserialdynamicprogramming.NewYork:AcademicPress[3]D`AmbrosioB.1991.Localexpressionlanguagesforprobabilisticdependence:apreliminaryreport.InUAI`91:ProceedingsoftheSeventhConferenceonUncertaintyinArtificialIntelligence.SanF