2008-07-09-eberhardt08a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_editor	editor	bibtex_author	author	date	note	address	container-title	volume	genre	issued	pdf	extras
Almost optimal intervention sets for causal discovery	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	eberhardt08a	0	Almost optimal intervention sets for causal discovery	161	168	161-168	161	false	McAllester, David A. and Myllym{"a}ki, Petri	given family David A. McAllester given family Petri Myllymäki	Eberhardt, Frederick	given family Frederick Eberhardt	2008-07-09	Reissued by PMLR on 30 October 2024.		Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence	R6	inproceedings	date-parts 2008 7 9	http://proceedings.mlr.press/r6/eberhardt08a/eberhardt08a.pdf