基于遞歸分解的因果結(jié)構(gòu)學(xué)習(xí)算法

蔡瑞初，張文輝，喬 杰，郝志峰，2

（1.廣東工業(yè)大學(xué) 計算機學(xué)院，廣州 510006；2.汕頭大學(xué) 理學(xué)院，廣東 汕頭 515063）

0 概述

從觀測數(shù)據(jù)中推斷變量之間的因果關(guān)系是當(dāng)今數(shù)據(jù)科學(xué)研究的熱點［1-2］。因果關(guān)系發(fā)現(xiàn)的研究可以揭露數(shù)據(jù)的產(chǎn)生機制，而數(shù)據(jù)產(chǎn)生機制對現(xiàn)實中的預(yù)測和干預(yù)問題有著極其關(guān)鍵的作用。在現(xiàn)有的研究中，因果關(guān)系發(fā)現(xiàn)方法應(yīng)用于生物醫(yī)學(xué)、教育學(xué)、經(jīng)濟學(xué)、流行病、氣象學(xué)等［3-4］多個領(lǐng)域。

傳統(tǒng)因果關(guān)系方法的研究是通過隨機控制實驗進行因果關(guān)系學(xué)習(xí)，但實驗所需費用高，或現(xiàn)有技術(shù)無法實現(xiàn)。因此，基于觀察數(shù)據(jù)的因果結(jié)構(gòu)學(xué)習(xí)方法備受關(guān)注。PEARL 等［5］從圖模型的角度給出一套因果關(guān)系發(fā)現(xiàn)的語言，提出一種因果圖模型，其中，節(jié)點表示變量，節(jié)點之間的有向邊表示變量之間的因果關(guān)系。基于該模型，PEARL 和SPIRTES 等［5-6］提出基于約束的因果結(jié)構(gòu)學(xué)習(xí)方法。該方法在忠誠性等假設(shè)下［7］，通過條件獨立性檢驗學(xué)習(xí)因果結(jié)構(gòu)。雖然這類方法能夠取得較準(zhǔn)確的結(jié)果，但是存在馬爾可夫等價類問題［8］，即部分因果關(guān)系無法被識別。馬爾可夫等價類在概率圖模型中指具有相同條件獨立，其變量和因果骨架相同，但方向不確定的結(jié)構(gòu)。假設(shè)由三個隨機變量x，y，z組成的骨架x-z-y存在相同的條件獨立性P(x|z)P(y|z)=P(x，y|z)，則可能存在3 種不同的結(jié)構(gòu)：x→z→y，x←z←y，x←z→y。

此外，基于約束的因果結(jié)構(gòu)學(xué)習(xí)方法在對條件候選集搜索時存在復(fù)雜度高的問題［9］。BERGSMA等［10］提出在連續(xù)變量的條件獨立性檢驗中，隨著變量數(shù)量的增加，對條件候選集的搜索復(fù)雜度將呈指數(shù)級增長。在該過程中，隨著變量數(shù)的增長，算法中變量條件獨立性檢驗條件集的數(shù)量也呈指數(shù)增長，使得算法的計算復(fù)雜度急劇增大。當(dāng)條件集Z的數(shù)量不斷增大時，條件獨立性檢驗的正確性有待驗證，同時極有可能出現(xiàn)第二類錯誤，即使變量間互相依賴，也可能被預(yù)測為相互條件獨立。當(dāng)條件集數(shù)量增加，而樣本量不足時，會增加噪聲或其他變量對無關(guān)變量的影響權(quán)重，使得原本相互不獨立的變量變?yōu)楠毩㈥P(guān)系［11］。

針對這類問題，研究人員提出采用遞歸分解的方法進行因果結(jié)構(gòu)學(xué)習(xí)［9，12-15］。這類方法的主要目標(biāo)是把一個問題遞歸地分解到兩個或多個規(guī)模更小的子問題空間中進行高效求解。但是，該類方法仍無法解決馬爾可夫等價類問題。

