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.

Key words： 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. In: Proceedings of the 2nd European Conference on Artificial Intelligence in Medicine. Berlin: Springer-Verlag, 1989, 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. In: Fifth International Workshop on Artificial Intelligence and Statistics. 1995, 112-128

7 Heckerman D. A tutorial on learning with Bayesian networks. In: Jordan M, ed. Learning in Graphical Models. Cambridge: MIT Press, 1999, 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. Oxford: Oxford Univ Press, 1996

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. In: Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann, 1995, 403-410

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

13 Ramsey J. A pc-style Markov blanket search for high-dimensional datasets. Technical Report, CMU-PHIL-177. Department of Philosophy, Carnegie Mellon University, 2006

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

15 Tsamardinos I, Aliferis C, Statnikov A. Time and sample efficient discovery of Markov blankets and direct causal relations. In: 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. In: Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. 1998, 514-522