计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 14-19.doi: 10.11896/jsjkx.200500155
李超1, 覃飙2
LI Chao1, QIN Biao2
摘要: 在因果网中,高效计算的最大可能解释(Most Probable Explanations,MPE)是一个关键问题。从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络。文中通过比较干预和微分的语义,揭示了MPE完全原子干预的微分语义。根据微分语义,因果网中原子干预MPE实例的计算可以归约为贝叶斯网络中的MPE实例的计算。接着,提出了一个联合树算法(Best JoinTree,BJT),它通过在因果网中只构建一个联合树来计算最好的原子干预,原子干预的结果包含一个BMPE(Best MPE)概率和它对应的实例。其中,BMPE概率是对MPE所有结点分别进行原子干预后得到的最高概率。BJT可以采用干预的效果来计算对应贝叶斯网络的MPE概率和MPE实例。最后,实验证实了绝大多数因果网在计算最好原子干预时,BJT的速度比目前最好的算法快了超过10倍。
中图分类号:
[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 |
|