CaltechAUTHORS
  A Caltech Library Service

On the number of experiments sufficient and in the worst case necessary to identify all causal relations among N variables

Eberhardt, Frederick and Glymour, Clark and Scheines, Richard (2012) On the number of experiments sufficient and in the worst case necessary to identify all causal relations among N variables. In: UAI'05 Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. AUAI Press , Arlington, VA, pp. 178-184. ISBN 0-9749039-1-4. https://resolver.caltech.edu/CaltechAUTHORS:20190327-085852486

[img] PDF - Accepted Version
See Usage Policy.

126Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190327-085852486

Abstract

We show that if any number of variables are allowed to be simultaneously and independently randomized in any one experiment, log_2(N) + 1 experiments are sufficient and in the worst case necessary to determine the causal relations among N ≥ 2 variables when no latent variables, no sample selection bias and no feedback cycles are present. For all K, 0 < K < 1/2 N we provide an upper bound on the number experiments required to determine causal structure when each experiment simultaneously randomizes K variables. For large N, these bounds are significantly lower than the N - 1 bound required when each experiment randomizes at most one variable. For k_(max) < N/2, we show that (N/k_(max) -1) + N/2k_(max) log_2(k_(max)) experiments are sufficient and in the worst case necessary. We offer a conjecture as to the minimal number of experiments that are in the worst case sufficient to identify all causal relations among N observed variables that are a subset of the vertices of a DAG.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1207.1389arXivDiscussion Paper
Additional Information:© 2005 AUAI Press. The second author is supported by NASA grant NCC2-1227 and a grant from the Office of Naval Research to the Florida Institute for Human and Machine Cognition for Human Systems Technology. The third author is supported by a grant from the James S. McDonnell Foundation.
Funders:
Funding AgencyGrant Number
NASANCC2-1227
Office of Naval Research (ONR)UNSPECIFIED
James S. McDonnell FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190327-085852486
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190327-085852486
Official Citation:Frederick Eberhardt, Clark Glymour, and Richard Scheines. 2005. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among N variables. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI'05), Fahiem Bacchus and Tommi Jaakkola (Eds.). AUAI Press, Arlington, Virginia, United States, 178-184.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94193
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:27 Mar 2019 22:11
Last Modified:03 Oct 2019 21:01

Repository Staff Only: item control page