计算机科学

计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 14-19.doi: 10.11896/jsjkx.200500155

• 计算机科学理论 • 上一篇    下一篇

高效计算因果网中的最大可能解释

李超1, 覃飙2   

  1. 1 中国政法大学商学院 北京100088
    2 中国人民大学信息学院 北京100872
  • 收稿日期:2020-06-24 修回日期:2020-08-12 出版日期:2021-04-15 发布日期:2021-04-09
  • 通讯作者: 覃飙(qinbiao@ruc.edu.cn)
  • 基金资助:
    中国政法大学科研创新项目(19ZFG79002);国家自然科学基金(61772534);教育部哲学社会科学重大课题(19JHQ007);中国政法大学新兴学科培育与建设计划;中央高校基本科研业务费专项资金

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)

846

摘要： 在因果网中,高效计算的最大可能解释(Most Probable Explanations,MPE)是一个关键问题。从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络。文中通过比较干预和微分的语义,揭示了MPE完全原子干预的微分语义。根据微分语义,因果网中原子干预MPE实例的计算可以归约为贝叶斯网络中的MPE实例的计算。接着,提出了一个联合树算法(Best JoinTree,BJT),它通过在因果网中只构建一个联合树来计算最好的原子干预,原子干预的结果包含一个BMPE(Best MPE)概率和它对应的实例。其中,BMPE概率是对MPE所有结点分别进行原子干预后得到的最高概率。BJT可以采用干预的效果来计算对应贝叶斯网络的MPE概率和MPE实例。最后,实验证实了绝大多数因果网在计算最好原子干预时,BJT的速度比目前最好的算法快了超过10倍。

关键词: MPE实例, 贝叶斯网络, 干预, 微分MPE, 因果网

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

中图分类号: 

  • 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] 李嘉睿, 凌晓波, 李晨曦, 李子木, 杨家海, 张蕾, 吴程楠.
基于贝叶斯攻击图的动态网络安全分析
Dynamic Network Security Analysis Based on Bayesian Attack Graphs
计算机科学, 2022, 49(3): 62-69. https://doi.org/10.11896/jsjkx.210800107
[2] 李超, 覃飙.
高效计算因果网中的干预
Efficient Computation of Intervention in Causal Bayesian Networks
计算机科学, 2022, 49(1): 279-284. https://doi.org/10.11896/jsjkx.210300028
[3] 韩丽霞, 张占营.
基于树增益朴素贝叶斯网络的服务定价策略
TAN-based Service Pricing Strategy
计算机科学, 2021, 48(6A): 203-. https://doi.org/10.11896/jsjkx.200900024
[4] 袁得嵛, 陈世聪, 高见, 王小娟.
基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法
Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game
计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079
[5] 徐源音,柴玉梅,王黎明,刘箴.
基于OCC模型和贝叶斯网络的情绪句分类方法
Emotional Sentence Classification Method Based on OCC Model and Bayesian Network
计算机科学, 2020, 47(3): 222-230. https://doi.org/10.11896/jsjkx.190200331
[6] 张成伟, 罗凤娥, 代毅.
基于数据挖掘的指定航班计划延误预测方法
Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining
计算机科学, 2020, 47(11A): 464-470. https://doi.org/10.11896/jsjkx.200600001
[7] 林朗, 张自力.
基于多头绒泡菌的贝叶斯网络结构学习
Bayesian Structure Learning Based on Physarum Polycephalum
计算机科学, 2019, 46(9): 206-210. https://doi.org/10.11896/j.issn.1002-137X.2019.09.030
[8] 柴慧敏, 方敏, 吕少楠.
基于态势评估技术的移动机器人局部路径规划
Local Path Planning of Mobile Robot Based on Situation Assessment Technology
计算机科学, 2019, 46(4): 210-215. https://doi.org/10.11896/j.issn.1002-137X.2019.04.033
[9] 姚宁, 苗夺谦, 张志飞.
因果信息在不同粒度上的迁移性
Transportability of Causal Information Across Different Granularities
计算机科学, 2019, 46(2): 178-186. https://doi.org/10.11896/j.issn.1002-137X.2019.02.028
[10] 邢志伟, 朱慧, 李彪, 罗谦.
基于贝叶斯网络的航班离港时间动态估计
Dynamic Estimation of Flight Departure Time Based on Bayesian Network
计算机科学, 2019, 46(10): 329-335. https://doi.org/10.11896/jsjkx.181102039
[11] 张志东,王志海,刘海洋,孙艳歌.
一种基于树型贝叶斯网络的集成多标记分类算法
Ensemble Multi-label Classification Algorithm Based on Tree-Bayesian Network
计算机科学, 2018, 45(3): 189-195. https://doi.org/10.11896/j.issn.1002-137X.2018.03.030
[12] 许建锐,李战武,徐安.
小样本贝叶斯网络结构学习的KDE-CGA算法
KDE-CGA Algorithm of Structure Learning for Small Sample Data Bayesian Network
计算机科学, 2017, 44(Z11): 437-441. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.093
[13] 刘冬瑞,刘东升,张丽萍,侯敏,王春晖.
基于贝叶斯网络预测克隆代码质量
Prediction of Code Clone Quality Based on Bayesian Network
计算机科学, 2017, 44(4): 165-168. https://doi.org/10.11896/j.issn.1002-137X.2017.04.036
[14] 付永平,邱玉辉.
一种基于贝叶斯网络的个性化协同过滤推荐方法研究
Method of Personalized Collaboration Filter Recommendation Based on Bayesian Network
计算机科学, 2016, 43(9): 266-268. https://doi.org/10.11896/j.issn.1002-137X.2016.09.053
[15] 曹如胜,倪世宏,张鹏,奚显阳.
一种基于云模型的贝叶斯网络EM参数学习算法
EM Parameter Learning Algorithm of Bayesian Network Based on Cloud Model
计算机科学, 2016, 43(8): 194-198. https://doi.org/10.11896/j.issn.1002-137X.2016.08.039
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
本系统由北京玛格泰克科技发展有限公司设计开发