A Recursive Markov Boundary-Based Approach to Causal Structure Learning
Preprint
Abstract
Constraint-based methods are one of the main approaches for causal structure learning that are particularly valued as they are asymptotically guaranteed to find a structure that is Markov equivalent to the causal graph of the system. On the other hand, they may require an exponentially large number of conditional independence (CI) tests in the number of variables of the system. In this paper, we propose a novel recursive constraint-based method for causal structure learning that significantly reduces the required number of CI tests compared to the existing literature. The idea of the proposed approach is to use Markov boundary information to identify a specific variable that can be removed from the set of variables without affecting the statistical dependencies among the other variables. Having identified such a variable, we discover its neighborhood, remove that variable from the set of variables, and recursively learn the causal structure over the remaining variables. We further provide a lower bound on the number of CI tests required by any constraint-based method. Comparing this lower bound to our achievable bound demonstrates the efficiency of the proposed approach. Our experimental results show that the proposed algorithm outperforms state-of-the-art both on synthetic and real-world structures.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Consistency guarantees for greedy permutation-based causal inference algorithmsBiometrika, 2021
- Learning causality and causality-related learning: some recent progressNational Science Review, 2017
- The max-min hill-climbing Bayesian network structure learning algorithmMachine Learning, 2006
- Gene Selection for Cancer Classification using Support Vector MachinesMachine Learning, 2002
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.The Journal of Philosophy, 1991
- Frequency Distribution of the Values of the Correlation Coefficient in Samples from an Indefinitely Large PopulationBiometrika, 1915