第6期 王双成，等：用于因果分析的混合贝叶斯网络结构学习 ·85· 定连续变量对应的离散变量的最优维数.设D, ,X(力，j,k=1,…h为条件的条件互信息 ,D得四是使用不同的离散化方案A(2≤h≤ 对给定的小正数一般取=0.01)，如果1(X,X M),选择一个h的值便得到一个离散化方案)离 X,:X<￡，就认为X和X之间条件独立 散化变量X,而得到的离散数据集序列，对每一个 1)补充丢失的依赖关系 离散化方案分别进行MDL标准打分，取加= 对不存在边的结点对X:和X,依次进行互信 inMDL (A D)}作为离散变量的维数 息1(X:,X)计算.如果1(X:,X)>￡，在G中增加 边X,·X.用L表示对应的边表，其中的元素是 MDL(AI D)=号21A1-LMD). 三元组(i,j,列，j>i,i=1,n,j=2,n,6= (4) 0,1,I=1和乃=0分别表示存在和不存在边x 式中Al表示离散化方案A中变量x在G X.这一过程最多需要(n+)(n+2)/2次互信息计算 中马尔可夫毯结构的参数数量： 2)删除冗余的依赖关系 由于连续变量重新离散化，可能存在一些冗余 L(A.D)1g(P(uI Mx DA))= 的边，通过下面的方法去除冗余的边.在G中，用 N∑p(xW,rw|Mxw,D,A Sx(X,X)和Sx,(X,X)分别表示X:和X的邻 域中在X,和X,链路81上的结点集，S(X,X)表 Πp(x,r,lMxw,D,A 示Sx,(X,X)和Sx(X,X)中具有较少结点的结 点集.对存在边的结点对X,X,设S(X,X)= Ig(p(x!,Mx,D A) {X,X”},如果存在和1≤和≤到使1(X, ΠP(xl元，MxW,D,A XX”,D<c,在G中删除边X,-X,和修改边 表L“:否则.选取·1(.川 2.2贝叶斯网络结构优化调整 X,Dw,如果存在加(1≤m≤1，加≠1)，使 贝叶斯网络结构优化调整包括结点顺序和结构 1X,XX,X”,DW)<￡，在G中删除边 调整2部分内容，通过优化将得到更好的贝叶斯网 X·X和修改边表L6:重新确定S(X,X),由于 络结构，直到迭代中的贝叶斯网络结构趋于稳定， 产生第2种依赖的信息流往往能被少数结点所阻塞 2.2.1依赖关系优化 (多数情况是1个或2个结点)，因此大部分的第2 利用贝叶斯网络的信息管道模型7181描述变 种边己被清除，S(X,X)将具有很少的冗余结点， 量之间存在的3种基本依赖关系（边）：1)传递依赖 如果1X,XS(X,X),DW)<￡，在G中删除 (transitive dependencies),结点之间存在直接的信 边X:-X和修改边表L.这一过程最多需要2 息流动，而且信息流不能被其他结点所阻塞，结点所 次条件互信息计算 表示的变量之间边缘和条件依赖：2)非传递依赖 2.2.2因果语义优化 (nontransitive dependencies),结点之间不存在直 因果语义优化就是边的方向优化，下面分别基 接的信息流动，而是由连接两结点之间的开路（不含 于碰撞识别和条件预测能力优化边的方向，以便得 碰撞结点的路径)产生信息流，这种信息流被切割集 到更适合于因果分析的贝叶斯网络 中的结点所阻塞，2个结点所表示的变量之间边缘 基于碰撞识别优化边的方向： 依赖，但条件独立；3)导出依赖(induced dependen- 在边表L&中查寻，选择结点对X,和X,设 cies),这种依赖是由V结构所导致，结点之间不存 X,和X,之间不存在边，在G中与X,和X,可能 在直接的信息流动，而是由V结构中的碰撞结点诱 形成V结构的结点为Xm,Xm,对每一个可能 发的信息流，结点所表示的变量之间边缘独立，但条 的V结构进行碰撞识别（汇聚识别）6-2，.对给定 件依赖 1(X.Xl Xm.D) 下面基于变量之间基本依赖关系和依赖分析思 的阈值6>0，如果 1(X:.X D) >1+」 想进行依赖关系优化（包括补充丢失的依赖关系和 1≤，则X,X和Xm形成V结构，定向为X,→ 删除冗余的依赖关系)和因果语义优化2部分内容 Xm.和X,→Xm,这一过程最多需要n(n-1)次条件 使用互信息和条件互信息进行变量之间定量条 互信息计算 件独立性检验，分别用1(X,X)和1(X,X引X, 使用碰撞识别调整方向后，可能还有一部分边 X)表示变量X,和X,之间的互信息和以X4, 的方向没有得到调整，下面基于变量之间的预测能 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net定连续变量对应的离散变量的最优维数. 设 D ( k) i2 , …, D ( k) iM ( k) i 是使用不同的离散化方案 Λh ( 2 ≤h ≤ M ( k) i ) ,选择一个 h 的值便得到一个离散化方案) 离 散化变量 Xi 而得到的离散数据集序列 ,对每一个 离散化方案分别进行 MDL 标准打分 , 取 h0 = min M ( k) i ≥h ≥2 { MDL (Λh | D ( k) ih ) }作为离散变量的维数. MDL (Λh | D ( k) ih ) = lg N 2 | Λh | - L (Λh | D ( k) ih ) . (4) 式中 :| Λh | 表示离散化方案 Λh 中变量 X ( k) i 在 G ( k) 中马尔可夫毯[1 ]结构的参数数量 : L (Λh | D ( k) ih ) = ∑ N i =1 lg ( P( ui | M X ( k) i , D ( k) ih ,Λh ) ) = N x ( k)∑i ,πx ( k) i p ( x ( k) i ,πx ( k) i | M X ( k) i , D ( k) ih ,Λh ) x ( k)∏i ∈πx j p ( x j ,πx j | M X ( k) i , D ( k) ih ,Λh ) · lg ( p ( x ( k) i | πx ( k) i , M X ( k) i , D ( k) ih ,Λh ) x ( k)∏i ∈πx j p ( x j | πx j , M X ( k) i , D ( k) ih ,Λh ) . 2. 2 贝叶斯网络结构优化调整 贝叶斯网络结构优化调整包括结点顺序和结构 调整 2 部分内容 ,通过优化将得到更好的贝叶斯网 络结构 ,直到迭代中的贝叶斯网络结构趋于稳定. 2. 2. 1 依赖关系优化 利用贝叶斯网络的信息管道模型[17 - 18 ] 描述变 量之间存在的 3 种基本依赖关系 (边) :1) 传递依赖 (transitive dependencies) ,结点之间存在直接的信 息流动 ,而且信息流不能被其他结点所阻塞 ,结点所 表示的变量之间边缘和条件依赖 ; 2) 非传递依赖 (non2transitive dependencies) ,结点之间不存在直 接的信息流动 ,而是由连接两结点之间的开路(不含 碰撞结点的路径) 产生信息流 ,这种信息流被切割集 中的结点所阻塞 ,2 个结点所表示的变量之间边缘 依赖 ,但条件独立 ;3) 导出依赖 (induced dependen2 cies) ,这种依赖是由 V 结构所导致 ,结点之间不存 在直接的信息流动 ,而是由 V 结构中的碰撞结点诱 发的信息流 ,结点所表示的变量之间边缘独立 ,但条 件依赖. 下面基于变量之间基本依赖关系和依赖分析思 想进行依赖关系优化 (包括补充丢失的依赖关系和 删除冗余的依赖关系) 和因果语义优化 2 部分内容. 使用互信息和条件互信息进行变量之间定量条 件独立性检验 ,分别用 I ( Xi , Xj) 和 I ( Xi , Xj | Xu 1 , …, Xu h ) 表示变量 Xi 和 X j 之间的互信息和以 X u 1 , …, Xu h ( uk ≠i , j , k = 1 , …, h) 为条件的条件互信息 , 对给定的小正数ε(一般取ε= 0. 01) ,如果 I( Xi , Xj | Xu 1 , …, Xu h ) <ε,就认为 Xi 和 Xj 之间条件独立. 1) 补充丢失的依赖关系 对不存在边的结点对 Xi 和 X j ,依次进行互信 息 I( Xi , Xj) 计算. 如果 I ( Xi , Xj) >ε,在 G ( k) 中增加 边 Xi - Xj . 用 L ( k) 0 表示对应的边表 ,其中的元素是 三元组( i , j ,η) , j > i , i = 1 , …, n , j = 2 , …, n ,δ= 0 ,1 ,η= 1 和η0 = 0 分别表示存在和不存在边 Xi - Xj .这一过程最多需要( n + 1) ( n + 2) / 2 次互信息计算. 2) 删除冗余的依赖关系 由于连续变量重新离散化 ,可能存在一些冗余 的边 ,通过下面的方法去除冗余的边. 在 G ( k) 中 ,用 S Xi ( Xi , Xj) 和 S X j ( Xi , Xj) 分别表示 Xi 和 X j 的邻 域中在 X i 和 X j 链路[18 ] 上的结点集 , S ( Xi , Xj ) 表 示 S Xi ( Xi , Xj) 和 S X j ( Xi , Xj) 中具有较少结点的结 点集. 对存在边的结点对 Xi , Xj , 设 S ( Xi , Xj ) = { X ( i , j) 1 , …, X ( i , j) t } ,如果存在 t0 (1 ≤t0 ≤t) 使 I ( Xi , Xj | X ( i , j) t 0 , D) <ε,在 G ( k) 中删除边 Xi - Xj和修改边 表 L ( k) 0 ; 否则 , 选取 X i t 3 = argmin X (i , j) k , t ≥k ≥1 { I ( Xi , Xj ) | X ( i , j) k , D ( k) } , 如果存在 h0 ( 1 ≤h0 ≤t , h0 ≠t 3 ) , 使 I( Xi , Xj | X ( i , j) h 0 , X ( i , j) t 3 , D ( k) ) <ε, 在 G ( k) 中删除边 Xi - Xj和修改边表 L ( k) 0 ;重新确定 S ( Xi , Xj) ,由于 产生第 2 种依赖的信息流往往能被少数结点所阻塞 (多数情况是 1 个或 2 个结点) ,因此大部分的第 2 种边已被清除 , S ( Xi , Xj ) 将具有很少的冗余结点 , 如果 I ( Xi , Xj | S ( Xi , Xj ) , D ( k) ) <ε,在 G ( k) 中删除 边 Xi - Xj 和修改边表 L ( k) 0 . 这一过程最多需要 2 n 2 次条件互信息计算. 2. 2. 2 因果语义优化 因果语义优化就是边的方向优化 ,下面分别基 于碰撞识别和条件预测能力优化边的方向 ,以便得 到更适合于因果分析的贝叶斯网络. 基于碰撞识别优化边的方向 : 在边表 L ( k) 0 中查寻 ,选择结点对 Xi 和 X j , 设 Xi 和 X j 之间不存在边 ,在 G ( k) 中与 Xi 和 X j 可能 形成 V 结构的结点为 X m1 , …, X mt ,对每一个可能 的 V 结构进行碰撞识别 (汇聚识别) [16 - 20 ] . 对给定 的阈值δ> 0 , 如果 I( Xi , Xj | X mh , D ( k) ) I ( Xi , Xj | D ( k) ) > ( 1 +δ) , 1 ≤h ≤t ,则 Xi , Xj 和 X mh形成 V 结构 ,定向为 Xi → X mh和 X j →X mh ,这一过程最多需要 n( n - 1) 次条件 互信息计算. 使用碰撞识别调整方向后 ,可能还有一部分边 的方向没有得到调整 ,下面基于变量之间的预测能 第 6 期 王双成 ,等 :用于因果分析的混合贝叶斯网络结构学习 ·85 ·