贝叶斯网络结构学习的发展与展望_贺炜

文章编号:100220411(2004)022*******

贝叶斯网络结构学习的发展与展望

贺　炜,潘　泉,张洪才

(西北工业大学自动控制系613信箱,陕西西安　710072)

摘　要:从最初的概率贝叶斯网络构建阶段到涌现大量研究成果的因果贝叶斯网络结构学习阶段,本文完整地回顾了贝叶斯网络结构学习的整个发展历程,并对该领域当前存在的问题及相关研究进行分析论述,给出了研究展望.值得一提的是,贝叶斯网络结构学习正在成为因果数据挖掘的主流.

关键词:概率贝叶斯网络;因果贝叶斯网络;贝叶斯网络结构学习;因果数据挖掘

中图分类号:TP18 文献标识码:A

Development and Prospect of B ayesian N et w ork Structure Learning

HE Wei,PAN Quan,ZHAN G Hong2cai

(Depart ment of Cybernetics,Northwest Polytechnical U niversity,Xiπan　710072,Chi na) Abstract:From the initial stage of probabilistic Bayesian network construction to the flourishing stage of causal Bayesian network structure learning,this paper firstly reviews Bayesian network structure learning.Then its current problems,related researches and prospects are discussed.It is worth of pointing out that the research of Bayesian network structure learning is becoming the mainstream in the field of causal data mining.

K eyw ords:probabilistic Bayesian network;causal Bayesian network;Bayesian network structure learning;

causal data mining

1　基本概念(B asic concepts)

1.1　贝叶斯网络

贝叶斯网络[1～9]又称为信念网络,是一种图型化的模型,能够图形化地表示一组变量间的联合概率分布函数.一个贝叶斯网络包括了一个结构模型和与之相关的一组条件概率分布函数.结构模型是一个有向无环图,其中的节点表示了随机变量,是对于过程、事件、状态等实体的某特性的描述,边则表示变量间的概率依赖关系.图中的每个节点都有一个给定其父节点情况下该节点的条件概率分布函数.这样,一个贝叶斯网络就用图形化的形式表示了如何将与一系列节点相关的条件概率函数组合成为一个整体的联合概率分布函数.因果贝叶斯网络是指具有因果含义的贝叶斯网络,其中每个节点的父节点被解释为该节点相对于模型中其它节点的直接原因.为了与之区别,有时也将没有因果意义的贝叶斯网络称为概率贝叶斯网络.

贝叶斯网络作为一种图形化的建模工具,具有一系列的优点:(1)贝叶斯网络将有向无环图与概率理论有机结合,不但具有了正式的概率理论基础,同时也具有更加直观的知识表示形式.一方面,它可以将人类所拥有的因果知识直接用有向图自然直观地表示出来,另一方面,也可以将统计数据以条件概率的形式融入模型.这样贝叶斯网络就能将人类的先验知识和后验的数据无缝地结合,克服框架、语义网络等模型仅能表达处理定量信息的弱点和神经网络等方法不够直观的缺点;(2)贝叶斯网络与一般知识表示方法不同的是对于问题域的建模.因此当条件或行为等发生变化时,不用对模型进行修正;(3)贝叶斯网络可以图形化表示随机变量间的联合概率,因此能够处理各种不确定性信息;(4)贝叶斯网络中没有确定的输入或输出节点,节点之间是相互影响的,任何节点观测值的获得或者对于任何节点的干涉,都会对其他节点造成影响,并可以利用贝叶斯网络推理来进行估计预测;(5)贝叶斯网络的推理是以贝叶斯概率理论为基础的,不需要外界的任何推理机制,不但具有理论依据,而且将知识表示与知

第33卷第2期2004年4月　信息与控制

Information and Control

Vol.33,No.2　

　Apr.,2004　

收稿日期:2003-03-17

　基金项目:国家自然科学基金资助项目(60172037);教育部“跨世纪优秀人才培养计划”基金资助项目(教技函[2001]1号)

识推理结合起来,形成统一的整体[11～13].

由于上述优点,贝叶斯网络很快就成为人工智能领域进行不确定性推理和建模的一个有效工具.利用贝叶斯网络对于事件或者属性间的带有不确定性的相互关系进行建模和推理在医学诊断、自然语言理解、故障诊断、启发式搜索、图像解释、目标识别以及不确定推理和预测等方面产生了很多成功的应用[14～17],这些应用大致可分为建立系统模型以辅助决策、实现特征融合以及进行分类的数据分析三大类.

1.2　贝叶斯网络结构学习

一般贝叶斯网络的构建是首先由相关领域的专家根据事物间的关系来确定出结构模型,即有向无环图,然后再利用其它方法确定每个节点的条件概率,但这样构建的网络模型无法保证其客观性和可靠性.因此,研究人员尝试引入客观的观测数据,希望通过将观测数据与专家知识相结合来共同构建贝叶斯网络,并进一步在没有专家先验知识的情况下,尝试完全从观测数据中学习得到网络结构和参数.其中网络结构的学习不但是整个学习过程的基础,并且是一个NP难题[18],因此更吸引了大量研究人员的注意.

研究人员借鉴统计学领域对多变量联合概率分布近似分解的方法[19],从多个角度对该问题进行研究,形成了基于独立性检验和基于评价与搜索的两大类算法[20].在一系列假设下,研究人员通过将先验信息与观测数据相结合,实现了多种网络结构模型的学习算法,进而提出了在没有任何先验信息情况下的相应算法.最近的研究开始减弱甚至放弃某些假设,从更一般意义下研究网络结构的学习.因果贝叶斯网络结构模型的学习有时也称为因果发现或因果挖掘.这是因为数据的处理所获得的结构模型反映了事物间因果关系的知识.从广义的角度讲,因果数据挖掘可以认为是从数据中发现有关因果性知识的过程.

2　概率贝叶斯网络构建阶段(Construction stage of probabilistic B ayesian net w ork)

