贝叶斯网络结构学习总结

贝叶斯网络结构学习总结一、 贝叶斯网络结构学习的原理从数据中学习贝叶斯网络结构就是对给定的数据集，找到一个与数据集拟合最好的网络。首先定义一个随机变量Sh，表示网络结构的不确定性，并赋予先验概率分布p(Sh)。然后计算后验概率分布p(ShID)。根据Bayesian定理有p(ShID)=p(Sh,D)/p(D)=p(Sh)p(DISh)/p(D)其中p(D)是一个与结构无关的正规化常数，p(DISh)是边界似然。于是确定网络结构的后验分布只需要为每一个可能的结构计算数据的边界似然。在无约束多项分布、参数独立、采用Dirichlet先验和数据完整的前提下，数据的边界似然正好等于每一个(i，j)对的边界似然的乘积，即p(DISh)=HFI「号H「气+%)-尸叫+N)k=1「气)二、 贝叶斯网络完整数据集下结构学习方法贝叶斯网络建模一般有三种方法：1)依靠专家建模；2)从数据中学习；3)从知识库中创建。在实际建模过程中常常综合运用这些方法，以专家知识为主导，以数据库和知识库为辅助手段，扬长避短，发挥各自优势，来保证建模的效率和准确性。但是，在不具备专家知识或知识库的前提下，从数据中学习贝叶斯网络模型结构的研究显得尤为重要。常用的结构学习方法主要有两类，分别是基于依赖性测试的学习和基于搜索评分的学习。第一类方法是基于依赖性测试的方法，它是在给定数据集D中评估变量之间的条件独立性关系，构建网络结构。基于条件独立测试方法学习效率最好，典型的算法包括三阶段分析算法(TPDA)。基于依赖性测试的方法比较直观，贴近贝叶斯网络的语义，把条件独立性测试和网络结构的搜索分离开，不足之处是对条件独立性测试产生的误差非常敏感。且在某些情况下条件独立性测试的次数相对于变量的数目成指数级增长。第二类方法是基于评分搜索的方法，其原理是在所有节点的结构空间内按照一定的搜索策略及评分准则构建贝叶斯网络结构，这种算法虽然能够搜索到精确的网络结构，但是由于结构空间很大，从所有可能的网络结构空间搜索最佳的贝叶斯网络结构被证明为NP-hard问题，所以一般需要使用启发式算法，代表性算法有K2算法等。基于搜索评分的方法是一种统计驱动的方法，试图在准确性、稀疏性、鲁棒性等多个因素之间找个平衡点。但由于搜索方法的先天弱点，导致用搜索评分的方法不一定能找到最好的结构，但是应用范围很广。当观察到的数据足够充分且计算次数足够多时，基于搜索评分的方法和基于依赖性测试的方法都可以学到“正确”的网络结构。此外，有人结合上述两种方法，提出了一些混合算法，这类算法首先利用独立性测试降低搜索空间的复杂度，然后执行评分搜索找到最佳网络，如稀疏候选算法(sparsecandidate)及MMHC(max-minhill-climbing)算法等。基于依赖性测试结构学习方法基于依赖性测试的结构学习算法将贝叶斯网络看作是编码了变量间独立性关系的图结构。它的核心思想是：通过样本集D验证条件独立性I(Xi，Xj|C)是否成立，若成立，则在网络S中节点Xi和Xj被C有向分割，节点Xi和Xj之间不存在边，若不成立，变量Xi和Xj是依赖的，网络中节点Xi和Xj之间存在边。然后，利用节点集之间的条件独立性，建造一个有向无环图，以尽可能多地覆盖这些条件独立性。常用的独立性检验的方法有X2检验和基于互信息的检验方法。基于依赖性测试的学习方法学习效率较高，而且能够获得全局最优解；但存在以下问题：1.判断两个节点是否独立或条件独立是困难的，变量间条件独立性检验的次数是随着变量的个数的增加指数级增长的；2.高阶的条件独立性检验的结果不够可靠。1993年Sprites等提出的SGS算法是典型的以条件独立性测试确定拓扑结构的算法。该算法从无向完全图出发，如果相节点间存在无向分割集，则删除它们间的边；然后通过统计测试来确定剩余边的方向。2002年，Cheng将信息论与统计测试相结合，使用相互信息代替了条件独立性测试。经过Drafting、Thickening、Thinning三个步骤，通过计算相互信息量来确定节点间的条件独立性。从而构造出多连接有向图模型。基于评分搜索的结构学习方法：贝叶斯网络基于评分搜索的结构学习方法主要包括两步模型选择和模型优化。模型选择部分要制定模型选择准则，即评分函数目前较常用的几个评分函数如下：最优参数对数似然函数，CH评分，BIC评分等，还有MDL(minimumdescriptionlength),AIC(Akaikeinformationcriterion)评分函数，HVL(holdoutvalidationlikelihood)评分(验证数据似然度】CVL(crossvalidationlikelihood)评分(交叉验证)。模型优化就是要根据模型选择准则，即评分函数，选择出评分最高的网络结构，也就是搜索策略问题。从所有可能的网络结构空间搜索最佳的贝叶斯网络结构被证明为NP-hard问题，所以一般使用启发式搜索算法，主要有K2，hill-climbing算法；随机重复爬山法(randomrestarthill-climbing)，禁忌搜索(tabusearch)，模拟退火(simulatedannealing)及遗传算法(geneticalgorithm)等。常用的评分函数介绍如下：最优参数对数似然函数结构C与相应的参数集合气组成贝叶斯网络(C，气)。相对于数据9最优的贝叶斯网(C*,°*)应该使对数似然函数达到最大，即l(匚*,0**19)=maxsupl(匚,019)« 匚 °°, 匚在概念上寻找最优的贝叶斯网络的过程可以分为两步：第一步寻找最优结构匚*，第二步寻找最优参数0**0对任一网络结构0,定义1*(。IS)=supl(C，七IS)作为网络结构的函数，i*(CIS)称为优参对数似然函数，最优结构。*应该使优参对数似然函数达到最大，即l*(0*I9)=maxl*(。19)，这就是最大优参似然准则。0家族CH评分设定p(BID)=rfscore(i,pa) ---B表示网络结构，D表示一组变量TOC\o"1-5"\h\zS i si=1X1，X2，...,Xn的完整实例数据q r(a)r「(合+n)\o"CurrentDocument"其中score(i,pa)=11[ j 11 曲 ―]\o"CurrentDocument"i j=1叫*+NPk=1 叫)其中N.是D中满足X=k，兀.=j的样本个数，N,=客，8=»。ijk i i ij* ijkij* ijkk=1 k=1在使用CH评分之前，首先需要选定参数先验分布p(0BIBs)中超参数8亦。通常这并非易事，因为理论上我们需要对每一个可能的结构都提供参数先验分布，然而结构数目众多，无法一一罗列。在实际中，人们往往规定一个等价样本量8和一个先验贝叶斯旺Bs，利用下式得到P(0BIBs)的超参数8亦:8jk=8PB(Xi=kI兀i=j)。BIC评分，即贝叶斯信息准则是在大样本前提下对边缘似然函数的一种近似，它有明确直观的意义，而且使用方便，是实际中最常用的评分函数。dlogP(910)浇logP(910,0*)一一logm2这就是模型结构0的BIC评分，记为BIC(°19)。BIC评分的第一项是模型0的优参对数似然度，它度量的是结构0与数据9的拟合程度。第二项是一个关于模型复杂度的罚项。若仅仅依据优参似然度来选择模型，会选到最复杂的完全贝叶斯网络，导致过度拟合。由于附加了一个模型复杂度的罚项，BIC有效地避免了过度拟合，直观上，基于BIC评分选择模型就是要选择既与数据拟合，又比较简单的模型。MDL评分它是最短描述长度(minimumdescriptionlength)的简称。这个准则的基本思想如下：数据分析的目的是要找出蕴含在数据中的规律，然后可以利用它们对数据进行压缩，从而降低数据的编码(描述)长度，所以，用贝叶斯网分析数据是否成功可以用数据和模型的编码总长度来度量。AIC评分它是Akaike信息准则的简称，他假设数据9是从一个概率分布P(X)中进行独立同分布抽样而得到的。AIC评分的出发点是要找一个贝叶斯网B*=(C*,0*)，使得P(X)与P(X)之间°* B*的KL距离最短，即KL(P,P「<KL(P,P),VB，在一定光滑条件下做大样本近似，可得如下结论，即B*的结构匚*应该满足：AIC(C*19)>AIC(C19),V。，其中，AIC(C19)=logP(91。,0*)-dAIC评分与BIC评分都是优参对数似然度加一个罚项，因此都称为罚项似然度。MDL也是罚项似然度。HVL评分罚项的作用是防止过度拟合，还有一种防止过度拟合的方法，它的基本思想是把数据9随机地分成训练数据9和验证数据9。对于一个模型结构C，首先基于训练数据对其参数进行t v估计，得到一个贝叶斯网(C,01)，然后计算验证数据9v对数似然度：HVL笆IS,9t)=logP(9I。,01)。这就是HVL评分函数。CVL评分，即交叉验证它的基本思想是多次计算模型的hvl评分，而每次都按照不同方式将9划分为9t和9,然后计算各次所得评分的平均值，并将其作为模型的最后评分。CVL评分比HVL评分更具鲁棒性，但其计算复杂度也高出HVL评分数倍。在大样本情况下，HVL准则，CVL准则都与AIC准则等价。典型算法介绍：三阶段算法：第一阶段：Drafting，计算每对节点间的互信息，建立完整的无向图；第二阶段：Thickening，如果节点对不是d-分割的话，把这一点对加入到边集中；第三阶段：Thinning，检察边集中的每个点对，如果两个节点是d-分割的，则移走这条边。K2算法：K2算法用贪婪搜索处理模型选择问题：先定义一种评价网络结构优劣的评分函数，再从一个网络开始，根据事先确定的最大父节点数目和节点次序，选择分值最高的节点作为该节点的父节点。K2算法使用后验概率作为评分函数：p(DIB)=rfscore(i,pa)i=1f 「(々「「(q，+nl其中score(i,pa)= I i 11 j 4]i 尸1「VN)k=1 E)K2算法伪代码:k2(X,p,p,9)输入：X={X1,X2，...,XJ 一组变量p 一个变量顺序（设它与变量下标一致）p 变量父亲节点个数的上界9 一组完整的数据输出：一个贝叶斯网匚J由节点X1，X2，...,Xn组成的无边图forj=1ton兀j7；VidJCH（<Xj，兀j>l9）;while（true）iJargmaxCH（<X,兀u{X}>l9）5吧 jjiV JCH（<Xj，兀ju{X}>l9）if（V>Vand仇jl<p）9 J%;兀jJ兀.u{X.};在9中加边X.TXj；elsebreak;endifendwhileendfor估计C的参数^return（C用）;K2的出发点是一个包含所有节点、但却没有边的无向图。在搜索过程中，K2按顺序逐个考察P中的变量，确定其父亲节点，然后添加相应的边。对某一变量X，假设K2已经j找到了它的一些父亲节点兀j。如果l气」<P，即Xj的父亲节点个数还未达到上界p，那么就要继续为它寻找父节点，具体做法是首先考虑哪些在P中排在Xj之前，但却还不是Xj的父亲节点的变量，从这些变量中选出Xj,它使得新家族CH评分七wJCHKXj.D{.}>19)达到最大；然后将Vnew与旧家族评分比较：如果Vnew>Void，则把X〔添加为Xj的父节点；否则停止为Xj寻找父亲节点。Hill-climbing算法爬山法的目标是要找出评分最高的模型，它从一个初始模型出发开始搜索，初始模型一般设为无边模型，在搜索的每一步，它首先用搜索算子对当前模型进行局部修改，得到一系列候选模型；然后计算每个候选模型的评分，并将最优候选模型与当前模型进行比较；若最优候选模型的评分大，则以它为下一个模型，继续搜索，否则，就停止搜索，并返回当前模型。搜索算子有三个：加边、减边和转边。加边和减边算子的使用有个前提，就是不能在网络中形成有向圈。爬山法可以使用任何评分函数。不同的评分函数有不同的要求：CH评分要求关于先验参数分布的超参数，而HVL及CVL评分则要求把数据分成训练数据和验证数据。因此，需要处理的算法细节也有所不同。爬山算法的伪代码如下：LearnBN_HC(X,9,f,匚0)输入：X 一组变量 9 一组关于X的完整数据f 一个罚项似然度评分函数；C0 一个初始贝叶斯网络结构输出：一个贝叶斯网络1U。匚0；BjQ的参数的最大似然估计oldScoreJf(匚,019)；while(true)匚*Jnull;0*Jnull;newScoreJ sfor(每个对匚做一次加边、减边或转边而得到的模型结构匚')0'J'的参数的最大似然估计；tempScoreJf(匚',0'19);if(tempScore>newScore)匚*J。';0*J0';newScoreJtempScore;endifendfor12if(newScore>oldScore)

。J。*;0jO*;oldScoreJnewScore;elsereturn(。,。);endifendwhile三、 贝叶斯网缺值数据下的结构学习贝叶斯网络缺值数据下的结构学习算法主要有SEM(structureEMlearningalgorithm)算法。它的基本思想是：从某初始模型结构。。和参数O0出发开始迭代，在进行了t次迭代得到了(。t,Ot)后，第t+1次迭代由以下两个步骤组成：⑴基于(匚t,Ot)对数据进行修补，使之完整；(2)基于修补后的完整数据9t对模型及参数进行一部优化。得到(匚t+1,01