The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of
reasoning: observational, interventional, and counterfactual, that reflect the
progressive sophistication of human thought regarding causation. We investigate
the computational complexity aspects of reasoning in this framework focusing
mainly on satisfiability problems expressed in probabilistic and causal
languages across the PCH. That is, given a system of formulas in the standard
probabilistic and causal languages, does there exist a model satisfying the
formulas? The resulting complexity changes depending on the level of the
hierarchy as well as the operators allowed in the formulas (addition,
multiplication, or marginalization).
We focus on formulas involving marginalization that are widely used in
probabilistic and causal inference, but whose complexity issues are still
little explored. Our main contribution are the exact computational complexity
results showing that linear languages (allowing addition and marginalization)
yield NP^PP-, PSPACE-, and NEXP-complete satisfiability problems, depending on
the level of the PCH. Moreover, we prove that the problem for the full language
(allowing additionally multiplication) is complete for the class succ$\exists$R
for languages on the highest, counterfactual level. Previous work has shown
that the satisfiability problem is complete for succ$\exists$R on the lower
levels leaving the counterfactual case open. Finally, we consider constrained
models that are restricted to a small polynomial size. The constraint on the
size reduces the complexity of the interventional and counterfactual languages
to NEXP-complete.

研究了 Pearl 的因果层次结构 (PCH) 框架中的推理和计算复杂性，重点关注概率和因果语言中表达的满足性问题，特别是与边缘化相关的方程，证明了不同层次和操作符的确切计算复杂性结果，以及对受限模型进行了考虑。

概率和因果可满足性：边缘化的影响

Probabilistic and Causal Satisfiability: the Impact of Marginalization

The abilities of humans to understand the world in terms of cause and effect
relationships, as well as to compress information into abstract concepts, are
two hallmark features of human intelligence. These two topics have been studied
in tandem in the literature under the rubric of causal abstractions theory. In
practice, it remains an open problem how to best leverage abstraction theory in
real-world causal inference tasks, where the true mechanisms are unknown and
only limited data is available. In this paper, we develop a new family of
causal abstractions by clustering variables and their domains. This approach
refines and generalizes previous notions of abstractions to better accommodate
individual causal distributions that are spawned by Pearl's causal hierarchy.
We show that such abstractions are learnable in practical settings through
Neural Causal Models (Xia et al., 2021), enabling the use of the deep learning
toolkit to solve various challenging causal inference tasks -- identification,
estimation, sampling -- at different levels of granularity. Finally, we
integrate these results with representation learning to create more flexible
abstractions, moving these results closer to practical applications. Our
experiments support the theory and illustrate how to scale causal inferences to
high-dimensional settings involving image data.

通过聚类变量及其域的方法，发展了一种新的因果抽象方法，以更好地适应由 Pearl 的因果层次结构引发的个体因果分布，并进一步将这些结果与表示学习相结合，将这些结果更接近实际应用。

神经因果抽象

Neural Causal Abstractions

Reasoning about the effect of interventions and counterfactuals is a
fundamental task found throughout the data sciences. A collection of
principles, algorithms, and tools has been developed for performing such tasks
in the last decades (Pearl, 2000). One of the pervasive requirements found
throughout this literature is the articulation of assumptions, which commonly
appear in the form of causal diagrams. Despite the power of this approach,
there are significant settings where the knowledge necessary to specify a
causal diagram over all variables is not available, particularly in complex,
high-dimensional domains. In this paper, we introduce a new graphical modeling
tool called cluster DAGs (for short, C-DAGs) that allows for the partial
specification of relationships among variables based on limited prior
knowledge, alleviating the stringent requirement of specifying a full causal
diagram. A C-DAG specifies relationships between clusters of variables, while
the relationships between the variables within a cluster are left unspecified,
and can be seen as a graphical representation of an equivalence class of causal
diagrams that share the relationships among the clusters. We develop the
foundations and machinery for valid inferences over C-DAGs about the clusters
of variables at each layer of Pearl's Causal Hierarchy (Pearl and Mackenzie
2018; Bareinboim et al. 2020) - L1 (probabilistic), L2 (interventional), and L3
(counterfactual). In particular, we prove the soundness and completeness of
d-separation for probabilistic inference in C-DAGs. Further, we demonstrate the
validity of Pearl's do-calculus rules over C-DAGs and show that the standard ID
identification algorithm is sound and complete to systematically compute causal
effects from observational data given a C-DAG. Finally, we show that C-DAGs are
valid for performing counterfactual inferences about clusters of variables.

该研究介绍了一种叫做 “集群有向无环图（Cluster DAGs）” 的新型图形建模工具，其可以基于有限的先验知识提供变量之间关系的部分规范，从而缓解了在复杂、高维度领域中指定完全因果图的严格要求。在该图形模型下，本研究还开发了基于 “Pearl's Causal Hierarchy” 的各层级的变量集聚进行推理的方法，并验证了 C-DAGs 的有效性。