统计分析常常要对多变量随机系统进行建模,以便进行密度估计等各种统计分析.用联合概率分布函数能清楚地描述多变量随机系统的统计特性,但难以获得数学解析公式表达.利用独立变量的联合概率分布能进行分解的特性,研究人员将较小相关性近似按照独立处理,从而实现联合概率的近似分解和图形表示,这就是早期的贝叶斯网络构建过程.我们称这一阶段的研究为概率贝叶斯网络构建阶段.

较早的研究是在1968年,C.K.Chow和C.N. Liu[19]给出了如何通过构建一个树状网络模型来对给定的联合概率分布P进行分解表示的算法.该算法用Kullback2Leibler交叉熵来衡量模型与联合概率P的近似程度,并对于变量间的独立性进行检验,以保证能找到最佳结构.该算法中所蕴涵的思想是后来所有相关研究的基础.G.Rebane和J udea Pearl[21]在1987年将Chow2Liu算法做了改进,将之扩展到多树结构,同时提出了利用条件独立性关系来确定边的方向的方法,开始了构建有向图的研究. Wermuth和Lauritzen[22]在1983年给出了一个通过检验变量间的独立性关系来确定节点之间是否存在边、从而构建出有向图的理论性算法,该算法所得出的网络结构不再限于树状,使得研究开始走向一般网络结构的学习.

概率贝叶斯网络逐渐形成一种常用的随机多变量系统的建模和分析工具.随后人工智能等领域也开始从构建因果系统模型的角度对贝叶斯网络进行研究.这样就进入下一阶段———因果贝叶斯网络结构学习阶段.

3　因果贝叶斯网络结构学习阶段(Learning stage of causal B ayesian net w ork)

20世纪80年代末,人工智能领域的研究人员注意到贝叶斯网络对不确定系统的建模能力后,开始利用它来构建不确定性专家系统,进行诊断、推理、估计等任务.贝叶斯网络构建的专家系统能够对于不同事物之间的因果关系进行定性和定量的描述,并根据相应的观测或干涉作出推理.这类模型一般是由领域专家根据主观的因果知识构建的.引入观测数据可以减少构建模型的主观性,并增加其可靠性.因此,如何结合先验因果知识来构建贝叶斯网络就成为一个重要的研究问题.

1991年,Cooper和Herskovits提出的K2算法[23]是结合先验信息进行贝叶斯网络结构学习的一个有实际意义的重要算法,在整个研究发展过程中占有重要地位.该算法在给定节点顺序这一先验信息的情况下,利用贝叶斯概率作为标准来评价模型与数据的符合程度,通过不断向网络中增加能提高评价指针的边的贪婪搜索方法来找出最佳网络结构.基于这一思路的方法被统称为基于评价和搜索

681信　息　与　控　制 33卷　

的结构学习方法.实际在1991年Herskovits和Cooper就已经提出了与K2算法原理相同的Kutato 算法[23],只是由于采用的评价指针为熵,计算量也稍大于K2算法,因此影响要小些.Heckerman等人在1994年的一份微软研究院技术报告[24]中,对于给定各种先验信息的情况下,如何进行贝叶斯网络结构学习进行了系统的研究,给出了将先验知识与统计数据相结合的统一框架的结构学习算法.

研究人员同时也尝试在没有任何先验信息的情况下进行贝叶斯网络结构的学习.Singh和Valtor2 ta[25]在1995年提出了一种混合算法.该算法首先通过对于一种基于独立性检验的算法———PC算法进行改进———来获得节点的顺序,然后再用K2算法学习网络结构.Lam[26]在1994年提出的算法用最小描述长度作为衡量标准,完全通过搜索与评价来找出正确的网络结构,而不需要知道节点顺序等先验信息.Wallace[27]在1996年发表的利用最小信息长度作为衡量标准的评价搜索算法也不需要节点顺序,并能取得相当好的效果.

沿着Pearl1988年的Boundary DA G算法[2]的思路,研究人员尝试通过检验变量间的独立性关系来构建网络结构,这类算法称为基于独立性检验的结构学习算法.首先是Srinivas[28]在1990年对Boundary DA G算法进行了扩展,在已知部分节点顺序和其它一些领域先验知识的情况下,通过独立性检验来重新构建网络结构.Spirtes[29]在1990年提出的SGS算法在不给定节点顺序的情况下,完全利用独立性检验来学习网络结构.但这是一个NP难题.1991年Spirtes对SGS算法的搜索策略进行改进,提出了PC算法[30].该算法对于稀疏网络的结构学习表现出较小的计算量.1997年,Jie Cheng提出的基于互信息的独立性检验构建算法[20]表现出非常好的效果.这是一种基于定量互信息检验的网络结构学习算法,算法假设将两节点A、B间的非Collider节点C放入条件集中会减少A、B节点间的互信息量,而将Collider节点D放入则会增加A、B 间的互信息量.通过这样的启发式评价函数来找到相应节点间的割集,进而确定节点间是否存在边.

初期研究是将领域专家的先验知识与观测数据相结合来构建相应的因果贝叶斯网络.随后研究人员又进一步尝试在较少的先验知识甚至无任何先验知识下,完全从观测数据中构建恰当的贝叶斯网络模型.于是整个发展阶段都是以构建特定领域的因果贝叶斯网络模型为目的.这就使得研究对象是一个相对狭窄的、已经由领域专家预先挑选处理过的数据集和变量集合,算法所要做的就是根据这些变量之间的统计特性来推断出他们之间存在的因果关系.这也是这类算法中所做的许多前提假设能够成立的原因.

4　当前存在的问题及相关研究(Existent problems and related researches)

4.1　马尔可夫等价类问题及其研究

在利用观测数据构建因果贝叶斯网络的研究中,人们证明了利用观测数据仅能确定贝叶斯网络的马尔可夫等价类[31].下面是马尔可夫等价类的定义:

马尔可夫等价类—表示了同样的独立性关系的网络结构被称为是属于同一马尔可夫等价类的.

同一马尔可夫等价类内的网络结构无法通过观测数据来区分开.这样网络中有些边的方向无法确定.在有领域专家存在的情况下,还可以利用专家的领域知识来帮助确定这些边的方向,但在没有专家先验信息的情况下,这便成为观测数据学习网络结构的一个根本缺陷.

