2025, Vol. 57
2. 计算智能与中文信息处理教育部重点实验室(山西大学) 山西 太原 030006
2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education(Shanxi University), Taiyuan 030006, China
在医学诊断、社会科学以及系统控制等多个领域，因果关系发现都有着广泛的应用[1-2]。对这些领域来说，揭示和理解数据中的因果关系具有深远且至关重要的意义。然而，已有的因果关系发现方法主要利用随机实验，往往成本高昂、耗时过长，甚至根本无法实施[3-4]。因此，基于观测数据的因果关系发现方法已经成为因果研究领域的核心。
因果关系发现是指在不同类型数据上添加各种因果假设(数据假设)的前提下，利用不同的工具和方法分析数据中隐含的变量间的因果关系，得到因果网络结构的过程[5]。其中，基于约束的方法是一类重要的因果关系发现方法，其在定向阶段依据对撞结构及Meek规则进行定向，如Spirtes等[6]提出的PC算法，而Colombo等[7]提出的PC-stable算法和Ramsey[8]提出的PC-Max算法均对PC算法的精确度和效率进行了改进。此外，一些算法是PC算法的延伸，例如Spirtes等[9]提出的快速因果推断(fast causal inference, FCI)算法，放松了因果充分性假设，可以处理存在混杂变量的情况。这些算法均依赖于条件独立性检验，而不同的因果网络可能有相同的条件独立性集合。具有相同条件独立性集合的因果网络属于同一马尔科夫等价类。因此，尽管上述算法在某些方面具有优势使定向更加准确，但它们都无法区分同一马尔科夫等价类中的具体因果网络结构。
马尔科夫等价类问题可通过函数因果模型对底层真实数据生成函数或参数做出一些额外的假设来进一步处理[10]。在函数因果模型中，噪声的恰当处理和建模能增强变量间因果关系的准确识别。因此，通过对噪声的假设发现变量间的因果关系是因果关系发现领域的关键手段，如线性非高斯无环模型[11](linear non-Gaussian acyclic model, LiNGAM)假设变量间关系线性且噪声非高斯。这类研究方法主要针对线性非高斯数据以及非线性数据，而对于线性高斯数据的关注则显得较为不足。因此，研究人员一直在寻求新的解决策略，以提升因果关系发现的准确性和实用性。
本研究探讨了当变量之间的关系呈线性时，在基于约束的方法发现马尔科夫等价类后，利用Cai-伪残差和变量间的独立性，识别并确定贝叶斯网络的三种结构。本文的主要贡献如下。
1) 提出了Cai-伪残差因果定向算法(Cai-pseudo residual causal orientation，PCO)，根据贝叶斯网络的三种结构在Cai-伪残差和变量间的独立性表现不一致，可以对它们进行有效区分。
2) 所提算法PCO仅要求变量间关系线性而不要求噪声类型，可以有效处理线性高斯数据。
3) 将所提算法PCO与不同算法融合，并应用在不同因果网络和数据中，实验结果表明，其能有效确定马尔科夫等价类中部分未定向边的方向，从而减少潜在的因果网络的数量。
1 基于Cai-伪残差与变量独立性的研究在本节中，主要介绍Cai-伪残差在因果关系发现中的定向原理及Cai-伪残差因果定向算法PCO。
1.1 贝叶斯网络的三种结构及其独立性贝叶斯网络是一种特殊的概率图模型，它充分利用了图论中模型的构建能力和概率论的不确定性处理能力[12]。如果把贝叶斯网络中的有向边视为因果关系，则将表示变量之间因果关系的贝叶斯网络模型称为因果贝叶斯网络。其中，节点代表随机变量，有向边则表示变量之间的直接因果关系，即A→B称为“A是B的直接原因”。因此，贝叶斯网络能够用于建立和解读因果关系，并据此进行因果推理。在贝叶斯网络中，存在以下三种基本结构。
定义1 [13] 链结构、叉结构、对撞结构。
1) 链结构、叉结构分别如图 1、图 2所示，其独立性表述均为：对于三个变量X，Y，Z满足X和Y不独立，即P(X, Y)≠P(X)P(Y)；但在给定Z的条件下X和Y独立，即P(X, Y|Z)= P(X|Z)P(Y|Z)。因此，链结构和叉结构属于同一马尔科夫等价类。
|
图 1 链结构示意图 Fig. 1 Illustration of chain structure |
|
图 2 叉结构示意图 Fig. 2 Illustration of fork structure |
2) 对撞结构如图 3所示，其独立性表述为：对于三个变量X，Y，Z满足X和Y相互独立，即
|
图 3 对撞结构示意图 Fig. 3 Illustration of collision structure |
因果关系发现中基于约束的众多算法均依赖于以下假设。
假设1 [14] 因果充分性假设。当变量集V中的任意两个变量的直接原因变量都存在V中时，变量集V就被认为是因果充分的。
假设2 [14] 因果马尔科夫性假设。对于给定变量集V和边集E的有向无环图G (V, E)，马尔科夫条件在G中被满足的唯一情况是：G中的任一节点在给定其直接原因(在因果网络中的父节点)时，与其所有非后代节点的任意组合都是条件独立的，那么把这种情况称为满足因果马尔科夫性假设。
假设3 [14] 因果忠诚性假设。对于一个具有因果充分性的变量集V，在概率P中，当且仅当P中的每个条件独立性都由因果网络G及其马尔科夫条件决定时，可以说G对于概率P是忠诚的。换句话说，如果G对于概率P是忠诚的，那么就认为概率P对于G也是忠诚的。
本研究利用Cai-伪残差与变量间的独立性对马尔科夫等价类进一步定向，有如下假设。
假设4 变量间关系线性假设。变量V满足
| $ V_i=\sum\limits_{V_j \in P a\left(V_i\right), j \neq i} a_{i j} V_j+\varepsilon_i, $ | (1) |
其中：aij为Vj到Vi的因果权重；Pa(Vi)为包含Vi的所有原因变量；εi是Vi的噪声变量。εi⊥εj, εi⊥Vk, j≠i, k≠i, j。
Cai等[15]在确定三个观测变量的潜在变量之间的因果方向时提出了Cai-伪残差。
定义2 [15] Cai-伪残差。对于三个变量X，Y，Z，X和Y的Cai-伪残差为
| $ \omega_{X Y}=X-\frac{Cov(X, Z)}{Cov(Y, Z)} Y 。$ |
对于三个变量X，Y，Z，X和Z，Z和Y之间存在未定向边X--Z--Y，若满足变量X和Y有且仅有这一条边，或变量Z仅存在这两条边时，则存在以下定理。
定理1 对于链结构X→Z→Y，有
1)
2)
3)
证明 根据以上假设，链结构有
1)
2)
3)
定理2 对于叉结构X←Z→Y，有
1)
2)
3)
证明 根据以上假设，叉结构有
1)
2)
3)
定理3 对于对撞结构X→Z←Y，有
1)
2)
3)
证明 根据以上假设，对撞结构有X=εX，Y= εY，Z=a1X+a2Y+εZ，则
1)
2)
3)
若不满足1)和2)，X-Y-Z示意图如图 4所示。
|
图 4 不满足条件1)和2)的X-Y-Z示意图 Fig. 4 Illustration of X-Y-Zthat does not meet conditions 1) and 2) |
设
1)
2)
3)
此独立性无法区分X，Y，Z三个变量间的结构。
根据定理1~3，区分贝叶斯网络三种结构的方法如下。
1) 当且仅当ωYZ⊥X时，将三元组X--Z--Y确定为链结构X→Z→Y。
2) 当满足ωXY⊥Z，ωXZ⊥Y，ωYZ⊥X时，将三元组X--Z--Y确定为叉结构X←Z→Y。
3) 当满足ωXZ⊥Y，ωYZ⊥X时，将三元组X--Z--Y确定为对撞结构X→Z←Y。
1.3 Cai-伪残差因果定向算法PCO本文提出的Cai-伪残差因果定向算法PCO，对未定向边的三元组进行分析，根据Cai-伪残差的定义及1.2节中阐述的方法确定三元组的结构。
由于样本量不足，独立性检验的结果不准确或不稳定，致使变量之间的因果关系不确定，则可能存在因果定向冲突问题，即双向边的问题。假设有两个连接起来的三元组X--Z--Y--W，对此结构进行定向，可能存在三元组X--Z--Y和三元组Z--Y--W分别确定为链结构和叉结构，最终得到X→Z←→Y→W，使之出现一条双向边Z←→Y。
面对这一问题，使用PC-Max算法[14]的思想：通过p值来衡量观察到的数据与假设因果结构一致的可能性。因此，当出现双向边时，选择最大p值的结构确定为真实因果网络的结构，可以提高边定向的准确性。
因果网络示意图如图 5所示。已有的基于约束的因果关系发现算法仅能确定V1--V3--V4三元组的对撞结构，在此基础上，利用Cai-伪残差的定义及三个定理，将V2--V1--V3三元组识别为链结构，从而导致产生双向边V1←→V3。故比较链结构和对撞结构的p值，选择最大p值的结构确定V1--V3的方向。
|
图 5 因果网络示意图 Fig. 5 Illustration of causal network |
算法1 Cai-伪残差因果定向算法PCO
输入：数据集
输出：进一步定向后的无环图G2。
1) 设S为图G1中包含未定向边的三元组的集合，list_structure←S中每个节点连接的边数的集合，i←0，temp←0，NV← []；
2) for each X--Z--Y∈S do
3) if list_structure(X)==list_structure(Y)==1 or list_structure(Z)==2 do
4) NV(i)←X--Z--Y
5) i=i+1
6) end if
7) end for
8) for i=1: |NV| do
9) for each Vi, Vj∈NV(i) do
10) Vk=NV(i)\Vi, Vj
11) if ωViVj⊥Vk do
12) temp=temp+1
13) end if
14) end for
15) if temp=3 do
16) Vi←Vj→Vk
17) else if temp=1且ωVjVk⊥Vi do
18) Vi→Vj→Vk
19) else if temp=1且ωViVj⊥Vk do
20) Vi←Vj←Vk
21) else if temp=2 do
22) Vi→Vj←Vk
23) end if
24) if NV(i)中存在双向边do
25) 根据NV(i)中包含此双向边的所有三元组的最大p值，确定此边的方向；
26) end if
27) end for
28) 输出图G2
2 实验将本文提出的因果定向算法PCO与PC[6]、PC-stable[7]、PC-Max[8]及FCI[9]四种算法相结合，即在这四种算法构建马尔科夫等价类后使用PCO算法对其进行定向，再使用Meek规则，记为PC-PCO、PCs-PCO、PCM-PCO及FCI-PCO(PC-stable算法、PC-Max算法分别用PCs、PCM表示)，并分别应用于线性高斯数据和线性非高斯数据。然后，PCO算法与这四种算法在不同节点数的因果网络中进行对比实验。对于线性非高斯数据，还与LiNGAM[11]算法进行了对比。
参照 https://www.bnlearn.com/bnrepository中的8个因果网络结构，根据1.2节的变量间关系的线性假设，其中因果权重aij服从均匀分布[-0.9, -0.5]∪[0.5, 0.9]，噪声分别服从标准高斯分布及期望为1的指数分布，对不同的因果网络合成线性高斯数据集和线性非高斯数据集。表 1展示了8个因果网络的基本信息，这些网络的分类依据是网络中包含的节点数目。其中，少于20个节点的网络被定义为小型网络，节点数为20~50的网络属于中型网络，具有50~100个节点的网络被称为大型网络，而具有100~1 000个节点的网络被视作超大型网络。
|
表 1 因果网络的基本信息 Tab. 1 Basic information of the causal networks |
表 2展示了8个因果网络的结构信息。所有因果网络均为稀疏网络。
|
|
表 2 因果网络的结构信息 Tab. 2 Structural information of the causal networks |
评价指标如下。
1) 结构汉明距离[12] (SHD)：从图A到图B需要对边进行操作(翻转、删除或增加)的次数，即两个图之间边的差异数量。通常用SHDn来评价算法优劣，即
| $ S H D n=\frac{S H D}{n} \text {, } $ | (3) |
其中：n表示节点数量。SHDn越小，表明算法得到的图与真实因果网络越接近。
2) 精确率[14](Precision)：算法发现真实因果网络中边的数量占发现的总边数量的比率，即
| $ { Precision }=\frac{T P}{T P+F P}, $ | (4) |
其中：TP指算法发现真实因果网络中边的数量；FP指算法发现不吻合或不存在真实因果网络中边的数量。Precision越大，算法获得的因果网络的准确率越高。
3) 召回率[14] (Recall): 算法发现真实因果网络中边的数量占真实因果网络的总边数量的比率，即
| $ { Recall }=\frac{T P}{T P+F N}, $ | (5) |
其中: FN指算法未发现的真实因果网络中边的数量。Recall越大，算法获得的正确的边的数量越多。
4) 链结构召回率(chain-r)：算法发现真实因果网络中链结构的数量占真实因果网络中链结构的数量的比率，即
| $ { chain }-r=\frac{ { chain-TP }}{ { chain-TP }+ { chain-FN }}, $ | (6) |
其中：chain-TP指算法发现真实因果网络中链结构的数量；chain-FN指算法未发现的真实因果网络中链结构的数量。
5) 叉结构召回率(fork-r)：算法发现真实因果网络中叉结构的数量占真实因果网络中叉结构的数量的比率，即
| $ { fork }-r=\frac{ { fork }-T P}{ { fork }-T P+ { fork }-F N}, $ | (7) |
其中：fork-TP指算法发现真实因果网络中叉结构的数量；fork-FN指算法未发现的真实因果网络中叉结构的数量。
6) 对撞结构召回率(collision-r)：算法发现真实因果网络中对撞结构的数量占真实因果网络中对撞结构的数量的比率，即
| $ { collision }-r=\frac{ { collision }-T P}{ { collision }-T P+ { collision }-F N}, $ | (8) |
其中：collision-TP指算法发现真实因果网络中对撞结构的数量；collision-FN指算法未发现的真实因果网络中对撞结构的数量。
2.2 不同因果网络中线性高斯数据的实验样本量和线性高斯数据为5 000，在不同的因果网络背景下进行一系列的因果关系发现算法对比实验。每个操作重复执行10次，并取结果的平均值。不同因果网络中针对线性高斯数据的算法结果对比见表 3。
|
|
表 3 不同因果网络中针对线性高斯数据的算法结果对比 Tab. 3 Comparison of algorithm results for linear Gaussian data on different causal networks |
表 3显示，从四个召回率评价指标来看，当PCO算法与四种基于约束的算法结合使用时，其在发现和定向边的能力上超过了直接使用四种算法的效果。原因在于，通过条件独立性检验发现和定向边的方法，存在不同的结构可能满足相同的条件独立性问题，如叉结构和链结构均满足
从精确率评价指标来看，所使用的Cai-伪残差计算方法识别的三种基本结构符合真实因果网络，从而提升了识别的准确性。
从SHDn评价指标来看，随着节点数量的增加，相较于其他算法，与PCO算法相结合的算法，其SHDn值变化较为稳定。
综合表 2和表 3可以看出，对于对撞结构占比较小的网络，算法性能有显著的提高；对于节点数量较少且对撞结构占比较大的网络，算法的性能提升则较为有限。例如数据集HEPAR2，其对撞结构占比较小，PC算法等可以识别的对撞结构较少，使用Meek规则可定向边也较少，且易出现对撞结构定向错误从而导致错误传递的问题。而所提算法PCO能直接识别三种结构，可以定向的边多且准确，性能有较大的提升。对于数据集MILDEW，其对撞结构占比大，PC算法等可定向的边较多，故性能提升较为有限。
2.3 不同因果网络中线性非高斯数据的实验本节实验过程与2.2节类似。不同因果网络中针对线性非高斯数据的算法结果对比见表 4。表 4展现了四种基于约束的因果关系发现算法及它们分别与PCO算法结合后的性能对比，并与LiNGAM[11]算法进行了对比。
|
|
表 4 不同因果网络中针对线性非高斯数据的算法结果对比 Tab. 4 Comparison of algorithm results for linear non-Gaussian data on different causal networks |
从表 4可以发现，其与表 3的算法优势一致。观察六个评价指标的结果可以看出，本文采用的基于Cai-伪残差与变量独立性的计算方法能准确地识别出真实因果图的链结构、叉结构和对撞结构。
此外，LiNGAM算法在处理线性非高斯数据时有卓越的表现，其性能显著优于其他算法。这主要因为LiNGAM是针对线性非高斯模型开发的算法，其利用非高斯噪声与变量之间的不对称性反映变量之间的因果方向，从而恢复因果网络。相比之下，PCO算法以基于约束的方法为基础，易存在错误边传播问题，对变量间因果关系的发现和定向均有影响。然而，随着节点数量的增加，FCI-PCO算法在召回率上表现较稳定。而在超大型网络上，LiNGAM算法的计算复杂度增加，并可能会因噪声影响其性能。因此，在ANDES网络中FCI-PCO算法在召回率上相较于LiNGAM算法有显著优势。值得注意的是，LiNGAM算法无法处理线性高斯数据，对此，本文提出的算法反而表现出其独特的优势。
3 结语本文研究了贝叶斯网络三种结构的Cai-伪残差特性，并提出Cai-伪残差因果定向算法PCO。PCO算法利用了贝叶斯网络的三种结构在Cai-伪残差与变量独立性方面的不同结果，实现了对这三种结构的有效区分。重要的是，该算法仅要求变量间的关系为线性，而不需要特定的噪声类型，大幅提高了其应用的广泛性。实验结果表明，在稀疏网络中，PCO算法与已知的四种基于约束的因果关系发现算法相融合，其性能相较于直接使用这四种算法有着明显的优势。在同一样本量下，其结构汉明距离评价指标相较于其他算法差异明显，精确率和召回率也有了较大提升。虽然针对线性非高斯数据开发的LiNGAM算法有显著的优势，但其无法处理线性高斯数据。因此，本文提出的因果关系定向算法能在多个因果网络中有效地确定未定向边的方向，揭示网络的隐含结构，同时有效地减少马尔科夫等价类的数量。
所提算法虽然在一定程度上解决了马尔科夫等价类问题，但对马尔科夫等价类进一步定向时需要满足一定的约束。并且，随着节点数量的增加，算法性能呈现下降趋势。未来将考虑不满足PCO算法约束的结构特性来弱化此约束，并对算法进行优化，以进一步准确地定向马尔科夫等价类中更多的无向边。此外，也将进一步完善Cai-伪残差与变量间独立性的方法，并考虑引入更多的分析工具，以增强其处理复杂网络结构和高维数据的能力，同时提升对模型中存在问题的敏感性，为实际应用提供更强大的工具。
| [1] |
SIDDIQI S H, KORDING K P, PARVIZI J, et al. Causal mapping of human brain function[J]. Nature reviews neuroscience, 2022, 23(6): 361-375. (  0) |
| [2] |
曹小敏, 刘进锋. 基于因果推断的两阶段长尾分类研究[J]. 郑州大学学报(理学版), 2024, 56(5): 31-38. CAO X M, LIU J F. A study of two-stage long-tail classification based on causal inference[J]. Journal of Zhengzhou university (natural science edition), 2024, 56(5): 31-38. DOI:10.13705/j.issn.1671-6841.2023122 ( 0) |
| [3] |
SCHÖLKOPF B, LOCATELLO F, BAUER S, et al. Toward causal representation learning[J]. Proceedings of the IEEE, 2021, 109(5): 612-634. ( 0) |
| [4] |
CAMPS-VALLS G, GERHARDUS A, NINAD U, et al. Discovering causal relations and equations from data[J]. Physics reports, 2023, 1044: 1-68. ( 0) |
| [5] |
ARONOW P M, SÄVJE F. The book of why: the new science of cause and effect[J]. Journal of the American statistical association, 2020, 115(529): 482-485. ( 0) |
| [6] |
SPIRTES P, GLYMOUR C. An algorithm for fast recovery of sparse causal graphs[J]. Social science computer review, 1991, 9(1): 62-72. ( 0) |
| [7] |
COLOMBO D, MAATHUIS M H. Order-independent constraint-based causal structure learning[J]. Journal of machine learning research, 2014, 15(1): 3741-3782. ( 0) |
| [8] |
RAMSEY J. Improving accuracy and scalability of the PC algorithm by maximizing P-value[EB/OL]. (2016-10-05)[2024-04-23]. https://doi.org/10.48550/arXiv.1610.00378.
( 0) |
| [9] |
SPIRTES P, MEEK C, RICHARDSON T. An algorithm for causal inference in the presence of latent variables and selection bias[M]. Palo Alto: AAAI Press, 1999: 211-252.
( 0) |
| [10] |
VERMA T S, PEARL J. Equivalence and synthesis of causal models[M]. New York: ACM Press, 2022: 221-236.
( 0) |
| [11] |
SHIMIZU S, HOYER P O, HYVÄRINEN A, et al. A linear non-Gaussian acyclic model for causal discovery[J]. Journal of machine learning research, 2006, 7: 2003-2030. ( 0) |
| [12] |
KITSON N K, CONSTANTINOU A C, GUO Z G, et al. A survey of Bayesian network structure learning[J]. Artificial intelligence review, 2023, 56(8): 8721-8814. ( 0) |
| [13] |
RUNGE J, GERHARDUS A, VARANDO G, et al. Causal inference for time series[J]. Nature reviews earth & environment, 2023, 4: 487-505. ( 0) |
| [14] |
YAO L, CHU Z, LI S, et al. A survey on causal inference[J]. ACM transactions on knowledge discovery from data, 2021, 15(5): 1-46. ( 0) |
| [15] |
CAI R C, XIE F, GLYMOUR C, et al. Triad constraints for learning causal structure of latent variables[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2019: 12863-12872.
( 0) |