An Automated Approach to Causal Inference in Discrete Settings

• URL: http://arxiv.org/abs/2109.13471v1
• Date: Tue, 28 Sep 2021 03:55:32 GMT
• Title: An Automated Approach to Causal Inference in Discrete Settings
• Authors: Guilherme Duarte, Noam Finkelstein, Dean Knox, Jonathan Mummolo, Ilya Shpitser
• Abstract summary: We show an algorithm to automatically bound causal effects using efficient dual relaxation and spatial branch-and-bound techniques. The algorithm searches over admissible data-generating processes and outputs the most precise possible range consistent with available information. It offers an additional guarantee we refer to as $epsilon$-sharpness, characterizing the incomplete bounds.
• Score: 8.242194776558895
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: When causal quantities cannot be point identified, researchers often pursue partial identification to quantify the range of possible values. However, the peculiarities of applied research conditions can make this analytically intractable. We present a general and automated approach to causal inference in discrete settings. We show causal questions with discrete data reduce to polynomial programming problems, and we present an algorithm to automatically bound causal effects using efficient dual relaxation and spatial branch-and-bound techniques. The user declares an estimand, states assumptions, and provides data (however incomplete or mismeasured). The algorithm then searches over admissible data-generating processes and outputs the most precise possible range consistent with available information -- i.e., sharp bounds -- including a point-identified solution if one exists. Because this search can be computationally intensive, our procedure reports and continually refines non-sharp ranges that are guaranteed to contain the truth at all times, even when the algorithm is not run to completion. Moreover, it offers an additional guarantee we refer to as $\epsilon$-sharpness, characterizing the worst-case looseness of the incomplete bounds. Analytically validated simulations show the algorithm accommodates classic obstacles, including confounding, selection, measurement error, noncompliance, and nonresponse.

Related papers

• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem. Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. We present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space.
  arXiv  Detail & Related papers  (2024-06-05T02:33:50Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• Synthesizing Tight Privacy and Accuracy Bounds via Weighted Model Counting [5.552645730505715]
  Two core challenges are finding expressive, compact, and efficient encodings of distributions of DP algorithms. We address the first challenge by developing a method for tight privacy and accuracy bound synthesis. We develop a framework for leveraging inherent symmetries in DP algorithms.
  arXiv  Detail & Related papers  (2024-02-26T19:29:46Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Encoding of data sets and algorithms [0.0]
  In many high-impact applications, it is important to ensure the quality of output of a machine learning algorithm. We have initiated a mathematically rigorous theory to decide which models are close to each other in terms of certain metrics. A given threshold metric acting on this grid will express the nearness (or statistical distance) from each algorithm and data set of interest to any given application.
  arXiv  Detail & Related papers  (2023-03-02T05:29:27Z)
• 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)
• Anomaly Detection via Controlled Sensing and Deep Active Inference [43.07302992747749]
  In this paper, we address the anomaly detection problem where the objective is to find the anomalous processes among a given set of processes. We develop a sequential selection algorithm that decides which processes to be probed at every instant to detect the anomalies. Our algorithm is based on active inference which is a general framework to make sequential decisions in order to maximize the notion of free energy.
  arXiv  Detail & Related papers  (2021-05-12T17:54:02Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19:48Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22: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.