一种可度量的贝叶斯网络结构学习方法

綦小龙 高 阳 王 皓 宋 蓓 周春蕾 张友卫

1(南京大学计算机科学与技术系 南京 210046)2(伊犁师范学院电子与信息工程学院 新疆伊宁 835000)3 (江苏方天电力技术有限公司 南京 211102) (qxl_0712@sina.com)

贝叶斯网络是个有向无圈图，图中节点表示随机变量，节点间的弧表示变量之间的直接依赖关系.每个节点都拥有一个概率分布，根节点所附的是它的边缘分布，而非根节点所附的是条件概率分布[1].

近几十年来，从数据中自动学习贝叶斯网络结构受到研究者的普遍关注[2-7].一般来说，目前有2类结构学习方式[2,8]:1)基于约束的结构学习.该方法根据整体Markov性，使用统计假设检验对数据中的条件依赖和条件独立性关系进行检验，找到对依赖和独立关系最好解释的某个结构[9-10].2)基于优化的结构学习.该方式定义了测量模型对观测数据拟合程度的评分函数，如贝叶斯评分和最小描述长度(minimum description length, MDL)评分[2].结构学习的任务是找到一个最大化该评分函数的结构.这2种方法有各自的优缺点：基于约束的方式是有效的，但是它对个体独立性检验中的失败敏感[8-9]；基于优化的方法每次都考虑整个网络，因此对于个体错误并不敏感，但是搜索的结构空间包含超指数个结构.一般来说，该问题是NP-hard问题[8,11].

针对上述2种方法的主要挑战，学者们做了大量的研究.对于基于搜索-评分的学习方法，根据寻找到的解是全局最优还是局部最优提出了精确学习方式和近似学习方式：精确方式[3,6,12-13]的解是全局最优，但是由于其指数级的时空复杂性，这些方法只适合于数据集规模小的领域；而近似方式[14-19]的解虽是局部最优，但是易于扩展到大规模数据上.

基于约束的贝叶斯网络结构学习一直以来不论是方法的研究[5,20-24]还是应用[25-28]都受到了学者们的广泛关注.然而，高阶独立性检验、指数级的检验次数、变量序的影响依然制约着现有算法的性能.为此，本文针对基于约束算法存在的部分问题，提出了一种基于度量信息矩阵的“偷懒”启发式策略方法.新方法不仅与现有算法在时间和精度性能上是可比的，而且易于处理大规模的稀疏网络.

1 相关工作

经典的基于约束的方法通常包含2个步骤：1)结构的骨骼识别;2)边定向.其中对于边定向一般有2类策略:一类是评分-搜索策略[22]，这种策略也被称之为混合策略;另一类是识别DAG的Markov等价类策略[5,20-24]，这类策略首先定向υ-结构，再进一步对其他边定向.

在这里，我们关注结构骨骼的识别，即通过一系列条件独立性检验确定潜在DAG结构是否存在边.常用的条件独立性检验方法有统计假设检验或互信息、条件互信息等[10].

根据采用的不同条件独立性检验策略，我们将基于约束的学习方式大致分为基于启发式策略学习[21-22]和基于PC(Peter-Clark)算法策略学习[5,20-24]两类.下面，我们分别对这2类方法中具有代表性的方法进行概述.

基于启发式的策略通过设置某种启发式函数来实现减少检验次数的目的或减少假阴性节点的目的，主要包括以下2种.

1) 文献[21]给出了一种三阶段依赖分析算法TPDA.该算法在Monotone DAG-faithful假定下，通过逐渐缩小条件集规模的启发式策略来减少独立性检验次数.虽然该算法的条件独立性测试次数是O(n4)，但是Monotone DAG-faithful假定和DAG-faithful假定是不相容的[2].

2) 文献[22]中的MMHC(max-min hill-climbing)虽然采用了一种可纳的启发式策略，但是也产生了大量的假阳性节点.为了减少假阳性节点，该方法对目标变量的CPC(candidate parents and children)中所有元素执行条件独立性检验，该检验次数是CPC规模的指数级.

