




中圖分類號:TP18 文獻標志碼:A DOI:10.13705/j.issn.1671-6841.2024102
文章編號:1671-6841(2025)06-0024-10
Abstract:In addressing the issues of Markov equivalence class in constraint-based causal discovery methods and the non-Gaussian noise assumption in functional causal models,the Cai-pseudo residual causal orientation algorithm was proposed using the three theorems of the Cai-pseudo residuals. Firstly, the relationships between variables were assumed to be linear,and no restrictions were imposed on the type of noise. With these conditions,the independence between the Cai-pseudo residuals and variables was manifested in diverse ways across the three distinct structures of Bayesian networks. Secondly,after construction of the Markov equivalence class using a constraint-based method,such varying associations were exploited to further distinguish the three structures and direct some previously undirected edges within the Markov equivalence class.Finally,experiments were performed on both linear Gaussian datasets and non-Gaussian datasets madeup of different causal network structures. The results highlighted that the proposed algorithm not only greatly lessened the quantity of undirected edges in the Markov equivalence class,but also notably enhanced the accuracy of causal direction determination.
Key Words:causal orientation;Bayesian network ; Markov equivalence class; pseudo residual; inde-pendence test
0 引言
在醫學診斷、社會科學以及系統控制等多個領域,因果關系發現都有著廣泛的應用[1-2]。對這些領域來說,揭示和理解數據中的因果關系具有深遠且至關重要的意義。然而,已有的因果關系發現方法主要利用隨機實驗,往往成本高昂、耗時過長,甚至根本無法實施[3-4]。因此,基于觀測數據的因果關系發現方法已經成為因果研究領域的核心。
因果關系發現是指在不同類型數據上添加各種因果假設(數據假設)的前提下,利用不同的工具和方法分析數據中隱含的變量間的因果關系,得到因果網絡結構的過程[5]。其中,基于約束的方法是一類重要的因果關系發現方法,其在定向階段依據對撞結構及Meek規則進行定向,如Spirtes等提出的PC 算法,而Colombo 等[7]提出的PC-stable算法和 Ramsey[8]提出的 PC-Max 算法均對 PC 算法的精確度和效率進行了改進。此外,一些算法是PC算法的延伸,例如Spirtes等°提出的快速因果推斷(fastcausalinference,FCI)算法,放松了因果充分性假設,可以處理存在混雜變量的情況。這些算法均依賴于條件獨立性檢驗,而不同的因果網絡可能有相同的條件獨立性集合。具有相同條件獨立性集合的因果網絡屬于同一馬爾科夫等價類。因此,盡管上述算法在某些方面具有優勢使定向更加準確,但它們都無法區分同一馬爾科夫等價類中的具體因果網絡結構。
馬爾科夫等價類問題可通過函數因果模型對底層真實數據生成函數或參數做出一些額外的假設來進一步處理[10]。在函數因果模型中,噪聲的恰當處理和建模能增強變量間因果關系的準確識別。因此,通過對噪聲的假設發現變量間的因果關系是因果關系發現領域的關鍵手段,如線性非高斯無環模型[1](linear non-Gaussian acyclic model,LiNGAM)假設變量間關系線性且噪聲非高斯。這類研究方法主要針對線性非高斯數據以及非線性數據,而對于線性高斯數據的關注則顯得較為不足。因此,研究人員一直在尋求新的解決策略,以提升因果關系發現的準確性和實用性。
本研究探討了當變量之間的關系呈線性時,在基于約束的方法發現馬爾科夫等價類后,利用Cai-偽殘差和變量間的獨立性,識別并確定貝葉斯網絡的三種結構。本文的主要貢獻如下。
1)提出了Cai-偽殘差因果定向算法(Cai-pseudoresidualcausalorientation,PCO),根據貝葉斯網絡的三種結構在Cai-偽殘差和變量間的獨立性表現不一致,可以對它們進行有效區分。
2)所提算法PCO僅要求變量間關系線性而不要求噪聲類型,可以有效處理線性高斯數據
3)將所提算法PCO與不同算法融合,并應用在不同因果網絡和數據中,實驗結果表明,其能有效確定馬爾科夫等價類中部分未定向邊的方向,從而減少潛在的因果網絡的數量。
1基于Cai-偽殘差與變量獨立性的研究
在本節中,主要介紹Cai-偽殘差在因果關系發現中的定向原理及Cai-偽殘差因果定向算法PCO。
1. 1 貝葉斯網絡的三種結構及其獨立性
貝葉斯網絡是一種特殊的概率圖模型,它充分利用了圖論中模型的構建能力和概率論的不確定性處理能力[12]。如果把貝葉斯網絡中的有向邊視為因果關系,則將表示變量之間因果關系的貝葉斯網絡模型稱為因果貝葉斯網絡。其中,節點代表隨機變量,有向邊則表示變量之間的直接因果關系,即
稱為“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) 。因此,鏈結構和叉結構屬于同一馬爾科夫等價類。
圖2叉結構示意圖
Figure 2Illustration of fork structure

