Tractable Bounding of Counterfactual Queries by Knowledge Compilation
This work provides a computational improvement for researchers and practitioners in causal inference, though it is incremental as it builds on existing methods for bounding queries.
The paper tackles the problem of efficiently bounding partially identifiable counterfactual queries in structural causal models by using symbolic knowledge compilation to create a reusable arithmetic circuit structure, achieving up to an order of magnitude speed-up compared to standard Bayesian network inference.
We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. Such a method requires multiple (Bayesian network) queries over models sharing the same structural equations and topology, but different exogenous probabilities. This setup makes a compilation of the underlying model to an arithmetic circuit advantageous, thus inducing a sizeable inferential speed-up. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values when computing the different queries. We also discuss parallelisation techniques to further speed up the bound computation. Experiments against standard Bayesian network inference show clear computational advantages with up to an order of magnitude of speed-up.