研究人员尝试将观测数据与可控试验产生的实验数据结合起来解决这一问题.Gregory[32]在1999年给出了将实验数据与观测数据相结合来学习网络结构的方法.Simon[33]和Murphy[34]在2001年都分别提出利用主动学习来学习贝叶斯网络结构的思想.其主要思想是利用某评价指针来估计能对下一步结构学习提供最大信息量的数据的形式,然后据此给出可控试验应采取的条件和形式.得到的试验数据应具有较高的信息量,并可将之与前面的观测数据学习结果相结合来进一步确定网络结构.因此,对于观测数据学习因果结构时无法区分边的方向的问题,可以通过这种结合试验数据的方法来解决.另外,Tian[35]在2001提出通过检测底层数据模型的变化来进行因果贝叶斯网络结构发现的方法,也可以在某种程度上解决这一问题.

4.2　前提假设过强问题及其研究

在贝叶斯网络结构学习中,人们发现算法的许多假设在实际中常常无法满足.因此,研究人员放松贝叶斯网络结构学习的前提假设,如数据完整性假设、无选择偏好假设和变量离散化假设等,尝试在更一般的情况下进行贝叶斯网络结构的学习.数据完整性假设表明数据集中不存在缺失项.对于存在缺失项的情况,人们提出了三种解决方法.第一种是抛

781

2期 贺　炜等:贝叶斯网络结构学习的发展与展望

弃存在缺失项的数据,这样会造成两个问题,一是会引起数据集变小,可能造成统计样本不够,二是可能这些缺失项的出现不是随机的,抛弃这些数据项会使得数据集无法正确反映实际;第二种方法是给缺失的值赋一个特定的值,如“无”,但这样有可能改变底层的统计关系;第三种方法是给缺失的值赋一个恰当的值,最好与原值近似,有许多方法来指派丢失数据项[36].Friedman[37]将EM算法与模型选择相结合,实现了缺失项估计和结构学习.Chickering[38]用近似评价函数来处理缺失项.

无选择偏好假设表明该数据集是对于实际总体的无偏采样.匹兹堡大学的Gregory F.Cooper[39]在2000年提出了一种存在选择偏好情况下的贝叶斯网络学习算法.该算法通过在有向图中引入一个新的变量节点S来表示具体的数据点是否会被采样到,并在那些会影响采样的变量节点与S之间建立有向边来表示他们对于采样的影响.通过对于这样一个修正网络的学习,从理论上就能避免选择偏好的影响.

许多算法都有变量离散化假设,即假设所面临的变量都是离散变量.对于实际系统中存在连续变量的情况,可以直接采取离散化的方法,如Fried2 man和G oldszmidt[40]在1996年提出根据评价函数来自动确定离散化的门限值,并据此将连续变量离散化的方法.也有研究人员尝试直接对于连续变量的贝叶斯网络或混合有连续变量和离散变量的网络结构进行学习.Heckerman和G eiger[41]在1995提出的贝叶斯评价标准能够处理离散和高斯连续分布情况下网络结构的评价问题,从而能够对连续和混合贝叶斯网络结构进行学习.1996年R.Hofmann 和V.Tresp[42]利用非线性条件密度估计来学习连续变量的条件概率,从而学习贝叶斯网络结构.1997年S.Monti和G. F.Cooper[43]提出通过人工神经网络来估计条件密度以学习连续变量的贝叶斯网络结构.上面这些方法较好地处理了连续变量的贝叶斯网络结构的学习问题.

5　因果数据挖掘初露端倪(Emergence of causal data mining)

5.1　因果发现算法的提出

利用因果贝叶斯网络的理论,研究人员研究因果关系的发现.Cooper[44]在1997年提出了一种简单易行的因果关系挖掘算法.该算法通过假定已知一个非结果节点W,利用贝叶斯网络结构的性质,对数据集进行搜索,找出满足条件的因果关系.Sil2 verstein[45]在1998年尝试了大型事物数据库的挖掘.

5.2　实际需要的呼唤

信息处理所面临的海量数据导致了数据挖掘的理论出现和算法发展.数据挖掘关联算法能对数据中隐含的变量之间的关联关系进行挖掘与发现;分类算法则能对于各个观测变量与目标变量之间的关联关系进行建模,从而根据观测变量的值对目标变量的值进行预测[46].然而,这些算法大都是对于事物之间的统计关联关系的挖掘发现,没有涉及到事物之间的底层因果结构.与统计关联规则相比,因果规则能够提供事物间的内在机制性的规律和知识,使人们能对干涉这些事物所产生的结果作出判断和预测.当已有的挖掘算法挖掘出有用的统计关联知识后,人们自然进一步期望能够获得对于事物的更加本质的认识.因此,在因果贝叶斯网络学习理论不断发展的基础上,各种因果知识发现的研究也不断展开[47～49].

6　因果挖掘的前景(Prospect of the causal data mining)

因果数据挖掘的研究仍然处于理论阶段,仅有少量实际应用[49,50].这是由于贝叶斯网络结构学习理论的发展是在一个相对单纯的数据背景下进行的,与数据挖掘所面临的情况不同,直接将这些算法应用到环境复杂的数据挖掘应用中,往往难以得到有意义的结果;同时,数据挖掘本身是一个人机交互的多步过程,需要前处理、算法和后处理相结合才有可能得出有意义的结论.另一方面,因果关系挖掘是对于数据中比统计关联规则更高层次的因果知识的发现,因此,如果能够在统计关联挖掘结果的基础上进行因果关系的挖掘,就能借用前者的成果,在已经加工处理过的信息的基础上,进一步精炼,得到更深层次的因果信息.

因此,成功的因果数据挖掘应是以贝叶斯网络结构学习理论为核心,将算法根据数据挖掘的要求进行改进,并与前处理相结合,同时将可控试验与后处理相结合,并与操作人员进行合理恰当的交互,从而达到最终发现因果关系的目的.我们已经开展了这方面的研究工作.由于因果知识能提供关于事物的本质的认识,对干涉的结果作出预测,因此因果挖掘有望在医学、经济、网络等领域中获得巨大的成功.