2)對撞結構如圖3所示,其獨立性表述為:對于三個變量 X,Y,Z 滿足 X 和 Y 相互獨立,即 P(X Y)=P(X)P(Y) ;但在給定 Z 的條件下都不再獨立,即 P(X,Y|Z)≠P(X|Z)P(Y|Z) 。
圖3對撞結構示意圖

1.2 貝葉斯網絡三種結構的Cai-偽殘差特性
因果關系發現中基于約束的眾多算法均依賴于以下假設。
假設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 滿足

其中: aij 為 Vj 到 Vi 的因果權重; Pa(Vi) 為包含 Vi 的所有原因變量; εi 是 Vi 的噪聲變量。 εi⊥εj,εi⊥ VΛk,j≠i,k≠i,j
Cai等[15]在確定三個觀測變量的潛在變量之間的因果方向時提出了Cai-偽殘差。
定義 2[15] (20 Cai-偽殘差。對于三個變量 X,Y Z,X 和 Y 的Cai-偽殘差為

對于三個變量 X,Y,Z,X 和 Z,Z 和 Y 之間存在未定向邊 X--Z--Y ,若滿足變量 X 和 Y 有且僅有這一條邊,或變量 Z 僅存在這兩條邊時,則存在以下定理。
定理1對于鏈結構 XZY ,有
1) ω?XY↓X,ω?XY↓Y,ω?XY↓Z
2) ωXZ↓X,ωXZ↓Y,ωXZ↓Z :
3) ωYZ⊥X,ωYZ⊥Y,ωYZ⊥Z, (20
證明根據以上假設,鏈結構有
a1a2X+ε?Y,Z=a1X+ε?Z ,則 Cov(X,Y)=2a1a2DX Cov(X,Z)=a1DX,Cov(Y,Z)=2a12a2DX+a2DεZ 0故
1)
,顯然
,ωXY↓Y,ωXY↓Z 。
2)
,顯然
ωXZ↓Y,ωXZ↓Z, 0
3) ωYZ=εY-a2εZ ,顯然 ω?YZ⊥X,ω?YZ⊥Y,ω?YZ⊥ Z 。
定理2 對于叉結構 XZY ,有
1) ω?XY⊥X,ω?XY⊥Y,ω?XY⊥Z
2) ωXZ↓X,ωXZ⊥Y,ωXZ⊥Z;
3) ωYZ⊥X,ωYZ⊥Y,ωYZ⊥Z
證明根據以上假設,叉結構有 X=a1Z+εX ,Y=a2Z+εY,Z=εZ ,則 Cov(X,Y)=a1a2DZ,Cov(X, Z)=a1DZ,Cov(Y,Z)=a2DZ 。故
,顯然 ωXY↓X,ωXY↓Y,ωXY⊥ Z。
2) ωXZ=εX ,顯然 ωXZ⊥X,ωXZ⊥Y,ωXZ⊥Z0 (204
3) ωYZ=εY ,顯然 ωYZ⊥X,ωYZ⊥Y,ωYZ⊥Z 。
定理3對于對撞結構 X?ZY ,有
1) ω?XY↓X,ω?XY↓Y,ω?XY↓Z
2) ωXZ⊥X,ωXZ⊥Y,ωXZ⊥Z;
3) ω?YZ⊥χ,ω?YZ⊥Y,ω?YZ⊥Z,
證明根據以上假設,對撞結構有 X=εx,Y= ε?Y,Z=a1X+a2Y+εz ,則 Cov(X,Y)= 0,Cov(X,Z)= a1DX,Cov(Y,Z)=a2DY 故
1)
,顯然 $\omega _ { _ { X Y } } \texttt { Y X } , \omega _ { _ { X Y } } \texttt { Y } _ { ! } \$ (204號 $\omega _ { _ { X Y } } \texttt { \backslash Z }$ 。
2) ωXZ=X ,顯然 ωXZ↓X,ωXZ⊥Y,ωXZ↓Z 。
3) ωYZ=Y ,顯然 ωYZ⊥χ,ωYZ⊥χY,ωYZ⊥Z 。
若不滿足1)和2), X-Y-Z 示意圖如圖4所示。
圖4不滿足條件1)和2)的X-Y-Z示意圖 Figure 4 Illustration of X-Y-Z that does not meet conditions1)and 2)

