混合加噪声模型与条件独立性检测的因果方向推断算法
|
摘要
从可观测的变量中推导出潜在的因果关系是人工智能领域的热点研究之一。传统的基于独立性检测的方法是通过检测V结构来确定一组马尔可夫等价类而非最终的因果关系;而加噪声模型算法却只能适应于低维度的因果网络结构。为此,提出一种采取分治策略的混合加噪声模型与条件独立性检测的因果方向推断方法。首先将一个n维因果网络分解成n个诱导子网络,分别归入三种基本结构(单度结构、非三角结构和存在三角的结构)中的一种,从理论上分别证明其有效性;其次对每个诱导子网络进行基于加噪声模型算法与条件独立性检测相结合的方向推断;最后把所有子网络合并起来构建成完整的因果关系网络。实验表明,该方法比传统的因果关系推断方法更加有效。
Inferring causal directions from observed variables is one of the fundamental problems in artificial intelligence( AI)field. Traditional conditional independence based methods usually learn causal directions by detecting V-structures and return Markov equivalence classes,instead of true causal structures. Most other direction learning methods can distinguish the equivalence classes,but are effective only in the bivariate( or two-dimensional) cases. This paper proposd a new approach for causal direction inference from general networks,based on a split-and-merge strategy. The method first decomposed an n-dimensional network into n induced subnetworks,each of which corresponded to a node in the network. Each induced subnetwork could be subsumed to one of the three substructures: one-degree,non-triangle and triangle-existence structures. It developed three effective algorithms to infer causalities from the three substructures,and learning these induced subnetworks orderly to achieved the whole causal structure of the multi-dimensional network. Experiments show that the method is more general and effective than traditional methods.
Inferring causal directions from observed variables is one of the fundamental problems in artificial intelligence( AI)field. Traditional conditional independence based methods usually learn causal directions by detecting V-structures and return Markov equivalence classes,instead of true causal structures. Most other direction learning methods can distinguish the equivalence classes,but are effective only in the bivariate( or two-dimensional) cases. This paper proposd a new approach for causal direction inference from general networks,based on a split-and-merge strategy. The method first decomposed an n-dimensional network into n induced subnetworks,each of which corresponded to a node in the network. Each induced subnetwork could be subsumed to one of the three substructures: one-degree,non-triangle and triangle-existence structures. It developed three effective algorithms to infer causalities from the three substructures,and learning these induced subnetworks orderly to achieved the whole causal structure of the multi-dimensional network. Experiments show that the method is more general and effective than traditional methods.
引文
[1] Pearl J. Causality:models,reasoning,and inference[M]. Cambridge:Cambridge University Press,2000:639.
[2] Spirtes P,Glymour C N,Scheines R. Causation,prediction,and search[M]. New York:Springer,1993:272-273.
[3] Cheng Jie,Bell D,Liu Weirui. Learning Bayesian networks from data:an efficient approach based on information theory[J]. Artificial Intelligence,1997,137(1-2):325-331.
[4] Chickering D M. Learning equivalence classes of Bayesian-network structures[J]. The Journal of Machine Learning Research,2002,2(3):445-498.
[5] Shimizu S,Hoyer P O,Kerminen A,et al. A linear non-Gaussian acyclic model for causal discovery[J]. Journal of Machine Learning Research,2006,7(4):2003-2030.
[6] Shimizu S,Inazumi T,Sogawa Y,et al. Directlingam:a direct method for learning a linear non-Gaussian structural equation model[J].Journal of Machine Learning Research,2011,12(2):1225-1248.
[7] Hoyer P O,Janzing D,Mooij J M,et al. Nonlinear causal discovery with additive noise models[C]//Proc of the 21st International Conference on Neural Information Processing Systems. 2009:689-696.
[8] Peters J,Mooij J M,Janzing D,et al. Causal discovery with continuous additive noise models[J]. Journal of Machine Learning Research,2013,15(1):2009-2053.
[9] Peters J,Janzing D,Schlkopf B. Identifying cause and effect on discrete data using additive noise models[C]//Proc of International Conference on Artificial Intelligence and Statistics. 2010:597-604.
[10]Cai Ruihu,Zhang Zhenjie,Hao Zhifeng. Sada:a general framework to support robust causation discovery[C]//Proc of the 30th International Conference on International Conference on Machine Learning.2013:208-216.
[11]Daniusis P,Janzing D,Mooij J,et al. Inferring deterministic causal relations[C]//Proc of the 26th Conference on Uncertainty in Artificial Intecligence. 2010:143-150.
[12] Janzing D,Mooij J,Zhang Kun,et al. Information-geometric approach to inferring causal directions[J]. Artificial Intelligence,2012,182-183(5):1-31.
[13]Janzing D,Steudel B,Shajarisales N,et al. Justifying informationgeometric causal inference[M]. Berlin:Springer International Publishing,2014:253-265.
[14]Zhang Kun,Hyvrinen A. On the identifiability of the post-nonlinear causal model[C]//Proc of the 25th Conference on Uncertainty in Artificial Intelligence.[S. l.]:AUAI Press,2009:647-655.
[15]Hao Zhifeng,Zhang Hao,Cai Ruichu,et al. Causal discovery on high dimensional data[J]. Applied Intelligence,2014,42(3):594-607.
[16]Cai Ruichu,Zhang Zhenjie,Hao Zhifeng. Causal gene identification using combinatorial V-structure search[J]. Neural Networks,2013,43(7):63-71.
[17]张浩,郝志峰,蔡瑞初,等.一种适用于高维网络的方向推断算法[J].小型微型计算机系统,2015,36(6):1358-1362.(Zhang Hao,Hao Zhifeng,Cai Ruichu,et al. An approach for inferring causal directions in high dimensional causal networks[J]. Journal of Chinese Mini-Micro Computer Systems,2015,36(6):1358-1362.)
[18]Mai Guizhen,Hong Yinghan,Peng Shiguo,et al. Inferring causal direction from multi-dimensional causal networks for assessing harmful factors in security analysis[J]. IEEE Access,2017,5:20009-20019.
[19]Mooij J,Janzing D,Peters J,et al. Regression by dependence minimization and its application to causal inference in additive noise models[C]//Proc of the 26th Annual International Conference on Machine Learning. New York:ACM Press,2009:745-752.
[20]Zhang Kun,Peters J,Janzing D,et al. Kernel-based conditional independence test and application in causal discovery[J]. Computer Science,2012,6(8):895-907.
[21] Zhang Kun,Hyvrinen A. Distinguishing causes from effects using nonlinear acyclic causal models[J]. Journal of Machine Learning Research,2008,6:157-164.
[22]Peters J,Janzing D,Schlkopf B. Causal inference on discrete data using additive noise models[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2011,33(12):2436-2450.
[2] Spirtes P,Glymour C N,Scheines R. Causation,prediction,and search[M]. New York:Springer,1993:272-273.
[3] Cheng Jie,Bell D,Liu Weirui. Learning Bayesian networks from data:an efficient approach based on information theory[J]. Artificial Intelligence,1997,137(1-2):325-331.
[4] Chickering D M. Learning equivalence classes of Bayesian-network structures[J]. The Journal of Machine Learning Research,2002,2(3):445-498.
[5] Shimizu S,Hoyer P O,Kerminen A,et al. A linear non-Gaussian acyclic model for causal discovery[J]. Journal of Machine Learning Research,2006,7(4):2003-2030.
[6] Shimizu S,Inazumi T,Sogawa Y,et al. Directlingam:a direct method for learning a linear non-Gaussian structural equation model[J].Journal of Machine Learning Research,2011,12(2):1225-1248.
[7] Hoyer P O,Janzing D,Mooij J M,et al. Nonlinear causal discovery with additive noise models[C]//Proc of the 21st International Conference on Neural Information Processing Systems. 2009:689-696.
[8] Peters J,Mooij J M,Janzing D,et al. Causal discovery with continuous additive noise models[J]. Journal of Machine Learning Research,2013,15(1):2009-2053.
[9] Peters J,Janzing D,Schlkopf B. Identifying cause and effect on discrete data using additive noise models[C]//Proc of International Conference on Artificial Intelligence and Statistics. 2010:597-604.
[10]Cai Ruihu,Zhang Zhenjie,Hao Zhifeng. Sada:a general framework to support robust causation discovery[C]//Proc of the 30th International Conference on International Conference on Machine Learning.2013:208-216.
[11]Daniusis P,Janzing D,Mooij J,et al. Inferring deterministic causal relations[C]//Proc of the 26th Conference on Uncertainty in Artificial Intecligence. 2010:143-150.
[12] Janzing D,Mooij J,Zhang Kun,et al. Information-geometric approach to inferring causal directions[J]. Artificial Intelligence,2012,182-183(5):1-31.
[13]Janzing D,Steudel B,Shajarisales N,et al. Justifying informationgeometric causal inference[M]. Berlin:Springer International Publishing,2014:253-265.
[14]Zhang Kun,Hyvrinen A. On the identifiability of the post-nonlinear causal model[C]//Proc of the 25th Conference on Uncertainty in Artificial Intelligence.[S. l.]:AUAI Press,2009:647-655.
[15]Hao Zhifeng,Zhang Hao,Cai Ruichu,et al. Causal discovery on high dimensional data[J]. Applied Intelligence,2014,42(3):594-607.
[16]Cai Ruichu,Zhang Zhenjie,Hao Zhifeng. Causal gene identification using combinatorial V-structure search[J]. Neural Networks,2013,43(7):63-71.
[17]张浩,郝志峰,蔡瑞初,等.一种适用于高维网络的方向推断算法[J].小型微型计算机系统,2015,36(6):1358-1362.(Zhang Hao,Hao Zhifeng,Cai Ruichu,et al. An approach for inferring causal directions in high dimensional causal networks[J]. Journal of Chinese Mini-Micro Computer Systems,2015,36(6):1358-1362.)
[18]Mai Guizhen,Hong Yinghan,Peng Shiguo,et al. Inferring causal direction from multi-dimensional causal networks for assessing harmful factors in security analysis[J]. IEEE Access,2017,5:20009-20019.
[19]Mooij J,Janzing D,Peters J,et al. Regression by dependence minimization and its application to causal inference in additive noise models[C]//Proc of the 26th Annual International Conference on Machine Learning. New York:ACM Press,2009:745-752.
[20]Zhang Kun,Peters J,Janzing D,et al. Kernel-based conditional independence test and application in causal discovery[J]. Computer Science,2012,6(8):895-907.
[21] Zhang Kun,Hyvrinen A. Distinguishing causes from effects using nonlinear acyclic causal models[J]. Journal of Machine Learning Research,2008,6:157-164.
[22]Peters J,Janzing D,Schlkopf B. Causal inference on discrete data using additive noise models[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2011,33(12):2436-2450.