Experimental Design for Causal Effect Identification

• URL: http://arxiv.org/abs/2205.02232v3
• Date: Thu, 17 Aug 2023 19:30:13 GMT
• Title: Experimental Design for Causal Effect Identification
• Authors: Sina Akbari, Jalal Etesami, Negar Kiyavash
• Abstract summary: We consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic approximation of it. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.
• Score: 31.23071073904698
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the causal effect. In this work, we consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic-factor approximation of it. This is done by establishing a connection between our problem and the minimum hitting set problem. Additionally, we propose several polynomial-time heuristic algorithms to tackle the computational complexity of the problem. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.

Related papers

• Fast Proxy Experiment Design for Causal Effect Identification [27.885243535456237]
  Two approaches to estimate causal effects are observational and experimental (randomized) studies. Direct experiments on the target variable may be too costly or even infeasible to conduct. A proxy experiment is conducted on variables with a lower cost to intervene on compared to the main target.
  arXiv  Detail & Related papers  (2024-07-07T11:09:38Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges) We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
  arXiv  Detail & Related papers  (2023-01-09T06:25:44Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Causal Effect Identification in Uncertain Causal Networks [30.239874638041904]
  Causal identification is at the core of the causal inference literature. We show that the edges in a causal graph exist with uncertainties which may, for example, represent degree of belief from domain experts. We propose efficient algorithms to approximate this problem evaluate them against both real-world networks and randomly generated graphs.
  arXiv  Detail & Related papers  (2022-08-09T09:44:45Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• Stochastic Causal Programming for Bounding Treatment Effects [8.879868078611443]
  Causal effect estimation is important for many tasks in the natural and social sciences. We use flexible learning algorithms and Monte Carlo methods to implement a family of solutions under the name of causal programming.
  arXiv  Detail & Related papers  (2022-02-22T10:55:24Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)
• Best Arm Identification in Spectral Bandits [0.0]
  Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint.
  arXiv  Detail & Related papers  (2020-05-20T04:12:04Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.