通過對實際場景數(shù)據(jù)的分析，本文發(fā)現(xiàn)在很多現(xiàn)實數(shù)據(jù)（如社交網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)等）中變量間的關(guān)系較稀疏，其組成的因果結(jié)構(gòu)也呈現(xiàn)稀疏性［16］（即每個變量的平均父親節(jié)點數(shù)量為2）。因此，結(jié)合實際場景數(shù)據(jù)的特征，本文提出一種基于遞歸分解的因果結(jié)構(gòu)學(xué)習(xí)算法CADR，在高維小樣本的數(shù)據(jù)中更高效地進行因果結(jié)構(gòu)學(xué)習(xí)。基于觀測樣本的稀疏性，設(shè)計一種新的遞歸分解算法，減少條件候選集的數(shù)量，使得條件獨立性檢驗更可靠。基于現(xiàn)有加性噪聲模型（Additive Noise Model，ANM）的噪聲和數(shù)據(jù)產(chǎn)生機制假設(shè)，解決條件獨立性檢驗中存在的馬爾可夫等價類問題。根據(jù)遞歸分解算法所得到的變量子集和加性噪聲模型，提出一種學(xué)習(xí)完全定向的有向無環(huán)圖（Complete Directed Acyclic Graph，CDAG）方法。

1 相關(guān)工作

傳統(tǒng)因果結(jié)構(gòu)學(xué)習(xí)的方法（如IC［5］、PC 算法［6，17-18］等）通過對變量進行條件獨立性檢驗，因存在馬爾可夫等價類問題，只能學(xué)習(xí)因果結(jié)構(gòu)的基本框架，無法學(xué)習(xí)到真正的因果關(guān)系。此外，大多數(shù)現(xiàn)有的因果結(jié)構(gòu)學(xué)習(xí)方法都是在假設(shè)樣本量足夠的前提下進行研究。部分因果結(jié)構(gòu)學(xué)習(xí)方法雖然對小樣本的因果關(guān)系發(fā)現(xiàn)進行研究［19］，但是實際上在一些高維、小樣本數(shù)據(jù)（如基因表達數(shù)據(jù)）上的實驗效果表現(xiàn)不佳。

針對高維數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)問題，研究人員通過縮小條件候選集的搜索范圍，并采用遞歸分解的方法進行因果關(guān)系發(fā)現(xiàn)。這類方法的主要目標(biāo)是將一個總問題遞歸地分解為兩個或多個規(guī)模更小且解法相同的子問題，從而提高求解效率。

在XIE 等［12］提出的框架中，對于隨機變量集合V：首先，通過條件獨立性檢驗學(xué)習(xí)每對隨機變量在給定其他所有節(jié)點集條件下的獨立性，得到一個無向獨立圖（Undirected Independence Graph，UIG）；其次，根據(jù)條件A⊥B|C，其中A，B，C?V，從UIG 中找出一個分解V={A，B，C}，把集合分解為更小的兩個子集V1=A∪C和V2=B∪C，再分別學(xué)習(xí)這兩個子集的UIG，并將其分解為更小的子集，遞歸地執(zhí)行該分解過程，直到子集無法再被分解；最后，通過基于約束的方法（如IC、PC 等算法）盡可能多地確定剩余無向邊的方向。之后，把這些局部因果結(jié)構(gòu)合并成一個全局因果結(jié)構(gòu)。這種方法擺脫了傳統(tǒng)方法對樣本量的依賴，但每次學(xué)習(xí)UIG 的條件集是除了節(jié)點對以外的其他所有節(jié)點，可能會降低條件獨立性檢驗的準(zhǔn)確率。LIU 等［14］通過基于搜索評分的方法來學(xué)習(xí)UIG，并取得較好的效果，但是在高維樣本中，通過搜索評分的方法學(xué)習(xí)UIG 的計算復(fù)雜度不斷增大。

條件獨立性檢驗的方法是通過檢測V-結(jié)構(gòu)來判斷局部結(jié)構(gòu)的因果方向，但因無法區(qū)分馬爾可夫等價類問題而學(xué)習(xí)到完全有向的因果結(jié)構(gòu)。針對該問題，研究人員提出加性噪聲模型的方法，通過對噪聲和數(shù)據(jù)產(chǎn)生的機制進行假設(shè)，根據(jù)觀測數(shù)據(jù)擬合噪聲，并判斷其與原因變量是否獨立，從而確定因果方向。這類方法的關(guān)鍵是對噪聲和數(shù)據(jù)產(chǎn)生機制進行假設(shè)。根據(jù)變量的數(shù)量將現(xiàn)有方法分為兩類：1）兩個變量因果方向判斷方法，如非線性非高斯模型［20］、基于回歸的模型［21］、基于核空間的方法［22-23］等；2）三個及以上變量的因果方向判斷方法，基于HSIC 的方法［24］、基 于KCIT 的方法［25］、基于ReCIT 的方法［11］等。在高維小樣本的情況下，因為這些方法需要大量計算變量與聯(lián)合分布之間的條件概率統(tǒng)計，要求樣本量必須充足，所以其實驗效果表現(xiàn)不佳。

