A Caltech Library Service

Almost Optimal Intervention Sets for Causal Discovery

Eberhardt, Frederick (2008) Almost Optimal Intervention Sets for Causal Discovery. In: UAI'08 Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence. AUAI Press , Arlington, VA, pp. 161-168. ISBN 0-9749039-4-9.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We conjecture that the worst case number of experiments necessary and sufficient to discover a causal graph uniquely given its observational Markov equivalence class can be specified as a function of the largest clique in the Markov equivalence class. We provide an algorithm that computes intervention sets that we believe are optimal for the above task. The algorithm builds on insights gained from the worst case analysis in Eberhardt et al. (2005) for sequences of experiments when all possible directed acyclic graphs over N variables are considered. A simulation suggests that our conjecture is correct. We also show that a generalization of our conjecture to other classes of possible graph hypotheses cannot be given easily, and in what sense the algorithm is then no longer optimal.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2008 AUAI Press. I am very grateful to Oleg Pikhurko for pointing me to Folkman's Theorem. This research was funded by a fellowship from the James S. McDonnell Foundation.
Funding AgencyGrant Number
James S. McDonnell FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20190327-085859738
Persistent URL:
Official Citation:Frederick Eberhardt. 2008. Almost optimal intervention sets for causal discovery. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI'08), David McAllester and Petri Myllymaki (Eds.). AUAI Press, Arlington, Virginia, United States, 161-168.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94195
Deposited By: George Porter
Deposited On:27 Mar 2019 21:59
Last Modified:02 Jun 2023 00:14

Repository Staff Only: item control page