用于部分因果效应识别的最优实验

# 用于部分因果效应识别的最优实验

来源: https://arxiv.org/html/2605.06993  
Tobias Maringgele  
慕尼黑工业大学  
[email protected]  

&Jalal Etesami  
慕尼黑工业大学  
[email protected]  

###### 摘要

因果查询通常无法仅从观测数据中完全识别，而能够收紧由此产生的界限的实验通常代价高昂。我们研究了在观察到实验结果之前，选择一个受成本约束的实验子集以最大程度地收紧目标查询界限的问题。我们将此形式化为*最大效力问题（max-potency problem）*，其中认知效力（epistemic potency）衡量实验保证的界限宽度在最坏情况下的减少量，并通过从 0-1 背包问题的归约证明该问题是 NP 难的。基于 Duarte 等人（2023）的多项式规划框架，我们给出了在离散设置下评估认知效力的一般程序。为了控制超指数级的搜索空间，我们引入了两个仅依赖于因果图和查询的图形剪枝标准：一种利用区域结构以线性时间认证零效力的新颖路径拦截规则，以及基于 ID 算法的可识别性检查。在 Erdős–Rényi 随机图和 11 个 *bnlearn* 基准网络上，这两种标准平均剪掉了 50–88% 的候选实验，且无需求解任何多项式程序。对于一般的子集搜索，我们表明经 ID 剪枝的实验是组合惰性的（combinatorially inert），从而将需要评估的子集数量减少了超指数级。最后，我们在观测 NHANES 数据上进行了端到端的演示，选择了用于估计体育活动对糖尿病影响的最优实验。

## 1 引言

因果推断的一个核心目标是估计处理对结果的影响。平均处理效应（ATE）等人群级摘要捕捉了总体行为，但许多决策取决于更细粒度的反事实量——例如，处理既是产生结果的必要原因又是充分原因的概率（$P_{NS}$）（Pearl, 1999; Mueller and Pearl, 2022）。此类查询很少能仅从观测数据中进行点识别；人们能做的最好是推导*界限*（Balke and Pearl, 1997; Tian and Pearl, 2000），而这些界限通常过宽，无法为决策提供相关依据。收紧这些界限需要额外的数据，而额外数据意味着实验，实验成本高昂且受预算限制。这引出了本文的中心问题：**给定因果图、观测分布和预算，事前选择的哪个实验子集能最大程度地收紧目标查询的界限？**

很好地回答这一问题意味着在运行实验之前推理实验的信息量，这与适应实际结果的顺序设计不同（Ailer 等人，2024），并且要在随变量数量呈超指数增长的搜索空间中进行。我们的贡献如下：

-   我们将此形式化为*最大效力问题*，其中认知效力衡量实验保证的界限宽度在最坏情况下的减少量，并通过从 0-1 背包问题的归约证明它是 NP 难的（第 4 节）。
-   我们给出了在离散设置下评估认知效力的一般程序，建立在 Duarte 等人（2023）的多项式规划框架之上（第 5 节）。
-   我们引入了两个仅依赖于因果图和查询的图形剪枝标准，以在不求解任何多项式程序的情况下认证候选实验的零效力：一种利用图形的区域结构以线性时间运行的新颖路径拦截规则，以及基于 ID 算法的可识别性检查（Shpitser and Pearl, 2006）。我们还表明，经 ID 剪枝的实验是*组合惰性*的：它们可以完全从子集搜索中移除（第 6 节）。
-   在 Erdős–Rényi 随机图和 11 个 *bnlearn* 基准网络上，当选择单个最优实验时，这两种标准平均剪掉了 50–88% 的候选实验。对于一般的子集搜索，仅 ID 惰性就将搜索空间指数平均降低了约 60%——这需要评估的子集数量呈超指数级减少。我们在观测 NHANES 数据上展示了完整的端到端流水线（第 7 节）。

### 1.1 相关工作

我们的工作连接了因果推断中两个 largely 独立的领域：因果*识别*，即询问查询是否可以从可用数据中唯一计算；以及*部分识别*，即询问当唯一计算不可能时，查询可以被约束得多紧。最优实验设计已针对前者进行了广泛研究；我们针对后者进行研究。

