Novel Ordering-Based Approaches for Causal Structure Learning in the Presence of Unobserved Variables
Open Access
- 26 June 2023
- journal article
- research article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 37 (10) , 12260-12268
Abstract
We propose ordering-based approaches for learning the maximal ancestral graph (MAG) of a structural equation model (SEM) up to its Markov equivalence class (MEC) in the presence of unobserved variables. Existing ordering-based methods in the literature recover a graph through learning a causal order (c-order). We advocate for a novel order called removable order (r-order) as they are advantageous over c-orders for structure learning. This is because r-orders are the minimizers of an appropriately defined optimization problem that could be either solved exactly (using a reinforcement learning approach) or approximately (using a hill-climbing search). Moreover, the r-orders (unlike c-orders) are invariant among all the graphs in a MEC and include c-orders as a subset. Given that set of r-orders is often significantly larger than the set of c-orders, it is easier for the optimization problem to find an r-order instead of a c-order. We evaluate the performance and the scalability of our proposed approaches on both real-world and randomly generated networks.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Equivalence and Synthesis of Causal Models2022
- On scoring Maximal Ancestral Graphs with the Max–Min Hill Climbing algorithmInternational Journal of Approximate Reasoning, 2018
- Scaling up the Greedy Equivalence Search algorithm by constraining the search space of equivalence classesInternational Journal of Approximate Reasoning, 2013
- Learning high-dimensional directed acyclic graphs with latent and selection variablesThe Annals of Statistics, 2012
- Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhoodData Mining and Knowledge Discovery, 2010
- Causality and Causal Modelling in the Social Sciences2009
- The max-min hill-climbing Bayesian network structure learning algorithmMachine Learning, 2006
- Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell DataScience, 2005
- Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian NetworksMachine Learning, 2003
- Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning1992