881信　息　与　控　制 33卷　

参　考　文　献(R eferences)

[1]　Jordan M I.Learning in Graphical Models[M].Massachusetts:

MIT Press,1998.

[2]　Pearl J.Probabilistic Reasoning in Intelligent Systems:Networks

of Plausible Inference[M].San Mateo CA:Morgan Kaufman

Publishers,1988.

[3]　Jensen F V.An Introduction to Bayesian Networks[M].New

Y ork:Springer,1996.

[4]　Jensen F V.Bayesian Networks and Decision Graphs[M].New

Y ork:Springer,2001.

[5]　Pearl J.Graphical Models for Probabilistic and Causal Reasoning

[A].The Computer Science and Engineering Handbook[M].

Boca Raton,FL,USA:CRC Press,1997,Volume1.697～

714.

[6]　Lauritzen S.Graphical Models[M].Oxford:Oxford University

Press,1996.

[7]　Cowell R G,Dawid A P,Lauritzen S L,et al.Probabilistic Net2

works and Expert Systems[M].New Y ork:Springer,1999.

[8]　刘志强.因果关系、贝叶斯网络与认知图[J].自动化学报,

2001,27(4):552～566.

[9]　胡玉胜,涂序彦,崔晓瑜,等.基于贝叶斯网络的不确定性知

识的推理方法[J].计算机集成制造系统2CIMS,2001,7

(12):65～68.

[10]　Huang C,Darwiche A.Inference in belief networks:a procedu2

ral guide[J],International Journal of Approximate Reasoning,

1996,15(3):225～263.

[11]　Dawid A P.Applications of a general propagation algorithm for

probabilistic expert systems[J].Statistics and Computing,

1992,2(2):25～36.

[12]　Buntine W L.Operations for learning with graphical models

[J].Journal of Artificial Intelligence Research,1994,2:159～

225.

[13]　Lauritzen S L,Spiegelhalter D J.Local computations with prob2

abilities on graphical structures and their application to expert

systems[J].Journal of the Royal Statistical Society,1988,50

(2):157～224.

[14]　Sahely B S G E,Bagley D M.Diagnosing upsets in anaerobic

waster water treatment using Bayesian belief networks[J].

Journal of Environmental Engineering,2001,127(4):302～

310.

[15]　Neil M,Fenton N,Forey S,et https://www.sodocs.net/doc/43696372.html,ing Bayesian belief net2

works to predict the reliability of military vehicles[J].Comput2 ing and Control Engineering Journal,2001,12(1):11～20. [16]　Ng G,Ong https://www.sodocs.net/doc/43696372.html,ing a qualitative probabilistic network to ex2

plain diagnostic reasoning in an expert system for chest pain diag2

nosis[A].Computers in Cardiology2000[C].Cambridge,

Massachusetts,USA:IEEE,2000.569～573.

[17]　傅　军,贺　炜,阎建国,等.贝叶斯网络在柴油机动力装置

故障诊断中的应用[J].上海海运学院学报,2001,22(3):68

～71.[18]　Chickering D M.Learning Bayesian networks is NP2complete

[A].Learning from Data:AI and Statistics V[M].New

Y ork:Springer,1996.121～130.

[19]　Chow C K,Liu C N.Approximating discrete probability distri2

butions with dependence trees[J].IEEE Transactions on Infor2

mation Theory,1968,IT-14(3):462～467.

[20]　Jie C,Greiner R.Learning Bayesian networks from data:an in2

formation2theory based approach[J].Artificial Intelligence,

2002,137(1-2):43～90.

[21]　Rebane G,Pearl J.The recovery of causal polytrees from statis2

tical data[A].Third Annual Conference on Uncertainty in Arti2 ficial Intelligence[C].Amsterdam:Morgan Kaufmann,1987.

222～228.

[22]　Wermuth N,Lauritzen S.Graphical and recursive models for

contingency tables[J].Biometrika,1983,70(1):537～552.

[23]　Herskovits https://www.sodocs.net/doc/43696372.html,puter2based Probabilistic2Network Construc2

tion[D].USA:Stanford University,1991.

[24]　Heckerman D,G eiger D.Chickering D M.Learning Bayesian

networks:the combination of knowledge and statistical data[J].

Machine Learning,1995,20(3):197～243.

[25]　Singh M,Valtorta M.Construction of Bayesian network struc2

tures form data:a brief survey and an efficient algorithm[J]In2

ternational Journal of Approximate Reasoning,1995,12(2):111

～131.

[26]　Lam W,Bacchus F.Learning Bayesian belief networks:an ap2

proach based on the MDL principle[J].Computational Intelli2

gence,1994,10(4):269～293.

[27]　Wallace C,K orb K B,Dai H.Causal discovery via MML[A].

Proceedings of the Thirteenth International Conference on Ma2

chine Learning[C].San Francisco:Morgan Kaufmann Publish2

ers,1996.516～524.

[28]　Srinivas S,Russell S,Agogino A.Automated construction of

sparse Bayesian networks from unstructured probabilistic models

and domain information[A].Fifth Annual Conference on Un2

certainty in Artificial Intelligence[C].Amsterdam:Morgan

Kaufmann,1990.295～308.

[29]　Spirtes C,G lymour P,Scheines R.Causality from probability

[A].Evolving Knowledge in Natural Science and Artificial In2

telligence[M].London:Piman,1990.181～199.

[30]　Spirtes P,G lymour C,Scheines R.An algorithm for fast recov2

ery of sparse causal graphs[J].Social Science Computer Re2

view,1991,9(1):62～72.

[31]　Pearl J,Wermuth N.When can association graphs admit a

causal interpretation[A].The Fourth International Workshop

on Artificial Intelligence and Statistics[C]https://www.sodocs.net/doc/43696372.html,uderdale,

FL:Springer,1993.41～150.

