TL;DR
This paper extends the d-separation criterion, a fundamental tool for reading conditional independencies from causal graphs, to systems with feedback loops. They demonstrate that d-separation remains a valid test for these complex, cyclic systems, provided the variables are discrete. This is a significant step towards analyzing real-world systems where feedback is common and variables are often best modeled discretely.
What Problem Does This Paper Address?
Bayesian networks, represented by Directed Acyclic Graphs (DAGs), are powerful tools for modeling probabilistic relationships and inferring conditional independencies. The d-separation criterion provides a graphical method to read these independencies directly from the DAG. However, this framework traditionally assumes acyclicity, meaning no feedback loops. Many real-world systems, from biological networks to digital circuits, inherently involve feedback. Applying d-separation directly to cyclic graphs can lead to incorrect conclusions about independencies. While previous work showed d-separation's validity for linear, Gaussian systems with feedback, this paper tackles the more general case of nonlinear, non-Gaussian systems, as long as the variables are discrete.
Methods
The core of the paper is proving that the d-separation criterion, which works for DAGs, can be extended to cyclic causal graphs under specific conditions. They achieve this by:
- Defining Causal Theories: They formalize causal models using a four-tuple including observed variables, unobserved disturbances, their distribution, and deterministic functions linking them. This framework allows for cyclic relationships.
- Introducing Semi-Markovian Theories: A special class of causal theories where disturbances are independent, simplifying analysis.
- Augmented Graphs: For general causal theories (where disturbances might be dependent), they introduce an "augmented graph" by adding dummy root nodes to represent dependencies among disturbances. This allows the d-separation criterion to be applied to the augmented graph.
- Leveraging Moralized Ancestral Graphs: They utilize a technique from Lauritzen et al. (1990) to transform directed graphs (even cyclic ones) into undirected graphs where d-separation in the DAG corresponds to graph separation in the undirected version. This is crucial for their proofs.
- Constraint Problems: They establish a connection between probability distributions induced by causal theories and the number of solutions to associated constraint problems. This allows them to translate probabilistic independencies into graph separation properties.
Datasets
Not discussed in the paper. The paper focuses on theoretical results and uses a synthetic example for illustration.
Key Insights and Ideas
- D-separation transcends acyclicity: The most significant insight is that the d-separation criterion, a cornerstone of Bayesian network analysis, can be generalized to cyclic causal graphs, provided the variables are discrete. This significantly expands the applicability of graphical causal models.
- Discrete variables are key: The discrete nature of variables is a critical assumption that enables the generalization. This suggests that for systems where continuous variables are approximated discretely, d-separation might still offer a reasonable approximation of true independencies.
- Feedback doesn't break d-separation (under conditions): The paper demonstrates that feedback loops, which complicate probability distributions, do not invalidate the graphical reading of independencies when variables are discrete.
- The power of graphical models for complex systems: This work highlights the continued relevance and power of graphical models for understanding complex systems, even those with non-trivial feedback structures.
Key Results
The paper's main result is stated in Theorem 2: For a semi-Markovian causal theory with discrete and finite domain variables, if the causal graph $G_T$ indicates that $X$ is d-separated from $Y$ given $Z$ (denoted $(X || Y|Z)_{G_T}$), then the variables $X$ and $Y$ are indeed conditionally independent given $Z$ in the induced probability distribution $P_T$ (denoted $(X \perp Y|Z)_{P_T}$).
Corollary 1 extends this to general causal theories by using an augmented graph $G'_T$.
The paper also provides an illustrative example (Figure 1) of a cyclic causal graph and demonstrates how the d-separation conditions advertised by the graph correspond to actual independencies in the induced probability distribution.
Limitations and Future Work
- Discrete Variables Assumption: The primary limitation is the requirement for discrete variables. The authors acknowledge that extending these results to continuous variables, especially in nonlinear systems, is challenging and may lead to spurious instabilities if not handled carefully (as hinted by an anonymous reviewer).
- Uniqueness of Solutions: The framework assumes that the functional relationships in the causal theory lead to a unique solution for observed variables given disturbances. This is a strong assumption that needs to be checked for cyclic systems.
- Future Work: The authors suggest that their findings have direct applications in diagnosing digital circuits and in learning the structure of feedback systems. They also implicitly point towards the need for robust methods for discretizing continuous feedback systems to leverage these results.
Summary updated