A Recursive Markov Boundary-Based Approach to Causal Structure Learning

• URL: http://arxiv.org/abs/2010.04992v3
• Date: Fri, 21 May 2021 02:37:14 GMT
• Title: A Recursive Markov Boundary-Based Approach to Causal Structure Learning
• Authors: Ehsan Mokhtarian, Sina Akbari, AmirEmad Ghassami, Negar Kiyavash
• Abstract summary: We propose a novel recursion-based method for causal structure learning. It significantly reduces the required number of conditional independence tests. Our experimental results show that the proposed algorithm outperforms state-of-the-art both on synthetic and real-world structures.
• Score: 22.38302412440357
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Induced Covariance for Causal Discovery in Linear Sparse Structures [55.2480439325792]
  Causal models seek to unravel the cause-effect relationships among variables from observed data. This paper introduces a novel causal discovery algorithm designed for settings in which variables exhibit linearly sparse relationships.
  arXiv  Detail & Related papers  (2024-10-02T04:01:38Z)
• Learning Discrete Latent Variable Structures with Tensor Rank Conditions [30.292492090200984]
  Unobserved discrete data are ubiquitous in many scientific disciplines, and how to learn the causal structure of these latent variables is crucial for uncovering data patterns. Most studies focus on the linear latent variable model or impose strict constraints on latent structures, which fail to address cases in discrete data involving non-linear relationships or complex latent structures. We explore a tensor rank condition on contingency tables for an observed variable set $mathbfX_p$, showing that the rank is determined by the minimum support of a specific conditional set. One can locate the latent variable through probing the rank on different observed variables
  arXiv  Detail & Related papers  (2024-06-11T07:25:17Z)
• Latent Hierarchical Causal Structure Discovery with Rank Constraints [19.61598654735681]
  We consider a challenging scenario for causal structure identification, where some variables are latent and they form a hierarchical graph structure. We propose an estimation procedure that can efficiently locate latent variables, determine their cardinalities, and identify the latent hierarchical structure.
  arXiv  Detail & Related papers  (2022-10-01T03:27:54Z)
• Revisiting GANs by Best-Response Constraint: Perspective, Methodology, and Application [49.66088514485446]
  Best-Response Constraint (BRC) is a general learning framework to explicitly formulate the potential dependency of the generator on the discriminator. We show that even with different motivations and formulations, a variety of existing GANs ALL can be uniformly improved by our flexible BRC methodology.
  arXiv  Detail & Related papers  (2022-05-20T12:42:41Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. We propose a novel computationally efficient constraint-based method that is sound and complete. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.
  arXiv  Detail & Related papers  (2021-10-22T19:49:59Z)
• Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment [79.5678820246642]
  We show that certain action-value methods are more sample efficient than policy-gradient methods on transfer problems that require only sparse changes to a sequence of previously optimal decisions. We generalize the recently proposed societal decision-making framework as a more granular formalism than the Markov decision process.
  arXiv  Detail & Related papers  (2021-06-28T21:29:13Z)
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures [132.74509389517203]
  We introduce a parametric variational family modelled by an autoregressive distribution over the space of discrete DAGs. In experiments, we demonstrate that the proposed variational posterior is able to provide a good approximation of the true posterior.
  arXiv  Detail & Related papers  (2021-06-14T17:52:49Z)
• A Local Method for Identifying Causal Relations under Markov Equivalence [7.904790547594697]
  Causality is important for designing interpretable and robust methods in artificial intelligence research. We propose a local approach to identify whether a variable is a cause of a given target based on causal graphical models of directed acyclic graphs (DAGs)
  arXiv  Detail & Related papers  (2021-02-25T05:01:44Z)
• Integer Programming for Causal Structure Learning in the Presence of Latent Variables [28.893119229428713]
  We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables. In particular, we generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formalize the IP-based ADMG learning model.
  arXiv  Detail & Related papers  (2021-02-05T12:10:16Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.