Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (4): 14-19.doi: 10.11896/jsjkx.200500155

• Computer Science Theory • Previous Articles     Next Articles

Efficient Computation of MPE in Causal Bayesian Networks

LI Chao1, QIN Biao2   

  1. 1 Business School,China University of Political Science and Law,Beijing 100088,China
    2 Information School,Renmin University of China,Beijing 100872,China
  • Received:2020-06-24 Revised:2020-08-12 Online:2021-04-15 Published:2021-04-09
  • About author:LI Chao,born in 1976,Ph.D,professor.Her main research interests include statistical machine learning and business intelligence.(chaoli@cupl.edu.cn)
    QIN Biao,born in 1972,Ph.D,associate professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include causal Bayesian network and machine lear-ning.
  • Supported by:
    Scientific Research and Innovation Project of China University of Political Science and Law(19ZFG79002),National Natural Science Foundation of China(61772534),Key Projects of Philosophy and Social Sciences Research of Ministry of Education(19JHQ007),New Discipline Construction Project of China University of Political Science and Law and Fundamental Research Funds for the Central Universities.

PDF (PC)

851

Abstract: This paper investigates the efficient computation of most probable explanations(MPE) in causal Bayesian networks(CBNs).From the perspective of a directed acyclic graph,researchers find that every CBN has a corresponding Bayesian network.By comparing the semantics of intervention with that of differentiation,this paper reveals the differential semantics of a full ato-mic intervention on MPE.Using the differential semantics,it reduces the computation of an MPE instantiation for an atomic intervention on a CBN to that of an MPE instantiation in the corresponding Bayesian network.Next,it proposes a jointree algorithm called BJT to compute the best atomic intervention,which includes the BMPE probability and a corresponding instantiation,by building only one jointree for a CBN.The BMPE probability is the highest probability of all atomic interventions on MPE in a CBN.BJT can use the causal effect to compute the MPE probability and an MPE instantiation for the corresponding Bayesian network.Finally,experimental results show that BJT performs more than one order of magnitude faster than the-state-of-the-art algorithm for computing the best atomic intervention in most CBNs.

Key words: Bayesian networks, Causal Bayesian networks, Differentiation of MPE, Intervention, MPE instantiation

CLC Number: 

  • TP311
[1]PEARL J.Causality:models,reasoning,and inference[M].Camb-ridge University Press,2009.
[2]LI C,QIN B.New algorithms for computing max-product instantiations[J].Application Research of Computers,2015,32(6):1711-1715.
[3]NIELSEN U,PELLET J,ELISSEE A.Explanation trees forcausal Bayesian networks[C]//Proc of the 24th Conference on Uncertainty Artificial Intelligence.2008:427-434.
[4]QIN B.Differential semantics of intervention in Bayesian net-works[C]//Proc of the 24th International Joint Conference on Artificial Intelligence.2015:710-716.
[5]PARK J,DARWICHE A.A differential semantics for jointree algorithms [J].Artificial Intelligence,2004,156(1):197-216.
[6]QIN B,WANG Q Y,LI C.An effective strategy for sensitivity analysis of Bayesian networks [J].Journal of Chinese Computer Systems,2016,37(4):732-737.
[7]MARINESCU R,LEE J,DECHTER R.AND/OR search formarginal MAP [J].Journal of Artificial Intelligence Research,2018,63:875-921.
[8]LOU Q,DECHTER R,IHLER A.Anytime anyspace AND/OR best-first search for bounding marginal MAP[C]//Proc of the 32nd Conference on Artificial Intelligence.2018:6392-6400.
[9]SHENOY P,SHAFER G.Propagating belief functions with local computations [J].IEEE Expert,1986,1(3):43-52.
[10]JENSEN F,ANDERSEN S.Approximations in Bayesian belief universes for knowledge based systems[C]//Proc of the 6th Conference on Uncertainty Artificial Intelligence.1990:162-169.
[11]DARWICHE A.Modeling and reasoning with bayesian net-works [M].Cambridge University Press,2009.
[12]HALPERN J.Axiomatizing causal reasoning [J].Journal of Artificial Intelligence Research,2000,12:317-337.
[13]LI C.Jointree algorithm for the differentiation of the MPE pro-blem [J].Journal of Chinese Computer Systems,2016,37(10):2306-2311。
[14]http://sourceforge.net/projects/bnj/.
[15]http://reasoning.cs.ucla.edu/ace.
[1] LI Chao, QIN Biao. Efficient Computation of Intervention in Causal Bayesian Networks [J]. Computer Science, 2022, 49(1): 279-284.
[2] YUAN De-yu, CHEN Shi-cong, GAO Jian, WANG Xiao-juan. Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game [J]. Computer Science, 2021, 48(3): 313-319.
[3] ZHANG Cheng-wei, LUO Feng-e, DAI Yi. Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining [J]. Computer Science, 2020, 47(11A): 464-470.
[4] CHAI Hui-min, FANG Min, LV Shao-nan. Local Path Planning of Mobile Robot Based on Situation Assessment Technology [J]. Computer Science, 2019, 46(4): 210-215.
[5] YAO Ning, MIAO Duo-qian, ZHANG Zhi-fei. Transportability of Causal Information Across Different Granularities [J]. Computer Science, 2019, 46(2): 178-186.
[6] WANG Han-jie, YANG Long-hao, FU Yang-geng, WU Ying-jie and GONG Xiao-ting. Differential Evolutionary Algorithm for Parameter Training of Belief Rule Base under Expert Intervention [J]. Computer Science, 2015, 42(5): 88-93.
[7] XIAO Meng and ZHANG You-peng. Parameters Learning of Bayesian Networks for Multistate System with Small Sample [J]. Computer Science, 2015, 42(4): 253-257.
[8] HE Xiao-li,BI Gui-hong and WANG Hai-rui. Evaluating Heterosexual HIV Transmission and Interventions Based on Agent Bipartite Dynamic Weighting Scale-free Network [J]. Computer Science, 2014, 41(1): 72-79.
[9] . Hidden Variable Discovering Algorithm of Bayesian Networks Based on Structural Decomposition and Factor Analysis [J]. Computer Science, 2012, 39(2): 250-254.
[10] WANG Xue-cheng,LI Hai-feng,LU Min-yan,YANG Shun-kun. Software Fault Diagnosis Framework Combining Bayesian Networks with SFMEA [J]. Computer Science, 2010, 37(9): 131-134.
[11] PENG Wu,YAO Shu-ping. Study on Intrusion Intention Recognition Based on the Probabilistic Inference [J]. Computer Science, 2010, 37(1): 79-82.
[12] . [J]. Computer Science, 2009, 36(6): 214-216.
[13] HU Chun-ling ,HU Xue-gang （School of Computer and Information, Hefei University of Technology, Hefei 230009, China）. [J]. Computer Science, 2009, 36(2): 199-202.
[14] QIN Hua-wang DAI Yue-wei WANG Zhi-quan （School of Automatization, Nanjing University of Science ＆ Technology, Nanjing 210094,China）. [J]. Computer Science, 2008, 35(7): 78-80.
[15] XU Guang-Mei ,YANG Bing-Ru, ZHANG Wei ,NING Shu-Rong （School of Information Engineering,Beijing University of Science and Technology, Beijing100083）. [J]. Computer Science, 2007, 34(1): 130-132.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.