|
|
|
|
On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables
Frederick Eberhardt, Clark Glymour, Richard Scheines
Abstract:
We show that if any number of variables are allowed to be simultaneously and independently randomized in any one experiment, log2(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/(2N) 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 kmax < N/2 , we show that (N/kmax-1)+N/(2kmax)log2(kmax) experiments aresufficient and in the worst case necessary. We over 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.
Keywords:
Pages: 178-184
PS Link:
PDF Link: /papers/05/p178-eberhardt.pdf
BibTex:
@INPROCEEDINGS{Eberhardt05,
AUTHOR = "Frederick Eberhardt
and Clark Glymour and Richard Scheines",
TITLE = "On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "178--184"
}
|
|
