基于课程学习权重集成的贝叶斯结构学习算法研究

刘凯越，周鋆

国防科技大学 信息系统工程重点实验室，湖南 长沙 410073

贝叶斯网络(Bayesian network, BN)，又称信念网络，在1985 年由Pearl[1]首先提出，是一种模拟人类推理过程、处理不确定性知识的一种图模型。BN 通过有向无环图和条件概率表可以清晰表示出变量之间的关系，帮助进行决策，为不确定性推理体系提供强有力的工具。目前，BN 已成功地应用于概率推理和因果建模的各种任务，同时在风险评估[2]、故障诊断[3]、决策系统[4]、基因序列分析、生物医学图像处理和疾病预测[5]等领域得到越来越多的应用。目前的BNSL 方法都是通过训练全部数据样本来进行学习节点之间的依赖关系，容易出现数据量过大、训练时间过长、容易陷入局部最优的问题。

由于认知科学的启发，Bengio 等[6]提出了课程学习(curriculum learning, CL)的概念，让模型从简单样本学习逐步过渡至复杂样本。CL 在计算机视觉和自然语言处理等多种场景下，在提高各种模型的泛化能力和收敛率方面表现出了强大的能力[7]。

本文基于课程学习思想，提出了一种基于课程学习权重集成的结构学习 (Bayesian network structure learning based on curriculum learning weight integration, BN-CW)算法，通过模仿人类学习认知过程，分阶段构造BN。该算法首先对原始数据集进行采样，对15 次骨架结构学习执行一次集成学习。对于每个训练样本，衡量节点之间的相互影响程度，从具有简单依赖关系的样本节点到复杂且依赖关系不明显的节点，根据相应课程阶段分配课程权重，将各学习结果所获得的网络边的权重进行集成，并利用边过滤来去除错误的边，将正确的边加入白名单，提高搜索效率和学习结果的精确度。

本文的研究重点包括4 个方面：

1）针对网络中节点之间的相互影响程度，提出了一种基于课程权重的互信息公式，相较于传统的互信息公式，可以更好地识别出变量之间的相互影响程度，且可以动态识别出各个课程阶段节点之间相互影响程度的变化。

2）基于课程阶段的划分，分阶段构造学习网络框架，在集成迭代中不断强化为修正项的学习，大大减少错误边的出现。

3）通过边约束策略增加正确边的可靠性，严格限制了错误边的出现，大大缩小了BN 的搜索空间，提高了后续搜索算法的效率。

4）在不同标准数据集上的实验结果表明，本文提出的BN-CW 算法可以有效减少BN 中学习的误差，提高结构学习的效率和准确度。

1 贝叶斯网络学习相关工作

1.1 贝叶斯结构学习方法

贝叶斯结构学习(Bayesian network structure learning, BNSL)方法是给定问题领域中的变量，以及这些变量的相关观测数据，学习变量间的相互影响关系的过程。由于结点间的影响是有向的，需要用一个有向无环的网络结构来描述，结构学习就是寻找与训练数据匹配度最好的BN 结构。通过大量的样本数据来提炼挖掘变量之间潜在的关系是目前BNSL 的一个主要趋势。然而由于候选结构的数量随着节点数量的增加呈现指数级的增长数据学习，因此BNSL 是多项式复杂程度的非确定性问题(non-deterministic polynomial,NP)[8]。目前主流的结构学习算法主要有：基于约束结构学习算法(constraint-based structure learning algorithm, CB)[9]、基于评分结构学习算法(scorebased structure learning algorithm, SB)[10]以及混合结构学习算法(hybrid structure learning algorithm,HS)[11]。

相较于SB 和HS 算法，CB 是目前发展较为活跃的算法，主要由评分函数和搜索算法2 部分组成。学者们侧重于通过对评分函数和搜索算法进行优化以提高算法的求解能力和准确度。评分函数主要包括基于信息论和基于贝叶斯2 种，具有代表性的评分函数包括K2 评分(CH 评分)[12]、贝叶斯– 狄利克雷等价一致先验(Bayesian Dirichlet equivalent uniform prior, BDeu)评分函数[13]、贝叶斯信息准则(Bayesian information criterion,BIC)评分函数[14]等。BN 的搜索空间可以分为有向无环图(directed acayclic graph, DAG)[15]、等价类[16]和节点序搜索空间[17]3 种。大部分的结构学习方法是在DAG 空间中进行搜索的，但DAG 搜索空间会随着节点数的增加呈现指数级的增长，常用的搜索策略为爬山搜索[18]、迭代搜索[19]、分布估计算法[20]等。相较于DAG 搜索空间，等价类空间搜索空间较小，且基于马尔可夫等价类进行划分，存在空间难以判断且复杂的问题。节点序搜索空间是按照节点的拓扑顺序进行划分的，算法的精确度对于节点序具有较强的依赖性[21]。虽然基于评分函数的搜索算法有较高的准确度和效率，但当数据结构复杂时，搜索空间过大使得算法很难收敛，难以在巨大的搜索空间内寻找到最优的网络结构。