2 基于遞歸分解的因果結(jié)構(gòu)學(xué)習(xí)

2.1 相關(guān)符號與概念

令G=(V，E)表示由變量集V={v1，v2，…，vn}組成的有向無環(huán)圖（Directed Acyclic Graph，DAG），D={X1，X2，…，Xn}表示觀測數(shù)據(jù)集，pa(vi)表示節(jié)點變量vi的父親節(jié)點。兩個不相鄰節(jié)點vi和vj之間的路徑（path）l表示該路徑上的第一個節(jié)點變量為vi，最后一個節(jié)點變量為vj，同時在該路徑上任意兩個相鄰節(jié)點都存在邊相連。在這樣的路徑中，vi是vj的一個祖先節(jié)點，vj是vi的一個子孫節(jié)點。

定義1在G=(V，E)中，如果在兩個不相鄰的變量vi和vj之間存在路徑l并滿足以下條件：

1）l包含一條鏈vi→z→vj或一個分叉vi←z→vj，其中，z∈Z。

2）l包含一個碰撞（又稱V-結(jié)構(gòu)［6］）vi→z←vj，其中，z及其子孫節(jié)點都不包含在Z中，則稱變量vi與vj被Z集合d-分離，或稱變量vi與vj被Z集合阻斷。

LIU 等［14］指出，d-分離可以被擴展到變量集中，在忠誠性假設(shè)下，如果存在兩個不相連的變量集A和變量集B，則滿足：?μ∈A，?ν∈B，μ、ν被Z集 合d-分離，則變量集A和變量集B被Z集合d-分離。

基于上述定義，本文給出因果關(guān)系的相關(guān)定義。根據(jù)PEARL 的圖模型理論，其對于因果貝葉斯網(wǎng)絡(luò)的定義［5］為：

定義2令P(v)表示變量集V的分布，Px(v)表示變量v經(jīng)過干預(yù)do(X=x)后得到的干預(yù)分布，其中，X?V，即將部分變量v的集合X值設(shè)為某個常數(shù)x，P*表示干預(yù)分布Px(v)和非干預(yù)分布P(v)的集合。在一個DAG 中，對于所有Px∈P*，當(dāng)且僅當(dāng)DAG 滿足以下三個條件，則稱G是分布P*相對應(yīng)的貝葉斯因果網(wǎng)絡(luò)：1）Px(v)是G的馬爾可夫類；2）對于所有Vi∈X，當(dāng)vi與X=x一致時，則Px(vi)=1；3）對于所有Vi?X，當(dāng)pai與X=x一致時，則Px(vi|pai)=P(vi|pai)，其中，pai表示變量vi的父親變量。

2.2 算法框架

本文基于因果圖模型，給出因果分解的定義。

因果分解實例示意圖如圖1所示，假設(shè)圖1（a）由變量集V學(xué)習(xí)得到的無向獨立圖，則它的因果分解為圖1（b）所示的5 個子集：C1={V1，V3，V4}，C2={V3，V4，V6}，C3={V6，V7，V8}，C4={V3，V6，V7}，C5={V2，V3，V5，V7}。

圖1 因果分解實例示意圖Fig.1 Schematic diagram of example for causal decomposition

因此，變量集V的因果結(jié)構(gòu)學(xué)習(xí)問題可以被轉(zhuǎn)換為m個子集{C1，C2，…，Cm}上的子結(jié)構(gòu)學(xué)習(xí)問題。該分解過程可以被遞歸地執(zhí)行，直到子問題小到預(yù)先設(shè)定的特定閾值θ。本文提出的遞歸因果結(jié)構(gòu)學(xué)習(xí)算法CADR 如算法1 所示。

