Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models

• URL: http://arxiv.org/abs/2509.03548v1
• Date: Tue, 02 Sep 2025 17:51:34 GMT
• Title: Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models
• Authors: João P. Arroyo, João G. Rodrigues, Daniel Lawand, Denis D. Mauá, Junkyu Lee, Radu Marinescu, Alex Gray, Eduardo R. Laurentino, Fabio G. Cozman,
• Abstract summary: We investigate partially identifiable queries in a class of causal models.<n>We focus on acyclic Structural Causal Models that are quasi-Markovian.<n>We look into scenarios where endogenous variables are observed, and a distribution over them is known.<n>In such circumstances, it may not be possible to precisely compute a probability value of interest.
• Score: 4.091309278105097
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Causal computations in Semi Markovian Structural Causal Models using divide and conquer [0.20999222360659608]
  Bjru et al. proposed a novel divide-and-conquer algorithm for bounding counterfactual probabilities in structural causal models.<n>In this paper, we investigate extending the methodology to textitsemi-Markovian SCMs.<n>Such models are capable of representing confounding relationships that Markovian models cannot.
  arXiv  Detail & Related papers  (2025-11-17T19:08:53Z)
• Identification of Causal Direction under an Arbitrary Number of Latent Confounders [54.76982125821112]
  In real-world scenarios, observed variables may be affected by multiple latent variables simultaneously.<n>We make use of the joint higher-order cumulant matrix of the observed variables constructed in a specific way.<n>We show that, surprisingly, causal asymmetry between two observed variables can be directly seen from the rank deficiency properties of such higher-order cumulant matrices.
  arXiv  Detail & Related papers  (2025-10-26T15:10:00Z)
• Sample, estimate, aggregate: A recipe for causal discovery foundation models [28.116832159265964]
  Causal discovery has the potential to uncover mechanistic insights from biological experiments.<n>We propose a supervised model trained on large-scale, synthetic data to predict causal graphs.<n>Our approach is enabled by the observation that typical errors in the outputs of a discovery algorithm remain comparable across datasets.
  arXiv  Detail & Related papers  (2024-02-02T21:57:58Z)
• A Heavy-Tailed Algebra for Probabilistic Programming [53.32246823168763]
  We propose a systematic approach for analyzing the tails of random variables. We show how this approach can be used during the static analysis (before drawing samples) pass of a probabilistic programming language compiler. Our empirical results confirm that inference algorithms that leverage our heavy-tailed algebra attain superior performance across a number of density modeling and variational inference tasks.
  arXiv  Detail & Related papers  (2023-06-15T16:37:36Z)
• Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach [7.059472280274009]
  We present an exact Bayesian inference method for discrete statistical models. We use a probabilistic programming language that supports discrete and continuous sampling, discrete observations, affine functions, (stochastic) branching, and conditioning on discrete events. Our inference method is provably correct and fully automated.
  arXiv  Detail & Related papers  (2023-05-26T16:09:59Z)
• Score-based Causal Representation Learning with Interventions [54.735484409244386]
  This paper studies the causal representation learning problem when latent causal variables are observed indirectly. The objectives are: (i) recovering the unknown linear transformation (up to scaling) and (ii) determining the directed acyclic graph (DAG) underlying the latent variables.
  arXiv  Detail & Related papers  (2023-01-19T18:39:48Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Causality-Based Multivariate Time Series Anomaly Detection [63.799474860969156]
  We formulate the anomaly detection problem from a causal perspective and view anomalies as instances that do not follow the regular causal mechanism to generate the multivariate data. We then propose a causality-based anomaly detection approach, which first learns the causal structure from data and then infers whether an instance is an anomaly relative to the local causal mechanism. We evaluate our approach with both simulated and public datasets as well as a case study on real-world AIOps applications.
  arXiv  Detail & Related papers  (2022-06-30T06:00:13Z)
• Probabilistic Kolmogorov-Arnold Network [1.4732811715354455]
  The present paper proposes a method for estimating probability distributions of the outputs in the case of aleatoric uncertainty. The suggested approach covers input-dependent probability distributions of the outputs, as well as the variation of the distribution type with the inputs. Although the method is applicable to any regression model, the present paper combines it with KANs, since the specific structure of KANs leads to computationally-efficient models' construction.
  arXiv  Detail & Related papers  (2021-04-04T23:49:15Z)
• Flexible mean field variational inference using mixtures of non-overlapping exponential families [6.599344783327053]
  I show that using standard mean field variational inference can fail to produce sensible results for models with sparsity-inducing priors. I show that any mixture of a diffuse exponential family and a point mass at zero to model sparsity forms an exponential family.
  arXiv  Detail & Related papers  (2020-10-14T01:46:56Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)
• Bayesian Sparse Factor Analysis with Kernelized Observations [67.60224656603823]
  Multi-view problems can be faced with latent variable models. High-dimensionality and non-linear issues are traditionally handled by kernel methods. We propose merging both approaches into single model.
  arXiv  Detail & Related papers  (2020-06-01T14:25:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.