除了基于启发式策略的学习方法外，也有很多学者通过改进经典的PC算法来进行结构学习.他们设计边排序方法[23]或序独立方法[24]来解决PC算法中变量序对潜在结构的影响.然而，这类方法虽然在一定程度上缓解了假阴节点问题，却无法很好地解决假阳性节点问题或检验次数指数级问题.

首先，介绍众所周知的PC算法[20].该算法也被广泛应用于解决实际问题，尤其在生物信息学[25-27]、关系型数据的因果模型挖掘[28]等领域.PC算法从一个由节点构成的完全无向图开始，随着条件集规模的增长，检验每一个变量对.主要特点是条件集随着完全无向图呈动态变化，这样避免了高阶独立性检测.但是为了防止假阳性节点的产生，在相同条件集规模下，除非变量的邻居集合的某个子集使得变量对独立，否则，还要考虑另一变量的邻居集合的子集情况.这样一来，条件独立性检验次数显著增加.另外，检验过程对变量顺序非常敏感，严重影响了PC算法的性能[25].

文献[23]提出了使用BDe(Bayesian Dirichlet extension)评分函数测量每条边的强度并根据强度执行条件独立性检验的方法.因为存在没有进行独立性检测变量对(边)，算法不能保证添加到最终图的变量对就是正确的决策.

文献[24]设计了一种序独立的PC-Stable算法，即条件独立性检验不会受到变量序的影响.该算法和PC算法的本质区别在于对相同条件集规模下的变量对执行条件独立性检验后，暂不更新无向图；而是当条件集规模增加后，再相应地更新无向图.相比之下，虽然减少了假阳性节点，却需要执行更多的条件独立性测试而且易于遭遇高阶独立性检验，效率比PC算法低.

为了提高其执行效率，文献[5]基于PC-Stable算法提出了一种多核并行化的处理方式.根据无向图的变化规律，将变量的邻接边分配到不同的处理器上，由于遵循了PC-Stable算法更新无向图的策略，所以在并行化计算条件独立性时，没有额外的通信开销.虽然极大地提升了PC-Stable算法效率，但是假阴性点依然没有得到好的解决.

上述方法的共同点是盲目地对到来的变量对立刻执行条件独立性检测，并没有考虑合适的时机；此外，由于条件集的选择也是盲目的，只要是变量邻居就有可能成为条件集元素，也会导致学习错误.

因此，本文提出了可度量的贝叶斯网络结构学习方法，创新点如下：1)提出了一种无需任何先验知识仅从样本中为每个变量自动地学习相应的变量序的方法，该方法称之为度量信息矩阵学习；2)根据度量信息矩阵提出了一种用于条件独立性检验的可靠启发式策略.该策略在度量信息矩阵的指导下，不仅能够合理地选择执行条件独立性检验的变量对，而且能合理地为其选择条件集.

2 BNSvo-learning算法

2.1 算法描述

数据中表现出来的变量间的依赖性包括直接依赖和间接依赖，我们期望在贝叶斯网络中评分最高的变量对就是直接依赖的变量对.测量变量对依赖强度的方法有互信息、偏相关性[29].

虽然全局最佳网络的学习是NP-hard问题，但是我们可以寻找一个近似最佳的网络.为此，选择高依赖关系的变量对(X,Y)并用这些边作为创建网络的启发式是合理的.因此，我们提出了一种可度量的贝叶斯网络结构学习方法，简称为BNSvo-learning.该方法与以往方法的本质区别在于不是盲目地执行条件独立性检测，而是根据度量信息利用“偷懒”启发式策略有序进行.该方法主要包含度量信息矩阵学习和“偷懒”启发式策略2部分.

