Article

Identifiability in causal Bayesian networks: a sound and complete algorithm

Authors:

Yimin Huang,

Marco ValtortaAuthors Info & Claims

AAAI'06: proceedings of the 21st national conference on Artificial intelligence - Volume 2

Pages 1149 - 1154

Published: 16 July 2006 Publication History

Abstract

This paper addresses the problem of identifying causal effects from nonexperimental data in a causal Bayesian network, i.e., a directed acyclic graph that represents causal relationships. The identifiability question asks whether it is possible to compute the probability of some set of (effect) variables given intervention on another set of (intervention) variables, in the presence of non-observable (i.e., hidden or latent) variables. It is well known that the answer to the question depends on the structure of the causal Bayesian network, the set of observable variables, the set of effect variables, and the set of intervention variables. Our work is based on the work of Tian, Pearl, Huang, and Valtorta (Tian & Pearl 2002a; 2002b; 2003; Huang & Valtorta 2006a) and extends it. We show that the identify algorithm that Tian and Pearl define and prove sound for semi-Markovian models can be transfered to general causal graphs and is not only sound, but also complete. This result effectively solves the identifiability question for causal Bayesian networks that Pearl posed in 1995 (Pearl 1995), by providing a sound and complete algorithm for identifiability.

References

[1]

Galles, D., and Pearl, J. 1995. Testing identifiability of causal effects. In Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence (UAI-95), 185-195.

Digital Library

Google Scholar

[2]

Huang, Y., and Valtorta, M. 2006a. On the completeness of an identifiability algorithm for semi-markovian models, TR-2006-001. Technical report, University of South Carolina Department of Computer Science. available at http://www.cse.sc.edu/mgv/reports/tr2006-001.pdf.

Google Scholar

[3]

Huang, Y., and Valtorta, M. 2006b. A study of identifiability in causal Bayesian networks, TR-2006-002. Technical report, University of South Carolina Department of Computer Science. available at http://www.cse.sc.edu/mgv/reports/tr2006-002.pdf.

Google Scholar

[4]

Pearl, J., and Robins, J. M. 1995. Probabilistic evaluation of sequential plans from causal models with hidden variables. In Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence (UAI-95), 444-453.

Digital Library

Google Scholar

[5]

Pearl, J. 1995. Causal diagrams for empirical research. Biometrika 82:669-710.

Crossref

Google Scholar

[6]

Pearl, J. 2000. Causality: Models, Reasoning, and Inference . New York, USA: Cambridge University Press.

Digital Library

Google Scholar

[7]

Shpitser, I., and Pearl, J. 2006. Identification of joint interventional distributions in recursive semi-markovian causal models, R-327. Technical report, Cognitive Systems Laboratory, University of California at Los Angeles. available at http://ftp.cs.ucla.edu/pub/stat_ser/r327.pdf.

Google Scholar

[8]

Tian, J., and Pearl, J. 2002a. A general identification condition for causal effects. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), 567-573.

Digital Library

Google Scholar

[9]

Tian, J., and Pearl, J. 2002b. On the testable implications of causal models with hidden variables. In Proceedings of the Eighteenth Annual Conference on Uncertainty in Artificial Intelligence(UAI-02), 519-527.

Digital Library

Google Scholar

[10]

Tian, J., and Pearl, J. 2003. On the identification of causal effects, 290-L. Technical report, Cognitive Systems Laboratory, University of California at Los Angeles. Extended version available at http://www.cs.iastate.edu/jtian/r290-L.pdf.

Google Scholar

[11]

Verma, T. S. 1993. Graphical aspects of causal models, R-191. Technical report, Cognitive Systems Laboratory, University of California at Los Angeles.

Google Scholar

Cited By

View all

Hyttinen AEberhardt FJärvisalo M(2015)Do-calculus when the true graph is unknownProceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence10.5555/3020847.3020889(395-404)Online publication date: 12-Jul-2015
https://dl.acm.org/doi/10.5555/3020847.3020889
Mooij JCremers J(2015)An empirical study of one of the simplest causal prediction algorithmsProceedings of the UAI 2015 Conference on Advances in Causal Inference - Volume 150410.5555/3020267.3020270(30-39)Online publication date: 16-Jul-2015
https://dl.acm.org/doi/10.5555/3020267.3020270
Bareinboim EPearl J(2012)Causal inference by surrogate experimentsProceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence10.5555/3020652.3020668(113-120)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.5555/3020652.3020668
Show More Cited By

Recommendations

IDENTIFIABILITY IN CAUSAL BAYESIAN NETWORKS: A GENTLE INTRODUCTION

In this article we describe an important structure used to model causal theories and a related problem of great interest to semi-empirical scientists. A causal Bayesian network is a pair consisting of a directed acyclic graph (called a causal graph) ...
Identifiability in causal bayesian networks
Identifiability guarantees for causal disentanglement from soft interventions
NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems

Causal disentanglement aims to uncover a representation of data using latent variables that are interrelated through a causal model. Such a representation is identifiable if the latent model that explains the data is unique. In this paper, we focus on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAAI'06: proceedings of the 21st national conference on Artificial intelligence - Volume 2

July 2006

1981 pages

ISBN:9781577352815

Editor:
Anthony Cohn
University of Leeds

Publisher

AAAI Press

Publication History

Published: 16 July 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hyttinen AEberhardt FJärvisalo M(2015)Do-calculus when the true graph is unknownProceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence10.5555/3020847.3020889(395-404)Online publication date: 12-Jul-2015
https://dl.acm.org/doi/10.5555/3020847.3020889
Mooij JCremers J(2015)An empirical study of one of the simplest causal prediction algorithmsProceedings of the UAI 2015 Conference on Advances in Causal Inference - Volume 150410.5555/3020267.3020270(30-39)Online publication date: 16-Jul-2015
https://dl.acm.org/doi/10.5555/3020267.3020270
Bareinboim EPearl J(2012)Causal inference by surrogate experimentsProceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence10.5555/3020652.3020668(113-120)Online publication date: 14-Aug-2012
https://dl.acm.org/doi/10.5555/3020652.3020668
Spirtes P(2010)Introduction to Causal InferenceThe Journal of Machine Learning Research10.5555/1756006.185990511(1643-1662)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.5555/1756006.1859905
Shpitser IPearl J(2008)Complete Identification Methods for the Causal HierarchyThe Journal of Machine Learning Research10.5555/1390681.14427979(1941-1979)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.5555/1390681.1442797
Valtorta MHuang Y(2008)IDENTIFIABILITY IN CAUSAL BAYESIAN NETWORKSCybernetics and Systems10.1080/0196972080203959439:4(425-442)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1080/01969720802039594
Shpitser IPearl J(2006)Identification of conditional interventional distributionsProceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence10.5555/3020419.3020472(437-444)Online publication date: 13-Jul-2006
https://dl.acm.org/doi/10.5555/3020419.3020472

Abstract

References

Cited By

Recommendations

IDENTIFIABILITY IN CAUSAL BAYESIAN NETWORKS: A GENTLE INTRODUCTION