Скачать или смотреть Efficient Intervention Design for Learning Causal DAGs, by Karthikeyan Shanmugam

Abstract: Network of cause effect relationships between measured variables is modeled as a causal DAG (Directed Acyclic Graph). In this talk, we focus on efficient adaptive intervention design for learning a causal DAG, with no latent confounders, given the observational equivalence class it belongs to as an input. We first consider equivalence class inputs whose skeleton is a tree. We consider a Bayesian framework where a prior over all directed trees is updated based on the outcome of every single node intervention each of which is adaptively designed based on current posterior. We provide an efficient algorithm that requires interventions that is within a factor of 2 from the best adaptive algorithm. We also show that information greedy approaches are exponentially sub-optimal in terms of the optimal number of interventions required. The main technical tool is a simple greedy algorithm that myopically optimizes a centrality measure on the skeleton of the true causal tree.

We generalize and extend the above approach for adaptive interventional design to learn an arbitrary causal DAGs given its equivalence class. We show that the half the maximum clique size is an instance specific fundamental lower bound for any algorithm to even verify the DAG structure through interventions given the equivalence class. Under mild assumptions on the equivalence class, we provide an adaptive algorithm inspired by the algorithm on causal trees that requires interventions that matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques.