Page 228 - 《软件学报》2025年第9期

郝志峰 等: 基于增强条件独立性检验的鲁棒因果发现算法 4139

例 1 说明在执行 CIT 检验时, 真实因果结构中的高方差父节点会影响子节点与其方差较小的父节点的 CIT
结果, 错误地判定它们相互独立. 下面进一步讨论基于“条件独立性冲突”“对称性校验”等方法在解决因果结构中
存在高方差节点的场景下所面临的局限性. 如图 2 所示, 真实结构 (图 1(c) 产生过程) 通过 Fisher_Z 检验得到
V 1 ,V 2 的相关关系结果为 0.021, p 值为 0.68. 基于高阶 CIT 的方法通常限制条件集 Z=1, 但由于变量在给定空集下
判断为独立, 算法便停止了下一步计算, 如图 2(b) 所示. 基于对称性校验的方法通过 CIT 获得每个变量的局部结
构, 但由于 CIT 错误判断 V 1 ,V 2 相互独立, 所以得到的局部结构关系对称, 因此 V 1 ,V 2 的因果边不会被对称校验的
方法进一步检验而找回, 如图 2(c) 所示. 基于条件独立性冲突的方法对当前结构执行所有可能的 CIT, 因此得到
V 1 /⊥V 2 |V 3 两种独立性冲突的结果, 进而通过一些逻辑规则或二次加权计算选择更可信的 CIT 结果. 但这
V i ⊥V j 和
些复杂的运算和设计难以保证正确的 CIT 结果被选中的可能性, 如图 2(d). 其中在真实结构的因果连通路径中 V 3
V 1 ,V 2 的连通节点, 引入它进入约束集实际上不符合 d-分离的定义. 并且这类方法由于涉及复杂的逻辑推
并不是
理判断, 节点数量常限制在 10 个以内, 算法十分复杂, 难以复现并投入实际应用.

真实结构 高阶 CIT 对称校验 条件独立性冲突
Var=50 :{ϕ} :{V 2 }
V 1 MB V 2 MB V 1 ⊥V 2 V 1 ⊥V 2 |V 3
V 3
条件集限制: Z=1 结构对称性 逻辑规则/二次加权计算
Var=1
V 1 ⊥V 2 |{ϕ}
V 1 V 2 V 1 ⊥V 2
V 1 ⊥V 2 |V 3
(a) (b) (c) (d)
图 2 基本方法的局限性

目前的方法无法有效找回被错误删除的因果连接边. 随着网络结构中节点数量增加, 高方差节点对于 CIT 结
果准确性的影响逐渐加剧, 这对于准确识别和学习变量间的因果关系带来了困难.
因此, 本文所研究的问题为: 如何在有限样本和真实因果结构存在高方差节点的条件下, 提高 CIT 的准确率,
减少因果图中遗漏的关键因果关系, 更准确地揭示观测数据中潜在的真实因果结构.

3 最大最小依赖的因果结构学习算法

本节针对有限样本和真实因果结构存在高方差节点的条件下, CIT 结果不准确导致因果边误删的问题, 提出
了一种基于“增强条件独立性检验”的约束类方法. 该方法的基本思想是利用一次检验得到的部分先验结构信息,
通过线性回归消除潜在的部分高方差父节点影响后, 再次对节点间的因果关系进行检验来增强 CIT 结果的可靠
性 (第 3.1 节). 并将这一思想融入启发式搜索框架, 通过优化图结构依赖得分 (第 3.2 节), 进一步设计了最大最小
依赖的因果结构学习算法 (max-min dependency causal learning, MMDCL). 下面给出算法框架概述, 随后在第 3.1
节和第 3.2 节中对算法的实现细节进行研究和提供必要的理论保证.
MMDCL 算法由“领域搜索”和“结构更新”两个阶段组成, 如图 3 所示. 在领域搜索阶段, 算法的目标是从当前
结构出发探索可能的候选邻域, 利用增强的条件独立性检验“找回”可能被误删的因果边. 在结构更新阶段, 算法的
目标是从上一阶段获得的候选结构中“选择”最接近潜在真实因果结构的候选结构, 并完成结构更新.
pd
算法 1 展示了 MMDCL 的伪代码, 该算法首先将 PC 算法输出的结构作为初始起点, 即 G , 并获得初始化的
非邻接节点集和分离集, 随后进入迭代过程 (第 1–5 行). 在每轮迭代中, 算法首先确定所有非邻接变量间可以添加
的因果边作为潜在搜索空间 (第 7 行). 对这些潜在因果边进行环路检测, 确保新加入的因果边不会形成环路, 并对
通过二次的增强 CIT 判断这些因果边是否应被加入结构中 (第 8 行). 算法接着评估候选结构的结构依赖, 寻找具
有最小结构依赖的候选结构 (第 9–14 行), 以此更新当前最优结构 (第 19 行). 迭代持续进行, 直到没有新的因果边
可以被添加或当前结构不再更新, 此时迭代停止 (第 21 行). 其中, 对于判断环路的部分, 为了尽可能避免出现环
路, 算法将 CPDAG 上的无向边视为双向连通的. 接下来本文将在第 3.1 节和第 3.2 节中详细介绍邻域搜索和结构
更新的完整过程.