Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias

• URL: http://arxiv.org/abs/2110.12036v1
• Date: Fri, 22 Oct 2021 19:49:59 GMT
• Title: Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias
• Authors: Sina Akbari, Ehsan Mokhtarian, AmirEmad Ghassami, Negar Kiyavash
• Abstract summary: 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.
• Score: 27.06618125828978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning the causal MAG of a system from observational data in the presence of latent variables and selection bias. Constraint-based methods are one of the main approaches for solving this problem, but the existing methods are either computationally impractical when dealing with large graphs or lacking completeness guarantees. We propose a novel computationally efficient recursive constraint-based method that is sound and complete. The key idea of our approach is that at each iteration a specific type of variable is identified and removed. This allows us to learn the structure efficiently and recursively, as this technique reduces both the number of required conditional independence (CI) tests and the size of the conditioning sets. The former substantially reduces the computational complexity, while the latter results in more reliable CI tests. We provide an upper bound on the number of required CI tests in the worst case. To the best of our knowledge, this is the tightest bound in the literature. We further provide a lower bound on the number of CI tests required by any constraint-based method. The upper bound of our proposed approach and the lower bound at most differ by a factor equal to the number of variables in the worst case. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world structures.

Related papers

• Recursive Causal Discovery [22.56309301911757]
  Causal discovery is often the first step toward the identification and estimation of causal effects. This paper builds upon and extends four of our prior publications. We present a unified framework for the proposed algorithms, refined with additional details and enhancements for a coherent presentation.
  arXiv  Detail & Related papers  (2024-03-14T11:46:25Z)
• Exploiting Structure for Optimal Multi-Agent Bayesian Decentralized Estimation [4.320393382724066]
  Key challenge in Bayesian decentralized data fusion is the rumor propagation' or double counting' phenomenon. We show that by exploiting the probabilistic independence structure in multi-agent decentralized fusion problems a tighter bound can be found. We then test our new non-monolithic CI algorithm on a large-scale target tracking simulation and show that it achieves a tighter bound and a more accurate estimate.
  arXiv  Detail & Related papers  (2023-07-20T05:16:33Z)
• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  We propose a worst-case consistency regularization technique for semi-supervised learning (SSL) We present a generalization bound for SSL consisting of the empirical loss terms observed on labeled and unlabeled training data separately. Motivated by this bound, we derive an SSL objective that minimizes the largest inconsistency between an original unlabeled sample and its multiple augmented variants.
  arXiv  Detail & Related papers  (2022-09-26T12:04:49Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  We consider active learning for binary classification in the agnostic pool-based setting. Our algorithm is superior to state of the art active learning algorithms on image classification datasets.
  arXiv  Detail & Related papers  (2021-05-13T18:24:30Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  Population-based methods can cope with a variety of different problems, including problems of remarkably higher complexity than those traditional methods can handle. The aim here is to develop and compare different CHTs suitable for PSOs, which are incorporated to an algorithm with general-purpose settings.
  arXiv  Detail & Related papers  (2021-01-25T01:49:10Z)
• A Recursive Markov Boundary-Based Approach to Causal Structure Learning [22.38302412440357]
  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.
  arXiv  Detail & Related papers  (2020-10-10T13:26:22Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.