Strong completeness and faithfulness in Bayesian networks

By Christopher Meek. 1995

A completeness result for d-separation applied to discrete Bayesian networks is presented and it is shown that in a strong measure-theoretic sense almost all discrete distributions for a given network structure are faithful; i.e. the independence facts true of the distribution are all and only those entailed by the network structure

Subfields: Probabilistic & Bayesian Methods, Knowledge Graphs & Representation

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

In Knowledge Graphs & Representation

Citations in the corpus

Causal Inference through a Witness Protection Program (2014, background): “Even if unfaithful distributions can be ruled out as pathological under seemingly reasonable conditions (Meek, 1995), distributions which lie close to (but not on) a simpler model may in practice be indistinguishable from distributions within that simpler model at finite sample sizes.”
Causal Discovery from Heterogeneous/Nonstationary Data (2019, methodology): “In such a case, one may further infer some causal directions by making use of Meek’s orientation rules (Meek, 1995) used in PC.”
Behind Distribution Shift: Mining Driving Forces of Changes and Causal Arrows (2017, neutral): “For those pairs of adjacent variables that do not have nonstationary causal modules, we try to infer causal directions, if possible, by Meek orientation rules [5].”
Multi-Level Cause-Effect Systems (2015, background): “o). The proof is split into two parts: (i) Express the theorem as a polynomial constraint on the space of all P(i;j;h) distributions. (ii) Show that the polynomial constraint is not trivial. This, by Meek (1995), implies that among all P(i;j;h) distributions, the fundamental causal partition on J is”
Visual Causal Feature Learning (2014, methodology): “Fig. 3 illustrates the relation between the causal and the observational partition implied by the theorem. We prove the Causal Coarsening Theorem (5) in Appendix A using a technique extending that of Meek (1995). Two points are worth noting here: First, CCT conﬁrms the intuition that the visual caus”
Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm (2005, background): “The output of Algorithm 2 is a CPDAG, which was first proved by Meek (1995b).”
A theory of causal learning in children: causal maps and Bayes nets. (2004, background): “…coefficients of linear models, faithfulness holds with a probability of 1, and similarly for absolutely continuous probability measures on the conditional probabilities (of each variable on each vector of values of its parents) in models with discrete variables (Meek, 1995; Spirtes et al., 1993).”
Causal Discovery and Inference: Concepts and Recent Methodological Advances (2016, background): “In the worse case, it is exponential in the number of variables, but for sparse graphs, it can run on hundreds of thousands of variables (Spirtes and Glymour 1991; Spirtes et al. 1993; Meek 1995).”
Joint Causal Inference from Multiple Contexts (2016, background): “More specifically, Meek (1995) showed that faithfulness holds generically for DAGs if (i) all variable domains are finite, or (ii) if all variables are real-valued, linearly related and have a multivariate Gaussian distribution.”
Three Problems for the Mutual Manipulability Account of Constitutive Relevance in Mechanisms (2012, background): “(See Varzi [2009] for examples of parts and wholes that have no spatio-temporal location.”
Learning Bayesian networks from data: An information-theory based approach (2002, methodology): “Section 7 compares this approach with the other standard approach, based on maximizing some score.”
Causal Inference from Graphical Models (2001, background): “As previously mentioned, results of Meek (1995) indicate that most distributions are indeed faithful.”
Estimating Causal Direction and Confounding of Two Discrete Variables (2016, background): “But the results of Geiger and Pearl (1988) and Meek (1995) only make an existential claim: That for any joint distribution a parameterization of the appropriate form exists for any causal structure in the Markov equivalence class.”
Causal Inference in the Presence of Latent Variables and Selection Bias (1995, methodology): “Combining an independence test algorithm for DAG search (essentially a special case of FCI) and greedy DAG searches based upon maximizing a score has proved successful in simulation studies (Spirtes and Meek 1995, Singh and Valorta 1993).”
Understanding Agent Incentives using Causal Influence Diagrams. Part I: Single Action Settings (2019, background): “ve just because the graph permits it. A similar criticism can be put forth against the d-connectivity: Two nodes that are d-connected are not necessarily conditionally dependent. In response to this, Meek (1995) has shown that almost all probability distributions will induce an incentive if the grap”
Single World Intervention Graphs ( SWIGs ) : A Unification of the Counterfactual and Graphical Approaches to Causality (2013, result): “Proof: It follows directly from the corresponding results for DAGs (Geiger and Pearl, 1993; Meek, 1995, see) that we may construct a distribution P (V(ã)) in which the independence corresponding to the d-connection does not hold.”