Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Robust Multilinear Model Learning Framework for 3D Faces
Multilinear models are widely used to represent the statistical variations of 3D human faces as they decouple shape changes due to identity and expression. Existing methods to learn a multilinear face model degrade if no…
3D Face ModellingFace ModelSemantic correspondenceApproximate Causal Effect Identification under Weak Confounding
Causal effect estimation has been studied by many researchers when only observational data is available. Sound and complete algorithms have been developed for pointwise estimation of identifiable causal queries. For non-…
Multilinear Hyperplane Hashing
Hashing has become an increasingly popular technique for fast nearest neighbor search in large databases. Despite its successful progress in classic point-to-point search, there are few studies regarding point-to-hyperpl…
Active LearningQuantizationSensitivitySource Identification for Mixtures of Product Distributions
We give an algorithm for source identification of a mixture of $k$ product distributions on $n$ bits. This is a fundamental problem in machine learning with many applications. Our algorithm identifies the source paramete…
TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions
Shapley values are a widely used tool for attributing importance and interactions among input variables in black-box models, but their computation involves a function defined over an exponentially large space of subsets.…