度量信息矩阵学习过程从给定的数据中使用互信息度量了所有变量之间依赖程度.根据该依赖程度，它为每个变量分配了一个变量序.我们把这些变量序组成的矩阵称之为度量信息矩阵mn×n.

度量信息矩阵刻画了变量间依赖程度的强弱，我们认为这是一种粗粒度上的刻画.原因是它并没有进一步刻画这种依赖程度是直接依赖还是间接依赖.此外，在实验观察中，我们发现互信息强的变量对在真实的网络结构中并不存在边，反而互信息相对弱的变量对在真实的网络中存在边.为了高效地获得潜在结构中真实的边，我们设计了一种“偷懒”启发式策略.根据度量信息矩阵，对变量序中任意一对变量执行条件独立性检验时，任意阶条件独立性断言都不依赖于序中前面的变量，除非该变量与行变量不独立.

算法具体描述如下：首先初始化了2个由节点构成的无向图矩阵mn×n和Gn×n.其中，mn×n是由变量序构成的度量信息矩阵.该矩阵中的每一行暗含了与行变量对应的变量的检验顺序.其中m(i,j)=k指示了矩阵的第i行、第j列元素变量k与变量i的依赖强度排在第j个位置.矩阵mn×n是动态变化，条件集的规模以及独立性计算由它决定.矩阵Gn×n刻画了最终每个变量的邻居集合，它随着度量信息矩阵变化.初始化时，i=j,G(i,j)=0，否则G(i,j)=1.在这里，0表示变量对之间没有边，1表示有边.

算法根据度量信息首先选择依赖程度最弱的变量对(i,m(i,j))执行条件独立性检测Ind(i,m(i,j)|S)，S⊆V{i,m(i,j)}，如果Ind(i,m(i,j)|S)=1，则设置G(i,m(i,j))=0同时设置m(i,j)=0；如果矩阵m中有0元素出现，那么后续变量的条件独立性检验的条件集就不再考虑该元素.即当处理变量对(i,m(i,j+k))时，如果∃j∈[1,j+k-1]满足m(i,j)=0,则S⊆V{i,m(i,j),m(i,j+k)}，否则S⊆V{i,m(i,j+k)}.

算法1. 基于变量序的贝网结构学习算法BNSvo-learning.

输入：数据集data;

输出：BNS结构G.

① 初始化矩阵Gn×n;

② 根据互信息学习信息度量矩阵mn×n;

③ for对矩阵m中的元素执行独立性检验

④ 初始化条件集规模:order←0;

⑤ 获取当前的条件集S;

⑥ while |S|

⑦ 执行条件独立性检验;

⑧ if条件独立性检验

⑨G(i,m(i,j))←0;*更新矩阵G和m*

⑩m(i,j)←0;

2.2 理论分析

BNSvo-learning算法根据度量信息矩阵执行条件独立性检验时，实际上采用了一种“偷懒”启发式的检验策略.下面分析该算法的一些重要性质.

在给出这些性质之前，先介绍需用到的信息论知识：H(X)指示了一个离散随机变量X的熵；H(X|Y)指示了2个随机变量X和Y之间的条件熵；I(X;Y)指示了2个随机变量X和Y之间的互信息.

定理1. 对任意2个随机变量X和Y，有:

1)I(X;Y)≥0;

2)H(X|Y)≤H(X).

上面两式当且仅当X和Y相互独立时等号成立[1].

定理2. 对任意3个离散随机变量X,Y和Z有:

1)I(X;Y|Z)≥0;

2)H(X|Y,Z)≤H(X|Z).

上面两式当且仅当X和Y相互独立时等号成立[1].

定理3. BNSvo-learning算法中，当I(X;Y)>I(X;Z)，给定Z时，X和Y不满足条件独立性.

证明. 充分条件，反证法.假定I(X;Y|Z)=0成立.

由定理2可得：

H(X|Y,Z)=H(X|Z)，

由I(X;Y)=H(X)-H(X|Y)可得：

H(X|Z)=H(X)-I(X;Z).

