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

4142 软件学报 2025 年第 36 卷第 9 期

Nei 的条件独立性检验, 这是为了
为了区分这些可能存在的因果关系, 算法需要进一步执行给定邻接节点集
保证节点间存在直接因果关系, 即节点在图结构上是直接相连的. 例如, 在图 5(d) 中, 通过节点 V 4 阻断了节点
V 3 ,V 5 的连通路径, 从而排除了节点 V 3 ,V 5 存在直接因果关系, 并不考虑添加这条因果边, 即定义 4 中的第 2 个条
( )
( ˆ V i ⊥ ˆ V j |dSet V i ,V j ∪S ).
件
通过对所有非邻接节点执行增强的条件独立性检验, 可以有效地找回在当前结构中可能遗漏的因果边. 为了
进一步保证结构更新的准确性, 算法将每个新增了一条因果边的图结构作为一个候选结构, 并针对这些候选结构
进行下一步的最优选择和结构更新. 在处理线性数据时, 本研究采用多元线性回归来消除已知的外部噪声. 尽管本
文的数据生成过程遵循线性模型, 但对于非线性或其他类型的数据, 本文提出的算法框架同样适用, 可以根据数据
特性选择多项式回归、梯度提升回归树 (GBRT) 等方法.

3.2 最小结构依赖的结构更新
在结构更新阶段, 算法的核心任务是从邻域搜索阶段获得的多个候选结构中“选择”最优结构, 并实现结构更
新. 为了评估出最优结构, 算法首先利用定向规则确定候选结构中无向边的方向, 然后通过定义的图结构依赖得分
和最小结构依赖逼近准则实现对于最优结构的选择.
算法首先应用 V 结构 [9] 和 Meek 规则 [21] 明确图中某些无向边的方向, 从而得到可以唯一表示当前候选邻域结
构的 CPDAG 图, 其中 V 结构的具体定义如定义 5 所示.
定义 5. V 结构 [9] . 在因果图 G 中, 若两个节点 V i ,V j 不直接相连, 但拥有一个共同邻居 , 并且满足 V i ⊥
V k
( ) ( )
V j |dSet V i ,V j 和 V i /⊥V j |(dSet V i ,V j ∪V k ), 则 V i ,V j 和 V k 构成 V 结构, 记作 V i → V k ← V j .
根据定义 4 可知邻域搜索阶段找回的因果边需要尽可能剔除已知先验父节点的噪声, 所以其对应的两端节点
中至少有一端具有已知的先验父节点, 因此该因果边可以通过 V 结构定义确定方向, 进而利用 Meek 规则 [21] 可以
进一步定向结构中的剩余无向边, 并获得可以唯一表示该领域结构的 CPDAG 图. 下面为了从多个候选结果中选
出最优结构, 定义了图结构依赖得分作为评价指标, 定义如定义 6.
定义 6. 图结构依赖得分. 对数据集 D 和算法获得的当前结构 G , G pd 的图结构依赖得分表示为对所有节点
pd
( pd ) ( )
V i ∈ V , 与其非邻接节点 V j ∈ Ad j G ,V i , 在给定对应的分离集 dSet V i ,V j 下的依赖得分之和, 公式为:

∑ n ( ( )) ( )
pd
MI G pd = MI i D,V i ,V j |dSet V i ,V j ,V j ∈ Ad j G ,V i (4)
i
基于图结构依赖得分的定义, 本节中通过最小结构依赖逼近准则 (命题 1) 检验在每次迭代过程中的候选邻域
结构是否存在更接近于真实的潜在因果结构, 并将最优的候选领域用于当前结构的下一步更新.
命题 1. 最小结构依赖逼近准则. 对于样本量大小为 m 的因果结构图 G 及其观测数据 D, 令 G pd 为图 G 删除部
T
T
分因果边所得到的部分因果结构图, G ′pd 表示在 G pd 上添加了 V i → V j 的有向边而构成的新的因果结构图, 其中
V tail = V j , 表示该边的尾节点. 如果 V i → V j 在图 G T 中存在, 且 m → ∞, 则有以下结论成立.
)
(1) 对图 G pd 上 V X ,V Y 之间的连通路径 P, 其中 ( V i → V j ∈ P, 则 V X ,V Y 在数据样本上 (条件) 相关性下降:

( ) ( )
MI ′ pd D,V X ,V Y |dSet(V X ,V Y )∪V tail ⩽ MI pd D,V X ,V Y |dSet(V X ,V Y ) (5)
G i G i
T
pd
(2) 相比图 G , G ′pd 的图结构依赖得分更趋近于真实结构 G 的图结构依赖得分:

(6)
MI G ′pd ⩽ MI G pd
T T V X ,V Y 的所有连通路
证明: 令 G 表示真实的因果结构图, 当样本量 m → ∞, 对于 G 上任意一对非邻接变量
P 的 dSet(V X ,V Y ), 那么这对变量之间的依赖将趋于 0:
径 P, 给定可以阻断 d-分离变量结合

( )
MI D,V X ,V Y |dSet(V X ,V Y ) → 0.
T
因此, 在 G 上, 所有非邻接变量对的依赖之和也趋于最小, 表示为:

∑ n ( )
lim m→∞ MI G T = MI i D,V X ,V Y |dSet(V X ,V Y ) → 0.
i
′
现考虑一种错误的情况, 在当前结构图 G 上错误地添加了一条有向边的 V i → V j ,V tail = V j , 形成新的候选图 G .
T G 上通过这条新增边连通的非邻
′
在 G 中实际不存在通过 V i → V j 的连通路径 P 连接变量 V X ,V Y . 因此, 在候选图