[32]　Cooper G F,Y oo C.Causal discovery from a mixture of experi2

mental and observational data[A].Fifth Annual Conference on

Uncertainty in Artificial Intelligence[C].Morgan Kaufmann,

CA:Morgan Kaufmann,1999.116～125.

[33]　Tong S,K oller D.Active learning for structure in Bayesian net2

works[A].Proceedings of the International Joint Conference on

981

2期 贺　炜等:贝叶斯网络结构学习的发展与展望

Artificial Intelligence[C].Seattle,Washington:Morgan Kauf2

mann,2001.863～869.

[34]　Murphy K.Active Learning of Causal Bayes Net Structure[R].

Berkeley:University of California,2001.

[35]　Tian J,Pearl J.Causal discovery from changes[A].Seven2

teenth Annual Conference on Uncertainty in Artificial Intelli2

gence[C].Seattle,Washington,USA:Morgan Kaufmann,

2001.512～521.

[36]　Little R J A,Rubin D B.Statistical Analysis with Missing Data

[M].New Y ork:John Wiley&Sons,1987.

[37]　Friedman N.The Bayesian structural EM algorithm[A].Four2

teenth Annual Conference on Uncertainty in Artificial Intelli2

gence[C].San Francisco,CA:Morgan Kaufmann,1998.125

～133.

[38]　Chickering D M,Heckerman D.Efficient approximations for

the marginal likelihood of incomplete data given a Bayesian net2

work[A].Twelfth Annual Conference on Uncertainty in Artifi2

cial Intelligence[C].Stanford,USA:Morgan Kaufmann,

1996.158～168.

[39]　Cooper G F.Causal modeling and discovery under selection

[A].Sixteenth Annual Conference on Uncertainty in Artificial

Intelligence[C].Stanford,California,USA:Morgan Kauf2

mann,2000.98～106.

[40]　Friedman N,G oldszmidt M.Discretizing continuous attributes

while learning Bayesian networks[A].Proceedings of the Thir2

teenth International Conference on Machine Learning[C].Bari,

Italy:Morgan Kaufmann,1996.157～165.

[41]　Heckerman D,G eiger D.Learning Bayesian networks:a unifi2

cation for discrete and G aussian domains[A].Eleventh Annual

Conference on Uncertainty in Artificial Intelligence[C].Mon2

treal,Quebec,Canada:Morgan Kaufmann,1995.274～284. [42]　Hofmann R,Tresp V.Discovering structure in continuous vari2

ables using Bayesian networks[A].Advances in Neural Infor2

mation Processing Systems[M].Cambridge,MA:MIT Press,

1996.500～506.

[43]　Monti S,Cooper G F.Learning Bayesian belief networks with

neural network estimators[A].Proceedings of the Conference

on Neural Information Processing Systems[C].Massachusetts:

MIT,1996.579～584.

[44]　Cooper G F.A simple constraint2based algorithm for efficiently

mining observational databases for causal relationships[J].Data

Mining and Knowledge Discovery,1997,1(2):203～224. [45]　Silverstein C,Brin S,Motwani R,et al.Scalable techniques for

mining causal structures[A].Proceedings of the1998Interna2

tional Conference on Very Large Data Bases[C].New Y ork,

N Y:Morgan Kaufmann,1998.594～605.

[46]　韩家炜.数据挖掘概念与技术[M].北京:机械工业出版社,

2001.

[47]　Dai H,K orb K B,Wallace C S,et al.A study of causal discov2

ery with weak links and small samples[A].Proceedings of the

Fifteenth International Joint Conference on Artificial Intelligence

[C].San Francisco,USA:Morgan Kaufmann Publishers,

1997.1304～1309.

[48]　Spirtes P,Cooper G.An experiment in causal discovery using a

pneumonia database[A].Proceedings of AI and Statistics99

[C].Florida:Morgan Kaufmann,1999.157～165.

[49]　Mani S,Cooper G F.A study in causal discovery from popula2

tion2based infant birth and death records[A].Proceedings of

the AMIA Annual Fall Symposium[C].Philadelphia,PA:

Hanley and Belfus Publishers,1999.315～319.

[50]　Mani S,Cooper G F.Causal discovery from medical textual data

[A].Proceedings of the AMIA Annual Fall Symposium[C].

Philadelphia,PA:Hanley and Belfus Publishers,2000.542～

546.

作者简介

贺　炜(1977-),男,博士生.研究领域为非确定性人工智能,数据挖掘.

潘　泉(1961-),教授,博士生导师.研究领域为自适应系统的建模、估计与控制,信息融合,C3I,小波理论及应用,多尺度系统理论等.

张洪才(1938-),男,教授,博士生导师.研究领域为动态系统建模、估计与仿真,非线性系统的估计与控制,系统的故障诊断与容错控制,多目标跟踪与多传感器数据融合等.

091信　息　与　控　制 33卷　

如何使用贝叶斯网络工具箱

如何使用贝叶斯网络工具箱 2004-1-7版 翻译：By 斑斑（QQ：23920620） 联系方式：banban23920620@https://www.sodocs.net/doc/43696372.html, 安装 安装Matlab源码 安装C源码 有用的Matlab提示 创建你的第一个贝叶斯网络 手工创建一个模型 从一个文件加载一个模型 使用GUI创建一个模型 推断 处理边缘分布 处理联合分布 虚拟证据 最或然率解释 条件概率分布 列表（多项式）节点 Noisy-or节点 其它（噪音）确定性节点 Softmax（多项式 分对数）节点 神经网络节点 根节点 高斯节点 广义线性模型节点 分类 / 回归树节点 其它连续分布 CPD类型摘要 模型举例 高斯混合模型 PCA、ICA等 专家系统的混合 专家系统的分等级混合 QMR 条件高斯模型 其它混合模型