为了解决BN 结构学习中的一些主要问题，许多研究人员已经提出了一些优化策略，包括引入先验知识[22]、集成学习[23−24]、专家知识整合[25]和矩阵分解[26]。但这些方法都是通过将训练样本整体放入算法中进行学习，来发现变量之间存在的依赖关系。在学习一些依赖关系时，不仅学习到的节点之间的数据噪声会影响到节点之间依赖关系的确立，一些无关的样本节点噪声也会干扰学习过程，导致错误依赖关系的建立。虽然一些学者通过A*剪枝操作[27]、添加约束[28]等操作来降低，数据中存在的大量噪声仍然会影响到算法本身的学习过程。

1.2 课程学习

2009 年的国际机器学习大会(International Conference on Machine Learning, ICML)上Bengio等[6]首次在机器学习的背景下提出了课程学习的概念，旨在通过模仿人类认知学习过程，从简单样本出发逐步过渡到复杂样本，使得模型具有更高的效率和准确度。课程学习的本质是非凸优化中延拓方法的扩展，从更平滑的目标函数逐步过渡至不太光滑的函数。随后，很多学者在相应的应用领域寻求课程学习的策略，比如弱监督物体定位[29]、物体检测[30]以及神经机器翻译[31−32]等，这些工作均证明了课程学习在小批量抽样中常规培训的明显好处。首次将课程学习策略应用与BNSL 的是文献[33]，通过课程学习的思想来增量构建BN 结构，并将各个阶段学习到的DAG 结构作为下一阶段的初始网络结构，最终学习到完整的网络结构。课程学习虽然在各个领域都取得了较为显著的成功，但主流著作中对于课程学习的研究仍相对较少，尤其是在贝叶斯结构学习方面。

考虑到前期课程阶段学习结果对后续课程阶段的影响，一旦前期课程阶段学习到错误边，会误导后续课程阶段的继续学习错误边。因此本文在前文研究的基础上，不再将前期课程阶段学习到的结果直接用于后续的课程学习，而是通过分配课程权重和权重集成约束的方式，将上一阶段的课程学习结果仅作为后续课程学习的参考，通过权重约束逐步减少错误边的出现，提高可靠边的数量。

2 BNSL 基本概念

2.1 贝叶斯网络

BN 由DAG 和对应的条件概率表组成。DAG 中的节点表示随机变量{X1,X2,···,Xn}，这些变量涵盖范围较为广泛，可以是可观测到的变量、隐变量，或者是未知参数等。节点之间的有向边表示2 个节点之间存在依赖关系并非条件独立的，其关系的依赖程度用条件概率表示。BN 结构的数学表示为

式中：V为BN 中的所有节点的集合，E为BN 结构中存在的边的集合。

BNSL 的目标是通过学习得到与样本数据集拟合度最高的网络结构。评分函数通常被用于判断BN 的好坏。本文采用BIC 评分函数，BIC 是在样本满足独立同分布假设的前提下，利用对数似然来衡量结构与数据之间的拟合程度。

式中：qi为变量xi父节点值组合的数量；misk为xi的父节点取s的值，xi取k值时的样本数量； θisk是似然条件概率，0 ≤θisk≤1。

2.2 权重互信息的构建

