jmlr jmlr2013 jmlr2013-41 jmlr2013-41-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Antti Hyttinen, Frederick Eberhardt, Patrik O. Hoyer
Abstract: Randomized controlled experiments are often described as the most reliable tool available to scientists for discovering causal relationships among quantities of interest. However, it is often unclear how many and which different experiments are needed to identify the full (possibly cyclic) causal structure among some given (possibly causally insufficient) set of variables. Recent results in the causal discovery literature have explored various identifiability criteria that depend on the assumptions one is able to make about the underlying causal process, but these criteria are not directly constructive for selecting the optimal set of experiments. Fortunately, many of the needed constructions already exist in the combinatorics literature, albeit under terminology which is unfamiliar to most of the causal discovery community. In this paper we translate the theoretical results and apply them to the concrete problem of experiment selection. For a variety of settings we give explicit constructions of the optimal set of experiments and adapt some of the general combinatorics results to answer questions relating to the problem of experiment selection. Keywords: causality, randomized experiments, experiment selection, separating systems, completely separating systems, cut-coverings
N. Alon, B. Bollob´ s, A. Gy´ rf´ s, J. Lehel, and A. Scott. Maximum directed cuts in acyclic dia a a graphs. Journal of Graph Theory, 55(1):1–13, 2007. E. Bareinboim and J. Pearl. In Proceedings of the Twenty-Eight Conference on Uncertainty in Artificial Intelligence, 2012. M. Bussieck. The minimal cut cover of a graph. Technical Report TR-94-02, Pennsylvania State University, 1994. M.-C. Cai. On separating systems of graphs. Discrete Mathematics, 49(1):15 – 20, 1984a. M.-C. Cai. On a problem of Katona on minimal completely separating systems with restrictions. Discrete Mathematics, 48(1):121 – 123, 1984b. 3068 E XPERIMENT S ELECTION FOR C AUSAL D ISCOVERY P. J. Cameron. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994. T. Claassen and T. Heskes. Causal discovery in multiple models from different experiments. In Advances in Neural Information Processing Systems 23, pages 415–423, 2010. G. Cooper and C. Yoo. Causal discovery from a mixture of experimental and observational data. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann, 1999. T. J. Dickson. On a problem concerning separating systems of a finite set. Journal of Combinatorial Theory, 7(3):191 – 196, 1969. D. Eaton and K. Murphy. Exact Bayesian structure learning from uncertain interventions. In Proceedings of the 11th International Conference on Artificial Intelligence and Statistics, Journal of Machine Learning Research Workshop and Conference Proceedings 2, 2007. F. Eberhardt. Causation and Intervention. PhD thesis, Carnegie Mellon, 2007. F. Eberhardt. Almost optimal intervention sets for causal discovery. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2008. F. Eberhardt, C. Glymour, and R. Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2005. F. Eberhardt, P. O. Hoyer, and R. Scheines. Combining experiments to discover linear cyclic models with latent variables. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, Journal of Machine Learning Research Workshop and Conference Proceedings 9, 2010. R. A. Fisher. The Design of Experiments. Hafner, 1935. J. R. Griggs, Sven Hartman, Uwe Leck, and I. T. Roberts. Full and maximal squashed flat antichains of minimum weight. Technical report, 2012. B. Halld´ rsson, M. Halld´ rsson, and R. Ravi. On the approximability of the minimum test collection o o problem. In Friedhelm auf der Heide, editor, Algorithms ESA 2001, volume 2161 of Lecture Notes in Computer Science, pages 158–169. Springer, 2001. M. Halld´ rsson. A still better performance guarantee for approximate graph coloring. Information o Processing Letters, 45(1):19 – 23, 1993. A. Hauser and P. B¨ hlmann. Two optimal strategies for active learning of causal models from u interventions. In Proceedings of the 6th European Workshop on Probabilistic Graphical Models, 2012. Y.-B. He and Z. Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9:2523–2547, 2008. 3069 H YTTINEN , E BERHARDT AND H OYER A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Causal discovery for linear cyclic models with latent variables. In Proceedings of the Fifth European Workshop on Probabilistic Graphical Models, 2010. A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Noisy-or models with latent confounding. In Proceedings of the Twenty-Seventh Conference Conference on Uncertainty in Artificial Intelligence, 2011. A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Causal discovery of linear cyclic models from multiple experimental data sets with overlapping variables. In Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, 2012a. A. Hyttinen, F. Eberhardt, and P. O. Hoyer. Learning linear cyclic causal models with latent variables. Journal of Machine Learning Research, 13:3387–3439, 2012b. S. Jukna. Extremal Combinatorics. Springer, 2011. G. Katona. On separating systems of a finite set. Journal of Combinatorial Theory, 1(2):174 – 194, 1966. G. Katona. A theorem of finite sets. In P. Erdos and G. Katona, editors, Theory of graphs. Akademiai Kiado and Academic Press, 1968. ´ A. Kisv¨ lcsey. Flattening antichains. Combinatorica, 26:65–82, 2006. o D.J. Kleitman and E.C. Milner. On the average size of the sets in a Sperner family. Discrete Mathematics, 6(2):141 – 147, 1973. J. B. Kruskal. The number of simplices in a complex. In R. Bellman, editor, Mathematical Optimization Techniques. University of California Press, 1963. A. K¨ ndgen, D. Mubayi, and P. Tetali. Minimal completely separating systems of k-sets. Journal u of Combinatorial Theory, Series A, 93(1):192 – 198, 2001. L. Liberti, L. Alfandari, and M.-C. Plateau. Edge cover by connected bipartite subgraphs. Annals of Operations Research, 188:307–329, 2011. P. Lieby. The separation problem. Honours thesis, Northern Territory University, 1994. P. Lieby. Extremal Problems in Finite Sets. PhD thesis, Northern Territory University, 1999. R. Loulou. Minimal cut cover of a graph with an application to the testing of electronic boards. Operations Research Letters, 12(5):301 – 305, 1992. S. Meganck, B. Manderick, and P. Leray. A decision theoretic approach to learning Bayesian networks. Technical report, Vrije Universiteit Brussels, 2005. B. M. E. Moret and H. D. Shapiro. On minimizing a set of tests. SIAM Journal on Scientific and Statistical Computing, 6(4):983–1003, 1985. R. Motwani and J. Naor. On exact and approximate cut covers of graphs. Technical report, Stanford University, 1993. 3070 E XPERIMENT S ELECTION FOR C AUSAL D ISCOVERY K. P. Murphy. Active learning of causal Bayes net structure. Technical report, U.C. Berkeley, 2001. J. Pearl. Causality. Oxford University Press, 2000. C. Ramsay and I. T. Roberts. Minimal completely separating systems of sets. Australasian Journal of Combinatorics, 13:129–150, 1996. C. Ramsay, I. T. Roberts, and F. Ruskey. Completely separating systems of k-sets. Discrete Mathematics, 183:265–275, 1998. A. R´ nyi. On random generating elements of a finite Boolean algebra. Acta Sci. Math. (Szeged), e 22:75–81, 1961. I. T. Roberts. The flat antichain conjecture for small average set size. Technical report, Northern Territory University, 1999. I. T. Roberts and Leanne J. Rylands. Minimal (n) and (n,h,k) completely separating systems. Australasian Journal of Combinatorics, 33:57 – 66, 2005. I. Shpitser and J. Pearl. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, 2006. J. Spencer. Minimal completely separating systems. Journal of Combinatorial Theory, 8(4):446 – 447, 1970. ¨ E. Sperner. Ein Satz uber Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27: 544–548, 1928. P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction and Search. MIT Press, 1993. S. Tong and D. Koller. Active learning for structure in Bayesian networks. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, 2001. K. Watanabe, M. Sengoku, H. Tamura, K. Nakano, and S. Shinoda. A scheduling problem in multihop networks. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E83-A(6):1222 – 1227, 2000. I. Wegener. On separating systems whose elements are sets of at most k elements. Discrete Mathematics, 28(2):219 – 222, 1979. D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967. 3071