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 vecV of n observable variables with respect to a given causal graph G with observable distribution P. Let Px 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=tildeO(nε-2) samples from P and O(mn) time, and outputs with high probability a description of a distribution hatP such that dTV(Px, hatP) ≤ ε, and: 1. [Evaluation] the description can return in O(n) time the probability hatP(vecv) for any assignment vecv to vecV 2. [Generation] the description can return an iid sample from hatP 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 ε, as well as if k=1 on the strong positivity parameter.