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

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

G 而
接变量 V X ,V Y , 这条路径 (V i → V j ) < P; 因为新增的路径不是真实路径的一部分, 所以 V X ,V Y 的依赖相对于图
言不会降低.

( ) ( )
D,V X ,V Y |dSet(V X ,V Y ) .
MI G ′ D,V X ,V Y |dSet(V X ,V Y )∪V tail > MI G i
i
T
′ G 中存在通
反之, 在当前结构图 G 上正确的添加了一条有向边 V i → V j ,V tail = V j , 形成新的候选图 G , 并且在
′ V i → V j ∈ P; 如
过 V i → V j 的连通路径 P 连接变量 V X ,V Y , 则在候选图 G 上非邻接变量对 V X ,V Y 经过 V i → V j 连通,
P
果通过 V i → V j 连通的路径 P 不被当前分离集 dSet(V X ,V Y ) 阻断, 那么添加 V j 到分离集中可以阻断路径 , 即
G
′
dSet(V X ,V Y )∪V tail 能有效地反映变量间的独立性, 使得 G 更接近潜在真实因果结构 , 因此:

( ) ( )
D,V X ,V Y |dSet(V X ,V Y ) .
′ D,V X ,V Y |dSet(V X ,V Y )∪V tail < MI G i
MI G i
G 上将得到更小的依赖之和, 更接
′
并且随着分离集的准确搜索, 节点之间的依赖将不断减小. 相对于图 G, 图
T
近潜在的真实结构 G . 使得:

lim m→∞ MI G ′ < lim m→∞ MI G .
′ T
在当前结构图 G 上正确的添加了一条有向边 V i → V j , 形成新的候选图 G , 当在 G 中存在 V i → V j 的有向边,
V X ,V Y , 则该边缘将不属于任何的非邻接变量对的连通路径 P, 图结
但不存在通过 V i → V j 的连通路径 P 连接变量
构的非邻接结合的图结构依赖得分将保持不变:

lim m→∞ MI G ′ = lim m→∞ MI G .
′ G 将更逼近潜在真实结构:
从而得到最终公式, 即添加正确边缘的候选图 G 相对于图

lim m→∞ MI G ′ ⩽ lim m→∞ MI G .
综上, 命题 1 得证.
在命题 1 的理论保证下, 算法基于最小结构依赖逼近准则可以学习到渐进正确的因果结构. 具体来说, 对候选
结构的依赖得分计算方法如算法 2 所示.
算法 2. 计算候选图结构依赖得分.
′pd ( ) { ( pd ) }
输入: 数据 D, 图 G , 节点对 V i ,V j , Ad j G ,V X ,V X ∈ V ,dSet 分离集;
′ pd
输出: 图 G 的MI, 更新分离集 dSet.
1. 初始化 MI = 0
)
2. 确定 G ′pd 中 ( V i ,V j 的方向, 将尾节点保存为 V tail
3. For V X ∈ V
(
4. For V Y ∈ Ad j G ,V X )
pd
( )
5. IF (V X ,V Y ) 通过 V i ,V j 连通
6. dSet(V X ,V Y ) = dSet(V X ,V Y )∪V tail
7. End if
8. End for
9. End for
∑ n ( ( )) ( )
pd
10. 计算图结构依赖得分 MI G ′pd = MI i D,V i ,V j |dSet V i ,V j ,V j ∈ Ad j G ,V i
i
,
MI G ′ pd dSet
11. Return
)
算法 2 中描述了图结构更新的计算规则. 算法首先确定 G 更新 ( V i ,V j 边的方向, 并保存尾节点为 V tail (当
′
)
V i → V j V tail = )(第 2 行). 对于所有在当前结构上非邻接的节点对, 如果有被 ( V i ,V j 连通的路径, 则将尾节点添
,
V j
)
(
dSet V i ,V j 集合 (命题 1). 并使用更新的分离集计算依赖, 返回结果后续使用.
加到他们的
通过应用增强条件独立性检验方法恢复可能遗失的因果边, 在最小结构依赖准则下, 可以在多个候选邻域结