Discovering causes and effects of a given node in Bayesian networks

Abstract

Causal relationships among variables can be depicted by a causal network of these variables. We propose a local structure learning approach for discovering the direct causes and the direct effects of a given target variable. In the approach, we first find the variable set of parents, children, and maybe some descendants (PCD) of the target variable, but generally we cannot distinguish the parents from the children in the PCD of the target variable. Next, to distinguish the causes from the effects of the target variable, we find the PCD of each variable in the PCD of the target variable, and we repeat the process of finding PCDs along the paths starting from the target variable. Without constructing a whole network over all variables, we find only a local structure around the target variable. Theoretically, we show the correctness of the proposed approach under the assumptions of faithfulness, causal sufficiency, and that conditional independencies are correctly checked.

Keywords

Directed acyclic graphs / causal networks / graphical models / structure learning

References

[1] Abramson B, Brown J, Edwards W, Murphy A, Winkler R. Hailfinder: A Bayesian system for forecasting severe weather. Int J Forecasting, 1996, 12(1): 57-71

[2] Aliferis C F, Statnikov A, Tsamardinos I, Mani S, Koutsoukos X D. Local causal and Markov blanket induction for causal discovery and feature selection for classification, Part I: algorithms and empirical evaluation. J Mach Learn Res, 2010, 11: 171-234

[3] Bai X, Padman R, Ramsey J, Spirtes P. Tabu search-enhanced graphical models for classification in high dimensions. INFORMS, 2008, 20: 423-437

[4] Beinlich I, Suermondt H, Chavez R, Cooper G. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks. Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine, 1989, Berlin: Springer-Verlag 247 256

[5] Binder J, Koller D, Russell S, Kanazawa K. Adaptive probabilistic networks with hidden variables. Machine Learning, 1997, 29(2–3): 213-244

[6] Chickering D, Geiger D, Heckerman D. Learning Bayesian networks: Search methods and experimental results. Fifth International Workshop on Artificial Intelligence and Statistics, 1995 112 128

[7] Heckerman D. Jordan M. A tutorial on learning with Bayesian networks. Learning in Graphical Models, 1999, Cambridge: MIT Press 301 354

[8] Ji J Z, Hu R B, Zhang H X, Liu C N. A hybrid method for learning Bayesian networks based on ant colony optimization. Applied Soft Computing, 2011, 11: 3373-3384

[9] Lauritzen S L. Graphical Models, 1996, Oxford: Oxford Univ Press

[10] Liu B H, Guo J H, Jin B Y. A note on minimal d-separation trees for structural learning. Artif Intell, 2010, 174: 442-448

[11] Meek C. Causal inference and causal explanation with background knowledge. Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, 1995, San Francisco: Morgan Kaufmann 403 410

[12] Pearl J. Causality: Models, Reasoning, and Inference, 2000, Cambridge: Cambridge Univ Press

[13] Ramsey J. A pc-style Markov blanket search for high-dimensional datasets. Technical Report, CMU-PHIL-177, 2006

[14] Spirtes P, Glymour C, Scheines R. Causation, Prediction, and Search, 2000 2nd ed Cambridge: MIT Press

[15] Tsamardinos I, Aliferis C, Statnikov A. Time and sample efficient discovery of Markov blankets and direct causal relations. Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining (KDD), 2003 673 678

[16] Tsamardinos I, Brown L, Aliferis C. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 2006, 65(1): 31-78

[17] Xie X, Geng Z. A recursive method for structural learning of directed acyclic graphs. J Mach Learn Res, 2008, 9: 459-483

[18] Xie X, Geng Z, Zhao Q. Decomposition of structural learning about directed acyclic graphs. Artif Intell, 2006, 170: 422-439

[19] Zhang N L. Probabilistic inference in influence diagrams. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998 514 522