计算机科学 ›› 2022, Vol. 49 ›› Issue (1): 279-284.doi: 10.11896/jsjkx.210300028

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

高效计算因果网中的干预

李超1, 覃飙2   

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

Efficient Computation of Intervention 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:2021-03-02 Revised:2021-06-14 Online:2022-01-15 Published:2022-01-18
  • About author:LI Chao,born in 1976,Ph.D,professor.Her main research interests include statistical machine learning and business intelligence.
    QIN Biao,born in 1972,Ph.D,vice professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include causal Baye-sian network and machine learning.
  • Supported by:
    Scientific Research and Innovation Project of China University of Political Science and Law(19ZFG79002),National Science Foundation of China(61772534),Research Foundation from Ministry of Education of China(19JHQ007),New Discipline Construction Project of China University of Political Science and Law and Fundamental Research Funds for the Central Universities.

摘要: 在因果网中,对和积问题因果效果的计算是其首要问题,从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络,干预是因果网的一个基本操作。类似于贝叶斯网络中的剪枝策略,在剪枝掉所有无效结点后,文中设计了一种优化的算法OFDo来计算对因果网中每个结点的完全原子干预。文中接着研究多干预操作,发现多干预操作具有可交换性,并基于多干预操作的可交换性证明了多干预操作的优化计算策略。最后,通过实验证实OFDo计算对因果网中所有结点完全原子干预的效率比目前的算法都好。

关键词: 多干预, 干预, 完全原子干预, 无效结点, 因果网

Abstract: In causal Bayesian networks (CBNs),it is a fundamental problem to compute the causal effect of sum product.From the perspective of a directed acyclic graph,we show every CBN has a corresponding Bayesian network.Intervention is a fundamental operation in CBNs.Similar to Bayesian networks,CBNs also have the pruning strategy.After pruning the barren nodes,this paper devises an optimized jointree algorithm to compute the full atomic intervention on each node in a CBN.Then,this paper explores the multiple interventions on multiple nodes,and finds that multiple interventions have the commutative property.On the basis of the commutative property in multiple interventions,this paper proves the strategies,which can be used to optimize the computation of the causal effect of multiple interventions.Finally,we report experimental results to demonstrate the efficiency of our algorithm to compute the causal effects in CBNs.

Key words: Barren nodes, Causal Bayesian networks, Full atomic intervention, Intervention, Multiple interventions

中图分类号: 

  • TP311
[1]PEARL J.Causality:models,reasoning,and inference [M].Camb-ridge University Press,2009.
[2]QIN B.Differential semantics of intervention in Bayesian net-works[C]//Proc. of the 24th International Joint Conference on Artificial Intelligence.2015:710-716.
[3]SHACHTE R.Evaluating influence diagrams[J].OperationsResearch,1986,34(6):871-882.
[4]PARK J,DARWICHE A.Morphing the hugin and shenoy-shafer architectures [C]//7th European Conference Symbolic and Quantitative Approaches to Reasoning with Uncertainty.2003:149-160.
[5]SHENOY P,SHAFER G.Propagating belief functions with local computations[J].IEEE Expert,1986,1(3):43-52.
[6]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.
[7]LI C,QIN B.New algorithms for computing max-product instantiations[J].Application Research of Computers,2015,32(6):1711-1715.
[8]LI C.Jointree algorithm for the differentiation of the MPE problem[J].Journal of Chinese Computer Systems,2016,37(10):2306-2311.
[9]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.
[10]LINZNER D,SCHMIDT M,KOEPPL H.Scalable StructureLearning of Continuous-Time Bayesian Networks from Incomplete Data[C]//Proc. of the 33rd Advances in Neural Information Processing Systems.2019:3741-3751.
[11]BHATTACHARJYA D,SHANMUGAM K,GAO T,et al.Event-Driven Continuous Time Bayesian Networks[C]//Proc. of the 34th AAAI Conference on Artificial Intelligence.2020:3259-3266.
[12]GRUTTEMEIER N,KOMUSIEWICZ C.Learning BayesianNetworks Under Sparsity Constraints:A Parameterized Complexity Analysis[C]//Proc. of the 29th International Joint Conference on Artificial Intelligence.2020:4245-4251.
[13]CHEN C,YUAN C.Learning Diverse Bayesian Networks[C]//Proc. of the 33th AAAI Conference on Artificial Intelligence.2019:7793-7800.
[14]LIAO Z,SHARAM C,CUSSENS J,et al.Finding All Bayesian Network Structures within a Factor of Optimal[C]//Proc. of the 33th AAAI Conference on Artificial Intelligence.2019:7892-7899.
[15]WANG S H,QIN B.Bayesian Network Structure Learning by Ensemble Learning and Feedback Strategy[J].Chinese Joural of Computers,2021,44(6):1051-1063.
[16]LI C,QIN B.Efficient Computation of MPE in Causal Bayesian Networks[J].Computer Science,2021,48(4):14-19.
[17]ALBINI E,RAGO A,BARONI P,et al.Relation-Based Counterfactual Explanations for Bayesian Network Classifiers[C]//Proc. of the 29th International Joint Conference on Artificial Intelligence.2020:451-457.
[1] 李超, 覃飙.
高效计算因果网中的最大可能解释
Efficient Computation of MPE in Causal Bayesian Networks
计算机科学, 2021, 48(4): 14-19. https://doi.org/10.11896/jsjkx.200500155
[2] 袁得嵛, 陈世聪, 高见, 王小娟.
基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法
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
[3] 姚宁, 苗夺谦, 张志飞.
因果信息在不同粒度上的迁移性
Transportability of Causal Information Across Different Granularities
计算机科学, 2019, 46(2): 178-186. https://doi.org/10.11896/j.issn.1002-137X.2019.02.028
[4] 王韩杰,杨隆浩,傅仰耿,吴英杰,巩晓婷.
专家干预下置信规则库参数训练的差分进化算法
Differential Evolutionary Algorithm for Parameter Training of Belief Rule Base under Expert Intervention
计算机科学, 2015, 42(5): 88-93. https://doi.org/10.11896/j.issn.1002-137X.2015.05.018
[5] 何晓力,毕贵红,王海瑞.
基于Agent动态加权二部无标度网络的异性HIV传播与政策调控模型
Evaluating Heterosexual HIV Transmission and Interventions Based on Agent Bipartite Dynamic Weighting Scale-free Network
计算机科学, 2014, 41(1): 72-79.
[6] 万国根 秦志光.
面向信息内容安全的文本过滤和分类系统研究与实现

计算机科学, 2005, 32(7): 159-161.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!