算法1遞歸因果結(jié)構(gòu)學(xué)習(xí)算法CADR

該算法的輸入包括樣本集D、變量集V、因果分解閾值θ，以及特定的因果結(jié)構(gòu)學(xué)習(xí)算法Ag。當(dāng)分解后的子問題足夠小（達到閾值θ）時，遞歸分解結(jié)束。同時，Ag用于從無法被分解的子問題中進行因果關(guān)系發(fā)現(xiàn)；否則，繼續(xù)分解為m個更小的子集。算法1的關(guān)鍵是找到一個因果分解C={C1，C2，…，Cm}。

2.3 因果分解學(xué)習(xí)

CADR 算法的關(guān)鍵是通過學(xué)習(xí)得到因果分解。為識別輸入變量之間的潛在因果分解，本文采用條件獨立性檢驗方法得到因果分解，其詳細過程如算法2 所示。

算法2尋找因果分解

首先，通過條件獨立性學(xué)習(xí)變量集V={v1，v2，…，vn}的一個無向獨立圖A，表示各變量之間的條件獨立性（是否有邊連接），Aij=1 表示變量vi和vj之間有邊連接，在2.4 節(jié)將會給出學(xué)習(xí)UIG 的詳細過程；然后，利用XIE 等［12］提出的方法，把變量集V分解成m個團（cliques）：C={C1，C2，…，Cm}，即需要尋找的因果分解。

本文通過上述方法將高維復(fù)雜的因果結(jié)構(gòu)學(xué)習(xí)任務(wù)分解到合適的維度上進行學(xué)習(xí)，縮小條件獨立性檢驗的搜索空間，進而獲得更精準(zhǔn)的因果結(jié)構(gòu)。

2.4 無向獨立圖學(xué)習(xí)

現(xiàn)有基于馬爾可夫毯［27］發(fā)現(xiàn)算法和偏相關(guān)方法都可用于無向獨立圖的發(fā)現(xiàn)，然而，基于馬爾可夫毯的算法因恢復(fù)出精確的道德圖，導(dǎo)致算法復(fù)雜度增大。在實際中，除道德圖的邊和骨架的邊以外，一些額外的邊在UIG 中也是允許存在的［14］。

基于偏相關(guān)的方法只能運用在線性高斯數(shù)據(jù)中，無法在非線性非高斯的情況下使用。而基于核空間的條件獨立性檢驗方法則適用于非線性非高斯的情況，如HSIC、KCIT 等方法，但是當(dāng)變量集較大而樣本量較少時，條件獨立性檢驗的結(jié)果則變得不準(zhǔn)確。此外，基于核的方法在樣本量較大時，其時間復(fù)雜度也較高。針對該問題，STROBL 等［28］基于隨機傅里葉特征方法提出非參數(shù)條件獨立檢驗算法RCIT。

RCIT 算法通過隨機傅里葉特征算法k(x，y)=E[ζ(x)，ζ(y)]，將變量映射到一個低維的歐幾里得空間，如式（1）所示：

因此，本文結(jié)合RCIT 方法提出一種q-order 條件獨立性檢驗方法。其中，q表示條件候選集S大小的閾值。為構(gòu)造一個無向獨立圖A，首先從一個完全有向圖出發(fā)，在給定條件候選集S的情況下檢驗兩個節(jié)點變量vi和vj的條件獨立性進行刪邊操作，如果獨立，則刪除vi與vj之間的邊，即Aij=Aji=0。條件候選集S的大小k從0 開始依次增加，且每次迭代其大小滿足：|S|≤q。通過逐步增加條件候選集的大小，可以有效地縮減算法條件候選集的搜索空間，提高算法運行效率。算法偽代碼如算法3 所示。

算法3學(xué)習(xí)無向獨立圖UIG

2.5 馬爾可夫等價類識別

