计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (10): 230-238.doi: 10.11896/jsjkx.221000046

• 人工智能 • 上一篇    下一篇

基于演化序搜索的混合贝叶斯网络结构学习方法

李明嘉, 钱鸿, 周爱民   

  1. 华东师范大学计算机科学与技术学院 上海200062
    华东师范大学上海智能教育研究院 上海200062
  • 收稿日期:2022-10-09 修回日期:2023-03-12 出版日期:2023-10-10 发布日期:2023-10-10
  • 通讯作者: 钱鸿(hqian@cs.ecnu.edu.cn)
  • 作者简介:(51205901074@stu.ecnu.edu.cn)
  • 基金资助:
    国家自然科学基金(62106076);上海市科学技术委员会科技创新行动计划项目(19511120601);上海市自然科学基金面上项目(21ZR1420300);上海市教育委员会与上海市教育发展基金会“晨光计划”项目(21CGA32);中央高校基本科研业务费专项资金

Hybrid Bayesian Network Structure Learning via Evolutionary Order Search

LI Mingjia, QIAN Hong, ZHOU Aimin   

  1. School of Computer Science and Technology,East China Normal University,Shanghai 200062,China
    Shanghai Institute of AI for Education,East China Normal University,Shanghai 200062,China
  • Received:2022-10-09 Revised:2023-03-12 Online:2023-10-10 Published:2023-10-10
  • About author:LI Mingjia,born in 1998,postgraduate.His main research interests include evolutionary machine learning,causal infe-rence and intelligent education.QIAN Hong,born in 1991,Ph.D,asso-ciate researcher.His main researchin-terests include derivative-free optimization,evolutionary machine learning,and intelligent education.
  • Supported by:
    National Natural Science Foundation of China(62106076),Science and Technology Commission of Shanghai Municipality(19511120601),Natural Science Foundation of Shanghai(21ZR1420300),“Chenguang Program” Sponsored by Shanghai Education Development Foundation and Shanghai Municipal Education Commission(21CGA32) and Fundamental Research Funds for the Central Universities.

PDF (PC)

1789

摘要： 贝叶斯网络是一种不确定性知识表示与推理的有效工具,学习其结构是利用这一工具进行推理的基础。现有的贝叶斯网络结构学习算法,在智能教育等应用场景中往往面临着难以权衡有效性与高效性的问题。一方面,评分搜索类方法能搜索到高质量的解,但面临着算法复杂度高的挑战。另一方面,混合类方法效率高,但所找到的解的质量不尽如人意。针对上述问题,提出了一种基于演化序搜索的混合贝叶斯网络结构学习方法(EvOS)。该方法首先通过约束类算法构建无向图骨架,然后利用演化算法搜索最优节点序,最后使用该节点序指导贪婪搜索得到贝叶斯网络结构。基于常用基准数据集以及教育知识结构发现任务,验证了所提方法的有效性与高效性。实验结果表明,所提方法相较于评分搜索类方法,能够在保持相仿精度的情况下最高加速百倍,且有效性显著高于混合类方法。

关键词: 贝叶斯网络, 结构学习, 序搜索, 演化优化, 知识结构发现

Abstract: Bayesian network is an effective tool for uncertainty knowledge representation and reasoning.Learning and discovering its structure is the basis of reasoning via this tool.Existing Bayesian network structure learning algorithms often encounter the dilemma of balancing effectiveness and efficiency in real-world applications such as intelligent education.On the one hand,score-and-search methods can find out the high-quality solutions,but they suffer from the high algorithmic complexity.On the other hand,hybrid methods are highly efficient but the quality of the found solutions is not satisfactory.To address the above dilemma,this paper proposes an evolutionary order search based hybrid Bayesian network structure learning method called EvOS.First,the proposed EvOS constructs an undirected graph skeleton through a constraint algorithm,and then applies an evolutionary algorithm to search for the optimal node order,and finally uses the found node order to guide the greedy search so as to obtain the Bayesian network structure.This paper conducts the empirical study to verify the effectiveness and efficiency of the proposed EvOS in the commonly-used benchmark datasets as well as the real-world task of educational knowledge structure discovery.Experimental results show that,compared with the score-and-search methods,EvOS is able to achieve up to 100 times speedup while maintaining the similar accuracy,and its effectiveness is significantly better than that of the hybrid methods.

Key words: Bayesian network, Structure learning, Order search, Evolutionary optimization, Knowledge structure discovery

中图分类号: 

  • TP183
