第4卷第4期 智能系统学报 Vol.4 No.4 2009年8月 CAAI Transactions on Intelligent Systems Ag.2009 doi:10.3969/i.i8sn.1673-4785.2009.04.009 贝叶斯网络的非忠实性分布 杨有龙，刘蔚，吴艳 (西安电子科技大学理学院，西安710071) 摘要：贝叶斯网络是图论和概率论有机融合的概率图形模型，主要用于统计推理和智能数据分析.理论上通常假 设由基于分布的独立关系可推出基于图结构的d分割，即贝叶斯网络上的分布是忠实的.针对布尔域上的贝叶斯网 络，研究了非忠实分布的构成，提出了贝叶斯网络上分布延拓的概念，得到忠实分布与非忠实分布的平凡延拓均是 非忠实分布. 关键词：贝叶斯网络；忠实性分布；图形模型 中图分类号：TP181;0235;029文献标识码：A文章编号：16734785(2009)04033504 Unfaithful distributions with respect to Bayesian networks YANG You-long,LIU Wei,WU Yan (School of Sciences,Xidian University,Xi'an 710071,China) Abstract:Bayesian networks are a marriage between probability theory and graph theory,and thus are probabilistic graphical models.They are mainly used for statistical inference and intelligent data analysis.It is usually supposed that the network retains the d-separation criterion that characterize graph structure from the independence con- straints based on distribution,that is,the distribution is a faithful distribution with respect to a Bayesian network. In this paper,some unfaithful distributions are characterized with respect to discrete Bayesian networks in a Boolean domain.It was shown that distributions trivially expanded from faithfulness or unfaithfulness are unfaithful distribu- tions with respect to Bayesian networks. Keywords:Bayesian networks;faithful distributions;graphical models 贝叶斯网络(Bayesian networks,BN)1o也称为tion)12,6,所以根据二者的匹配关系，可将图G上 信念网络，是一类非常重要的概率图形模型.它利用 的分布P分为马尔可夫分布(Markov distribution)、 概率理论处理和描述不同知识成份条件下的不确定 忠实分布(faithful distribution)以及完美分布(perfect 性，也是机器学习、人工智能及统计学习等领域的研 distribution).对于任一有向无循环图G,Geiger等4] 究热点之一，主要应用于数据分析、推理预测以及故 得出G上的忠实分布一定存在，对于离散贝叶斯网 障诊断等方面.贝叶斯网络的构成要素主要是：1) 络，Meek2得到非忠实分布(unfaithful distribution) 结构：有向非循环图(directed acyclic graph,DAG) 的勒贝格测度为0，可见对离散型贝叶斯网络，忠实 G=(V,E),其中的节点表示变量，边表示变量之间 分布不但存在，而且很多.由于图上的分布要么是忠 的因果关系；2)参数：描述节点（或称为顶点、变量） 实的，要么是非忠实的，所以探讨非忠实分布的构成 之间因果关系的概率分布P. 依然有利于贝叶斯网络的理论研究和应用研究.正 变量集V上的分布P描述了变量之间的概率 如[0,1]上的全体有理数的勒贝格测度为0，无理数 依赖关系.表示为变量之间的独立关系.作为图G 的测度为1，即使如此有理数在数域仍然扮演了重 上的节点集'，有向无循环图G可描述节点之间的 要的角色，同时贝叶斯网络的学习与逼近忠实成非 可分性，DAG上的可分性表示为d-分割(d-separa- 忠实的分布关系密切山，因此研究非忠实性分布有 利于从数据中学习贝叶斯网络.近年来关于贝叶斯 收稿日期：20090507. 基金项目：国家自然科学基金资助项目(60574075). 网络的理论和应用研究非常活跃，可参考文献[4,7 通信作者：杨有龙.E-mail:ylyang@mail.xidan.edu.cn. 8,10],特别是文献[10]综述了贝叶斯网络扩展研
·336 智能系统学报 第4卷 究的方方面面，文献[7-8]将贝叶斯网络和核方相结 Ic(X;YIZ)表示给定变量集Z时，变量集X和 合，研究了基于图表模型的数据分类理论，文献[4] Y中任何2个变量之间不存在激活路，即称给定变 将贝叶斯网络和粗糙体相结合，研究了数据特征提 量集Z时，X和Yd-可分（或d-分割）.非d-可分表 取问题 示为Ie(X;YIZ).Ip(X;YIZ)表示给定变量集Z, 本文针对布尔域上的贝叶斯网络，提出了贝叶 变量集X和Y独立，即P(X;YIZ)=P(XIZ),不独 斯网络上分布延拓的概念，得出忠实分布与非忠实 立表示为Lp(X;YIZ).对于分布P,如果由Ie(X;Y 分布的平凡延拓均是非忠实分布.本文接下来的一 IZ)可得到I(X;YIZ),则称有向非循环图G=（V, 节是基本概念和术语；第2节是本文的主要结论；第 E)上的分布P是马尔可夫分布(Markov distribu- 3节是本文的总结 ion).反之，如果由Ip(X;YIZ)可得到Ic(X;YIZ), 1背景知识 则称P是定义在有向非循环图G上的完美分布 (perfect distribution).对于满足马尔可夫条件的贝 本节介绍一些基本概念和术语1,6.详细内容 叶斯网络B=(G,),由文献[6]知当Ie[X;YIZ]成 可参考文献[6]. 立时，必有I(X;YIZ)成立.由于文献[2]已证得非 定义1马尔可夫条件.设G=(V,E)是一有向 忠实分布的测度为0，所以在研究贝斯网络的结构 非循环图.P是定义在随机变量集V上的联合概率 学习和推理时，总假定BN上的分布满足忠实性 分布.如果对于每一个变量X∈Y,它的所有父节点 2主要结论及证明 组成的集合PAx给定时，{X}独立于它的所有非子 孙节点NDx,那么称G=(V,E)满足马尔可夫条件 设离散型贝叶斯网络B=(V,E,P)上的变量集 Markov condition). 按拓扑序标注为V={X1,X2,…,Xn},即变量（或称 定义2贝叶斯网络.设G=(V,E)是一有向非 节点、顶点)X在G中的父节点集PA:C{X1,X2, 循环图，P是定义在随机变量集V上的联合概率分 …,X:-1},记m:=IPA:表示X:父亲节点的数量.当 布，而且(G,P)满足马尔可夫条件，那么称B=（V, 所有变量的取值范围为X,∈{0,1}时，称B为布尔 E,P)为贝叶斯网络 域上的贝叶斯网络.本文只考虑布尔域上的贝叶斯 显然，给定贝叶斯网络B的结构G=（V,E)时， 网络，因此可利用m,维向量集Π：={0,1}={αI G上的分布构成一个集合9由于贝叶斯网络B上 a=（1,2,…,cm）,ck∈{0,1}，1≤k≤m:}表示X 的分布正是指其结构G上的分布，即B=(V,E,P) 的父节点集PA:的取值情况.例如当PA:={X,X2, 同样表示一个贝叶斯网络，它的结构图为G=(V, Xa,X4,Xs},a=(0,1,1,1,0)时，表示X有5个父 E),G上的分布P∈，因此本文中B=(V,E,P)与 节点，而且PA:=表示第一、五个父节点取0，其他 B=(V,E,9列不加区别，或通过上下文理解，由于贝 3个节点取1，此时X:取值的概率参数可表示为 叶斯网络B=(V,E,P)满足马尔可夫条件，所以 P.a=p（X:=1IPA:=a）和1-Pa= p(X:=0IPA:=a),其中p,表示在分布P中X,的 P(X,X2,…,Xn)=ΠP({X}IPA:) 父节点集PA:=a时，X取1的概率. 式中：V={X1,X2,…,Xn},PA表示X:的父节点构 令B。表示无连接边的贝叶斯网络，即B。=(G%, 成的集合.对于有向非循环图G=(V,E),如果存在 P)、Go=(V,E)且E=中，那么对于任意的变量X,Y∈ 节点集X1,X2,…,Xt},k≥2，使得(Xn,Xn+1)∈E V及ZCV,因为不存在连接X和Y的链，当然无激活 或(X+1,Xa)∈E,其中2≤i≤k,那么称连接这k个 路，所以1c(X;YIZ)成立，从而I(X;YIZ)成立.因此对 节点的边集为从X,到X,的一条链，表示为Lxx= 于B。而言，它的分布一定是忠实分布. [X1,X2,…,Xt]. 性质1贝叶斯网络B。上的任何分布均是忠 定义3激活路.设G=(V,E)是一有向非循环 实分布. 图，变量X,YeV和变量集ZCV,若接连X和Y的 显然B。上的分布和它的结构图完美匹配，当给 一条链Lxy=[X,X1,X,2,…,Xt,Y]的内部变量X B。增加有向边，同时将它的分布进行扩充，那么所 (1≤i≤k)满足以下条件：1)X:是头对头（→X←-） 得的结构图与分布关系如何？下面首先定义分布的 连接时，X属于Z或者它的某一个子孙节点属于Z; 扩充，即分布的延拓 2)X不是头对头连接时，X:不属于Z.则称链L是 定义4分布的延拓和限制.设布尔域上的贝 给定变量集Z时的激活路(Active path). 叶斯网络B1=(V,E1,)、B2=(V,E2,),且E1C
第4期 杨有龙，等：贝叶斯网络的非忠实性分布 ·337· E2,其中变量集为V={X,X2,…,Xn.设P1∈， 点，可由边集E,得到E2.因此给定变量子集Z时， P2∈，变量X:∈V在B,、B2中的父节点集分别为 在DAGG2=(V,E2)中链T=[X:,X1,…,X,X]依 PA和PA,显然PA CPA,不妨设PA={X,, 然激活.故16(X:,X,Z)成立， X}和PA={X,…,Xk,…,X},其中k=m、T= 其次证I(X,XZ)成立.因为 m.如果对于任意的参数pa∈P1,a∈{0,1}，存在 P(81X,Z)= P2(Xi,Xj,Z) 参数p。∈P2,B∈{0,1}'，使得B=(a,y),其中y∈ P2 (Xi,Z) 0,1}-,使得p。=,则称分布P2是分布P在 ∑4zux(ΠP,(X,1P4)） B2上的延拓，分布P1是分布P2在B:上的限制.若 ∑4e-zux( ΠP,(XIPA) 对任意的y∈{0,1}-，有pig=pa,其中B=（a, Y),则称分布P2是分布P,在B2上的平凡延拓 ∑4u(IiP(X,1PA) 引理1设B=（V,E,是布尔域上不同于 ∑4-uw（ΠiP(X:1PM) B。=(V,E,)的贝叶斯网络，那么存在分布P∈ P (X:,Xi,Z) ,使得P是B上的非忠实分布. P (Xi,Z) =P (X:I X,Z)= 证明因为E,CE,不妨设P。∈，以及P∈ P (X;,Z) 是分布P。在B上的平凡延拓，下面证明P是B上 P,(X1z)=P.2 的非忠实性分布.由于ECE,所以存在(X,X)∈E 且对任意k≤-1，PA=中以及PAC{X:,X+1,…, ∑4s-u(ΠP.(X:1PA) X,-},于是1(X,X中).可见要证明P是B上的 ∑4e-2Π.P(X,lPA) 非忠实性分布，仅需证(X:,XI中)成立，即B上的 ∑4-zu〈IiP,(X1PA) 分布P诱导出变量X和X独立.因为 ∑P(X,X2,…,X) ∑-zΠiP(X,1PA) P(XI X) P2 (Xj,Z) P(X) P2(Z) =P2(X1Z), P(X)P(X2)...P(X;-1)P(XI PA;) 所以Ip,(X,X,1Z)成立.QED. X7XX Po(X;) 由上述定理可知，分布的平凡延拓保持了非忠实 性，那么分布的平凡延拓是否保持了忠实性？一方 ∑P(X)P(X2)…P(X-1)P(XIPA;) X 面，由上述定理的证明可知分布的平凡延拓保持了 Po(X;) 变量的独立关系，另一方面，边集的增加产生新的激 P(X:)P,(X2=P,(X)=P(X), 活路，难以保持变量之间的d可分性，所以分布的平 Po(X;) 凡延拓不能保持分布的忠实性.因此有以下结论， 所以在贝叶斯网络B上由I,(X,X|φ)不能推出 引理3设有向非循环图G=（V,E),其中节点 Ic(X,X|中).QED. 集V按祖先序为V={X,…,Xn},若不相邻节点 引理2设贝叶斯网络B=(V,E1,)、B2= X,X∈V且i<j,那么Ic(X,XIPA)成立 (V,E2,)且E,CE2,如果P∈是B:上的非忠 证明假设给定变量X的父节点集PA时，X 实分布，那么P1在B2上的平凡延拓分布P2∈是 和X之间存在激活路中： B2上的非忠实分布. X-X-X2-…-Xk-X, 证明由于P,是B,上的非忠实分布，所以存 那么，X.PA,否则π不是激活路.可见在G中X 在X,X∈V及ZCV使得1（X,XIZ)和I6（X, 和X的连接边方向为X→X,不失一般性不妨设 XZ)成立.下面证明I,(X:,XIZ)和16(X,X|Z) X是在激活路T中最靠近X的头对头节点，即激 成立 活路π为 首先证16，(X:,X1Z)成立.由16，（X:,X1Z)成 X:-X1-…-X-)→X。←… 立可知，给定变量集Z时，在结构图DAGG,=(V, ←Xt←-X E)中存在激活路T=[X,X1,…,X,X];又有 由于i<j,所以X,≠X根据激活路的定义，可 G2=(V,E2)可知，在不改变变量原有拓扑序的同时 知X。∈PA,或者X的一个子孙节点属PA,于是在 （V=(X1,X2,…,Xn),通过增加某些变量的父节 有向非循环图G中出现循环，产生矛盾，因此给定
·338 智能系统学报 第4卷 变量X的父节点集PA时，X:和X之间不存在激 [3 LEVITZ M,PERLMAN M D,MADIGAN D.Separation 活路，即Ic(X,XIPA)成立. and completeness properties for ampchain graph Markov 引理4设贝叶斯网络B,=（V,E1,)、B2= [J].The Annals of Statistics,2001,29(6):1751-1784. [4]SLEZAK D.Degrees of conditional (in)dependence:a (V,E2,)且E,CE2,如果P∈是B1上的忠实 framework for approximate Bayesian networks and examples 分布，那么P,在B2上的平凡延拓分布P2∈是 related to the rough set-based feature selection[J].Informa- B2上的非忠实分布. tion Science8,2009,179(3):197-209. 证明由于E,CE2,所以存在节点X:∈V使得 [5]SETTIMI R,SMITH J Q.Geometry,moments and condi- tional independence trees with hidden variables J].The X:生PA及X:ePA,即(X:,X)生E1,(X,X)eE2: Annals of Statistics,2000,28(4):1179-1205. 由于X:和X在B,中不相邻以及i<j,根据引理3 [6]RICHARD E.Neapolitan.Leaming Bayesian networks 可知I6（X,XIPA)成立，于是得n（X,X,IPA). [M].[S.I.Prentice Hall,2003:102-107. 再利用引理2的第2部分证明可得I,(X:,X,1 [7]YANG Youlong,WU Yan.Inner product space and concept PA).显然根据X和X中的相邻性可得I6（X,X classes induced by Bayesian networks[J].Acta Application Mathematicae,2009,106(3):337-348. PA)不成立.因此分布P2是B2上的非忠实分布. [8]YANG Youlong,WU Yan.VC dimension and inner product QED space induced by Bayesian networks[J].Interational Jour- 定理1设贝叶斯网络B,=(V,E1,)、B2= nal of Approximate Reasoning,2009,50(7):1036-1045. (V,E2,)、E1CE2以及P∈，那么P,在B2上的 [9]杨有龙，高晓光.基于BD度量的局部网络结构分析[J]. 平凡延拓分布P2∈9是B2上的非忠实分布. 模式识别与人工智能，2003,16(1)：17-21. YANG Youlong,GAO Xiaoguang.Analysis of structure of 证明根据上述引理2和吗引理4可得定理1成立. local networks based on the Bayesian dirichlet metric[J]. 从上述定理可知，通过概率分布的平凡延拓获 Pattern Recognition and Artificial Intelligence,2003,16 得贝叶斯网络上的非忠实分布，因此对于给定贝叶 (1):1721. 斯网络，容易获得它的非忠实分布.自然想到另一个 [10]陈英武，高研方.贝叶斯网络扩展研究综述[J].控制与 问题：是否存在保持非忠实性的非平凡延拓分布？ 决策，2008,23(10)：1081-1086,1091. CHEN Yingwu,GAO Yanfang.Survey of extended Bayes- 显然存在，首先将非忠实性的分布平凡延拓，其次改 ian networks [J].Control and Decision,2008,23(10): 变平凡延拓为非平凡延拓即可. 1081-1086,1091 作者简介： 3 结束语 杨有龙，男，1967年生，博士，教授， 研究贝叶斯网路的分布是否忠实，有利探讨BN 硕士生导师，现为陕西省数学会理事，主 的学习和推理.本文针对布尔域上的贝叶斯网路，通 要研究方向为图形模型、数据分类和智 能优化等，参加的科研项目荣获2005年 过定义概率分布的延拓，得到任何分布的平凡延拓 度陕西省科学技术奖二等奖；2005年陕 均是非忠实分布，因此对于给定的贝叶斯网路，容易 西高等学校科学技术奖一等奖：2008年 获得它的非忠实分布.进一步可以探讨哪类贝叶斯 陕西高等学校科学技术奖二等奖.发表学术论文30余篇. 网络的非忠实分布一定来自于这种分布的平凡延 刘蔚，女，1986年生，硕士研究 拓，或者哪一类贝叶斯网络的非忠实分布并不是来 生，主要研究方向为数据融合和贝叶斯 源于这种分布的平凡延拓以及如何构造，这些基本 网络. 问题的深入探讨一定会促进贝叶斯网络的理论和应 用研究 参考文献： 吴艳，女，1969年生，副教授，主 [1]CHICKERING D M,MEEK C.On the incompatibility of 要研究方向为图形模型、选址问题及优 faithfulness and monotone DAG faith-fulness[J].Artificial 化理论 Inteligence,2006,170(8):653-666. [2]MEEK C.Strong completeness and faithfulness in Bayesian networks[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.Morgan Kaufmann, San Mateo,USA,1995:411-418