Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models
This work addresses a specific challenge in causal inference for scenarios with limited observational data, offering incremental improvements in computational efficiency for domain-specific applications.
The paper tackles the problem of computing tight probability bounds for partially identifiable queries in quasi-Markovian structural causal models, where exogenous variables are not fully specified, by developing a new algorithm that simplifies multilinear and linear programming constructions and shows superior performance in experiments.
We investigate partially identifiable queries in a class of causal models. We focus on acyclic Structural Causal Models that are quasi-Markovian (that is, each endogenous variable is connected with at most one exogenous confounder). We look into scenarios where endogenous variables are observed (and a distribution over them is known), while exogenous variables are not fully specified. This leads to a representation that is in essence a Bayesian network where the distribution of root variables is not uniquely determined. In such circumstances, it may not be possible to precisely compute a probability value of interest. We thus study the computation of tight probability bounds, a problem that has been solved by multilinear programming in general, and by linear programming when a single confounded component is intervened upon. We present a new algorithm to simplify the construction of such programs by exploiting input probabilities over endogenous variables. For scenarios with a single intervention, we apply column generation to compute a probability bound through a sequence of auxiliary linear integer programs, thus showing that a representation with polynomial cardinality for exogenous variables is possible. Experiments show column generation techniques to be superior to existing methods.