Causal computations in Semi Markovian Structural Causal Models using divide and conquer
Anna Rodum Bjøru, Rafael Cabañas, Helge Langseth, Antonio Salmerón · 2025
Read Causal computations in Semi Markovian Structural Causal Models using divide and conquer by Anna Rodum Bjøru, Rafael Cabañas, Helge Langseth, Antonio Salmerón (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13852.txt.
Introduction
Anna Rodum Bjøru, Rafael Cabañas, Helge Langseth, and Antonio Salmerón extend a recent method for bounding what-if probabilities in causal models. The earlier divide-and-conquer method split a big causal model into small pieces that could be solved exactly, then combined the bounds. It only handled Markovian models, where each outside factor touches just one variable.
Many real problems need semi-Markovian models, where one outside factor can sway several variables and create hidden confounding. The authors use a minimal example to show why the extension is hard, then propose several workable strategies. They judge those strategies both in theory and through a computing study, mapping where each one holds up.
Catalog record
| CREATOR | Anna Rodum Bjøru, Rafael Cabañas, Helge Langseth, Antonio Salmerón |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Causal computations in Semi Markovian Structural Causal Models using divide and conquer Anna Rodum Bjøru, Rafael Cabañas, Helge Langseth, Antonio Salmerón Abstract Recently, Bjøru et al. [ 3 , 4 ] proposed a novel divide-and-conquer algorithm for bounding counterfactual probabilities in structural causal models (SCMs). They assumed that the SCMs were learned from purely observational data, leading to an imprecise characterization of the marginal distributions of exogenous variables. Their method leveraged the canonical representation of structural equations to decompose a general SCM with high-cardinality exogenous variables into a set of sub-models with low-cardinality exogenous variables. These sub-models had precise marginals over the exogenous variables and therefore admitted efficient exact inference. The aggregated results were used to bound counterfactual probabilities in the original model. The approach was developed for Markovian models, where each exogenous variable affects only a single endogenous variable. In this paper, we investigate extending the methodology to semi-Markovian SCMs, where exogenous variables may influence multiple endogenous variables. Such models are capable of representing confounding relationships that Markovian models cannot. We illustrate the challenges of this extension using a minimal example, which motivates a set of alternative solution strategies. These strategies are evaluated both theoretically and through a computational study. 1 Introduction Structural causal models (SCMs) with discrete variables [ 2 , 11 ] are probabilistic graphical models (PGMs) designed for causal and counterfactual reasoning that enable reasoning about hypothetical scenarios. SCMs consist of endogenous (observable) and exogenous (usually latent) variables, with endogenous values determined from the exogenous ones through structural equations. Causal analysis is often described using Pearl’s ladder [ 12 ] . At the first rung are the observational queries (e.g., “What if I see this?”). Answering such queries based on passively observed data is the scope of standard statistical models, and the results are based on the calculation of conditional distributions. At the second rung we find interventional queries (e.g., “What if I do this?”). These are calculable by, for instance, causal Bayesian models [ 11 ] and are represented by conditional distributions after interventions based on so-called do-calculus [ 11 ] . Finally, the last rung holds counterfactual queries that address hypothetical scenarios (e.g., “What if we had done this instead of passively observing that?”). They are calculable by SCMs. However, when the SCM model is learned from data, the result of such queries are not necessarily precisely defined, and the answer to the query will then be given as an imprecise probability, and represented through a (non-degenerate) interval. Unfortunately, the computational complexity of calculating these intervals exactly is overwhelming even for medium-sized models, and this has motivated research into computationally efficient approaches. The Divide and Conquer for Causal Computation (DCCC) method [ 3 , 4 ] can bound non-identifiable queries by, for each exogenous variable, solving a linear programming problem that characterizes all exogenous distributions consistent with the available data. Its main advantage over other approaches is that DCCC reduces the computational complexity of the problem by removing certain exogenous states, thereby transforming the model into a collection of simpler SCMs, each of which admits a unique solution to the corresponding linear program. However, DCCC is designed for Markovian models, in which each exogenous variable is allowed to have only one endogenous child. In this work, we address the challenges of extending DCCC to semi-Markovian models, where exogenous variables are allowed to have more than one endogenous child. Our main contributions are as follows: • We show how DCCC can be extended in a specific semi-Markovian topology to obtain the exact solution. In addition, we analyse how ignoring the confounding relations and applying DCCC in its Markovian form can be used to approximate the solution. • We extend DCCC to accommodate multiple data sources (observational and experimental) and examine how the type of data influences the informativeness of the solution. The remainder of this paper is organized as follows. Section 2 introduces the fundamental definitions and notation related to SCMs. A summary of DCCC for Markovian models is provided in Section 3 . The main contributions are presented in the subsequent two sections: Section 4 describes the exact extension of DCCC to semi-Markovian models, incorporating both observational and experimental data; Section 5 presents approximate versions of DCCC obtained by omitting confounding relations. Section 6 reports the experimental evaluation, and Section 7 concludes the paper and gives directions for future research. 2 Background 2.1 Basic notation We use upper-case letters to denote random variables and lower-case for their possible values (or states), while \Omega_{V} denotes the state space of variable V . Similarly, \mathbf{V}=\{V_{1},V_{2},\ldots,V_{n}\} denotes a set of variables and \mathbf{v} a joint state of its domain \Omega_{\mathbf{V}}=\displaystyle\times_{V\in\mathbf{V}}\Omega_{V} . Variables are omitted from assignments when their context is clear, and we may for instance simply denote P(V=v) as P(v) . We will sometimes abuse notation by writing that, e.g., P(X|Y)=g_{1}(X,Y) as a shorthand to denote that the relationship P(X=x|Y=y)=g_{1}(x,y) holds for all x\in\Omega_{X} and y\in\Omega_{Y} . Similarly, we may also write P(X|\mathrm{do}(Y))=g_{2}(X,Y) to describe a general relationship between P(X=x|\mathrm{do}(Y=y)) and g_{2}(x,y) that will hold for all x\in\Omega_{X} and y\in\Omega_{Y} . Finally, \tilde{P} is used to denote empirical distributions. 2.2 Structural causal models Structural causal models (SCMs) [ 11 ] are a class of PGMs used for causal and counterfactual reasoning, consisting of two types of nodes: endogenous nodes, which represent the internal variables of the modelled problem, and exogenous nodes, which represent factors outside the model. Formally, an SCM \mathcal{M} is a 4-tuple \langle\mathbf{U},\mathbf{V},\mathcal{F},\mathcal{P}\rangle , where [ 2 ] • \mathbf{U} is a set of exogenous variables that are determined by factors outside the model, • \mathbf{V} is a set of variables \{V_{1},V_{2},\ldots,V_{n}\} , called endogenous, that are determined by other (exogenous and endogenous) variables in the model, i.e. by variables in \mathbf{U}\cup\mathbf{V} , • \mathcal{F} is a set of functions \{f_{V_{1}},f_{V_{2}},...,f_{V_{n}}\} called structural equations (SE), such that each of them is a function f_{V_{i}}:\Omega_{\mathrm{Pa}_{V_{i}}}\to\Omega_{V_{i}} , where \mathrm{Pa}_{V_{i}} are the variables directly determining V_{i} , including the exogenous parent U_{i}\subseteq\mathbf{U} , • \mathcal{P} is a set of probability distributions P(U) for each U\in\mathbf{U} . The structural equations \mathcal{F} define a directed acyclic graph (DAG) \mathcal{G} , referred to as the causal graph of the model, where the nodes correspond to the variables in \mathbf{U}\cup\mathbf{V} . The domains of both the endogenous and exogenous variables are assumed to be finite and discrete. A discrete exogenous variable, taking values on a finite set of unobserved states, is enough to represent all counterfactual distributions [ 17 ] . When the distributions for the exogenous variables are not known, we refer to the model as a partially specified SCM, denoted by a calligraphic letter, such as \mathcal{M} . In contrast, if all such distributions are provided, the model is considered fully specified and is denoted as, e.g., M . Figure 1 , shows an example of an SCM [ 10 ] . The causal graph on the left includes the endogenous variables \mathbf{V}=\{T,S\} , representing the treatment and survival , respectively. The goal is to analyze whether receiving treatment ( T=1 ) contributes to survival ( S=1 ). Meanwhile, \mathbf{U}=\{Q,R\} represents the set of exogenous variables, which are assumed to be root nodes, with endogenous variables as their children.