Learning and Sampling of Atomic Interventions from Observations
We study the problem of efficiently estimating the effect of an intervention on a single variable (atomic interventions) using observational samples in a causal Bayesian network. Our goal is to give algorithms that are efficient in both time and sample complexity in a non-parametric setting. Tian and Pearl (AAAI `02) have exactly characterized the class of causal graphs for which causal effects of atomic interventions can be identified from observational data. We make their result quantitative. Suppose P is a causal model on a set $\vec{V}$ of n observable variables with respect to a given causal graph G with observable distribution $P$. Let $P_x$ denote the interventional distribution over the observables with respect to an intervention of a designated variable X with x. Assuming that $G$ has bounded in-degree, bounded c-components ($k$), and that the observational distribution is identifiable and satisfies certain strong positivity condition, we give an algorithm that takes $m=\tilde{O}(n\epsilon^{-2})$ samples from $P$ and $O(mn)$ time, and outputs with high probability a description of a distribution $\hat{P}$ such that $d_{\mathrm{TV}}(P_x, \hat{P}) \leq \epsilon$, and: 1. [Evaluation] the description can return in $O(n)$ time the probability $\hat{P}(\vec{v})$ for any assignment $\vec{v}$ to $\vec{V}$ 2. [Generation] the description can return an iid sample from $\hat{P}$ in $O(n)$ time. We also show lower bounds for the sample complexity showing that our sample complexity has an optimal dependence on the parameters $n$ and $\epsilon$, as well as if $k=1$ on the strong positivity parameter.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Bayesian causal inference via probabilistic program synthesis
Causal inference can be formalized as Bayesian inference that combines a prior distribution over causal models and likelihoods that account for both observations and interventions. We show that it is possible to implemen…
Bayesian InferenceCausal InferenceProbabilistic ProgrammingProgram SynthesisCollaborative Causal Discovery with Atomic Interventions
We introduce a new Collaborative Causal Discovery problem, through which we model a common scenario in which we have multiple independent entities each with their own causal graph, and the goal is to simultaneously learn…
Causal DiscoveryClusteringOSCAR: Occupancy-based Shape Completion via Acoustic Neural Implicit Representations
Accurate 3D reconstruction of vertebral anatomy from ultrasound is important for guiding minimally invasive spine interventions, but it remains challenging due to acoustic shadowing and view-dependent signal variations. …
3D ReconstructionSubset verification and search algorithms for causal DAGs
Learning causal relationships between variables is a fundamental task in causal inference and directed acyclic graphs (DAGs) are a popular choice to represent the causal relationships. As one can recover a causal graph o…
Causal InferenceA Causal Bandit Approach to Learning Good Atomic Interventions in Presence of Unobserved Confounders
We study the problem of determining the best intervention in a Causal Bayesian Network (CBN) specified only by its causal graph. We model this as a stochastic multi-armed bandit (MAB) problem with side-information, where…