**因果识别。** Shpitser 和 Pearl（2006）提出了一种健全且完整的算法（*ID 算法*），用于确定变量子集 $X$ 对目标子集 $Y$ 的因果效应，记为 $P(y \mid do(x))$，是否仅从观测数据中可识别，当且仅当不存在称为*阻碍（hedge）*的特定图形结构时成立。Bareinboim 和 Pearl（2012）将其扩展到也具有特定形式的实验数据的设置，引入了*z-可识别性*：如果查询 $P(y \mid do(x))$ 可以从观测分布 $P(V)$ 以及通过对指定变量子集 $Z$ 进行干预获得的分布中唯一计算，则该查询是*z-可识别*的。直观地说，对 $Z$ 的干预可以打破仅从观测中防止识别的某些混淆结构。Lee 等人（2019）进一步将其扩展到*一般可识别性*（g-可识别性），其中可用数据是形式为 $\{P(V \setminus Z_i \mid do(Z_i))\}_{i=0}^m$ 的任意干预分布集合，而不是单个族。Kivva 等人（2022）为 g-可识别性提供了一种健全且完整的算法，将其简化为一系列经典 ID 子问题。

**实验设计。** Akbari 等人（2025）为*完全*识别制定了最小成本干预设计（MCID）问题，证明它是 NP 难的，并提出了一种基于最小击中集（minimum hitting sets）的算法。Elahi 等人（2024）将 MCID 重构为加权部分 MAX-SAT 和整数线性规划实例，在实践中实现了数量级的加速。两者都关注点识别。更接近我们 regime 的是，Ailer 等人（2024）在非线性、混淆的工具变量（IV）设置中顺序设计间接实验以缩小界限间隙；而我们研究离散图中的事前子集选择，具有零效力的图形证书。

**部分识别和因果界限。** Balke 和 Pearl（1997）使用响应类型变量上的线性规划推导二元因果效应的尖锐（即最紧可能）界限；他们的方法仅限于具有特定图形结构的离散，特别是二元设置。Tian 和 Pearl（2000）为单个二元处理和结果的因果概率（$P_{NS}, P_N, P_S$）提供了闭式界限，也要求离散变量。Zhang 等人（2022）通过规范结构因果模型（SCMs）从观测和干预分布的任意组合约束反事实查询。Duarte 等人（2023）通过多项式规划将其进一步推广到离散设置中的任意因果和反事实查询。Sachs 等人（2023）刻画了这些多项式程序简化为线性程序的条件。Shridharan 和 Iyengar（2023b）用响应类型扩展了这一类以剪枝基础 LP。Shridharan 和 Iyengar（2023a）进一步表明，在准马尔可夫图（quasi-Markovian graphs）（Zaffalon 等人，2020）上，多项式次数减少到*被干预*的 c-组件的数量，从而在最多干预两个 c-组件时产生 LP 或 QP 公式。与我们的类似，后者利用了 c-因子分解（Tian and Pearl, 2002），但在受限图类上减少内部程序的结构复杂性；我们相反使用 c-因子结构（第 6.1 节）在一般 ADMG 上事前认证实验无信息。在相关方向上，Li 等人（2026）刻画了二元因果概率的尖锐界限宽度至多为 $2\epsilon$ 的条件。

## 2 初步知识

**符号。** 随机变量用大写字母表示，其值用小写字母表示；粗体表示集合。对于随机变量 $X$，我们写 $\text{supp}(X)$ 以指代其支撑集。当 $X$ 是二元变量，即 $|\text{supp}(X)|=2$ 时，我们对 $X=1$（或 true）使用 $x$，对 $X=0$（或 false）使用 $x'$。

**结构因果模型（SCM）。** SCM 是一个元组 $\mathcal{M}=(\boldsymbol{V}, \boldsymbol{U}, \boldsymbol{F}, P(\boldsymbol{U}))$，包含观测（内生）变量 $\boldsymbol{V}$、潜在（外生）变量 $\boldsymbol{U}$、结构方程 $\boldsymbol{F}=\{f_V\}_{V \in \boldsymbol{V}}$，其中每个 $f_V$ 将 $V$ 的值确定为其（潜在和观测）父母值的函数。

