2020, Vol. 41
2. 东北大学 计算机科学与工程学院, 辽宁 沈阳 110169
2. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
目前, 贝叶斯网络作为数据处理和分析工具被广泛应用, 特别是用于解决不确定性环境下的决策问题[1].在大数据环境下, 如何提高复杂贝叶斯网络学习和推理的时间效率是贝叶斯网络在新的应用环境下的挑战.
目前, 贝叶斯网络结构学习存在大量研究, 其中具有代表性的算法分为基于评分搜索的算法[2-4]和基于依赖分析的算法[5-7].基于评分搜索的方法以一个评分函数作为评定准则, 利用搜索算法在网络结构空间中寻找与训练数据最为匹配的最优网络结构.但是目前已证明寻找最优网络结构是一个NP难问题[8].基于依赖分析的方法是将贝叶斯网络视为表示独立节点间关系的图模型, 通过对其进行条件依赖及独立性检验, 获取对这些依赖和独立性关系给出最好解释的某个图模型的马尔可夫等价类, 经典算法包括SGS算法、PC算法[9]等.
一个节点的马尔可夫毯(Markov blanket, MB)是指图形模型中除去该节点的剩余节点中与之有信息传递的所有节点变量, 即该节点所有的父子节点和配偶节点.通过发现图结构中所有节点的马尔可夫毯可以高效地构建贝叶斯网络无向依赖图.现有的马尔可夫毯发现算法分为基于全局条件独立信息的发现算法和基于局部条件独立信息的发现算法.全局算法中候选的马尔可夫毯节点个数往往较多, 由于搜索策略的局限性, 数据效率普遍不高.基于局部条件独立信息的发现算法是通过检查单个节点X∉MB与目标节点的条件独立性来搜寻目标节点的马尔可夫毯, 而非直接对目标节点的马尔可夫毯进行寻找.这种方法所需的条件集合个数通常比节点的马尔可夫毯集合个数少, 因此学习效率相对较高.典型算法有PCMB(parents and children based Markov boundary)算法[10]和IPC-MB(iterative parent-child based search of Markov blanket)算法[11]等.
本文提出一种基于马尔可夫毯的贝叶斯网络结构学习算法(an improved structure learning algorithm of Bayesian network based on Markov blanket, IBN-MB).首先, 对经典马尔可夫毯发现算法(IPC-MB)进行改进, 提出一种改进的马尔可夫毯学习算法, 该算法能够高效、准确地发现节点的父子节点与配偶节点, 减少条件独立检验次数, 迅速建立贝叶斯网络结构的无向图.然后, 结合贝叶斯网络中D-分割特性和基于马尔可夫毯发现算法得到的局部拓扑结构即V结构, 以及BIC评分函数, 快速确定无向图中边的方向, 得到最优贝叶斯网络结构.最后, 以互联云的QoE评价为仿真实验背景, 建立模型并进行对比与分析.实验结果表明, 本文提出的IBN-MB算法能够高效确定贝叶斯网络结构, 排除网络结构的马尔可夫等价类, 在机器学习效率和预测精度方面均优于传统方法.
1 IBN-MB算法的设计本文提出的基于马尔可夫毯的贝叶斯网络结构学习算法分为三部分, 即改进的马尔可夫毯发现算法、基于拓扑信息确定有向边的方向和基于BIC评分函数确定有向边的方向.
1.1 改进的马尔可夫毯发现算法本文对已有的IPC-MB算法进行如下改进, 并提出了适合于贝叶斯网络结构学习的马尔可夫毯发现算法.
1) IPC-MB算法通过调用GenPC算法发现单个节点的马尔可夫毯, 但基于马尔可夫毯发现算法进行贝叶斯网络结构的学习时, 需要发现所有节点的马尔可夫毯.为防止对相同节点重复调用GenPC算法, 本文算法对所有节点调用GenPC算法来发现对应父子节点集合, 并将发现结果存储下来, 以方便后续配偶节点的发现.
2) 因为配偶节点只出现在贝叶斯网络结构D-分割中的汇连情况中, 目标节点T的V结构如图 1所示.为了后续节点快速发现马尔可夫毯, 本文算法对已发现节点的拓扑信息即V结构进行存储, 就可以从目标节点的父子集合中删除部分已知父节点, 从而更有效率地发现配偶节点.
|
图 1 V结构 Fig.1 V structure |
3) 本文算法利用条件独立测试发现目标节点T的配偶节点, 寻找并存储的V结构经过了多次条件独立性测试, 该结构是可信的、不变的, 因此存储的V结构能够在后续算法中高效确定边的方向.
4) IPC-MB算法的复杂度主要体现在GenPC算法的两层FOR循环上, 本文算法分别对两层循环进行优化, 提高算法效率.
原算法外层循环是从候选集合ADJ(T)中随机选择一个节点, 在目标节点T与该节点间执行条件独立性测试, 若两节点条件独立, 则将该节点从ADJ(T)中删除.改进算法根据与目标节点的依赖程度对候选节点集合中的节点进行排序, 首先对与目标节点依赖程度低的节点进行条件独立性测试, 这样能更快地从ADJ(T)中删除与目标节点条件独立的节点.依赖程度大小是通过G2测试中的检验统计量进行衡量的, 具体使用函数p的值, 如式(1)所示.p的值越大表明节点X与目标节点条件独立的可能性越大.每次外层循环时, 选择当前候选节点集合中p最大的节点与目标节点进行条件独立性测试.
|
(1) |
5) IPC-MB算法的内层循环为从候选节点集合中产生条件集S, 在该条件集下执行条件独立性测试, 判断是否将节点X加入目标节点的父子节点集合中, 该方法不加区分地对待候选节点集合中的所有节点.本文研究发现, 如果一个节点在之前的条件独立性测试中更多地参与条件集并有效分割路径, 那么在之后的测试中, 该节点被选中进入条件集的可能性越大, 因此本文提出如下定义作为节点被选为条件集的衡量标准.改进算法对给定变量集合S排序, 以便尽量选择可以有效分割目标节点与候选节点的条件集S.
定义1 如果集合S为节点X曾经参与过的条件集, 且该条件集曾有效分割路径, 则称为有效条件集, |S|为集合的大小.节点X被选进条件集的概率为
|
(2) |
对两节点执行条件独立性测试时, 条件集的大小不止为1, 因此需考虑一个集合被选作条件集的概率.
定义2 一个集合S被选作条件集的概率等于集合S中所有节点X(X∈S)被选入条件集的概率之和, 集合S被选作条件集的概率为
|
(3) |
6) IPC-MB算法得到的目标节点T的父子节点集合可能包含假正节点.
定义3 如果在候选节点集合ADJ(T)的任何子集下, 两个节点的条件独立性测试均显示两节点是条件依赖的, 那么这两个节点是邻接的, 且两个节点互为对方的父子节点集合中一员, 则该节点称为对方节点的假正节点(false positive).
如图 2所示, 若求目标节点T的父子节点集合, 当条件集的大小为0时, 节点B与T独立, 此时从ADJ(T)中将节点B删除, 但节点T, C在条件集合{A, B}下条件独立, 因此过早删除节点B将会导致在后续的条件独立性测试中, 无法测试出节点T与C条件独立, 导致节点C在GenPC过程结束后依然存在于节点T的父子节点集合中.
|
图 2 对称原则示例 Fig.2 Example of symmetry principle |
为解决上述问题, 改进算法使用两个节点间的对称关系, 即两个节点相互在对方节点的父子节点集合中删除多余的假正节点.在图 2中, 节点T经过GenPC算法后得到父子节点集合CPC(T)={A, C}, 对C调用GenPC过程得到父子节点集合CPC(C)={A, B}, C∈CPC(T)而T∉CPC(C), 不满足节点间的对称关系, 因此C是T的假正节点, 可将节点C从T的父子节点集合中删除.
基于以上改进, 本文提出了改进的马尔可夫毯发现算法(算法1), 该算法通过调用改进的GenPC算法(算法2)和GenSET算法(算法3)完成了贝叶斯网络所有节点的马尔可夫毯的发现并存储了局部拓扑信息即V结构用于后续边的方向确定.
算法1 改进的马尔可夫毯发现算法
|
表 |
算法2 改进的GenPC算法
|
|
表 |
算法3 GenSET算法
|
|
表 |
其中, 第1~6行是对所有节点调用改进的GenPC算法发现所有节点的父子节点集合, 通过第2行将CanADJ(T)设置为网络结构中除节点T外所有的节点.第7~23行发现所有节点的马尔可夫毯集合.其中, 第8行将节点T的马尔可夫毯初始化为其父子节点集合.第10行中CanSP为节点X的父子节点集合, 表示目标节点将从其子节点的父子节点集合中寻找配偶节点.第11~13行采用了对称原则.第14~21行通过条件独立性测试来寻找目标节点的配偶节点, 这里检验条件独立性使用的测试方法为G2测试.第16~19行存储在目标节点T的马尔可夫毯发现过程中得到V结构.
改进的GenPC算法发现父子节点的基本原理如下:在一个可信网络理论中, 如果节点X, Y满足对于所有的Z(Z⊆U-{X, Y}), 均不存在X⊥Y|Z, 那么节点X, Y在贝叶斯网络中是邻接的.因此, 只要证明对任一集合Z(Z⊆U-{X, Y})的条件下, 存在X⊥Y|Z, 那么节点X, Y是不邻接的, 它们之间不存在边.在候选节点集合的所有子集条件下, 检验节点T与候选节点X间的条件独立性, 一旦存在一个条件集S, 使得X⊥T|S, 则将候选节点X从CPC(T)中删除.
其中, 第7~14行进行目标节点与候选节点的条件独立性测试, 若测试通过, 则在第8行将候选节点从候选集合中删除; 第9行存储两节点条件独立的条件集; 第10~12行更新条件集中所有节点被选入条件集的概率, 第19行将ADJ(T)赋值给父子节点集合CPC(T); 第20行返回目标节点的父子节点集合.
GenSET算法的主要目的是返回排序后的、给定大小的条件集.
1.2 基于V结构确定边的方向本文提出的IBN-MB算法设计两种贝叶斯网络结构中边的方向的确定方法.其中, 基于V结构的边的方向确定方法具体过程分为以下两个步骤:一是直接根据马尔可夫毯发现算法中得到并存储的V结构确定边的方向; 二是根据V结构进行一定推理来确定边的方向.
本文提出的改进马尔可夫毯发现算法中采取的是后向策略, 即删除已确认的不邻接节点, 因此已发现的目标节点的父子节点集合必然包含最终网络结构中所有节点的父子节点集合, 根据父子节点集合进一步推导出的V结构也必定包含最终网络结构中所有的V结构.由此可知, 在下一步确定边的方向时不会再产生V结构.根据D-分割理论, 贝叶斯网络结构中3个节点之间只存在顺连、分连和汇连三种结构.而汇连结构就是V结构, 由于网络结构中不会再产生该结构, 因此在确定边的方向时只可能产生顺连和分连两种结构, 通过以上理论进行推理, 确定剩余边的方向.
1.3 基于BIC评分函数确定边的方向基于本文算法中得到的V结构基本可以确定贝叶斯网络结构中边的方向, 但是也有特殊情况, 即不能通过V结构确定所有边的方向, IBN-MB算法给出了基于BIC评分函数的解决方案.
BIC评分函数是在样本满足独立同分布假设的前提下, 用对数似然度度量结构与数据之间的拟合程度.具体评分函数式为
|
(4) |
式中:G是由n个节点构成的贝叶斯网络结构; D为给定的数据集, 样本集数目为m; ri为第i个节点Xi的取值空间大小, Xi的父节点集合π(Xi)中所有可能的取值组合个数
利用BIC评分函数对剩余边的方向进行确认时, 需要将评分函数进行分解, 使其变为局部结构的评分函数:
|
(5) |
式中:第1项为度量结构与数据之间的拟合程度; 第2项为对模型复杂度的罚项, 防止过度拟合情况的出现.
当节点X与Y之间存在一条未确定方向的边时, 首先假定这条边为X→Y, 即Y为X的父节点, 这种情况下局部结构的BIC评分为S1, 如式(6)所示:
|
(6) |
然后假设这条边为X←Y, 即X为Y的父节点, 这种情况下局部结构的BIC评分S2为
|
(7) |
比较S1与S2的大小, 若S1 < S2, 说明S1代表的网络结构即为最优结构, 即有向边方向为X→Y; 反之, 则X←Y.
贝叶斯网络为有向无环图, 但得到的贝叶斯网络结构可能有环路存在, 需要进行解环操作.具体方案为:若环与V结构并存, 首先保证涉及V结构的边的方向不作改变, 之后将其余边中任意一条边的方向改变, 达到解环的效果; 若两者不并存, 则直接将三条边中任意一条边的方向改变解环.
2 仿真实验与结果分析 2.1 仿真实验设计本文构建基于贝叶斯网络的互联云QoE评价模型作为仿真实验的背景, 验证所提出算法的准确率和效率.实验设计了互联云应用测试环境, 开发了视频播放应用, 实验中邀请每位用户观看在不同网络传输状况下的9段视频, 并分别对这些视频给出QoE评分, 汇总并存储为QoE评价数据集.然后随机分为训练样本和测试样本, 使用K-折交叉检验算法进行训练, 其中K=10, 基于本文提出的IBN-MB算法训练得到的贝叶斯网络互联云QoE评价模型如图 3所示.模型中的节点分别代表QoE及其部分影响因素:X1表示视频类型, X2表示用户性别, X3表示网络延迟, X4表示网络带宽, X5表示视频码率, X6表示用户清晰度感受, X7表示视频分辨率, X8表示用户响应速度感受, X9表示用户流畅度感受, Y表示用户给出的QoE评价.
|
图 3 QoE评价模型贝叶斯网络结构图 Fig.3 Structure of QoE evaluation model based on BN |
使用决策树C4.5算法与IBN-MB算法进行性能对比与分析.为了反映本文设计的互联云QoE评价模型的优劣, 将通过以下几个指标进行性能评价.
1) F-measure:F-measure综合了预测准确率与召回率两方面指标, 其中预测准确率见性能指标2的定义.召回率Recall定义为正确预测QoE值的个数占应被成功预测的QoE值个数的比例.其中, BNFi为属于第i类但未被正确识别的测试样例的个数.
|
(8) |
|
(9) |
F-measure综合了预测准确率与召回率两方面指标, 定义为
|
(10) |
2) 预测准确率:预测准确率是指从给定的QoE评价指标中正确预测QoE值的个数占所有个数的百分比.预测准确率计算公式为
|
(11) |
|
(12) |
式中:BNCi为正确识别的第i类测试样例的个数; BNIi为属于第i类的测试样例的个数; M为QoE取值空间个数.
3) 时间开销:时间开销是衡量人工智能模型性能的重要指标.本文利用对条件独立性测试(conditional independence test, CI)的调用次数作为衡量模型时间开销性能的具体方法.
通过以上3个性能指标, 对基于IBN-MB算法与C4.5算法的评价模型进行了仿真实验.实验结果分析如下:
1) 对模型的F-measure指标进行比较, 令k为10, 结果如图 4所示:随着样本数的增加, 基于两种算法的评价模型的F-measure值均呈现平缓上升的趋势, 样本数与预测准确率近似呈线性关系.基于IBN-MB算法的F-measure值略高于基于C4.5算法的评价模型.
|
图 4 不同IBN与C4.5算法时样本数对F-measure的影响 Fig.4 Effect of sample number on F-measure under different IBN and C4.5 |
2) 对基于IBN-MB算法与C4.5算法训练的模型预测准确率进行对比, 结果如图 5所示.
|
图 5 不同IBN与C4.5算法时样本数对预测准确率的影响 Fig.5 Effect of sample number on prediction accuracy under different IBN and C4.5 |
当k为10时, 随着样本数的增加, 基于两种算法的评价模型预测准确率均呈现稳步上升的趋势, 且上升趋势趋于稳定.基于IBN-MB算法的评价模型预测准确率略高于基于C4.5算法的评价模型.
3) 分别令k取3, 5和10时, 对基于IBN-MB算法的评价模型预测准确率进行验证, 结果如图 6所示.可知, 随着样本数的增加, 基于IBN-MB算法的QoE评价模型预测准确率呈逐步上升的趋势.当k取10时, 评价模型的预测准确率基本最高, 当k取3时, 模型的预测准确率最低.
|
图 6 不同k时样本数对预测准确率的影响 Fig.6 Effect of sample number on prediction accuracy under different k |
4) 分别对评价模型的时间开销指标进行比较, 基于IBN-MB算法的评价模型中调用CI测试次数明显低于基于PC算法.这是因为IBN-MB算法在构建无向图时, 使用了存储网络结构拓扑信息和对候选节点排序等改进策略, 因此能够尽早删除与目标节点条件独立的节点, 从而降低了CI测试次数, 减少时间开销.
3 结论1) 本文提出一种改进的基于马尔可夫毯的贝叶斯网络结构发现算法, 该算法能高效、准确地发现父子节点与配偶节点, 确定贝叶斯网络结构无向图.在此基础上高效确定拓扑结构中边的方向.
2) 基于本文算法对互联云QoE评价问题进行建模, 仿真实验结果表明, 新算法在准确率和性能上均优于传统算法.
| [1] |
Pearl J. Probabilistic reasoning in intelligent systems[J]. Computer Science Artificial Intelligence, 1988, 70(2): 1022-1027. |
| [2] |
Chua C, Ong H. Comparison of scoring functions on greedy search Bayesian network learning algorithms[J]. Pertanika Journal of Science & Technology, 2017, 25(3): 719-734. |
| [3] |
Gheisari S, Meybodi M R. BNC-PSO:structure learning of Bayesian networks by particle swarm optimization[J]. Information Sciences, 2016, 348: 272-289. DOI:10.1016/j.ins.2016.01.090 |
| [4] |
Yuan C, Malone B. Learning optimal Bayesian networks:a shortest path perspective[J]. Journal of Artificial Intelligence Research, 2013, 48(1): 23-65. |
| [5] |
Beek P V, Hoffmann H F. Machine learning of Bayesian networks using constraint programming[J]. Lecture Notes in Computer Science, 2015, 9255: 429-445. |
| [6] |
Kojima K, Perrier E, Imoto S, et al. Optimal search on clustered structural constraint for learning Bayesian network structure[J]. Journal of Machine Learning Research, 2010, 11(1): 285-310. |
| [7] |
Perrier E, Imoto S, Miyano S. Finding optimal Bayesian network given a super structure[J]. Journal of Machine Learning Research, 2012, 9(4): 2251-2286. |
| [8] |
周志华.机器学习[M].北京: 清华大学出版社, 2016. (Zhou Zhi-hua.Machine learning[M].Beijing: Tsinghua University Press, 2016. ) |
| [9] |
Spirtes P, Glymour C, Scheines R. Causation, prediction, and search[J]. Computer Journal, 2001, 36(3): 3568-3580. |
| [10] |
Gao T, Ji Q. Efficient Markov blanket discovery and its application[J]. IEEE Transactions on Cybernetics, 2016, 47(5): 1169-1179. |
| [11] |
Schlüter F. A survey on independence-based Markov networks learning[J]. Artificial Intelligence Review, 2014, 42(4): 1069-1093. DOI:10.1007/s10462-012-9346-y |