設 X=a1Z+b1W+εx,Y=a2Z+b2W+εy,Z= εz,W=a3Z+εW ,則 X,Y,Z 有以下獨立性:
1) ω?XY↓X,ω?XY↓Y,ω?XY↓Z 2) ω?XZ↓X,ω?XZ↓Y,ω?XZ↓Z :3) ω?YZ⊥X,ω?YZ⊥Y,ω?YZ⊥Z, 此獨立性無法區分 X,Y,Z 三個變量間的結構。根據定理1~3,區分貝葉斯網絡三種結構的方法如下。1)當且僅當 ω?YZ⊥X 時,將三元組 X--Z--Y 確定為鏈結構 XZY, 。2)當滿足 ωXY⊥Z,ωXZ⊥Y,ωYZ⊥X 時,將三元組 X--Z--Y 確定為叉結構 XZY, 03)當滿足 ω?XZ⊥Y,ω?YZ⊥X 時,將三元組 X-- Z--Y 確定為對撞結構 X?ZY. 0
1.3 Cai-偽殘差因果定向算法PCO
本文提出的Cai-偽殘差因果定向算法PCO,對未定向邊的三元組進行分析,根據Cai-偽殘差的定義及1.2節中闡述的方法確定三元組的結構。
由于樣本量不足,獨立性檢驗的結果不準確或不穩定,致使變量之間的因果關系不確定,則可能存在因果定向沖突問題,即雙向邊的問題。假設有兩個連接起來的三元組 X--Z--Y--W ,對此結構進行定向,可能存在三元組 X--Z--Y 和三元組 Z--Y-- W 分別確定為鏈結構和叉結構,最終得到 XZ Y?W ,使之出現一條雙向邊 ZY? □
面對這一問題,使用 PC-Max 算法[14]的思想:通過 p 值來衡量觀察到的數據與假設因果結構一致的可能性。因此,當出現雙向邊時,選擇最大 p 值的結構確定為真實因果網絡的結構,可以提高邊定向的準確性。
因果網絡示意圖如圖5所示。已有的基于約束的因果關系發現算法僅能確定 V1--V3--V4 三元組的對撞結構,在此基礎上,利用Cai-偽殘差的定義及三個定理,將 V2--V1--V3 三元組識別為鏈結構,從而導致產生雙向邊 V1V3 。故比較鏈結構和對撞結構的 p 值,選擇最大 p 值的結構確定 V1--V3 的方向。
圖5因果網絡示意圖
Figure 5Illustration of causal network

無環圖 G1(V,E) 。
算法1Cai-偽殘差因果定向算法PCO輸入:數據集 V={V1 , V2 ,…, Vn} ,部分有向
輸出:進一步定向后的無環圖 G2 。1)設 s 為圖 G1 中包含未定向邊的三元組的集
i,list_structure S 中每個節點連接的邊數的集合
元組的最大 p 值,確定此邊的方向;26) end if27)end for28)輸出圖 G2 (204號
2 實驗
將本文提出的因果定向算法PCO 與 PC[6] 、PC-stable[7] PC-Max[8] 及 FCI[9] 四種算法相結合,即在這四種算法構建馬爾科夫等價類后使用PCO算法對其進行定向,再使用Meek規則,記為PC-PCO、PC,-PCO、 PCu-PCO 及FCI-PCO(PC-stable 算法、PC-Max算法分別用PC PCu 表示),并分別應用于線性高斯數據和線性非高斯數據。然后,PCO算法與這四種算法在不同節點數的因果網絡中進行對比實驗。對于線性非高斯數據,還與LiNGAM[]算法進行了對比。
參照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因果網絡的基本信息

表2因果網絡的結構信息
Table 2 Structural information of the causal networks

2.1 評價指標
評價指標如下。
1)結構漢明距離 [12](SHD) :從圖A到圖B需要對邊進行操作(翻轉、刪除或增加)的次數,即兩個圖之間邊的差異數量。通常用 SHDn 來評價算法優劣,即

其中: n 表示節點數量。 SHDn 越小,表明算法得到的圖與真實因果網絡越接近。
2)精確率[14](Precision):算法發現真實因果網絡中邊的數量占發現的總邊數量的比率,即

