第1期 李冰寒，等：利用互信息学习贝叶斯网络结构 69… 示在给定节点X:的父节点时X:的条件概率，节点 j=1,2,…,n; 集V的联合概率分布可由式(1)表示. 2)计算I(X:;X),i≠j,ij=1,2,…,n; P(X1=a1,X2=2,…,X.=an)= 3)对HX:,X∈V,i≠j,若I(X;X)<e,其中e ΠP(X:=a1m:=F). 为阈值(0<e<1),则令E1=E,1{X-X. (1) iI 应注意的是，阈值e的取值与G,中无向边的个 式中：π：表示节点X:在G中的父节点集 数有关.如果ε过大（接近于1），则很大可能会删除 定义2DAGG的V结构是指由3个节点构成 真实网络中实际存在的边；如果ε过小，则G,中可 的有序节点组(X,Y,Z),满足下面2个条件： 能包含较多不存在于真实网络的冗余边.在贝叶斯 1)G包含有向边X+Y和Z+Y: 树络的结构学习中，通常取￡的值为0.01，因为这 2)在G中X和Z不相邻. 样能保证真实网络中的大部分边存在于G中，而且 定义3随机变量X和Y的互信息定义如 G,中含有较少的冗余边. 下： 2.2确定G1的最大支撑树G I(X;Y)=H(X)-H(XI Y) 本阶段将图中每条边上的权定义为节点间的互 式中：H(X)和H()分别是X和Y的信息熵，H(XI 信息，然后利用Pim算法构造无向图G1=(V,E,) Y)是在给定Y下X的条件信息熵.H(X)、H(XIY) 的最大支撑树.由于第1阶段构造的初始无向图 定义如下： G=(V,E,)可能包含多于三节点的环，而这些环的 H(X)=- ∑P(X)log(P(X)), 存在将会导致当前无向图不可一致延拓；但是在等 价类空间上进行贪婪搜索的输入图应该是一个可一 H(XI)=-∑∑P(X=x,Y=)· 致延拓的本质图，故第2阶段通过构造最大支撑树 log(P(X x:I Y=y:)). 来精简初始无向图，使得精简后的无向图G2=（V, 式中：n和m分别表示X和Y的状态个数.X和Y之 E2)可一致延拓. 间的互信息是对称的，即I(X;Y)=I(Y;X), 对于无向图G1=(V,E),设它的权矩阵为W= (0),S为V的一个非空子集，5=八S,定义： 2构造贝叶斯网络的改进算法 rI(X;X),若X-X∈E; 算法的思想是从完全无向图开始，第1阶段删 =0, 其他 除互信息小于给定阈值ε节点间的边，构造初始无 [S,]={X:-X∈E1IX:∈S,XeS1. 向图G,;第2阶段利用图论中的Pim算法寻找G 构造G最大支撑树的具体步骤如下： 的最大支撑树G2,精简初始无向图G;第3阶段根 1)任取X:∈V,令S={X},Eo=0,k=0. 据条件独立测试对G2中的无向边添加方向，得到部 2)若Sk=V,结束，以S为顶点集、E为边集的 分有向图G3;第4阶段对G3中剩余的无向边任意 图即是G的最大支撑树；否则转3)· 添加方向，构造可能的非循环有向图G4;第5阶段 3)构造[Sk,S],若[S,S]=,则G1不连通， 从G4开始，利用贪婪算法]在等价类空间上进行 算法停止：否则，设w(e,)=,w(e),e4=X- 搜索，得到和数据匹配最好的贝叶斯网络结构的本 Xk,X∈Sk,令S+1=SU{Xk},E+1=EkU{ez}, 质图G·,具体算法可分为以下5个阶段 k=k+1,转1). 2.1构造初始无向图G 2.3确定最大支撑树G2中边的方向得到G 由于随机变量X和Y之间的互信息度量了在 根据条件独立测试可以确定出形如X-Z一Y和 已知Y的新观察值时对X取值的不确定性的减少， X→Y-Z的子结构中无向边的方向.具体算法如下： 反之亦然，从而随机变量间的依赖程度可通过评价 1)令G3=G2 它们之间的互信息值来衡量.如果两节点X:、X之 2)确定G3中所有的子结构X-Z-Y,其中X 间的互信息小于某个临界值，即I(X:;X)<B,则在 和Y不相邻. 真实网络中这两节点极大可能不相邻，因为反映它 3)对于每个子结构X-Z-Y,若P(XIZ)≠ 们之间依赖程度的互信息值小于阈值ε，从而它们 P(XIY,Z)且对于添加边X-Y后的三角环X-Z- 之间不存在边.具体算法如下： Y-X,令S=☑.对每个节点W∈八{X,Y,Z},计算 1)令V={X1,X2,…,Xn},E1={X-Xli≠j,i, W与其他各节点（不包含Z)的互信息并降序排列