参数学习 从一个文件里加载数据 从完整的数据中进行最大似然参数估计 先验参数 从完整的数据中（连续）更新贝叶斯参数 数据缺失情况下的最大似然参数估计（EM算法） 参数类型 结构学习 穷举搜索 K2算法 爬山算法 MCMC 主动学习 结构上的EM算法 肉眼观察学习好的图形结构 基于约束的方法 推断函数 联合树 消元法 全局推断方法 快速打分 置信传播 采样（蒙特卡洛法） 推断函数摘要 影响图 / 制定决策 DBNs、HMMs、Kalman滤波器等等

安装 安装Matlab代码 1.下载FullBNT.zip文件。 2.解压文件。 3.编辑"FullBNT/BNT/add_BNT_to_path.m"让它包含正确的工作路径。 4.BNT_HOME = 'FullBNT的工作路径'; 5.打开Matlab。 6.运行BNT需要Matlab版本在V5.2以上。 7.转到BNT的文件夹例如在windows下，键入 8.>> cd C:\kpmurphy\matlab\FullBNT\BNT 9.键入"add_BNT_to_path"，执行这个命令。添加路径。添加所有的文件夹在Matlab的路 径下。 10.键入"test_BNT"，看看运行是否正常，这时可能产生一些数字和一些警告信息。（你可 以忽视它）但是没有错误信息。 11.仍有问题？你是否编辑了文件？仔细检查上面的步骤。

贝叶斯网络结构学习的发展与展望_贺炜

文章编号:100220411(2004)022******* 贝叶斯网络结构学习的发展与展望 贺　炜,潘　泉,张洪才 (西北工业大学自动控制系613信箱,陕西西安　710072) 摘　要:从最初的概率贝叶斯网络构建阶段到涌现大量研究成果的因果贝叶斯网络结构学习阶段,本文完整地回顾了贝叶斯网络结构学习的整个发展历程,并对该领域当前存在的问题及相关研究进行分析论述,给出了研究展望.值得一提的是,贝叶斯网络结构学习正在成为因果数据挖掘的主流. 关键词:概率贝叶斯网络;因果贝叶斯网络;贝叶斯网络结构学习;因果数据挖掘 中图分类号:TP18 文献标识码:A Development and Prospect of B ayesian N et w ork Structure Learning HE Wei,PAN Quan,ZHAN G Hong2cai (Depart ment of Cybernetics,Northwest Polytechnical U niversity,Xiπan　710072,Chi na) Abstract:From the initial stage of probabilistic Bayesian network construction to the flourishing stage of causal Bayesian network structure learning,this paper firstly reviews Bayesian network structure learning.Then its current problems,related researches and prospects are discussed.It is worth of pointing out that the research of Bayesian network structure learning is becoming the mainstream in the field of causal data mining. K eyw ords:probabilistic Bayesian network;causal Bayesian network;Bayesian network structure learning; causal data mining 1　基本概念(B asic concepts) 1.1　贝叶斯网络 贝叶斯网络[1～9]又称为信念网络,是一种图型化的模型,能够图形化地表示一组变量间的联合概率分布函数.一个贝叶斯网络包括了一个结构模型和与之相关的一组条件概率分布函数.结构模型是一个有向无环图,其中的节点表示了随机变量,是对于过程、事件、状态等实体的某特性的描述,边则表示变量间的概率依赖关系.图中的每个节点都有一个给定其父节点情况下该节点的条件概率分布函数.这样,一个贝叶斯网络就用图形化的形式表示了如何将与一系列节点相关的条件概率函数组合成为一个整体的联合概率分布函数.因果贝叶斯网络是指具有因果含义的贝叶斯网络,其中每个节点的父节点被解释为该节点相对于模型中其它节点的直接原因.为了与之区别,有时也将没有因果意义的贝叶斯网络称为概率贝叶斯网络. 贝叶斯网络作为一种图形化的建模工具,具有一系列的优点:(1)贝叶斯网络将有向无环图与概率理论有机结合,不但具有了正式的概率理论基础,同时也具有更加直观的知识表示形式.一方面,它可以将人类所拥有的因果知识直接用有向图自然直观地表示出来,另一方面,也可以将统计数据以条件概率的形式融入模型.这样贝叶斯网络就能将人类的先验知识和后验的数据无缝地结合,克服框架、语义网络等模型仅能表达处理定量信息的弱点和神经网络等方法不够直观的缺点;(2)贝叶斯网络与一般知识表示方法不同的是对于问题域的建模.因此当条件或行为等发生变化时,不用对模型进行修正;(3)贝叶斯网络可以图形化表示随机变量间的联合概率,因此能够处理各种不确定性信息;(4)贝叶斯网络中没有确定的输入或输出节点,节点之间是相互影响的,任何节点观测值的获得或者对于任何节点的干涉,都会对其他节点造成影响,并可以利用贝叶斯网络推理来进行估计预测;(5)贝叶斯网络的推理是以贝叶斯概率理论为基础的,不需要外界的任何推理机制,不但具有理论依据,而且将知识表示与知 第33卷第2期2004年4月　信息与控制 Information and Control Vol.33,No.2　 　Apr.,2004　 收稿日期:2003-03-17 　基金项目:国家自然科学基金资助项目(60172037);教育部“跨世纪优秀人才培养计划”基金资助项目(教技函[2001]1号)

贝叶斯网络结构学习及其应用研究_黄解军