其中: TP 指算法發現真實因果網絡中邊的數量; FP 指算法發現不吻合或不存在真實因果網絡中邊的數量。Precision越大,算法獲得的因果網絡的準確率越高。
3)召回率 [14](Recall) :算法發現真實因果網絡中邊的數量占真實因果網絡的總邊數量的比率,即

其中: FN 指算法未發現的真實因果網絡中邊的數量。Recal越大,算法獲得的正確的邊的數量越多。
4)鏈結構召回率(chain-r):算法發現真實因果網絡中鏈結構的數量占真實因果網絡中鏈結構的數量的比率,即

其中:chain-TP指算法發現真實因果網絡中鏈結構的數量;chain-FN指算法未發現的真實因果網絡中鏈結構的數量。
5)叉結構召回率(fork-r):算法發現真實因果網絡中叉結構的數量占真實因果網絡中叉結構的數量的比率,即

其中:fork-TP指算法發現真實因果網絡中叉結構的數量;fork-FN指算法未發現的真實因果網絡中叉結構的數量。
6)對撞結構召回率(collision-r):算法發現真實因果網絡中對撞結構的數量占真實因果網絡中對撞結構的數量的比率,即

其中:collision-TP指算法發現真實因果網絡中對撞結構的數量;collision-FN指算法未發現的真實因果網絡中對撞結構的數量。
2.2不同因果網絡中線性高斯數據的實驗
樣本量和線性高斯數據為5000,在不同的因果網絡背景下進行一系列的因果關系發現算法對比實驗。每個操作重復執行10次,并取結果的平均值。不同因果網絡中針對線性高斯數據的算法結果對比見表3。
表3不同因果網絡中針對線性高斯數據的算法結果對比
Table 3 Comparison of algorithm results for linear Gaussian data on different causal networks

續表3 Continuedtable3

表3顯示,從四個召回率評價指標來看,當PCO算法與四種基于約束的算法結合使用時,其在發現和定向邊的能力上超過了直接使用四種算法的效果。原因在于,通過條件獨立性檢驗發現和定向邊的方法,存在不同的結構可能滿足相同的條件獨立性問題,如叉結構和鏈結構均滿足 P(X,Y∣Z)= P(X|Z)P(Y|Z) 。因此,僅依賴條件獨立性檢驗無法準確識別所有的因果關系,而將PCO算法融入這四種基于約束的算法中,可以更準確地識別貝葉斯網絡中的三種基本結構,從而發現和定向更多的邊,進一步提高召回率。
從精確率評價指標來看,所使用的Cai-偽殘差計算方法識別的三種基本結構符合真實因果網絡,從而提升了識別的準確性。
從 SHDn 評價指標來看,隨著節點數量的增加,相較于其他算法,與PCO算法相結合的算法,其SHDn 值變化較為穩定。
綜合表2和表3可以看出,對于對撞結構占比較小的網絡,算法性能有顯著的提高;對于節點數量較少且對撞結構占比較大的網絡,算法的性能提升則較為有限。例如數據集HEPAR2,其對撞結構占比較小,PC算法等可以識別的對撞結構較少,使用Meek規則可定向邊也較少,且易出現對撞結構定向錯誤從而導致錯誤傳遞的問題。而所提算法PCO能直接識別三種結構,可以定向的邊多且準確,性能有較大的提升。對于數據集MILDEW,其對撞結構占比大,PC算法等可定向的邊較多,故性能提升較為有限。
2.3不同因果網絡中線性非高斯數據的實驗
本節實驗過程與2.2節類似。不同因果網絡中針對線性非高斯數據的算法結果對比見表4。表4展現了四種基于約束的因果關系發現算法及它們分別與PCO算法結合后的性能對比,并與LiNGAM[]算法進行了對比。
從表4可以發現,其與表3的算法優勢一致。觀察六個評價指標的結果可以看出,本文采用的基于Cai-偽殘差與變量獨立性的計算方法能準確地識別出真實因果圖的鏈結構、叉結構和對撞結構。
此外,LiNGAM算法在處理線性非高斯數據時有卓越的表現,其性能顯著優于其他算法。這主要因為LiNGAM是針對線性非高斯模型開發的算法,其利用非高斯噪聲與變量之間的不對稱性反映變量之間的因果方向,從而恢復因果網絡。相比之下,PCO算法以基于約束的方法為基礎,易存在錯誤邊傳播問題,對變量間因果關系的發現和定向均有影響。然而,隨著節點數量的增加,FCI-PCO算法在召回率上表現較穩定。而在超大型網絡上,LiNGAM算法的計算復雜度增加,并可能會因噪聲影響其性能。因此,在ANDES網絡中FCI-PCO算法在召回率上相較于LiNGAM算法有顯著優勢。值得注意的是,LiNGAM算法無法處理線性高斯數據,對此,本文提出的算法反而表現出其獨特的優勢。
表4不同因果網絡中針對線性非高斯數據的算法結果對比
Table 4Comparison of algorithm results for linear non-Gaussian data on different causal networks

