计算机科学 ›› 2023, Vol. 50 ›› Issue (10): 230-238.doi: 10.11896/jsjkx.221000046
李明嘉, 钱鸿, 周爱民
LI Mingjia, QIAN Hong, ZHOU Aimin
摘要: 贝叶斯网络是一种不确定性知识表示与推理的有效工具,学习其结构是利用这一工具进行推理的基础。现有的贝叶斯网络结构学习算法,在智能教育等应用场景中往往面临着难以权衡有效性与高效性的问题。一方面,评分搜索类方法能搜索到高质量的解,但面临着算法复杂度高的挑战。另一方面,混合类方法效率高,但所找到的解的质量不尽如人意。针对上述问题,提出了一种基于演化序搜索的混合贝叶斯网络结构学习方法(EvOS)。该方法首先通过约束类算法构建无向图骨架,然后利用演化算法搜索最优节点序,最后使用该节点序指导贪婪搜索得到贝叶斯网络结构。基于常用基准数据集以及教育知识结构发现任务,验证了所提方法的有效性与高效性。实验结果表明,所提方法相较于评分搜索类方法,能够在保持相仿精度的情况下最高加速百倍,且有效性显著高于混合类方法。
中图分类号:
[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. |
|