贝叶斯网络简介

贝叶斯网络简介IntroductiontoBayesianNetworks基本框架•贝叶斯网络：概率论图论基本思路•贝叶斯网络是为了处理人工智能研究中的不确定性(uncertainty)问题而发展起来的.•贝叶斯网络是将概率统计应用于复杂领域进行不确定性推理和数据分析的工具。•BN是一种系统地描述随即变量之间关系的工具。建立BN的目的主要是进行概率推理(probabilisticinference)。•用概率论处理不确定性的主要优点是保证推理结果的正确性。几个重要原理•链规则(chainrule)•贝叶斯定理(Bayes’theorem)•利用变量间条件独立性),...,,|()...|()(),...,,(2112121nnnXXXXPXXPXPXXXP•Whatarethey?–Bayesiannetsareanetwork-basedframeworkforrepresentingandanalyzingmodelsinvolvinguncertainty•Whataretheyusedfor?–Intelligentdecisionaids,datafusion,featurerecognition,intelligentdiagnosticaids,automatedfreetextunderstanding,datamining•Wheredidtheycomefrom?–Crossfertilizationofideasbetweentheartificialintelligence,decisionanalysis,andstatisticcommunities贝叶斯网络的几个主要问题贝叶斯网络概率推理(ProbabilisticInference)结构学习(structurelearning)参数学习(Parameterlearning)分类(classification)隐变量及隐结构学习(Hiddenvariablesandhiddenstructurelearning)一个简单贝叶斯网络例子一个简单贝叶斯网络例子•计算过程：•(1)•P(y1|x1)=0.9•P(z1|x1)=P(z1|y1,x1)P(y1|x1)+P(z1|y2,x1)P(y2|x1)•=P(z1|y1)P(y1|x1)+P(z1|y2)P(y2|x1)•=0.7*0.9+0.4*0.1=0.67•P(w1|x1)=P(w1|z1,x1)P(z1|x1)+P(w1|z2,x1)P(z2|x1)•=P(w1|z1)P(z1|x1)+P(w1|z2)P(z2|x1)•=0.5*0.67+0.6*0.33=0.533•该计算利用向下概率传播及链式规则。一个简单贝叶斯网络例子•计算过程：•(2)•P(y1)=P(y1|x1)P(x1)+P(y1|x2)P(x2)=0.9*0.4+0.8*0.6=0.84•P(z1)=P(z1|y1)P(y1)+P(z1|y2)P(y2)=0.7*0.84+0.4*0.16=0.652•P(w1)=P(w1|z1)P(z1)+P(w1|z2)P(z2)=0.5*0.652+0.6*0.348=0.5348•P(w1|y1)=P(w1|z1)P(z1|y1)+P(w1|z2)P(z2|y1)•=0.5*0.7+0.6*0.3=0.53•P(w1|y2)=P(w1|z1)P(z1|y2)+P(w1|z2)P(z2|y2)•=0.5*0.4+0.6*0.6=0.56•P(w1|x1)=P(w1|y1)P(y1|x1)+P(w1|y2)P(y2|x1)•=0.53*0.9+0.56*0.1=0.533••该计算利用向上概率传播及贝叶斯定理。为什么要用贝叶斯网络进行概率推理？•理论上，进行概率推理所需要的只是一个联合概率分布。但是联合概率分布的复杂度相对于变量个数成指数增长，所以当变量众多时不可行。•贝叶斯网络的提出就是要解决这个问题。它把复杂的联合概率分布分解成一系列相对简单的模块，从而大大降低知识获取和概率推理的复杂度，使得可以把概率论应用于大型问题。•统计学、系统工程、信息论以及模式识别等学科中贝叶斯网络特里的多元概率模型：朴素贝叶斯模型，隐类模型，混合模型，隐马尔可夫模型，卡尔曼滤波器等。•动态贝叶斯网络主要用于对多维离散时间序列的监控和预测。•多层隐类模型，能够揭示观测变量背后的隐结构。概率论基础贝叶斯网络所依赖的一个核心概念是条件独立:ConditionalIndependence基本概念例子P(C,S,R,W)=P(C)P(S|C)P(R|S,C)P(W|S,R,C)chainrule=P(C)P(S|C)P(R|C)P(W|S,R,C)since=P(C)P(S|C)P(R|C)P(W|S,R)since贝叶斯网络应用医疗诊断，工业，金融分析，计算机（微软Windows,Office），模式识别：分类，语义理解军事（目标识别，多目标跟踪，战争身份识别等），生态学，生物信息学（贝叶斯网络在基因连锁分析中应用），编码学，分类聚类，时序数据和动态模型图分割与变量独立•图分割，有向分割（d-separate,d-分割）变量X和Y通过第三个变量Z间接相连的三种情况：阻塞(block)设Z为一节点集合，X和Y是不在Z中的两个节点。考虑X和Y之间的一条通路。如果满足下面条件之一，则称被Z所阻塞：1．有一个在Z中的顺连节点；2．有一个在Z中的分连节点3．有一个汇连节点W，它和它的后代节点均不在Z中。图分割与变量独立•如果X和Y之间的所有通路都被Z阻塞，则说Z有向分割(directedseparate)X和Y，简称d-separate,d-分割。那么X和Y在给定Z时条件独立。•定理（整体马尔科夫性）设X和Y为贝叶斯网N中的两个变量，Z为N中一个不包含X和Y的节点集合。如果Zd-分割X和Y，那么X和Y在给定Z时条件独立，即•d-分割是图论的概念，而条件独立是概率论的概念，所以定理揭示了贝叶斯网络图论侧面和概率论侧面之间的关系。马尔科夫边界与端正图马尔科夫边界：条件独立性在贝叶斯网络中，一个节点X的马尔科夫边界(Markovboundary)包括其父节点、子节点、以及子节点的父节点。端正图(Moralgraph):团树传播算法-junctiontree设G为一有向无环图，如果将G中每个节点的不同父节点结合，即在他们之间加一条边，然后去掉所有边的方向，所得到的无向图成为G的端正图。贝叶斯网络推理(Inference)贝叶斯网络可以利用变量间的条件独立对联合分布进行分解，降低参数个数。•推理(inference)是通过计算来回答查询的过程•计算后验概率分布：P(Q|E=e)贝叶斯网络推理(Inference)1变量消元算法(Variableelimination)利用概率分解降低推理复杂度。使得运算局部化。消元过程实质上就是一个边缘化的过程。最优消元顺序：最大势搜索，最小缺边搜索贝叶斯网络推理(Inference)2.团树传播算法利用步骤共享来加快推理的算法。团树（cliquetree）是一种无向树，其中每一个节点代表一个变量集合，称为团(clique)。团树必须满足变量连通性，即包含同一变量的所有团所导出的子图必须是连通的。•用团树组织变量消元的算法。计算共享•团树传播算法基本步骤：–将贝叶斯网络转化为团树–团树初始化–在团树中选一个团作为枢纽–全局概率传播：CollectMessage;DistributeMessage–边缘化，归一化团树传播算法示例（[TLR]是枢纽节点）变量消元和团树传播算法都是精确推理算法。贝叶斯网络推理(Inference)3.近似推理(1)随机抽样算法：顺序抽样法，MCMC抽样•是一类应用于数值积分和统计物理中的近似计算方法。基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似计算感兴趣的量。•随机抽样算法理论基础是大数定律。MCMC算法—吉布斯抽样(Gibbssampling)。它首先随机生成一个与证据E=e相一致的样本s1作为起始样本。此后，每个样本si的产生都依赖于前一个样本si-1,且si与si-1最多只有一个非证据变量的取值不同，记改变量为X。•X的取值可以从非证据变量中随机选取，也可以按某个固定顺序轮流决定。•在si中，X的值通过随机抽样决定，抽样分布是：•当样本数时，马氏链理论保证了算法返回的结果收敛于真正的后验概率。吉布斯抽样的缺点是收敛速度慢，因为马氏链往往需要花很长时间才能真正达到平稳分布。(2)变分法。贝叶斯网络学习1.结构学习：发现变量之间的图关系，2.参数学习：决定变量之间互相关联的量化关系。贝叶斯网络结构学习选择具有最大后验概率的结构。基于评分函数(scoringfunction)：BIC,MDL,AIC等拉普拉斯近似(Laplaceapproximation):对拉普拉斯近似简化，得BIC:①BIC既不依赖于先验也不依赖于参数坐标系统②第一项度量参数模型预测数据的优良程度，第二项用于惩罚模型复杂度结构学习算法算法：K2:通过为每个结点寻找父结点集合来学习贝叶斯网络结构。它不断往父结点集中添加结点，并选择能最大化数据和结构的联合概率的结点集。HillClimbing(operators:edgeaddition,edgedeletion,edgereversion)从一个无边结构开始，在每一步，它添加能最大化BIC的边。算法在通过添加边不能再提高结构得分时停止。缺值数据结构学习：StructuralEMSEM不是每次迭代都同时优化模型结构和参数，而是先固定模型结构进行数次参数优化后，再进行一次结构加参数优化，如此交替进行。目的：减小计算复杂度。贝叶斯网络参数学习最大似然估计完全基于数据，不需要先验概率：贝叶斯估计假定在考虑数据之前，网络参数服从某个先验分布。先验的主观概率,它的影响随着数据量的增大而减小。贝叶斯网络参数学习缺值数据最大似然估计：EM算法（迭代算法）1基于对数据进行修补，使之完整(E-step)2基于修补后的完整数据计算的最大似然估计(M-Step)EM算法是收敛的。隐结构模型学习隐变量是取值未被观察到的变量。通过数据分析：1隐变量的个数2隐结构3隐变量的势4模型参数方法：基于评分函数的爬山法G是一个隐变量模型，D是一组数据。是G的参数的某一个最大似然估计，是G的有效维数。隐变量势学习爬山算法隐结构学习双重爬山算法贝叶斯网络用于分类和因果关系分析(1)NaïveBayesiannetworks(2)TreeaugmentBayesiannetworks,etal.(3)PC(Spirtesetal.,2000),IC(Pearl,2000)algorithm动态贝叶斯网络DBN:DynamicBayesiannetworks•Dealingwithtime•Inmanysystems,dataarrivessequentially•DynamicBayesnets(DBNs)canbeusedtomodelsuchtime-series(sequence)data•SpecialcasesofDBNsinclude–State-spacemodels–HiddenMarkovmodels(HMMs)SoftwareToolsMicrosoft’sMSBNXBNTKevinMurphy.BayesNetToolboxforMatlab(BNT).~murphyk/Software/BNT/bnt.html,2001.参考文献(美)拉塞尔，(美)诺文著.姜哲等译.人工智能—一种现代方法(第二版)，北京：人民邮电出版社，2004.6.(Chapter13,14,15,20).KevinPatrickMurphy.DynamicBayesianNetworks:Representation,Inferencea