Learning Sparse Causal Models is not NP-hard
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Causal DiscoveryModel DiscoverySelection biasSimilar Papers 제목 키워드 기반
Proof Supplement - Learning Sparse Causal Models is not NP-hard (UAI2013)
This article contains detailed proofs and additional examples related to the UAI-2013 submission `Learning Sparse Causal Models is not NP-hard'. It describes the FCI+ algorithm: a method for sound and complete causal mod…
Model DiscoverySelection biasWhy Are Some Emotions Harder for LLMs? Uncovering the Causal Mechanisms of Emotion Inference via Sparse Autoencoders
Large language models (LLMs) are increasingly used in emotionally sensitive human-AI applications, where reliable emotion detection is essential. However, their emotion recognition abilities remain uneven: models often p…
Emotion RecognitionExperimental Design for Cost-Aware Learning of Causal Graphs
We consider the minimum cost intervention design problem: Given the essential graph of a causal graph and a cost to intervene on a variable, identify the set of interventions with minimum total cost that can learn any ca…
Experimental DesignEfficient Permutation Discovery in Causal DAGs
The problem of learning a directed acyclic graph (DAG) up to Markov equivalence is equivalent to the problem of finding a permutation of the variables that induces the sparsest graph. Without additional assumptions, this…
Causal Abstraction: A Theoretical Foundation for Mechanistic Interpretability
Causal abstraction provides a theoretical foundation for mechanistic interpretability, the field concerned with providing intelligible algorithms that are faithful simplifications of the known, but opaque low-level detai…
Explainable Artificial Intelligence (XAI)