Exact Bayesian structure learning from uncertain interventions

Abstract

We show how to extend the dynamic programming algorithm of Koivisto [KS04, Koi06], which computes the exact posterior marginal edge probabilities p(Gij = 1|D) of a DAG G given data D, to the case where the data is obtained by interventions (experiments). In particular, we consider the case where the targets of the interventions are a priori unknown. We show that it is possible to learn the targets of intervention at the same time as learning the causal structure. We apply our exact technique to a biological data set that had previously been analyzed using MCMC [SPP + 05, EW06]. 1