由H(X|Z,Y)=H(X)-I(X;Z,Y)可得：

H(X)-I(X;Z)=H(X)-I(X;Z,Y).

由I(X;Z)=I(X;Z,Y)可得：

I(X;Z)>I(X;Y).

与已知I(X;Y)>I(X;Z)相矛盾，充分条件得证.

必要条件：

由I(X;Y|Z)=H(X|Z)-H(X|Z,Y)，
且H(X|Z)=H(X)-I(X,Z)可得：
I(X;Y|Z)=H(X)-I(X;Z)-H(X|Z,Y)，
由H(X|Z,Y)≤H(X|Y)
且H(X)-I(X;Z)-H(X|Z,Y)≥
H(X)-I(X;Z)-H(X)+I(X;Y)可得：
H(X)-I(X;Z)-H(X|Z,Y)≥
I(X;Y)-I(X;Z).
由I(X;Y)>I(X;Z)可得：
H(X)-I(X;Z)-H(X|Z,Y)>0，
可得：I(X:Y|Z)>0.

证毕.

定理3证明了在一阶条件独立性检验过程中，互信息强的变量对是否独立一定不依赖于互信息弱的变量.为此，BNSvo-learning算法对任意一变量对执行一阶条件独立性检验时，没有考虑变量序中前面的变量作为其条件集.

为了进一步说明BNSvo-learning算法的有效性，我们给出定理4和推论1.

定理4. BNSvo-learning算法中，当I(X;Y)>I(X;Z)，I(X;Y)>I(X;W)且I(X;Z|Φ)=0或I(X;W|Φ)=0时,给定Z，X和Y不满足条件独立性.

证明.

由I(X;Y)>I(X;Z)，
I(X;Y)>I(X;W)，
I(X;Z|Φ)=0可得：
I(X;Z,W)

由定理3可知，定理4成立.

证毕.

定理4说明了边缘独立的变量对和互信息弱的变量组合得到高阶的条件集不能影响互信息强的变量对的条件独立性断言.为此，在检验过程中算法不考虑这样的条件集.

推论1. 当I(X;Y)

直观上来说，该启发式策略遵循：如果互信息强的变量组合的条件集不能使得变量对独立，那么含有强度弱的变量的条件集也不能使得变量对独立.形式化说明如下：

假定I(X;W)0,那么I(X;Y|Z,W)>0或者I(X;Y|W,H)>0.尤其当条件集的规模较大时，弱的变量提供的信息会更少.

在做条件独立性断言的决策时，我们期望2种情况出现：①I(X;Y|Φ)=0,这意味着无论2个随机变量X和Y在矩阵mn×n中的顺序如何，二者满足边缘独立.②对于变量X而言，S⊆V{X,Y}，∃I(X;Y)

定义1. 不一致性断言.随机变量X和Y分别执行完条件独立性检验后，存在X∈adj(Y),Y∉adj(X)，我们称随机变量X和Y之间的条件独立性断言为不一致性断言.

我们不期望不一致性断言的出现.因为我们很难对该类断言做出合理的决策.如果选择独立性成立，那么可能造成假阴性边，否则造成假阳性边.事实上，选择不成立是可靠的.最糟糕的情况就是执行条件独立性检测后，变量X的邻居集合没有任何变化，简单地说，花了大量的时间做了无用功，但是这至少保证了没有假阴性边，保证了存在找到最佳的贝叶斯网络结构的可能性.

定理5. BNSvo-learning算法是可纳的.

算法采用的启发式策略避免了由高阶独立性检验造成的假阴性节点.另外，对任意变量对(X,Y)执行条件独立性检验时，如果独立，则对X的邻居集合修订adj(X)=adj(X)Y；变量Y的邻居集合adj(Y)保持不变.换句话说，对于变量Y而言，它和X是否条件独立只与Y和其对应的变量序有关.这样防止由变量X的误判对变量Y的影响.

