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 of n observable variables with respect to a given causal graph G with observable distribution . Let denote the interventional distribution over the observables with respect to an intervention of a designated variable X with x. Assuming that has bounded in-degree, bounded c-components (), and that the observational distribution is identifiable and satisfies certain strong positivity condition, we give an algorithm that takes samples from and time, and outputs with high probability a description of a distribution such that , and: 1. [Evaluation] the description can return in time the probability for any assignment to 2. [Generation] the description can return an iid sample from in time. We also show lower bounds for the sample complexity showing that our sample complexity has an optimal dependence on the parameters and , as well as if on the strong positivity parameter.