[1]TING C,CHEAH W,CHIUNG C.Student engagement mode-ling using bayesian networks[C]//Proceedings of IEEE International Conference on Systems,Man,and Cybernetics.New York:IEEE,2013:2939-2944.
[2]LI J R,LING X B,LI C X,et al.Dynamic Network SecurityAnalysis Based on Bayesian Attack Graphs [J].Computer Science,2022,49(3):62-69.
[3]WANG S F,HE S,WU Y,et al.Fusion of visible and thermalimages for facial expression recognition [J].Frontiers of Computer Science,2014 8(2):232-242.
[4]XU Y Y,CHAI Y M,WANG L M,et al.Emotional Sentence Classification Method Based on OCC Model and Bayesian Network [J].Computer Science,2020,47(3):222-230.
[5]SPIRTES P,CLARK G,RICHARD S.Causation,prediction,and search [M].Massachusetts:MIT Press,2000:221-234.
[6]MARGARITIS D.Learning Bayesian network model structure from data [D].Pittsburgh,Pennsylvania:Carnegie-Mellon Univ,Pittsburgh Pa School of Computer Science,2003.
[7]SCHWARZ G.Estimating the dimension of a model [J].The Annals of Statistics,1978,6(2):461-464.
[8]AKAIKE H.A new look at the statistical model identification [J].IEEE Transactions on Automatic Control,1974,19(6):716-723.
[9]BUNTINE W.Theory refinement on Bayesian networks[C]//Proceedings of the 7th Conference on Uncertainty in Artificial Intelligence.San Francisco:Morgan Kaufmann,1991:52-60.
[10]HECKERMAN D,DAN G,DAVID M C.Learning Bayesiannetworks:The combination of knowledge and statistical data [J].Machine Learning,1995,20(3):197-243.
[11]COOPER G F,HERSKOVITS E.A Bayesian method for the induction of probabilistic networks from data [J].Machine Lear-ning,1992,9(4):309-347.
[12]LARRANAGA P,KUIJPERS C M H,MURGA R H,et al.Learning Bayesian network structures by searching for the best ordering with genetic algorithms [J].IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,1996,26:487-493.
[13]CHICKERING D M.Optimal structure identification withgreedy search [J].Journal of Machine Learning Research,2002,3:507-554.
[14]COOPER G F.The computational complexity of probabilistic inference using Bayesian belief networks [J].Artificial Intelligence,1990,42(2/3):393-405.
[15]TSAMARDINOS I,BROWN L E,ALIFERIS C F.The max-min hill-climbing Bayesian network structure learning algorithm [J].Machine Learning,2006,65(1):31-78.
[16]GASSE M,ALEX A,HAYTHAM E.A hybrid algorithm forBayesian network structure learning with application to multi-label learning [J].Expert Systems with Applications,2014,41(15):6755-6772.
[17]HOLLAND J.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan Press,1975:174-186.
[18]JIN Y C,SENDHOFF B.A systems approach to evolutionary multiobjective structural optimization and beyond [J].IEEE Computational Intelligence Magazine,2009,4(3):62-76.
[19]QIAN H,YU Y.Derivative-free reinforcement learning:a re-view [J].Frontiers of Computer Science,2021,15(6):156336.
[20]LARRANAGA P,POZA M,YURRAMENDI Y,et al.Structure learning of Bayesian networks by genetic algorithms:A perfor-mance analysis of control parameters [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(9):912-926.
[21]ETXEBERRIA R,LARRANAGA P,JUAN M P.Analysis ofthe behaviour of genetic algorithms when learning Bayesian network structure from data [J].Pattern Recognition Letters,1997,18(11／12／13):1269-1273.
[22]MATZKEVICH I,BRUCE A.The topological fusion of Bayes nets[C]//Proceedings of the 8th Annual Conference on Uncertainty in Artificial Intelligence.San Francisco:Morgan Kaufmann,1992:191-198.
[23]LV Y L,MIAO J Z,LIANG J Y,et al.BIC-based node order learning for improving Bayesian network structure learning [J].Frontiers of Computer Science,2021 15(6):156337.
[24]AOUAY S,JAMOUSSI S,AYED Y B.Particle swarm optimization based method for Bayesian network structure learning[C]//Proceedings of 5th International Conference on Modeling,Simulation and Applied Optimization.New York:IEEE,2013:1-6.
[25]WU Y H,JOHN M,DAVID C.Two novel ant colony optimization approaches for Bayesian network structure learning[C]//Proceedings of the 2010 IEEE Congress on Evolutionary Computation.New York:IEEE,2010:1-7.
[26]SPIRTES P,ZHANG K.Causal discovery and inference:con-cepts and recent methodological advances[C]//Proceedings of Applied Informatics.Springer Open,2016:1-28.
[27]PEARL J.Causality:models,reasoning and inference(SecondEdition)[M].Cambridge:Cambridge University Press,2009:123-145.
[28]SPIRTES P,MEEK C.Learning Bayesian networks with dis-crete variables from data[C]//Proceedings of the 1st Annual Conference on Knowledge Discovery and Data Mining,Montreal.Menlo Park:Morgan Kaufmann,1995:294-299.
[29]LAURITZEN S L,DAVID J S.Local computations with probabilities on graphical structures and their application to expert systems [J].Journal of the Royal Statistical Society:Series B(Methodological),1988,50(2):157-194.
[30]SACHS K,PEREZ O,PE'ER D,et al.Causal protein-signaling networks derived from multi parameter single-cell data[J].Science,2005,308(5721):523-529.
[31]SPIEGELHALTER D J,DAWID A P,LAURITZENS L,et al.Bayesian analysis in expert systems [J].Statistical Science,1993,8(3):219-247.
[32]BINDER J,KOLLER D,RUSSELL S,et al.Adaptive probabilistic networks with hidden variables [J].Machine Learning,1997,29(2):213-244.
[33]BEINLICH I A,SUERMONDTH J,CHAVEZ R M,et al.The ALARM monitoring system:A case study with two probabilistic inference techniques for belief networks[C]//LNMI 38:Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine.Berlin,Heidelberg:Springer,1989:247-256.
[34]ABRAMSON B,BROWN J,EDWARDS W,et al.Hailfinder:A Bayesian system for forecasting severe weather [J].Interna-tional Journal of Forecasting,1996,12(1):57-71.
[35]COLOMBO D,MATHUIS M H.Order-Independent Constraint-Based Causal Structure Lear-ning [J].Journal of Machine Learning Research,2014,15:3921-3962.
[36]WU R Z,LIU Q,LIU Y P,et al.Cognitive modelling for predicting examinee performance[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence.Menlo Park:AAAI,2015:1017-1024.
[37]TORRE J.DINA model and parameter estimation:A didactic[J].Journal of Educational and Behavioral Statistics,2009,34(1):115-130.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发