Learning Sparse Causal Models is not NP-hard
Lists
Only you see this
Abstract
This paper shows that causal model discovery is not an NP-hard problem, in the sense that for sparse graphs bounded by node degree k the sound and complete causal model can be obtained in worst case order N^{2(k+2)} independence tests, even when latent variables and selection bias may be present. We present a modification of the well-known FCI algorithm that implements the method for an independence oracle, and suggest improvements for sample/real-world data versions. It does not contradict any known hardness results, and does not solve an NP-hard problem: it just proves that sparse causal discovery is perhaps more complicated, but not as hard as learning minimal Bayesian networks.
BibTeX
@inproceedings{claassen2013learning,
author = {Tom Claassen and Joris M. Mooij and Tom Heskes},
title = {{Learning Sparse Causal Models is not NP-hard}},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2013},
url = {https://openreview.net/forum?id=U-ExFk3AI-q},
}Loading related content...