無向獨立圖學(xué)習(xí)是基于約束的方法實現(xiàn)的，而基于約束的方法通過依次檢驗每對節(jié)點的條件獨立性來判斷是否存在邊，進而得到一個基本骨架。該基本骨架根據(jù)V-結(jié)構(gòu)和其他一些規(guī)則，如Meek’s rules［29］盡可能多地確定邊的因果方向［30］。但這種做法會存在馬爾可夫等價類的問題，無法確定方向的因果邊。假設(shè)存在一個局部結(jié)構(gòu)x-z-y，且x⊥y|Z，根據(jù)定義1，如果存在一個變量z?Z，且其任何子孫都不包含在Z中，則確定該局部結(jié)構(gòu)為一個V-結(jié)構(gòu)：x→z←y。當(dāng)z∈Z時，則無法通過條件獨立性來確定該局部結(jié)構(gòu)的因果方向，即該結(jié)構(gòu)是一個馬爾可夫等價類。在給出定理1 的前提下，V-結(jié)構(gòu)的可識別性可以通過定理2 來保證。

定理1在因果馬爾可夫和因果忠誠性假設(shè)下，當(dāng)且僅當(dāng)兩個DAG 具有相同的V-結(jié)構(gòu)時，即兩個聚合的箭頭，其尾部沒有箭頭連接，它們在觀測上是等價的［5］。

定理2在因果馬爾可夫和因果忠誠性假設(shè)下，V-結(jié)構(gòu)是可識別的。

證明在因果馬爾可夫和因果忠誠性假設(shè)下，如果V-結(jié)構(gòu)不可識別，那么存在兩個結(jié)構(gòu)G和G'，使得{vi，vj，vk}在G中是V-結(jié)構(gòu)，在G'上不是V-結(jié)構(gòu)，且該兩個結(jié)構(gòu)是等價的。根據(jù)定理1，若兩個結(jié)構(gòu)等價，則一定存在相同的V-結(jié)構(gòu)，所以矛盾。因此，V-結(jié)構(gòu)可識別。

對于通過條件獨立性檢驗方法得到的無向圖，可以先識別V-結(jié)構(gòu)，確定相應(yīng)的因果方向。此時，需要解決的問題：當(dāng)z∈Z時，如何確定因果方向。

針對這一問題，受因果函數(shù)模型的啟發(fā)，本文考慮利用加性噪聲模型識別在馬爾可夫等價類變量之間的因果關(guān)系，其識別方法通過定理3 來驗證。

定理3假設(shè)一組變量集合V由非線性非高斯加性噪聲模型生成，其所有子集相應(yīng)的子結(jié)構(gòu)都滿足忠誠性假設(shè)，且存在兩個隨機變量x，y∈V以及由其他變量組成的集合Z滿足x⊥y|Z，并存在z∈Z與x，y相連。nxz或nyz表示利用z回歸x或y得到的殘差，當(dāng)x⊥nxz（或y⊥nyz）成立時，則z是x的原因，即z→x（或z是y的原因：z→y）。

基于定理3，得到馬爾可夫等價類的識別方法。首先，根據(jù)條件獨立性檢驗得到無向圖，結(jié)合定義1識別V-結(jié)構(gòu)；其次，在剩余未定向的結(jié)構(gòu)中根據(jù)定理3確定其邊的因果方向。通過上述方法獲取到包含更多因果邊信息的因果圖，從而解決馬爾可夫等價類問題。

2.6 時間復(fù)雜度分析

CADR 算法的時間復(fù)雜度主要取決于條件獨立性檢驗的次數(shù)。在CADR 算法中，原始變量集合V={v1，v2，…，vn} 被因果分解為m個子集C={C1，C2，…，Cm}，且|Cm|≤n，則該求解因果分解集合的時間復(fù)雜度為，其中，kmax表示子集變量最多的數(shù)量，kmax=max(|C1|，|C2|，…，|Cm|)。同 時，CADR 算法還需要計算每次迭代過程中條件獨立性檢驗的次數(shù)。基于無向獨立圖進行q階條件獨立性檢驗的每次迭代都需要遍歷所有變量對，其時間復(fù)雜度為O(nq+2)。因此，CADR 算法的時間復(fù)雜度為。當(dāng)數(shù)據(jù)維度高于100，q設(shè)置為3 時，CADR 可以得到準(zhǔn)確的實驗結(jié)果，且縮短運行時間。

3 實驗與結(jié)果分析

