Report
Learning and Sampling of Atomic Interventions from Observations
| العنوان: | Learning and Sampling of Atomic Interventions from Observations |
|---|---|
| المؤلفون: | Bhattacharyya, Arnab, Gayen, Sutanu, Kandasamy, Saravanan, Maran, Ashwin, Vinodchandran, N. V. |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Science - Data Structures and Algorithms, Statistics - Machine Learning, I.2.6 |
| الوصف: | 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. Comment: 26 pages, 4 figures, a version appeared in ICML 2020 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2002.04232 |
| رقم الانضمام: | edsarx.2002.04232 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |