Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.03548 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915478056730624 |
|---|---|
| author | Arroyo, João P. Rodrigues, João G. Lawand, Daniel Mauá, Denis D. Lee, Junkyu Marinescu, Radu Gray, Alex Laurentino, Eduardo R. Cozman, Fabio G. |
| author_facet | Arroyo, João P. Rodrigues, João G. Lawand, Daniel Mauá, Denis D. Lee, Junkyu Marinescu, Radu Gray, Alex Laurentino, Eduardo R. Cozman, Fabio G. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03548 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models Arroyo, João P. Rodrigues, João G. Lawand, Daniel Mauá, Denis D. Lee, Junkyu Marinescu, Radu Gray, Alex Laurentino, Eduardo R. Cozman, Fabio G. Artificial Intelligence 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. |
| title | Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2509.03548 |