引用本文

王海羽, 刘浩然, 张力悦, 张春兰, 刘彬. 基于节点块序列约束的局部贝叶斯网络结构搜索算法. 自动化学报, 2020, 46(6): 1210-1219. doi: 10.16383/j.aas.c180108

WANG Hai-Yu, LIU Hao-Ran, ZHANG Li-Yue, ZHANG Chun-Lan, LIU Bin. Local Bayesian Network Structure Searching Using Constraint of Node Chunk Sequence. ACTA AUTOMATICA SINICA, 2020, 46(6): 1210-1219. doi: 10.16383/j.aas.c180108

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180108

关键词

贝叶斯网络结构学习，定向最大支撑树，节点块序列，K2算法 

摘要

针对K2算法过度依赖节点序和节点序搜索算法评价节点序效率较低的问题, 提出一种基于节点块序列约束的局部贝叶斯网络结构搜索算法, 该算法首先通过评分定向构建定向支撑树结构, 在此基础上构建节点块序列, 然后利用节点块序列确定每个节点的潜在父节点集, 通过搜索每个节点的父节点集构建网络结构, 最后对该结构进行非法结构修正得到最优贝叶斯网络结构.利用标准网络将算法与几种不同类型的改进算法进行对比分析, 验证该算法的有效性.

文章导读

贝叶斯网络(Bayesian network, BN)是表示复杂概率知识的有力工具, 通过有向无环图和条件概率表表示变量之间的联合概率分布, 有助于理解变量之间的因果关系以及数据集特征[1], 已广泛应用于医学[2]、风险评估[3]、自然语言处理[4]等多个领域[5].贝叶斯网络学习主要包括结构学习和参数学习, 其中贝叶斯网络结构的准确度直接影响参数学习和推理结果精度, 但是通过数据学习贝叶斯网络结构是NP难的.国内外专家学者提出了许多从数据中学习贝叶斯结构的方法, 其中最常见的是基于评分搜索的算法[6], 这类算法通过评分函数对网络结构进行评分搜索, 寻找最优得分的网络结构, 可以学习比较精确的网络结构, 但随着网络规模的增加, 搜索空间呈指数增长, 且大部分启发式评分算法在进行种群迭代时会出现大量非法结构[7], 当网络规模较大时, 对非法结构的修正会产生较高的时间复杂度, 影响算法效率.

最大支撑树算法(Maximum weight spanning tree, MWST)[8]通过保留互信息[9]值最大的节点关系, 可以有效地缩减搜索空间.然而, MWST算法是通过随机选择根节点对结构中相邻的节点进行定向生成有向图, 该方法定向得到的边不具有因果语义, 结构准确度较低. Pearl[10]利用碰撞识别判断节点间因果关系, 该算法效率较高, 但只能对具有多父节点的边进行定向; Jiang等[11]通过相对条件平均熵对节点间关系进行定向, 该方法操作简单但准确率较低.

K2算法[11]利用节点序约束搜索过程, 可以显著减少搜索空间并有效避免产生非法结构且性能优于大部分经典算法和启发式算法.节点序对K2算法性能影响极大, 良好的排序需要大量的专家知识, 由于专家知识的差异性, 网络规模较大时难以实现[12].为此研究人员提出了许多解决方案, 如Chen等[13]结合信息论, 利用条件独立测试和穷举搜索进行节点间定向并对节点进行排序, 但该算法时间复杂度较高; Ko等[14]提出通过条件频率的方法确定K2算法的节点排序, 该算法通过简化搜索策略, 降低了时间复杂度, 但数据量对算法结果影响较大; Leray等[15]提出MWST-K2 (Maximum weight spanning tree-K2)算法, 通过最大支撑树拓扑排序生成节点序, 但由于最大支撑树算法定向的精度较低, 导致运行结果并不理想; Faulkner[16]提出K2GA (K2-genetic algorithm)算法, 以节点序视为遗传算法的染色体, 通过修改后的K2算法对每条染色体进行评分得到种群适应度, 并进行种群迭代, 将贝叶斯网络结构学习问题转化为节点序搜索问题; Wu等[17]利用蚁群算法对K2GA算法中的遗传算法进行替换, 提出K2ACO (K2-ant colony optimization)算法; Aouay等[18]提出PSOK2 (Particle swarm optimization-K2)算法, 通过粒子群算法对节点序进行更新, 利用节点序作为K2算法的先验知识进行贝叶斯网络构建, 通过AIC (Akaike information criterion)评分函数对网络结构进行评分得到对应节点序的适应度函数进行种群迭代, 但算法效率较低, 运行速度较慢; 刘浩然等[19]提出MAK (MWST-ACO-K2 (Maximum weight spanning tree-ant colony optimization-K2))算法, 该算法融合最大支撑树和蚁群算法搜索节点序, 在处理小型网络时可取得较理想的结果, 与K2GA、K2ACO、PSOK2等基于节点序搜索的贝叶斯结构学习算法类似, 需要对种群中所有个体运行K2算法得到对应的适应度值, 才能对种群进行更新迭代, 存在算法时间复杂度较高, 不同的参数设置对结果影响较大, 在大中型网络效果不理想等问题.

