# zbMATH — the first resource for mathematics

Geometry of the faithfulness assumption in causal inference. (English) Zbl 1267.62068
Summary: Many algorithms for inferring causality rely heavily on the faithfulness assumption. The main justification for imposing this assumption is that the set of unfaithful distributions has Lebesgue measure zero, since it can be seen as a collection of hypersurfaces in a hypercube. However, due to sampling error the faithfulness condition alone is not sufficient for statistical estimation, and strong-faithfulness has been proposed and assumed to achieve uniform or high-dimensional consistency. In contrast to the plain faithfulness assumption, the set of distributions that is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly large as we show in this paper. We study the strong-faithfulness condition from a geometric and combinatorial point of view and give upper and lower bounds on the Lebesgue measure of strong-faithful distributions for various classes of directed acyclic graphs. Our results imply fundamental limitations for the PC-algorithm and potentially also for other algorithms based on partial correlation testing in the Gaussian case.

##### MSC:
 62H05 Characterization and structure theory for multivariate probability distributions; copulas 05C20 Directed graphs (digraphs), tournaments 65C60 Computational problems in statistics (MSC2010) 62H20 Measures of association (correlation, canonical correlation, etc.) 05C90 Applications of graph theory
##### Software:
 [1] A. Becker, D. G. and Meek, C. (2000). Perfect tree-like Markovian distributions. In Proceedings of the 16 th Conference on Uncertainty in Artificial Intelligence 19-23. Morgan Kaufmann, San Francisco, CA. · Zbl 1122.60013 [2] Adler, R. J. and Taylor, J. E. (2007). Random Fields and Geometry . Springer, New York. · Zbl 1149.60003 [3] Chickering, D. M. (2003). Optimal structure identification with greedy search: Computational learning theory. J. Mach. Learn. Res. 3 507-554. · Zbl 1084.68519 [4] Guth, L. (2009). Minimax problems related to cup powers and Steenrod squares. Geom. Funct. Anal. 18 1917-1987. · Zbl 1190.53038 [5] Kalisch, M. and Bühlmann, P. (2007). Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J. Mach. Learn. Res. 8 613-636. · Zbl 1222.68229 [6] Kalisch, M., Mächler, M., Colombo, D., Maathuis, M. H. and Bühlmann, P. (2011). Causal inference using graphical models with the R package pcalg. Journal of Statistical Software 47 1-26. [7] Lin, S., Uhler, C., Sturmfels, B. and Bühlmann, P. (2012). Hypersurfaces and their singularities in partial correlation testing. Unpublished manuscript. Available at . · Zbl 1308.62110 [8] Maathuis, M. H., Kalisch, M. and Bühlmann, P. (2009). Estimating high-dimensional intervention effects from observational data. Ann. Statist. 37 3133-3164. · Zbl 1191.62118 [9] Pearl, J. (2000). Causality : Models , Reasoning , and Inference . Cambridge Univ. Press, Cambridge. · Zbl 0959.68116 [10] Ponstein, J. (1966). Self-avoiding paths and the adjacency matrix of a graph. SIAM J. Appl. Math. 14 600-609. · Zbl 0146.45901 [11] Robins, J. M., Scheines, R., Spirtes, P. and Wasserman, L. (2003). Uniform consistency in causal inference. Biometrika 90 491-515. · Zbl 1436.62025 [12] Spirtes, P., Glymour, C. and Scheines, R. (2001). Causation , Prediction and Search , 2nd ed. MIT Press, Cambridge. · Zbl 0981.62001 [13] Spirtes, P. and Zhang, J. (2012). A uniformly consistent estimator of causal effects under the $$k$$-triangle-faithfulness assumption. Unpublished manuscript. · Zbl 1331.62277 [14] Sullivant, S., Talaska, K. and Draisma, J. (2010). Trek separation for Gaussian graphical models. Ann. Statist. 38 1665-1685. · Zbl 1189.62091 [15] van de Geer, S. and Bühlmann, P. (2013). $$\ell_0$$-penalized maximum likelihood for sparse directed acyclic graphs. Ann. Statist. · Zbl 1267.62037 [16] Zhang, J. and Spirtes, P. (2003). Strong faithfulness and uniform consistency in causal inference. In Proceedings of the 19 th Conference on Uncertainty in Artificial Intelligence 632-639. Morgan Kaufmann, San Francisco, CA. [17] Zhang, J. and Spirtes, P. (2008). Detection of unfaithfulness and robust causal inference. Minds and Machines 18 239-271.