A Single Iterative Step for Anytime Causal Discovery
- URL: http://arxiv.org/abs/2012.07513v2
- Date: Thu, 24 Dec 2020 11:29:06 GMT
- Title: A Single Iterative Step for Anytime Causal Discovery
- Authors: Raanan Y. Rohekar, Yaniv Gurwicz, Shami Nisimov, Gal Novik
- Abstract summary: We present a sound and complete algorithm for recovering causal graphs from observed, non-interventional data.
We rely on the causal Markov and faithfulness assumptions and recover the equivalence class of the underlying causal graph.
We demonstrate that our algorithm requires significantly fewer CI tests and smaller condition sets compared to the FCI algorithm.
- Score: 7.570246812206772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a sound and complete algorithm for recovering causal graphs from
observed, non-interventional data, in the possible presence of latent
confounders and selection bias. We rely on the causal Markov and faithfulness
assumptions and recover the equivalence class of the underlying causal graph by
performing a series of conditional independence (CI) tests between observed
variables. We propose a single step that is applied iteratively, such that the
independence and causal relations entailed from the resulting graph, after any
iteration, is correct and becomes more informative with successive iteration.
Essentially, we tie the size of the CI condition set to its distance from the
tested nodes on the resulting graph. Each iteration refines the skeleton and
orientation by performing CI tests having condition sets that are larger than
in the preceding iteration. In an iteration, condition sets of CI tests are
constructed from nodes that are within a specified search distance, and the
sizes of these condition sets is equal to this search distance. The algorithm
then iteratively increases the search distance along with the condition set
sizes. Thus, each iteration refines a graph, that was recovered by previous
iterations having smaller condition sets -- having a higher statistical power.
We demonstrate that our algorithm requires significantly fewer CI tests and
smaller condition sets compared to the FCI algorithm. This is evident for both
recovering the true underlying graph using a perfect CI oracle, and accurately
estimating the graph using limited observed data.
Related papers
- Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
Testing a hypothesized causal model against observational data is a key prerequisite for many causal inference tasks.
While a model can assume exponentially many conditional independence relations (CIs), testing all of them is both impractical and unnecessary.
We introduce c-LMP for causal graphs with hidden variables and develop a delay algorithm to list these CIs in poly-time intervals.
arXiv Detail & Related papers (2024-09-22T21:05:56Z) - New metrics and search algorithms for weighted causal DAGs [7.424262881242935]
We study causal graph discovery via adaptive interventions with node-dependent costs.
We define a new benchmark that captures the worst-case interventional cost for any search algorithm.
We provide adaptive search algorithms that achieve logarithmic approximations under various settings.
arXiv Detail & Related papers (2023-05-08T03:48:37Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing.
The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph.
For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
arXiv Detail & Related papers (2023-02-08T08:17:43Z) - Characterization and Learning of Causal Graphs with Small Conditioning
Sets [6.52423450125622]
Constraint-based causal discovery algorithms learn part of the causal graph structure by systematically testing conditional independences.
We propose a novel representation that allows us to graphically characterize $k$-Markov equivalence between two causal graphs.
We conduct synthetic, and semi-synthetic experiments to demonstrate that the $k$-PC algorithm enables more robust causal discovery in the small sample regime.
arXiv Detail & Related papers (2023-01-22T00:24:22Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
This paper considers the problem of online clustering with bandit feedback.
It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines.
We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
arXiv Detail & Related papers (2022-02-09T06:05:05Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G.
matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms.
In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
arXiv Detail & Related papers (2022-01-25T00:10:03Z) - Iterative Causal Discovery in the Possible Presence of Latent
Confounders and Selection Bias [7.570246812206772]
We present a sound and complete algorithm for recovering causal graphs in the presence of latent confounders and selection bias.
ICD relies on the causal Markov and faithfulness assumptions and recovers the equivalence class of the underlying causal graph.
We demonstrate empirically that ICD requires significantly fewer CI tests and learns more accurate causal graphs compared to FCI, FCI+, and RFCI algorithms.
arXiv Detail & Related papers (2021-11-07T14:04:46Z) - Information-Theoretic Generalization Bounds for Iterative
Semi-Supervised Learning [81.1071978288003]
In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles.
Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
arXiv Detail & Related papers (2021-10-03T05:38:49Z) - Efficient Neural Causal Discovery without Acyclicity Constraints [30.08586535981525]
We present ENCO, an efficient structure learning method for directed, acyclic causal graphs.
In experiments, we show that ENCO can efficiently recover graphs with hundreds of nodes, an order of magnitude larger than what was previously possible.
arXiv Detail & Related papers (2021-07-22T07:01:41Z) - Improving Efficiency and Accuracy of Causal Discovery Using a
Hierarchical Wrapper [7.570246812206772]
Causal discovery from observational data is an important tool in many branches of science.
In the large sample limit, sound and complete causal discovery algorithms have been previously introduced.
However, only finite training data is available, which limits the power of statistical tests used by these algorithms.
arXiv Detail & Related papers (2021-07-11T09:24:49Z) - Consistency of a Recurrent Language Model With Respect to Incomplete
Decoding [67.54760086239514]
We study the issue of receiving infinite-length sequences from a recurrent language model.
We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
arXiv Detail & Related papers (2020-02-06T19:56:15Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.