**无环有向混合图（ADMG）。** SCM 的因果结构由观测变量上的 ADMG $\mathcal{G}=(\boldsymbol{V}, E^d, E^b)$ 总结，其中有向边 $V_i \to V_j \in E^d$ 表示 $V_j$ 结构上依赖于 $V_i$，双向边 $V_i \leftrightarrow V_j \in E^b$ 表示 $V_i$ 和 $V_j$ 的隐藏共同原因。有向部分是无环的。对于节点 $V \in \boldsymbol{V}$，$\boldsymbol{pa}(V)$、$\boldsymbol{ch}(V)$ 和 $\boldsymbol{anc}(V)$ 分别表示其父母、孩子和祖先；这些自然地扩展到集合。在本文的图中，隐藏共同原因显示为带有指向其孩子的有向边的虚线节点；这等价于 ADMG 表示中的双向边。

对 $X \subseteq \boldsymbol{V}$ 的*干预*，记为 $do(X=x)$，用常数值 $x \in \text{supp}(X)$ 替换 $\boldsymbol{G}$ 中 $X \in \boldsymbol{X}$ 的每个结构方程 $f_X$，移除指向 $X$ 的所有传入边。$Y \subseteq \boldsymbol{V} \setminus \boldsymbol{X}$ 上由此产生的*干预后分布*，$P(Y_x) = P(Y \mid do(X=x))$，当存在隐藏混淆器时，可能与观测条件 $P(Y \mid X=x)$ 不同。我们写 $P(Y \| do(X))$ 以表示由 $x \in \text{supp}(X)$ 索引的干预后分布族。

*反事实*是一个涉及矛盾干预的陈述。例如，在二元情况下，反事实概率可以采取 $P(y_x, y'_{x'})$ 的形式用于变量 $X, Y$。在本文中，我们将仅考虑上述这样的合取语句形式的反事实，其中每个合取项都是一个反事实*世界*。我们用 $\mathfrak{C}$ 表示给定语句中出现的所有反事实世界的集合。在上面的例子中，$|\mathfrak{C}|=2$，对于每个世界 $c \in \mathfrak{C}$，有对 $X^{(c)}$ 的干预和对 $Y^{(c)}$ 的结果。

**离散变量和响应类型变量。** 我们假设 $\boldsymbol{V}$ 中的所有变量都是具有已知有限支撑集的离散变量。由于每个结构方程 $f_V$ 将有限数量的父母配置映射到有限输出，它只能编码有限数量的不同输入-输出行为。对于每个潜在扰动 $U_k$，这些行为通过离散*响应类型* $R_k$ 在 $U_k$ 的孩子中进行索引。集合 $\boldsymbol{R}=\{R_k\}_{U_k \in \boldsymbol{U}}$ 是有限的，固定的 $r \in \text{supp}(\boldsymbol{R})$ 完全确定模型（包括所有反事实）。用 $\boldsymbol{R}$ 替换潜在变量 $\boldsymbol{U}$ 产生一个等效模型，不失一般性（Duarte 等人，2023，命题 1）。给定 $(\mathcal{G}, P(\boldsymbol{V}), \text{supp}(\boldsymbol{V}))$ 和目标查询，Duarte 等人（2023）的多项式规划框架在 $\boldsymbol{R}$ 上构建一个程序，其最优解是查询的尖锐界限。形式化构建见附录 A。

## 3 因果界限和认知效力

**设置。** 我们给定观测变量 $\boldsymbol{V}$（均为离散）上的 ADMG $\mathcal{G}$，分布为 $P(\boldsymbol{V})$ 以及因果查询 $\theta$，其可能对应于干预后、反事实或其功能。注意，使用 Duarte 等人（2023）的框架，尖锐观测界限 $L_\theta \leq \theta \leq U_\theta$ 是通过在 $\boldsymbol{R}$ 上优化多项式程序获得的。

我们定义 $\mathcal{A}:=\{ (y_x), (y_x, y'_{x'}), \dots \}$ 作为*候选实验*集合，即响应类型变量 $\boldsymbol{R}$ 的任意多项式函数。我们广泛使用该术语：$\mathcal{A}$ 可能包含物理上可实现的实验，如随机对照试验和干预（Raghavan and Bareinboim, 2025），以及应用领域中可辩护的结构假设，如单调性。多项式程序将两者统一视为对 $\boldsymbol{R}$ 的约束。对于任何 $\mathcal{a} \subseteq \mathcal{A}$ 且结果为 $p_{\mathcal{a}}$，添加约束...