續表4 Continuedtable4

3 結語
本文研究了貝葉斯網絡三種結構的Cai-偽殘差特性,并提出Cai-偽殘差因果定向算法PCO。PCO算法利用了貝葉斯網絡的三種結構在Cai-偽殘差與變量獨立性方面的不同結果,實現了對這三種結構的有效區分。重要的是,該算法僅要求變量間的關系為線性,而不需要特定的噪聲類型,大幅提高了其應用的廣泛性。實驗結果表明,在稀疏網絡中,PCO算法與已知的四種基于約束的因果關系發現算法相融合,其性能相較于直接使用這四種算法有著明顯的優勢。在同一樣本量下,其結構漢明距離評價指標相較于其他算法差異明顯,精確率和召回率也有了較大提升。雖然針對線性非高斯數據開發的LiNGAM算法有顯著的優勢,但其無法處理線性高斯數據。因此,本文提出的因果關系定向算法能在多個因果網絡中有效地確定未定向邊的方向,揭示網絡的隱含結構,同時有效地減少馬爾科夫等價類的數量。
所提算法雖然在一定程度上解決了馬爾科夫等價類問題,但對馬爾科夫等價類進一步定向時需要滿足一定的約束。并且,隨著節點數量的增加,算法性能呈現下降趨勢。未來將考慮不滿足PCO算法約束的結構特性來弱化此約束,并對算法進行優化,以進一步準確地定向馬爾科夫等價類中更多的無向邊。此外,也將進一步完善Cai-偽殘差與變量間獨立性的方法,并考慮引入更多的分析工具,以增強其處理復雜網絡結構和高維數據的能力,同時提升對模型中存在問題的敏感性,為實際應用提供更強大的工具。
參考文獻:
[1] SIDDIQISH,KORDINGKP,PARVIZIJ,etal.Causal mapping of human brain function[J].Nature reviews neuroscience,2022,23(6):361-375.
[2] 曹小敏,劉進鋒.基于因果推斷的兩階段長尾分類研 究[J].鄭州大學學報(理學版),2024,56(5):31- 38. CAO X M,LIU JF. 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.
[3] SCHOLKOPFB,LOCATELLOF,BAUERS,etal.Toward causal representation learning[J].Proceedingsof theIEEE,2021,109(5):612-634.
[4] CAMPS-VALLS G,GERHARDUS A,NINAD U,et al. Discovering causal relations and equations from data[J]. Physics reports,2023,1044:1-68.
[5] ARONOW P M,SAVJE F. The book of why:the new scienceofcauseand effect[J].Journal ofthe American statistical association,2020,115(529):482-485.
[6] SPIRTES P,GLYMOUR C.An algorithm for fast recovery of sparse causal graphs[J]. Social science computer review,1991,9(1):62-72.
[7] COLOMBO D,MAATHUIS M H. Order-independent constraint-based causal structure learning[J]. Journal of machine learning research,2014,15(1):3741-3782.
[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.
[9] SPIRTESP,MEEKC,RICHARDSON T.An algorithm forcausal inference inthepresence oflatentvariablesand selection bias[M]//Computation,Causation,and Discovery.Palo Alto:AAAI Press,1999:211-252.
[10]VERMAT S,PEARL J. Equivalence and synthesisof causal models[M]//Probabilistic and Causal Inference. New York:ACM Press,2022:221-236.
[11]SHIMIZU S,HOYERPO,HYVARINEN A,et al.A linear non-Gaussian acyclic model for causal discovery [J].Journal of machine learning research,2O06,7: 2003-2030.
[12] KITSON N K,CONSTANTINOU A C,GUO ZG,et al. A survey of Bayesian network structure learning[J].Artificial intelligence review,2023,56(8):8721-8814.
[13]RUNGE J,GERHARDUS A,VARANDO G,et al. Causal inference for time series[J].Naturereviews earth amp;environment,2023,4:487-505.
[14]YAOL,CHUZ,LIS,etal.A surveyoncausal inference[J]. ACM transactions on knowledge discovery from data,2021,15(5):1-46.
[15]CAIRC,XIEF,GLYMOURC,et al.Triad constraints forlearning causal structure of latent variables[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems. Cambridge:MIT Press, 2019:12863-12872.