×

Faithfulness of probability distributions and graphs. (English) Zbl 1444.62079

Summary: A main question in graphical models and causal inference is whether, given a probability distribution \(P\) (which is usually an underlying distribution of data), there is a graph (or graphs) to which \(P\) is faithful. The main goal of this paper is to provide a theoretical answer to this problem. We work with general independence models, which contain probabilistic independence models as a special case. We exploit a generalization of ordering, called preordering, of the nodes of (mixed) graphs. This allows us to provide sufficient conditions for a given independence model to be Markov to a graph with the minimum possible number of edges, and more importantly, necessary and sufficient conditions for a given probability distribution to be faithful to a graph. We present our results for the general case of mixed graphs, but specialize the definitions and results to the better-known subclasses of undirected (concentration) and bidirected (covariance) graphs as well as directed acyclic graphs.

MSC:

62H22 Probabilistic graphical models
68T05 Learning and adaptive systems in artificial intelligence

Software:

TETRAD
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] R. Ayesha Ali, Thomas S. Richardson, and Peter Spirtes. Markov equivalence for ancestral graphs. Annals of Statistics, 37(5B):2808-2837, 2009. · Zbl 1178.68574
[2] Steen A. Andersson, David Madigan, and Michael D. Perlman. Alternative Markov properties for chain graphs. Scandinavian Journal of Statistics, 28:33-85, 2001. · Zbl 0972.60067
[3] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3:507-554, 2003. · Zbl 1084.68519
[4] Peter Clifford. Markov random fields in statistics. In G. R. Grimmett and D. J. A. Welsh, editors, Disorder in Physical Systems: A Volume in Honour of John M. Hammersley, pages 19-32. Oxford University Press, 1990. · Zbl 0736.62081
[5] David R. Cox and Nanny Wermuth. Linear dependencies represented by chain graphs (with discussion). Statistical Science, 8(3):204-218; 247-277, 1993. · Zbl 0955.62593
[6] John N. Darroch, Steffen L. Lauritzen, and Terry P. Speed. Markov fields and log-linear interaction models for contingency tables. Annals of Statistics, 8:522-539, 1980. · Zbl 0444.62064
[7] A. Philip Dawid. Conditional independence in statistical theory (with discussion). Journal of the Royal Statistical Society Series B, 41(1):1-31, 1979. · Zbl 0408.62004
[8] Mathias Drton and Thomas S. Richardson. Binary models for maginal independence. Journal of the Royal Statistical Society Series B, 41(2):287-309, 2008. 26 · Zbl 1148.62043
[9] Shaun Fallat, Steffen Lauritzen, Kayvan Sadeghi, Caroline Uhler, Nanny Wermuth, and Piotr Zwiernik. Total positivity in Markov structures. Annals of Statistics., 45(3), 2017. · Zbl 1414.60010
[10] Morten Frydenberg. The chain graph Markov property. Scandinavian Journal of Statistics, 17:333-353, 1990. · Zbl 0713.60013
[11] Dan Geiger, Thomas S. Verma, and Judea Pearl. Identifying independence in Bayesian networks. Networks, 20:507-534, 1990. · Zbl 0724.05066
[12] Clark Glymour, Richard Scheines, Peter Spirtes, and Kevin Kelly.Discovering Causal Structure. Academic Press, 1987. · Zbl 0778.68004
[13] Samuel Karlin and Yosef Rinott. Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions. Journal of Multivariate Analysis, 10(4):467-498, 1980. · Zbl 0469.60006
[14] Samuel Karlin and Yosef Rinott. M-matrices as covariance matrices of multinormal distributions. Linear Algebra and its Applications, 52:419 – 438, 1983. · Zbl 0538.62040
[15] G¨oran Kauermann. On a dualization of graphical Gaussian models. Scandinavian Journal of Statistics, 23(1):105-116, 1996. · Zbl 0912.62006
[16] Harri Kiiveri, Terry P. Speed, and J. B. Carlin. Recursive causal models. Journal of the Australian Mathematical Society, Series A, 36:30-52, 1984. · Zbl 0551.62021
[17] Steffen L. Lauritzen. Graphical Models. Clarendon Press, Oxford, United Kingdom, 1996. · Zbl 0907.62001
[18] Steffen L. Lauritzen and Kayvan Sadeghi. Unifying Markov properties for graphical models. Annals of Statistics, To appear, 2017. URL https://arxiv.org/abs/1608.05810. · Zbl 1303.60064
[19] Steffen L. Lauritzen and David J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B, 50:157-224, 1988. · Zbl 0684.68106
[20] Steffen L. Lauritzen and Nanny Wermuth. Graphical models for association between variables, some of which are qualitative and some quantitative. Annals of Statistics, 17:31-57, 1989. · Zbl 0669.62045
[21] Radim Lnˇeniˇcka and Frantiˇsek Mat´uˇs. On Gaussian conditional independence structures. Kybernetika, 43(3):327-342, 2007. · Zbl 1144.60302
[22] Christopher Meek. Strong completeness and faithfulness in Bayesian networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI’95, pages 411-418, San Francisco, CA, USA, 1995.
[23] Richard E. Neapolitan. Learning Bayesian Networks. Prentice Hall, Upper Saddle River, NJ, USA, 2004.
[24] Jose M. Pe˜na. Faithfulness in chain graphs: The discrete case. International Journal of Approximate Reasoning, 50:1306-1313, 2009. 27 · Zbl 1416.62376
[25] Jose M. Pe˜na. Faithfulness in chain graphs: The Gaussian case. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS 2011), volume 15, pages 588-599. JMLR.org, 2011.
[26] Jose M. Pe˜na. Marginal AMP chain graphs. International Journal of Approximate Reasoning, 55:1185-1206, 2014. · Zbl 1433.05304
[27] Judea Pearl. Probabilistic Reasoning in Intelligent Systems : networks of plausible inference. Morgan Kaufmann Publishers, San Mateo, CA, USA, 1988. · Zbl 0746.68089
[28] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, New York, NY, USA, 2nd edition, 2009. · Zbl 1188.68291
[29] Judea Pearl and Azaria Paz. Graphoids: A Graph-based Logic for Reasoning about Relevance Relations. University of California (Los Angeles). Computer Science Department, 1985. · Zbl 07672241
[30] Jonas Peters. On the intersection property of conditional independence and its application to causal discovery. Journal of Causal Inference, 3:97-108, 2015.
[31] Joseph Ramsey, Jiji Zhang, and Peter Spirtes. Adjacency-faithfulness and conservative causal inference. In UAI. AUAI Press, 2006.
[32] Thomas Richardson. Markov properties for acyclic directed mixed graphs. Scandinavian Journal of Statistics, 30(1):145-157, 2003. · Zbl 1035.60005
[33] Thomas S. Richardson and Peter Spirtes. Ancestral graph Markov models. Annals of Statistics, 30(4):962-1030, 2002. · Zbl 1033.60008
[34] Kayvan Sadeghi. Stable mixed graphs. Bernoulli, 19(5(B)):2330-2358, 2013. · Zbl 1317.05077
[35] Kayvan Sadeghi. Marginalization and conditioning for LWF chain graphs. Annals of Statistics, 44(4):1792-1816, 2016. · Zbl 1359.62284
[36] Kayvan Sadeghi and Steffen L. Lauritzen. Markov properties for mixed graphs. Bernoulli,, 20(2):676-696, 2014. · Zbl 1303.60064
[37] Bernd S.W. Schr¨oder. Ordered Sets: An Introduction. Birkh¨auser, Boston, 2003.
[38] De W. Soh and Sekhar C. Tatikonda. Testing unfaithful Gaussian graphical models. In Z. Ghahramani, M. Welling, C. Cortes, N.d. Lawrence, and K.q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2681-2689. Curran Associates, Inc., 2014. · Zbl 1434.68455
[39] Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2000. · Zbl 0806.62001
[40] Daniel Steel. Homogeneity, selection, and the faithfulness condition. Minds and Machines, 16(3):303-317, 2006.
[41] Milan Studen´y. Multiinformation and the problem of characterization of conditional independence relations. Problems of Control and Information Theory, 18:3-16, 1989. 28
[42] Milan Studen´y. Probabilistic Conditional Independence Structures. Springer-Verlag, London, United Kingdom, 2005.
[43] Milan Studen´y and Remco R. Bouckaert. On chain graph models for description of conditional independence structures. Annals of Statistics, 26(4):1434-1495, 1998. · Zbl 0930.62066
[44] Caroline Uhler, Garvesh Raskutti, Peter B¨uhlmann, and Bin Yu. Geometry of the faithfulness assumption in causal inference. Annals of Statistics, 41(2):436-463, 2013. · Zbl 1267.62068
[45] Thomas Verma and Judea Pearl. On the equivalence of causal models. In Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-90), pages 220-227, New York, NY, 1990.
[46] Nanny Wermuth. Probability distributions with summary graph structure. Bernoulli, 17 (3):845-879, 2011. · Zbl 1245.62062
[47] Nanny Wermuth and David R. Cox. On association models defined over independence graphs. Bernoulli, 4:477-495, 1998. · Zbl 1037.62054
[48] Nanny Wermuth and Kayvan Sadeghi. Sequences of regressions and their independences. TEST, 21(2):215-252 and 274-279, 2012. · Zbl 1259.62063
[49] Nanny Wermuth, Giovanni M. Marchetti, and David R. Cox. Triangular systems for symmetric binary variables. Electronic Journal of Statistics, 3:932-955, 2009. · Zbl 1326.62145
[50] James Woodward. Causal independence and faithfulness. Multivariate Behavioral Research, 33(1):129-148, 1998.
[51] Jiji Zhang and Peter Spirtes. Strong faithfulness and uniform consistency in causal inference. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, UAI’03, 2003. · Zbl 1331.62277
[52] Jiji Zhang and Peter Spirtes. Detection of unfaithfulness and robust causal inference. Minds and Machines, 18(2):239-271, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.