本文通過大量的仿真數(shù)據(jù)實驗以及真實貝葉斯網(wǎng)絡(luò)實驗來驗證CADR 算法的有效性，并與XIE等［12］提出的遞歸因果結(jié)構(gòu)學(xué)習(xí)方法（Xie_rec）、傳統(tǒng)PC+ANM 的方法（PC_ANM）、ZHENG［31］等提出的非參數(shù)因果結(jié)構(gòu)學(xué)習(xí)方法（Notear_Sob）進行對比。實驗指標(biāo)為召回率（Recall）、精確率（Precision）和F1評分。實驗環(huán)境為Intel?CoreTMi7-9750H CPU @ 2.60 GHz，編程環(huán)境為Python 3.7。

3.1 仿真數(shù)據(jù)實驗

本文在非線性非高斯模型假設(shè)下仿真因果貝葉斯網(wǎng)絡(luò)數(shù)據(jù)，數(shù)據(jù)生成方式與CAI 等［13］提出的方法類似。在仿真實驗中，首先隨機生成一組根節(jié)點，其次迭代地隨機選擇根節(jié)點，并將其作為父親節(jié)點來生成后代節(jié)點，其數(shù)據(jù)產(chǎn)生機制表示為：

其中：f(·)表示非線性函數(shù)，從{x2，x3，sin(x)，cos(x)}中隨機選取；噪聲ni服從非高斯分布。

本文的仿真數(shù)據(jù)實驗基于不同維度和樣本量設(shè)置一系列隨機實驗，其變量維度范圍為var=｛10，20，30，40，50｝，樣本大小為n_sample=｛100，200，300，400，500｝。基于不同的參數(shù)設(shè)置，隨機生成因果圖，根據(jù)非線性非高斯結(jié)構(gòu)方程模型隨機生成數(shù)據(jù)，得到不同參數(shù)設(shè)置下的樣本。

在仿真數(shù)據(jù)實驗中，本文考慮到非線性非高斯加性噪聲在維度小于7 時的實驗效果較好，因此，當(dāng)因果分解時子集的大小閾值θ設(shè)置為6，在條件獨立性檢驗中，設(shè)條件候選集的大小閾值q=3。每個變量維度和樣本量的組合數(shù)據(jù)實驗都重復(fù)20 次，取每組實驗結(jié)果的平均值作為評價指標(biāo)。

不同算法的仿真實驗結(jié)果如圖2 所示。從圖2可以看出：CADR 算法的因果結(jié)構(gòu)學(xué)習(xí)效果比其他三種因果結(jié)構(gòu)發(fā)現(xiàn)算法更好。在不同的樣本量上（如圖2（a）所示），CADR 算法幾乎在所有樣本量的F1 評分都要優(yōu)于其他三種算法。同時，本文在不同變量維度的情況下（如圖2（b）所示）的實驗效果優(yōu)于其他三種算法的效果。基于遞歸分解的算法Xie_rec 的F1 評分優(yōu)于傳統(tǒng)算法PC_ANM 和Notear_Sob 算法，且其效果差距隨變量數(shù)的增加而不斷增加。基于遞歸分解的算法將高維小樣本的因果結(jié)構(gòu)學(xué)習(xí)轉(zhuǎn)化到低維，以有效緩解原本在高維因果結(jié)構(gòu)學(xué)習(xí)樣本量不足的問題。在樣本量不變、維度減小的情況下，基于遞歸分解算法的計算準(zhǔn)確率得到提升。在基于遞歸分解的算法中，CADR 在實驗中的F1 評分高于Xie_rec，Xie_rec 方法經(jīng)過條件獨立性檢驗后，只是通過V-結(jié)構(gòu)和其他一些定向規(guī)則來確定因果方向，可能存在部分無法識別的無向邊，而CADR 算法可以有效區(qū)分馬爾可夫等價類，得到一個完全有向的因果結(jié)構(gòu)。

圖2 不同算法的仿真實驗結(jié)果對比Fig.2 Simulated experimental results comparison among different algorithms

3.2 馬爾可夫等價類識別實驗

為進一步評估CADR 算法在因果推斷的優(yōu)勢，本文對比CADR 算法和Xie_rec 算法在因果結(jié)構(gòu)學(xué)習(xí)的能力。CADR 與Xie_rec 方法的馬爾可夫等價類識別結(jié)果對比如圖3 所示。真實因果圖如圖3（a）所示，根據(jù)該因果圖，本文通過非線性非高斯結(jié)構(gòu)方程模型生成數(shù)據(jù)，并在樣本量足夠的情況下把兩種算法應(yīng)用到該數(shù)據(jù)中，以恢復(fù)真實因果圖。圖3（b）和圖3（c）所示為由CADR 算法和Xie_rec 算法學(xué)習(xí)得到的因果圖。