为了进一步减少时间代价，算法在保证质量的前提下，对BNSvo-learning算法做了进一步的改进，当m(i,j)=0，对于变量m(i,j)而言，在变量i的索引iindex满足iindex

这样做的想法很直观，对于变量X而言,如果变量对(X,Y)条件独立性成立，那么对于变量Y而言，如果变量X之后仍有许多互信息强的变量，那么(X,Y)条件独立性成立的概率很大.

算法2. 改进后的学习算法IBNSvo-learning.

输入:数据集data;

输出：更新后的m.

① for矩阵m中第m(i,j)行的每一个元素

② if变量i在第m(i,j)行中的索引为iindex

④m(m(i,j),iindex)←0;

⑤G(m(i,j),i)←0;

⑥ end if

⑦ end if

⑧ end for

⑨ returnm.

改进后算法的实现，只需将IBNSvo-learning算法的行①～⑨嵌入在BNSvo-learning算法的行⑩～之间即可.

3 实 验

为了说明BNSvo-learning算法的性能，我们从贝叶斯网络知识库(the Bayesian network repository, BNR)[30]中选择了5个不同规模的网络.同时也使用了拼贴技术[31]生成了一个适中规模网络Insurance 1和大网络Insurance 2.表1展示了7个网络中的节点数、弧数、最大父节点数和最大状态数.

Table 1 Bayesian Networks Used in the Evaluation Study表1 在评估研究中使用的贝叶斯网络

3.1 实验结果对比

为了说明算法的可靠性，我们从以下4个方面来验证算法：1)变量的状态数少，属性数少，样本量10 000时(Asia-8,Sachs-11)； 2)变量的状态数多，属性数适中，样本量10 000时(Alarm-37，Child-20)；3)变量状态数多，属性数多，样本量5 000时(Insurance1，Insurance2);4)变量的状态数少，属性数多，样本量5 000时(Pigs-441).

我们采用了边评分的评价方法来验证算法的精度性能即计算缺失边数(Missing)、多余边数(Additional)以及反向边数(Reverse).Edge Type越低表明算法的性能越好.表2给出了学习结构的边评分结果,其中，HC(Hill-Climbing)是指经典的基于评分方式的近似结构学习算法[1].

Table 2 Results Comparison of Our Method with Classic Algorithms表2 和经典算法的对比实验结果

表2中的空白项表示由于内存不足或时间代价过高没有得到最终解.对于HC算法，在实验中发现，当数据维数超过200时，就警示“内存不足”.其原因是：当前结构的候选邻居接近n2，每一个候选邻居都是一个n×n的矩阵，故需要n4的存储空间.对于PC和PC-Stable以及MMHC算法，时间代价过高.究其原因：随着数据维数的增加以及变量对的非独立性关系的成立，导致条件集规模迅速增大，从而使得独立性检测次数的指数级增长速度很快.

然而，本文提出的BNSvo-learning算法不仅不会遭遇到上述其他算法内存不足或时间代价高的情况，而且通过和真实结构的对比，除了Child数据外，解的质量优于对比算法.这不仅表现在简单的数据集Asia和Sachs上，而且对于高维稀疏的数据集Pigs依然出色.

为了说明BNSvo-learning算法在有限样本条件下的可靠性，我们分别在属性数是370，样本量是500，1 000，5 000的Alarm数据集[31]上进行了验证.由表3可以看出，在处理样本量小、属性数多的数据集时，BNSvo-learning算法依然表现良好.

Table3ResultsComparisonofOurMethodwithConstraint-BasedAlgorithms

表3 与经典基于约束的算法的对比实验结果

3.2 时间代价对比实验结果

本文提出的BNSvo-learning算法不仅在网络的结构质量上有保障，而且在时间的需求上也合理.下面我们分别从实验和理论进行验证和说明.表4给出了和经典算法在时间需求上的对比实验.

Table 4 Performance Comparison of Algorithms in Time Cost表4 算法在时间代价上的性能比较 s