为了更好地划分课程阶段，衡量样本节点之间的相互影响程序，提出了权重互信息(weights of mutual information, WMI）。

定义1已知数据集D中2 个节点变量Xs和Xt，其Xs和Xt之间的相互影响程度WMI 的计算公式定义如下：

式中：I(Xs,Xt)是节点Xs和Xt的互信息；W(Xs)为节点的课程权重值；Ind(Xs)为节点Xs在课程集合中的位置，即权重由课程节点在课程中的学习次序决定。

3 基于BN-CW 的贝叶斯结构学习

本文主要是基于课程学习权重集成的思想来分阶段构建贝叶斯网结构，利用爬山法(hill climbing, HC)搜索到最终的网络结构，图1 给出了算法的整体框架。

图1 BN-CW算法框架

算法分为4 个阶段：

1）集成采样过程。通过Bagging 集成抽样，通过可重复的抽样技术生成多个数据集。

2）课程学习阶段。利用WMI（Xi,Xj。）选择候选节点Hi与课程节点集合中各节点Ci相关性最强的节点作为下一个课程节点。根据课程阶段，得到课程节点之间的依赖关系，得到无向初始网络结构G∗，不同的课程权重分配给学习的边。

3）集成学习阶段。根据集成学习的结果，通过评分优化函数对每次得到的无向图骨架进行迭代优化，得到每条边集成后的权重值。

4）边过滤与搜索。通过集成学习优化得到的骨架，得到无向图骨架权重表示Wk，通过设置阈值删除权重不满足阈值 α的边，将得到的骨架作为初始DAG，通过爬山算法和BIC 评分函数得到最终的BN 结构。

3.1 课程阶段的划分

BN-CW 算法构建基于课程学习的BN，在培训步上训练标准序列C={Q1,Q2,···,Qn}。图2 给出了BN 构建的课程匹配机制、计算节点间以及节点与集合之间的相互影响程度，划分课程阶段，对不同课程阶段学习到的边匹配不同的权重。

图2 BN 构造的课程匹配机制

3.1.1 初始节点的选取

信息熵表示信息流中的平均信息量。对于由多个离散信源组成的信息，其信息熵可以用信源概率的负对数的均值来表示。

式中：pi为信息源出现的概率，n为信息源个数。

根据信息熵的定义，对于一个事件，整体概率越小，包含的信息量越大。扩展到网络中的节点，信息熵越小，节点包含的信息量越少，越容易学习。按照由浅入深的思路，初始节点满足：

3.1.2 后续课程节点的选取

根据课程学习的思想，为了考虑不同课程阶段下课程节点与候选节点之间整体影响程度的变化，通过WMI 来衡量变量之间的关联方式，WMI 可以更加准确描述变量可能存在的依赖关系，且不受数据节点序列的影响，更具有鲁棒性。

定义2将数据集D中的节点划分为课程节点集合Ci和候选节点集合Hi，其划分依据如下：

定义3数据集D中候选节点Xi与课程集合Ci中各课程节点的最大权重互信息定义如下：

通过衡量各个候选节点集合节点与课程节点之间的权重互信息，将满足条件的候选节点加入下一阶段的课程节点。

3.2 初始网络构建

3.2.1 无向图骨架构建

本文采用集成优化的思想对原始数据进行采样，每隔15 次设置一次集成学习。对于每个训练样本，课程学习构造的骨架Si被用作先验知识，对每次集成学习得到的骨架进行优化，得到更优的骨架Sbi。骨架优化函数 cs是将2 个骨架结构进行比较，将相同的边放入Es中，将不同的边放入Ed中，将相同的无向边添加到初始骨架中，遍历Ed中的边eij并将其添加到Si−1，比较得分变化。如果得分增加，则将其相加，直到得分不再增加。遍历结束形成一个骨架结构Sbi并获得一个权重矩阵Wi。它的定义如下：

其中，骨架中的边划分为

式中：eij为节点i和节点j之间的边，Si为经过第i次采样后学习到的BN 骨架，Es为2 次采样后网络学习都存在的边，Ed为采样后学习过程中出现的相异边。

式中：s(Si−1)为学习到的骨架结构Si−1的评分值，则为骨架结构Si−1加入边eij后所得到的评分值。当Ed为1 时，保留骨架中对应的eij，相反则删除eij。对于多次学习后学到的相同边执行保留操作。

3.2.2 权重集成和边过滤

通过每次学习到的骨架的权重矩阵集合W进行集成，权重值表示每条边学习到的可信度，权重值越高，表示学习到该条边的可靠性更大，权重值的合理分配为后续贝叶斯结构学习提供了更加可靠的初始骨架结构。每条边的权重定义为

式中：n为优化次数，s为课程阶段数目，为第k次迭代后在第s次课程中节点Xi和Xk之间边出现的次数。

为了确保学习到的骨架结构的准确性并减少搜索空间，对学习边设置约束，计算平均权重avgW，并根据经验值设置阈值 α为0.6，如果Weij＜avgW，则删除eij；否则，保留对应的边eij。

具体的算法如算法1 所示。

算法1BN-CW 算法

输入：训练数据集D、样本大小n、BN 节点集合X、学习步长t、课程数量nc

输出：对应的BN 结构DAG

4 实验结果与分析

4.1 实验设置与数据集

本文使用Python 语言中的Pgmpy 工具包。选取了4 种不同规模的标准数据集进行对比实验，通过抽样形成了不同数据规模的样本。根据实验对比效果，BN-CW 算法中的学习步长t根据数据集的出入度进行设计；实验中所涉及到的相关数据集如表1 所示。

表1 标准数据集

4.2 结果分析

为了验证算法的有效性，本文涉及到的指标有F1 分数(F1-Score)、结构汉明距离(structural Hamming distance, SHD)、正确边数(true positive,TP），对生成的BN 进行评价。SHD 值越小表示学习到的BN 越接近真实网络，TP 值越大说明学习到的正确边越多。

4.2.1 WMI 和MI 的对比

验证WMI 方法的有效性，选取互信息(mutual information, MI)值作为参照，对WMI 值和MI 值方法构建的初始网络的进行了对比实验，来判断WMI 方法是否具有更好地分析变量间相互影响程度的能力。对4 种标准数据集分别进行采样，共32 组对比实验，而每一组对比实验有10 组数据，实验结果是10 组实验结果的平均值和与最优值的百分比。实验结果如图3 和图4 所示。

图3 比较使用WMI 和MI 构建初始网络的SHD 实验结果

图4 比较使用WMI 和MI 构建初始网络的TP 实验结果

图3 和图4 详细绘制了标准数据集上MI 和WMI 方法构造出来的BN，在Cancer 数据集的实验结果中，WMI 方法只有在采样500 次的错误边数和MI 方法相同，其他指标均大大优于MI 方法；在Asia 数据集上可以明显看出WMI 方法在各项指标上完全由于MI 方法。对于Child 和Alarm 数据集，WMI 方法在一些指标上略差于MI 方法，由于节点数目较多时，课程阶段的划分影响了WMI 对于数据节点之间影响关系的判断。

4.2.2 不同数据集下BN-CW 算法和其他算法性能对比

实验中对4 种标准数据集分别采样，样本大小为500、1 000、1 500 和2 000，与HC、皮特–克莱克算法(Peter-Clark algorithm, PC)、最大最小爬山法(max-min hill-climbing, MMHC)[34]、基于迹指数和增广拉格朗日的非组合优化(non-combinatorial optimization via trace exponential and augmented lagrangian for structure learning, NOTEARS[35]、遗传算法(genetic algorithm, GA)和基于遗传算法改进的粒子群算法(particle swarm optimization with genetic algorithm, PSO-GA)[36]等算法进行对比，每组对比实验有10 组 数据，取10 组数据的平均值，实验结果如图5 和图6 所示。从图5 中可以看出，在SHD 的表现上，BN-CW 算法相较于其他结构学习算法具有明显的优势。对于Cancer 数据集，当样本量较小时，算法略次于NOTEARS 算法，但随着样本量的增大，汉明距离逐渐降低，当样本量大于或者等于1 k 时，BN-CW 算法相较于其他算法具有显著优势。对于Asia 和Child 网络，该算法均有明显优势。相较于其他算法，BNCW 算法性能表现较为稳定，说明了BN-CW 设置的边约束机制和集成优化策略可以显著降低错误边的出现概率。

图5 标准数据集上不同算法的汉明距离

图6 标准数据集上不同算法的F1-score

从图6 可发现，BN-CW 在4 种标准数据集上的F1-score 值均优于其他算法，特别是在Cancer和Alarm 数据集上，BN-CW 的优势远超过其他算法。而在Child 和Asia 网络仅在部分样本略次于NOTEARS 算法和PC 算法。从F1-score 指标上也反映出BN-CW 算法具有更高的精确度，构建出来的网络结构更加接近真实结构。

通过图5 和图6 的分析可以发现，本文提出的BN-CW 算法在各数据集上均有较好的表现，说明该算法具有普适性。将初始无向骨架作为先验知识用于结构学习，能够有效压缩搜索空间，提高算法的搜索效率。课程阶段的不断学习可以不断地加强正确边的学习，弱化错误依赖关系的影响，减少错误边的出现，边约束可以进一步地过滤掉错误边，这也是算法在汉明距离表现出色的原因。特别对于大型网络，在学习过程中，通过不断调整优化骨架结构使得初始网络不断接近真实网络，因此生成的BN 也会越接近真实网络。但是BN 的搜索学习最终是通过HC 算法实现的，与标准网络相比还存在一定的误差(如多边、反边)，容易陷入局部最优。由于是对于节点数目较多的中大型网络，这也是在这些数据集上的某些指标为次优的原因。

5 结束语

本文结合课程学习思想和集成策略进行BNSL 中，提出了BN-CW 算法，提出了WMI 的概念，并推导了WMI 的计算公式，通过实验验证了WMI 相较于传统的互信息，具有更加优秀的识别变量关联程度的能力。课程阶段的划分学习，可以在集成迭代中不断加强对正确边的识别，并在课程阶段的学习过程中，大量减少了错误依赖关系的出现，一定程度上减少了错误边的出现。通过在标准数据集上进行实验，并与其他的结构学习算法进行对比，验证了算法在结构学习上的有效性和普适性。但在后期的搜索过程中使用HC 算法进行搜索，很容易陷入局部最优，导致算法效果的下降。未来的工作包括2 个方面：1）探索如何实现课程学习过程的反馈和自修正，实现学习过程中自调整；2）进一步研究如何将课程学习的思想应用于搜索的迭代优化过程跳出局部最优，从而优化算法的搜索效果。