收稿日期:2004-01-23。 项目来源:国家自然科学基金资助项目(60175022)。 第29卷第4期2004年4月武汉大学学报#信息科学版 Geomatics and Information Science of Wuhan U niversity V ol.29No.4Apr.2004 文章编号:1671-8860(2004)04-0315-04文献标识码:A 贝叶斯网络结构学习及其应用研究 黄解军1 万幼川1 潘和平 1 (1 武汉大学遥感信息工程学院,武汉市珞喻路129号,430079) 摘 要:阐述了贝叶斯网络结构学习的内容与方法,提出一种基于条件独立性(CI)测试的启发式算法。从完全潜在图出发,融入专家知识和先验常识,有效地减少网络结构的搜索空间,通过变量之间的CI 测试,将全连接无向图修剪成最优的潜在图,近似于有向无环图的无向版。通过汽车故障诊断实例,验证了该算法的可行性与有效性。 关键词:贝叶斯网络;结构学习;条件独立性;概率推理;图论中图法分类号:T P18;T P311 贝叶斯网络学习是贝叶斯网络的重要研究内容,也是贝叶斯网络构建中的关键环节,大体分为结构学习和参数学习两个部分。由于网络结构的空间分布随着变量的数目和每个变量的状态数量呈指数级增长,因此,结构学习是一个NP 难题。为了克服在构建网络结构中计算和搜索的复杂性,许多学者进行了大量的探索性工作[1~5]。至今虽然出现了许多成熟的学习算法,但由于网络结构空间的不连续性、结构搜索和参数学习的复杂性、数据的不完备性等特点,每种算法都存在一定的局限性。本文提出了一种新算法,不仅可以有效地减少网络结构的搜索空间,提高结构学习的效率,而且可避免收敛到次优网络模型的问题。 1 贝叶斯网络结构学习的基本理论 1.1 贝叶斯网络结构学习的内容 贝叶斯网络又称为信念网络、概率网络或因果网络[6] 。它主要由两部分构成:1有向无环图(directed acyclic graph,DAG),即网络结构,包括节点集和节点之间的有向边,每个节点代表一个变量,有向边代表变量之间的依赖关系;o反映变量之间关联性的局部概率分布集,即概率参数,通常称为条件概率表(conditional probability table,CPT),概率值表示变量之间的关联强度或置信度。贝叶斯网络结构是对变量之间的关系描 述,在具体问题领域,内部的变量关系形成相对稳定的结构和状态。这种结构的固有属性确保了结构学习的可行性,也为结构学习提供了基本思路。贝叶斯网络结构学习是一个网络优化的过程,其目标是寻找一种最简约的网络结构来表达数据集中变量之间的关系。对于一个给定问题,学习贝叶斯网络结构首先要定义变量及其构成,确定变量所有可能存在的状态或权植。同时,要考虑先验知识的融合、评估函数的选择和不完备数据的影响等因素。 1.2 贝叶斯网络结构学习的方法 近10年来,贝叶斯网络的学习理论和应用取得了较大的进展。目前,贝叶斯网络结构学习的方法通常分为两大类:1基于搜索与评分的方法,运用评分函数对网络模型进行评价。通常是给定一个初始结构(或空结构),逐步增加或删减连接边,改进网络模型,从而搜索和选择出一个与样本数据拟合得最好的结构。根据不同的评分准则,学习算法可分为基于贝叶斯方法的算法[3,7]、基于最大熵的算法[8]和基于最小描述长度的算法[1,2]。o基于依赖关系分析的方法,节点之间依赖关系的判断通过条件独立性(CI )测试来实现,文献[9,10]描述的算法属于该类算法。前者在DAG 复杂的情况下,学习效率更高,但不能得到一个最优的模型;后者在数据集的概率分布与DAG 同构的条件下,通常获得近似最优的模型[11],

贝叶斯网络结构学习总结

贝叶斯网络结构学习总结 一、 贝叶斯网络结构学习的原理 从数据中学习贝叶斯网络结构就是对给定的数据集，找到一个与数据集拟合最好的网络。 首先定义一个随机变量h S ，表示网络结构的不确定性，并赋予先验概率分布()h p S 。然后计算后验概率分布(|)h p S D 。根据Bayesian 定理有 (|)(,)/()()(|)/()h h h h p S D p S D p D p S p D S p D == 其中()p D 是一个与结构无关的正规化常数，(|)h p D S 是边界似然。 于是确定网络结构的后验分布只需要为每一个可能的结构计算数据的边界似然。在无约束多项分布、参数独立、采用Dirichlet 先验和数据完整的前提下，数据的边界似然正好等于每一个（i ，j ）对的边界似然的乘积，即 1 1 1 () ()(|)()() i i q r n ij ijk ijk h i j k ij ij ijk N p D S N ===Γ?Γ?+=Γ?+Γ?∏∏ ∏ 二、 贝叶斯网络完整数据集下结构学习方法 贝叶斯网络建模一般有三种方法：1）依靠专家建模；2）从数据中学习；3）从知识库中创建。在实际建模过程中常常综合运用这些方法，以专家知识为主导，以数据库和知识库为辅助手段，扬长避短，发挥各自优势，来保证建模的效率和准确性。但是，在不具备专家知识或知识库的前提下，从数据中学习贝叶斯网络模型结构的研究显得尤为重要。 常用的结构学习方法主要有两类，分别是基于依赖性测试的学习和基于搜索评分的学习。 第一类方法是基于依赖性测试的方法，它是在给定数据集D 中评估变量之间的条件独立性关系，构建网络结构。基于条件独立测试方法学习效率最好，典型的算法包括三阶段分析算法（TPDA ）。基于依赖性测试的方法比较直观，贴近贝叶斯网络的语义，把条件独立性测试和网络结构的搜索分离开，不足之处是对条件独立性测试产生的误差非常敏感。且在某些情况下条件独立性测试的次数相对于变量的数目成指数级增长。 第二类方法是基于评分搜索的方法，其原理是在所有节点的结构空间内按照一定的搜索策略及评分准则构建贝叶斯网络结构，这种算法虽然能够搜索到精确的网络结构，但是由于结构空间很大，从所有可能的网络结构空间搜索最佳的贝叶斯网络结构被证明为NP-hard 问题，所以一般需要使用启发式算法，代表性算法有K2算法等。基于搜索评分的方法是一种统计驱动的方法，试图在准确性、稀疏性、鲁棒性等多个因素之间找个平衡点。但由于搜索方法的先天弱点，导致用搜索评分的方法不一定能找到最好的结构，但是应用范围很广。 当观察到的数据足够充分且计算次数足够多时，基于搜索评分的方法和基于依赖性测试的方法都可以学到“正确”的网络结构。 此外，有人结合上述两种方法，提出了一些混合算法，这类算法首先利用独立性测试降

目前主要存在两类贝叶斯网络学习方法