从表4中可以看出，所提算法BNSvo-learning在时间性能上显著优于经典的算法，尤其在处理高维稀疏数据集Pigs时，该算法能在6 943 s中求解，而对比算法在以天为单位的时间内得不到解.其原因在之前的精度性能实验中已作了分析，这里不再赘述.

3.3 BNSvo-learning及其改进算法时间代价对比

我们分别选取了不同规模的数据集，从时间代价层面展示了2种算法的性能，如表5所示.从表5中可以看出，随着数据集属性数的增多，改进后的算法明显优于BNSvo-learning算法.

IBNSvo-learning算法时间代价小的主要原因有2点：1)当设置m(m(i,j),iindex)=0，算法没有再对变量对(m(i,j),i)执行条件独立性检测.具体而言，假设对于变量m(i,j)而言，还有w个待检变量，那么最坏的情况可能要执行2w次条件独立性检测.2)变量m(i,j)对应的其他变量的条件独立性检测次数减少.如果没有置0，最坏的情况下，条件独立性检测次数是2w+1；置0，最坏的情况下是2w.

Table 5 Performance Comparison of Algorithms in Time Cost表5 算法在时间代价上的性能比较 s

3.4 真实世界实验

为了评估所提出算法在实际应用中的效果，我们用真实的数据集进行了实验.该数据集来源于供热机组3个月全工况监测数据.其中数据维数为50，每个月的样本量分别为43 200，44 640，44 641条，变量的最大状态数是10.由于没有真实的网络结构，我们仅在时间代价性能上做了对比实验.表6给出了在真实的电力数据集上关于需求时间的对比实验.

Table 6 Performance Comparison of Algorithms in Time Cost表6 算法在时间代价上的性能比较 s

从表6可以看出，当数据维数适中、样本量较大时，所提算法依然能够在合理的时间内求解，这表明BNSvo-learning算法能够很好地扩展到大样本量的数据集上.此外，经典的爬山算法表现得相对很差，主要原因是样本量过大使得评分函数需要的计算时间加长.

4 总结与展望

本文的贡献如下：1)首次尝试提出使用变量间互信息来刻画变量序的度量信息矩阵，以实现条件独立性检验不是盲目地选择变量对，而是依赖于度量信息矩阵提供的信息有选择地进行；2)基于度量信息矩阵提议了一种合理的“偷懒”启发式策略，有效地避免高阶独立性，减少检验次数，保证了检验可靠性.我们从理论上证明算法的有效性，从实验上验证了算法的高效性和可靠性.但是由于在定向阶段我们采用了与PC算法类似的方式，这种方式对个体定向错误敏感，尤其是υ-结构的定向，后期将探讨采用评分-搜索的策略解决定向问题；另外，对于数据集Child，本文所提算法虽然在时间性能和Missing上优于对比算法，但会导致过多的Additional和Reverse.跟踪实验发现，Additional主要是由于当样本数小于自由度时(相关概念读者可查阅文献[20])经典的算法和所提算法都采用了选择依赖的方法，后期我们将针对该问题进行研究.

QiXiaolong, born in 1981. PhD candidate and lecturer. His main research interests include probabilistic graphical models, machine learning.

GaoYang, born in 1972. PhD, professor, PhD supervisor. Committee member of CCF. His main research interests include reinforcement learning, agent theory (belief revision) and multi-agent systems, intelligent system, image process and video surveillance.

WangHao, born in 1983. PhD, assistant researcher. His main research interests include rank-aware query processing, reco-mmender systems, reinforcement learning & transfer learning (wanghao@nju.edu.cn).

SongBei, born in 1994. Master candidate. Her main research interests include industrial big data analysis, probabilistic graph model (songbei07@gmail.com).

ZhouChunlei, born in 1973. Engineer. Her main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (13913918185@163.com).

ZhangYouwei, born in 1986. Engineer. His main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (15905166639@163.com).