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

基于贝叶斯网络的各种抽样方法的比较摘要: 本文主要介绍了贝叶斯网的基本概念以及重要性抽样方法的基本理论和概率推理, 重点介绍了两种重要的抽样方法, 即逻辑抽样方法和似然加权法, 并且比较了它们的优缺点关键词: 贝叶斯网 抽样法 无偏估计1引言英国学者T.贝叶斯1763年在论有关机遇问题的求解中提出一种归纳推理的理论, 后被一些统计学者发展为一种系统的统计推断方法, 称为贝叶斯方法采用这种方法作统计推断所得的全部结果, 构成贝叶斯统计的内容认为贝叶斯方法是唯一合理的统计推断方法的统计学者, 组成数理统计学中的贝叶斯学派, 其形成可追溯到 20世纪 30 年代到5060年代, 已发展为一个有影响的学派Zhang和Poole首先提出了变量消元法, 其原理自关于不定序动态规划的研究（Bertele and Brioschi,1972）相近的工作包括DAmbrosio（1991）、Shachter（1994）、Shenoy（1992）等人的研究近期关于变量消元法的研究可参见有关文献【1】由于变量消元法不考虑步骤共享, 故引进了团树传播法, 如Hugin方法在实际应用中, 网络节点往往是众多的, 精确推理算法是不适用的, 因而近似推理有了进一步的发展. 重要性抽样法（Rubinstein, 1981）是蒙特尔洛积分中降低方差的一种手段, Henrion（1988）提出了逻辑抽样, 它是最简单也是最先被用于贝叶斯网近似推理的重要性抽样算法. Fung和Chang（1989）、Shachter和Peot（1989）同时提出了似然加权算法. Shachter和Peot（1989）还提出了自重要性抽样和启发式重要性抽样算法. Fung和Favero（1994）提出了逆序抽样（backward sam-pling）, 它也是重要性抽样的一个特例. Cheng和Druzdzel（2000）提出了自适应重要性抽样算法, 同时也给出了重要性抽样算法的通用框架, 这就是各种抽样方法的发展状况. 本文就近似推理阐述了两种重要的抽样方法即逻辑抽样方法和似然加权法, 并比较了它们的优缺点2. 基本概念2.1 贝叶斯网络的基本概念贝叶斯网络是一种概率网络, 用来表示变量之间的依赖关系, 是带有概率分布标注的有向无环图, 能够图形化地表示一组变量间的联合概率分布函数贝叶斯网络模型结构由随机变量（可以是离散或连续）集组成的网络节点, 具有因果关系的网络节点对的有向边集合和用条件概率分布表示节点之间的影响等组成其中节点表示了随机变量, 是对过程、事件、状态等实体的某些特征的描述; 边则表示变量间的概率依赖关系起因的假设和结果的数据均用节点表示, 各变量之间的因果关系由节点之间的有向边表示, 一个变量影响到另一个变量的程度用数字编码形式描述因此贝叶斯网络可以将现实世界的各种状态或变量画成各种比例, 进行建模2.2重要性抽样法基本理论设是一组变量在其定义域上的可积函数考虑积分 (2.2.1) 为了近似计算这一积分, 重要性抽样方法将上式改写为如下形式: (2.2.2) 这里, 被看成是一组随机变量, 是的一个联合分布, 称为重要性分布, 它满足以下条件: 对的任意取值, 如果, 那么.接下来, 重要性抽样方法从独立地抽取个样本并基于这些样本来对积分进行估计: （2.2.3）可以证明, 是的一个无偏估计, 且根据强大数定律, 当样本量趋于无穷时, 几乎收敛于.重要性抽样法的性能主要从两个方面来衡量: 一个是算法复杂度, 另一个是近似解的精度因此, 人们用计算所需的时间和的方差之积来度量重要性抽样法的效率:越小, 算法的效率越高, 收敛速度也就越快, 从而获得高精度近似所需的样本量不大这里, 方差可用下式计算: （2.2.4）重要性分布的选择是提高算法效率的关键由于重要性分布的选择对时间复杂度的影响不大, 因此为了提高算法的效率, 应该选用使得方差尽可能小的重要性分布根据式(2.2.4),若被积函数, 则最优重要性分布为.此时, 样本被集中在值较大的重要区域由于本身是未知的, 在实际中很少能够从抽样, 只能寻找与尽量接近的分布重要性分布与最优分布越接近, 方差就越小2.3重要性抽样法的概率推理考虑一个贝叶斯网, 用记其中所有变量的集合,记所表示的联合概率分布设观测到证据.下面将讨论如何近似计算一组查询变量取某值的后验概率.设是一些变量的集合, 是的一个子集合, , 并设为的一个取值定义函数 （2.3.1） 按条件概率的定义, 有 （2.3.2）根据式（2.3.1）和可以分别表示成如下形式: （2.3.3） （2.3.4）于是可以利用重要性抽样法来对它们进行近似对于近似的一般性质, 有一点需要注意根据以上讨论, 利用重要性抽样法获得的对和的估计是无偏的3. 重要性抽样方法3.1逻辑抽样法要用重要性抽样法解决式（2.3.3）和式（2.3.4）的问题, 首先需要选择一个重要性分布一个很自然的想法就是选用联合分布本身来作为重要性分布, 其中, 这样就得到了逻辑抽样逻辑抽样法首先从分布中抽取样本注意到分解为其中表示那些在拓扑序排列中那些在节点之前的节点的一个集合.因此可以按照贝叶斯网的拓扑序对其中的变量逐个进行抽样: 对待抽样变量,若它是根节点, 则按分布进行抽样; 若是非根节点, 则按分布是进行抽样, 这里是父节点的抽样结果, 在对抽样时是已知的, 为顺序抽样, 此过程需要从一些单变量概率分布随即抽样Cloudy(C)WetGrass(W)Sprinkler(S)Rain(R) （图1）对图1所示的贝叶斯网, 用逻辑抽样法计算, 逻辑抽样法生成一个样本的过程如下: 假设对顺序抽样过程获得了个独立样本, 其中满足的有个, 而在这个样本中, 进一步满足的有个根据式（2.2.3）和式（2.3.3） , 有 类似地, 根据式（2.2.3）和（2.3.4）可得 =.将上面两式代入式（2.3.2）, 可得, （4.1.1）这就是通过逻辑抽样法获得的对后验概率的近似, 它是在所有满足的样本中, 进一步满足的样本比例逻辑抽样法所产生与证据不一致的那些样本相当于被舍弃因此, 逻辑抽样有时也称为舍选抽样3.2似然加权法似然加权法是重要性抽样的一个特例, 提出它的一个主要目的是避免逻辑抽样因舍弃样本而造成浪费在抽样过程中, 它按拓扑序对每个变量进行抽样: 当不是证据变量时, 抽样方法与逻辑方法一致; 而当是证据变量时, 则以的观测值作为抽样结果这样保证了每一个样本都与证据一致, 从而可以利用, 不必舍弃对图1所示的贝叶斯网, 用似然加权法计算, 似然加权法生成一个样本的过程如下: （1）对根节点, 从抽样, 假设得到;（2）对节点, 因为是证据变量, 所以抽样结果被视为它的观测值; （3）对节点, 抽样分布为, 假设得到;（4）最后对叶节点抽样, 抽样分布为,假设得到.最后产生的样本为=.设,是通过上述过程抽得的个样本下面讨论怎样基于它们对和进行近似设是的一个子集对任一的函数, 用表示当变量取中的值时, 这个函数的函数值对任一, 是中一些变量的函数于是, 是当变量取中的值时, 这个函数的函数值用记所有非证据变量的集合, 即,设是似然加权法所使用的重要性分布不难看出, , 而于是有 注意.于是有对每个=1,2, , , 样本与证据一致, 因此对一函数, 有.所以, . .根据式(2.2.3)和式(2.3.3), 可得 (4.1.2)其中. 类似地, 根据式（2.2.3）和式（2.3.4）, 可得 . （4.1.3）将式(4.1.2)和式(4.1.3)代入式(2.3.2), 得. （4.1.4）4. 两种抽样方法的优缺点 逻辑抽样的优点是简单易行, 缺点是当概率很小时, 算法效率低, 收敛速度慢事实上, 问题的最优重要性分布是, 而抽样使用的是分布, 两者差别显著: 前者的概率质量集中在X的与一致的那些取值处, 而后者在这些区域的概率值却很小, 随着的减小, 所抽得的与一致的样本个数将会减少, 因此大量样本被舍弃, 造成了计算资源的浪费与逻辑抽样相比, 似然加权法相当于为每个样本都赋予一个权重.设为中的取值, 则可以写成当所有证据变量都是叶节点时, 权重是, 即给定时的似然度似然加权法的优点是每个样本都被利用, 效率比逻辑抽样有很大提高. 当所有证据变量都位于网络顶端时, 重要性分布正好就是最优分布, 似然加权的效率达到最优在其它情况下, 重要性分布与最优分布可能差别显著, 尤其是当概率很小时这时, 算法的收敛会很慢, 即要获得高精度的近似所需的样本量会增加参考文献1 Becker A,Geiger D.2001.A sufficiently fast algorithm for finding close to optimal clique trees.Artificial Intelligence,125(1-2):3172 Bertele U,Brioschi F.Nonserial dynamic programming.New York:Academic Press3 DAmbrosio B.1991.Local expression languages for probabilistic dependence:a preliminary report. In UAI91:Proceedings of the Seventh Conference on Uncertainty in Artificial Intelligence .San Francisco:Morgan Kaufmann Publishers.951024 Shachter R D 1994.Symbolic probabilistic inference in belief networks. In Proceedings of the Eighth National Conference on Artificial Intelligence.1261315 Zhang N L,PooleD.1994.A simple approach to Bayesian network computations.In Proc.of the Tenth Canadian Conference on Artificial Intelligence.1711786李奔波.多品种小批量生产工序能力和控制图研究D.重庆: 重庆大学数学系研究所.2006.4: 17.7 王洪琦, 许有玲.1999.面向21世纪中医基础理论研究状和未来M.北京: 军事医学科学出版社.8秦静等.质量管理学M.北京: 科学出版社, 2007.9徐岚等.SPC在多品种小批量生产线的应用研究J.微电子学, 2007,37(5): 68268410袁普及.基于成组技术的质量控制的研究D.南京:南京航空