1贝叶斯网络参数学习 （1）目标是：给定网络拓扑结构S和训练样本集D，利用先验知识，确定贝叶斯网络模型各结点处的条件概率密度，记为：p(?/D，s)。 （2）常见的数学习方法有最大似然估计算法、贝叶斯估计算法、不完备数据下参数学习等。即用MLE公式和BE公式、EM来求参数。 ?最大似然估计方法中，参数是通过计算给定父结点集的值时，结点不同取值的出现频率， 并以之作为该结点的条件概率参数；最大似然估计的基本原理就是试图寻找使得似然函数最大的参数。 ?贝叶斯估计方法假定一个固定的未知参数?，考虑给定拓扑结构S下，参数?的所有 可能取值，利用先验知识，寻求给定拓扑结构S和训练样本集D时具有最大后验概率的参数取值。由贝叶斯规则，可以得出： ?不完备数据下参数学习：数据不完备时参数学习的困难在于参数之间不是相互独立的， MLE方法的似然函数和贝叶斯估计方法的后验概率都无法分解成关于每个参数独立计算的因式。EM算法的实质是设法把不完备数据转化为完备数据。 在不完全数据集上学习贝叶斯网络，Fhedma 提出了structural EM算法，该算法结合了EM 算法和结构搜索的方法，EM算法用于优化网络参数，结构搜索用于模型选择。 2贝叶斯网络结构学习 目前主要存在两类贝叶斯网络学习方法：基于搜索和评分的方法(Search and Score based Method)和基于独立性测试的方法(Conditional Independence Testing based Method). 2.1基于搜索和评分的方法 主要由两部分组成（评分函数和搜索算法）。 2.1.1常用的评分函数 有贝叶斯评分函数和基于信息论的评分函数。 （1）贝叶斯评分函数(MAP测度)

贝叶斯网络Matlab

Matlab贝叶斯网络建模 1 FullBNT简介 基于Matlab的贝叶斯网络工具箱BNT是kevin p.murphy基于matlab语言开发的关于贝叶斯网络学习的开源软件包，提供了许多贝叶斯网络学习的底层基础函数库，支持多种类型的节点（概率分布）、精确推理和近似推理、参数学习及结构学习、静态模型和动态模型。 1.1贝叶斯网络表示 BNT中使用矩阵方式表示贝叶斯网络，即若节点i到j有一条弧，则对应矩阵中 值为1，否则为0。 1.2结构学习算法函数 BNT中提供了较为丰富的结构学习函数，都有： 1. 学习树扩展贝叶斯网络结构的 算法 . 2. 数据完整条件下学习一般贝叶斯网络结构学习算法 表1-1 数据完整条件下贝叶斯结构算法 算法名称调用函数 K2算法learn_struct_k2() 贪婪搜索GS（greedy search）算法earn_struct_gs()

3. 缺失数据条件下学习一般贝叶斯网络结构学习算法 表1-2 缺失数据条件下贝叶斯结构算法 1.3参数学习算法函数 1. BNT中也提供了丰富的参数学习函数，都有： 2. 完整数据时，学习参数的方法主要有两种：最大似然估计learn_params()和贝叶斯方法bayes_update_params(); 3. 数据缺失时，如果已知网络拓扑结构，用EM算法来计算参数， learn_params_em ()。 1.4推理机制及推理引擎 为了提高运算速度，使各种推理算法能够有效应用，BNT工具箱采用了引擎 机制，不同的引擎根据不同的算法来完成模型转换、细化和求解。这个推理过程如下： BNT中提供了多种推理引擎，都有：

贝叶斯网络研究

黄友平 构建一个指定领域的贝叶斯网络包括三个任务： ①标识影响该领域的变量及其它们的可能值； ②标识变量间的依赖关系，并以图形化的方式表示出来； ③学习变量间的分布参数，获得局部概率分布表。 实际上建立一个贝叶斯网络往往是上述三个过程迭代地、反复地交互过程。 一般情况下，有三种不同的方式来构造贝叶斯网：①由领域专家确定贝叶 斯网的变量（有时也成为影响因子）节点，然后通过专家的知识来确定贝叶斯网络的结构，并指定它的分布参数。这种方式构造的贝叶斯网完全在专家的指导下进行，由于人类获得知识的有限性，导致构建的网络与实践中积累下的数据具有很大的偏差；②由领域专家确定贝叶斯网络的节点，通过大量的训练数据，来学习贝叶斯网的结构和参数。这种方式完全是一种数据驱动的方法，具有很强的适应性。而且随着人工智能、数据挖掘和机器学习的不断发展，使得这种方法成为可能。如何从数据中学习贝叶斯网的结构和参数，已经成为贝叶斯网络研究的热点。③由领域专家确定贝叶斯网络的节点，通过专家的知识来指定网络的结构，而通过机器学习的方法从数据中学习网络的参数。这种方式实际上是前两种方式的折中，当领域中变量之间的关系较明显的情况下，这种方法能大大提高学习的效率。 在由领域专家确定贝叶斯网络的节点后，构造贝叶斯 网的主要任务就是学习它的结构和参数。 为使贝叶斯网作为知识模型是可用的， 在学习过程中致力于寻找一种最简单的网络结构是非常必要的，这种简单的结构模型称之为稀疏网络，它含有最少可能的参数及最少可能的依赖关系。 Bayesian 网是联合概率分布的简化表示形式，可以计算变量空间的任意概 率值。当变量数目很大时，运用联合概率分布进行计算通常是不可行的，概率数目是变量数目的指数幂，计算量难以承受。Bayesian 网利用独立因果影响关系解决了这个难题。Bayesian 网中三种独立关系：条件独立、上下文独立及因果影响独立。三种独立关系旨在把联合概率分布分解成更小的因式，从而达到节省存储空间、简化知识获取和领域建模过程、降低推理过程中计算复杂性的目的，因此可以说独立关系是Bayesian 网的灵魂。 贝叶斯网络结构的方法分成两类： 基于评分的方法（Based on scoring）和 基于条件独立性的方法（Based on Conditional independence）。 。基于评分的方法把贝叶斯网络看成是含有属性之