贝叶斯网络的结构和建造

贝叶斯网络的结构和建造

20世纪80年代，伯斯基网络成功应用于专家系统，成为一种流行的方法，用于表达不确定性知识和论证。近几年研究者们进一步研究直接从数据中学习并生成Bayesian网络的方法,包括Bayesian方法、类Bayesian方法和非Bayesian方法,为Bayesian网络用于数据采掘和知识发现开辟了道路。这些新的方法和技术还在发展之中,但是已经在一些数据建模问题中显示出令人瞩目的效果。1局部概率分布Bayesian网络是一个带有概率注释的有向无环图。这个图模型能表示大变量集合的联合概率分布,可以分析大量变量之间的相互关系,利用Bayesian方法的学习和统计推断功能,实现预测、分类、聚类、因果分析等数据采掘任务。关于一组变量X={X1,X2,…,Xn}的Bayesian网络由以下两部分组成:1)一个表示X中变量的条件独立断言的网络结构S;2)与每一个变量相联系的局部概率分布集合P。S是一个有向无环图,S中的节点一对一地对应于X中的变量,节点之间缺省弧线表示条件独立。S和P定义了X的联合概率分布。为了建立Bayesian网络,第1步,必须确定为建立模型有关的变量及其解释。第2步,建立一个表示条件独立断言的有向无环图。根据概率乘法公式有p(x)=n∏i=1p(xi|x1,x2,⋯,xi-1).(1)p(x)=∏i=1np(xi|x1,x2,⋯,xi−1).(1)用Pai表示变量Xi的父节点集,则p(x)=n∏i=1p(xi|Ρai).(2)p(x)=∏i=1np(xi|Pai).(2)于是,为了决定Bayesian网络的结构,需要:1)将变量X1,X2,…,Xn按某种次序排序;2)决定满足式(2)的父节点集Pai(i=1,2,…,n)。从原理上说,如何从n个变量中找出适合条件独立的顺序,是一个组合爆炸问题。因为要比较n!种变量顺序。不过,通常可以在现实问题中决定因果关系,而且因果关系一般都对应于条件独立的断言。因此,可以从原因变量到结果变量划一个带箭头的弧来直观表示变量之间的因果关系。第3步,指派局部概率分布p(xi|Pai)。在离散的情形,需要为每一个变量Xi的父节点集的各个状态指派一个分布。显然,以上各步可能交叉进行,而不是简单的顺序进行可以完成的。2局部分布函数及参数假设变量组X=(X1,X2,…,Xn)的联合概率分布可以编码在某个网络结构S中,即p(x|θs‚Sh)=n∏i=1p(xi|Ρai,θi‚Sh)‚(3)p(x|θs‚Sh)=∏i=1np(xi|Pai,θi‚Sh)‚(3)其中:θi是分布p(xi|Pai,θi,Sh)的参数向量,θs是参数组(θ1,θ2,…,θn)的向量,而Sh表示物理联合分布可以依照S被分解的假设。此外,假设从X的物理联合概率分布得到一个随机样本D={x1,…,xN}。于是Bayesian网络的概率学习问题可以简单地表示成:给定随机样本D,计算后验分布p(θs|D,Sh)。假定变量Xi∈X是离散的,有ri个可能的值x1i,x2i,…,xrii,一个分布对应于Pai的一个状态。也就是说,假定p(xki|Ρjai,θi‚Sh)=θijk>0‚i=1,2,⋯,n;j=1,2,⋯,qi;k=1,2,⋯,ri‚(4)p(xki|Pjai,θi‚Sh)=θijk>0‚i=1,2,⋯,n;j=1,2,⋯,qi;k=1,2,⋯,ri‚(4)其中:P1ai,P2ai,…,Pqiai表示Pai的qi个取值状态,qi=∏Xi∈Ρairi。θi=((θijk)rik=2)qij=1是参数,θij1没有列入,因为θij1=1-ri∑k=2θijk,可以通过计算得到。为方便起见,定义参数向量θij=(θij2‚θij3‚⋯‚θijri)‚i=1‚2‚⋯‚n；j=1‚2‚⋯‚qi.给定局部分布函数,需要有以下两个假设,才能以封闭的形式计算后验分布p(θs|D,Sh):1)在随机样本D中没有缺失数据,这时又称D是完整的;2)参数向量θij是相互独立的,即p(θs|Sh)=n∏i=1qi∏j=1p(θij|Sh)。这就是参数独立假设。在以上两个假设下,对于给定的随机样本D,参数仍然保持独立,即p(θs|D,Sh)=n∏i=1qi∏j=1p(θij|D,Sh).(5)于是可以独立地更新每一个参数向量θij。假设每一个参数向量θij有先验Dirichlet分布Dir(θij|αij1,αij2,…,αijri),则后验分布为p(θij|D,Sh)=Dir(θij|αij1+Νij1‚αij2+Νij2‚⋯‚αijri+Νijri),(6)其中Nijk是D中Xi=xki且Pai=Pjai事例的数目。现在可以计算D中第N+1个事例出现的概率p(xΝ+1|D,Sh)=Ep(θs|D,Sh)(ri∏i=1θijk)。利用参数对给定D保持独立,可以计算数学期望:p(xΝ+1|D,Sh)=∫n∏i=1θijkp(θs|D,Sh)dθ=n∏i=1∫θijkp(θij|D,Sh)dθij.通过计算可得p(xΝ+1|D,Sh)=n∏i=1αijk+Νijkαij+Νij‚(7)其中αij=ri∑k=1αijk且Νij=ri∑k=1Νijk.当样本数据不完全时,一般要借助于近似方法,如Monte-Carlo方法,Gaussian逼近,以及EM(期望-极大化)算法求ML(极大似然)或MAP(极大后验)等。尽管有成熟的算法,其计算开销是比较大的。3网络结构的确定当不能确定Bayesian网络的结构时,可以用Bayesian方法从给定数据中学习网络的结构。由于数据采掘面对的是大量数据,一时往往难以断定变量之间的关系,因此这个问题更具有现实意义。首先定义一个随机变量Sh,表示网络结构的不确定性,并赋予先验概率分布p(Sh)。然后计算后验概率分布p(Sh|D)。根据Bayesian定理有p(Sh|D)=p(Sh,D)/p(D)=p(Sh)p(D|Sh)/p(D)‚(8)其中:p(D)是一个与结构无关的正规化常数,p(D|Sh)是边界似然。于是确定网络结构的后验分布只需要为每一个可能的结构计算数据的边界似然。在无约束多项分布、参数独立、采用Dirichlet先验和数据完整的前提下,数据的边界似然正好等于每一个(i,j)对的边界似然的乘积,即p(D|Sh)=n∏i=1qi∏j=1Γ(αij)Γ(αij+Νij)ri∏k=1Γ(αijk+Νijk)Γ(αijk).(9)该公式由Cooper和Herskovits于1992年首次给出。在一般情况下,n个变量的可能的网络结构数目大于以n为指数的函数。逐一排除这些假设是很困难的。可以使用两个方法来处理这个问题:“模型选择”和“有选择的模型平均”。前者是从所有可能的模型(结构假设)中选择一个“好的”模型,并把它当作正确的模型。后者是从所有可能的模型中选择合理数目的“好”模型,并认为这些模型代表了所有情况。若干研究者(Chickering,Heckerman)的工作表明,使用贪心搜索法选择单个好的模型通常会得到准确的预测。使用Monte-Carlo方法进行模型平均也很有效,甚至可以得到更好的预测。4线上的多模型先验下面是一个使用Bayesian网络进行数据采掘和知识发现的应用实例(Sewell和Shah)。数据来自华盛顿高级中学的10318名高年级学生。每个学生用下列变量及其相应的状态来描述:性别(SEX):男、女;社会经济状态(SES):低、中下、中上、高;智商(IQ):低、中下、中上、高;家长的鼓励(PE):低、高;升学计划(CP):是、否;目标是从数据中发现影响高中学生上大学意向的因素。数据已经整理成表1所示的格式。表中每个数据表示对于5个变量的某种取值组合统计所得到的人数。例如,第一个数据表示对(SEX=男,SES=低,IQ=低,PE=低,CP=是)这种组合统计得到的人数为4。第二个数据则表示对(SEX=男,SES=低,IQ=低,PE=低,CP=否)这种组合统计得到的人数为349。其后的数据表示依次轮换每个变量可能的状态统计得到的人数。变量依照从右到左的顺序轮换,状态则按照上面列出的各变量状态顺序轮换。先假定没有隐藏变量,使用容量为5的等值样本和p(x|Shc)服从均匀分布的先验网络。排除掉SEX和SES有父节点、CP有子节点的网络结构之后,假定其它所有网络结构都是等可能的。因为数据集是完整的,可以用式(8)和式(9)计算网络结构的后验概率。通过对所有网络结构的穷举搜索,发现两个最可能的网络结构(如图1)。右边的网络曾由Spirtes等用非Bayesian方法于1993年选出。最值得怀疑的结果是:社会经济状况对智商有直接的影响。为了考证这个结果,考虑一个新的模型,即将图1中原来模型的直接影响用一个指向SES和IQ的隐藏变量代替。此外还考虑这样的模型,隐藏变量指向SES,IQ和PE,而且在SES—PE和PE—IQ两个连接中分别去掉两个、一个和0个,对每个结构将隐藏变量的状态数从2变到6。使用Laplace逼近的Cheeseman-Stutz变体计算这些模型的后验概率。为了找最大后验构成˜θs,使用EM算法,并在带有不同的随机初始化的θs的100次运行中取最大的局部极大值。这些模型中带有最大后验概率的一个如图2所示。这个模型的可能性比不含有隐藏变量的最好模型高2×1010倍。假定没有忽略合理的模型,那么有强烈的证据表明:有一个隐藏变量在影响着SES(社会经济状态)和IQ(智商)。分析图2可知,隐藏变量对应于“家长的素质”。5全样本信息的使用使用Bayesian方法从先验信息和样本信息学习Bayesian网络的结构和概率分布,进而建立Bayesian网络,为Bayesian网络在数据采掘和知识发现中的应用开辟了道路。与其它用于数据采掘的方法相比,Bayesian网络有如下特点:1)可以综合先验信息和样本信息,既可避免只使用先验信息可能带来的主观偏见,也可避免只使用样本信息带来的噪音影响。并且,这在样本难得或者代价高昂时特别有用;2)能够处理不完整数据问题;3)可以发现数据间的因果关系;2)和3)在实际问题中经常遇到,而且用其它模型难以处理。4)有成熟的近似算法。虽然任意Bayesian网络的概率推断是NP难题,但是很