圖3 CADR 與Xie_rec 方法的馬爾可夫等價類識別結(jié)果對比Fig.3 Recognition results of Markov equivalence classes comparison among CADR and Xie_rec methods

通過CADR 可以完全恢復(fù)出真實的因果圖，盡管Xie_rec 能恢復(fù)出正確的骨架和V-結(jié)構(gòu)，但無法區(qū)分馬爾可夫等價類和得到完全有向的因果圖。根據(jù)定理1，CADR 通過原因變量擬合結(jié)果變量以得到噪聲，并利用非線性非高斯數(shù)據(jù)中因果關(guān)系的不可逆性得到因果方向。因此，CADR 算法可以有效區(qū)分馬爾可夫等價類，識別出所有邊的方向，得到一個完全有向的因果圖。

3.3 真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)實驗對比

本文在非線性非高斯加性噪聲的模型下，通過對不同的真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)進行對比，并根據(jù)實驗結(jié)果評估本文所提的CADR 算法。這些真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)一般涵蓋各種應(yīng)用，包括醫(yī)學(xué)研究的Alarm 數(shù)據(jù)集、Pathfinder 數(shù)據(jù)集、天氣預(yù)測的Hailfinder 數(shù)據(jù)集、系統(tǒng)故障診斷的Win95pts 數(shù)據(jù)集以及智能教學(xué)指導(dǎo)系統(tǒng)的Andes 數(shù)據(jù)集、豬育種系譜Pigs 數(shù)據(jù)集以及基因調(diào)控網(wǎng)絡(luò)Link 數(shù)據(jù)集。表1所示為真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計數(shù)據(jù)。從表1 可以看出：貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)中變量的父親節(jié)點（最大入度）均不超過6，說明真實因果網(wǎng)絡(luò)結(jié)構(gòu)具有稀疏性的特點。

表1 真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計數(shù)據(jù)Table 1 Statistical data of real Bayesian network structure

當(dāng)樣本量設(shè)置為變量數(shù)的3 倍時，本文將實驗得到的召回率、精確率和F1 評分作為評價指標(biāo)。真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的評價指標(biāo)如表2 所示，加粗表示最優(yōu)的數(shù)據(jù)。CADR 算法在所有真實結(jié)構(gòu)上具有更優(yōu)的精確率和F1評分，驗證本文提出的CADR 算法的有效性，特別是在高維的情況下。CADR 算法在不同數(shù)據(jù)集上的運行時間均低于其他算法。從表2 可以看出：CADR算法在因果結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確率和效率方面具有較優(yōu)的效果。實驗結(jié)果表明，CADR 算法在高維小樣本數(shù)據(jù)的因果結(jié)構(gòu)學(xué)習(xí)問題上具有較強的識別能力，能夠提升因果結(jié)構(gòu)學(xué)習(xí)的效率和識別正確率。

表2 真實貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的實驗結(jié)果Table 2 Experimental results of real Bayesian network structures

4 結(jié)束語

本文提出一種基于遞歸分治方法的因果結(jié)構(gòu)學(xué)習(xí)算法CADR，用于高維小樣本數(shù)據(jù)的因果關(guān)系學(xué)習(xí)。通過因果分解方法把基于高維變量集的因果推斷問題逐步分解為維度更小的子問題。結(jié)合RCIT和PC-style 提出一種高效的算法，以得到一個無向獨立圖，從而減少條件獨立性檢驗的次數(shù)。同時，采用遞歸因果分解把得到的骨架分解為更小的子圖，減小下一步條件獨立性檢驗的搜索空間。在此基礎(chǔ)上，利用非線性非高斯加性噪聲模型的因果關(guān)系識別馬爾可夫等價類。實驗結(jié)果表明，CADR 可以得到較為精確的因果圖，能有效提高算法的效率和條件獨立性檢驗的準(zhǔn)確率。下一步將針對稠密網(wǎng)絡(luò)的因果結(jié)構(gòu)學(xué)習(xí)進行研究，以提高CADR 的穩(wěn)健性。