本文提出一种基于节点块序列约束的局部贝叶斯网络结构搜索算法(Bayesian network construction based on node chunk sequence constraints)- NCSC算法.算法首先对最大支撑树进行评分定向构建定向支撑树结构, 利用该结构搜索得到节点块序列.之后利用节点块序列作为搜索顺序, 将定向支撑树结构作为先验知识, 通过节点块序列确定每个节点的潜在父节点集, 对每个节点的父节点集进行搜索, 构建初始网络结构.最后对该结构进行非法结构修正, 得到最优贝叶斯网络结构.通过将位于相同节点块的节点视为等价节点, 避免对节点块内元素进行排列, 解决了基于节点序搜索的贝叶斯结构学习算法评价节点序时间代价严重的问题, 可以在不借助专家知识的情况下得到较为精确的贝叶斯网络结构.

图 1  由定向支撑树构建节点块序列的例子

图 2  由节点块序列搜索潜在父节点集的简单例子

图 3  Alarm网络中不同算法精度对比

针对K2算法过度依赖节点序, 节点序搜索算法评价节点序质量时间代价严重的问题.提出了一种基于节点块序列约束的局部网络结构搜索算法, 通过构建定向支撑树生成节点块序列, 同时将相同节点块内的节点视为等价节点, 有效地确定了每个节点的潜在父节点集, 扩展了每个节点集的搜索范围, 避免对节点块内元素进行排列, 解决了基于节点序搜索的贝叶斯结构学习算法评价节点序时间代价严重的问题.利用每个节点的父节点集构建初始网络降低了非法结构修正的次数.仿真实验表明, 在不使用节点序作为先验知识且无需人为设置复杂参数的情况下, 算法运行结果接近以标准节点序作为先验节点序的K2算法的精度, 与不同种类的改进算法相比, NCSC算法在精度和运行速度上都有不同程度的提高, 相比于简化爬山法运行速度平均提升了100倍以上.

作者简介

王海羽  

燕山大学信息科学与工程学院硕士研究生.主要研究方向为贝叶斯网络, 动态贝叶斯网络, 人工智能, 进化算法, 故障诊断与预测. E-mail: anderwwhy@outlook.com

张力悦  

燕山大学信息科学与工程学院硕士研究生.主要研究方向为智能算法, 贝叶斯网络, 故障诊断与预测. E-mail: zly15128506765@163.com

张春兰  

燕山大学信息科学与工程学院硕士研究生.主要研究方向为智能优化, 贝叶斯网络, 故障诊断与预测. E-mail: 15076053886@163.com

刘彬  

燕山大学信息科学与工程学院教授.主要研究方向为深度学习, 贝叶斯网络, 故障诊断与预测. E-mail: liubin@ysu.edu.cn

刘浩然  

燕山大学信息科学与工程学院教授.主要研究方向为贝叶斯网络, 人工智能, 无线传感器网络, 故障诊断与预测.本文通信作者. E-mail: liuhaoranysu125@163.com