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 model discovery in the presence of latent confounders and/or selection bias, that has worst case polynomial complexity of order $N^{2(k+1)}$ in the number of independence tests, for sparse graphs over $N$ nodes, bounded by node degree $k$. The algorithm is an adaptation of the well-known FCI algorithm by (Spirtes et al., 2000) that is also sound and complete, but has worst case complexity exponential in $N$.
Code (0)
등록된 구현이 없습니다.
Tasks
Model DiscoverySelection biasSimilar Papers 제목 키워드 기반
Supplement to "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs"
This supplementary material includes three parts: some preliminary results, four examples, an experiment, three new algorithms, and all proofs of the results in the paper "Reversible MCMC on Markov equivalence classes of…
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)} inde…
Causal DiscoveryModel DiscoverySelection biasGranger Causality for Compressively Sensed Sparse Signals
Compressed sensing is a scheme that allows for sparse signals to be acquired, transmitted and stored using far fewer measurements than done by conventional means employing Nyquist sampling theorem. Since many naturally o…
Causal Inferencecompressed sensingConnectivity EstimationQuantum State TomographyProofs and Supplementary Material: Unified Characterization and Precoding for Non-Stationary Channels
This document provides the supplementary material including a comprehensive related work, the complete proofs and extended evaluation results that support the manuscript, "Unified Characterization and Precoding for Non-S…
LEMMAA Collective, Probabilistic Approach to Schema Mapping: Appendix
In this appendix we provide additional supplementary material to "A Collective, Probabilistic Approach to Schema Mapping." We include an additional extended example, supplementary experiment details, and proof for the co…