謝 峰,曾 艷

1(北京大學(xué) 概率統(tǒng)計(jì)系,北京 100871)

2(清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,北京 100084)

1 引 言

近年來,基于觀測(cè)數(shù)據(jù)的因果結(jié)構(gòu)學(xué)習(xí)研究,即因果發(fā)現(xiàn)(causal discovery),引起了越來越多學(xué)者的關(guān)注,并被廣泛應(yīng)用在神經(jīng)學(xué)、經(jīng)濟(jì)學(xué)等領(lǐng)域中[1-6].傳統(tǒng)的因果結(jié)構(gòu)學(xué)習(xí)算法通常被分為兩大類:基于約束的(constraint-based)算法,例如Peter Clark(PC)[7],Grow-Shrink(GS)[8],Fast Causal Inference(FCI)[9],Really Fast Causal Inference(RFCI)[10]和Iterative Causal Discovery(ICD)[11]算法,和基于評(píng)分的算法,例如Greedy Equivalence Search(GES)[12],Fast Greedy Equivalence Search(FGES)[13],GOBNILP-DEV[14]等算法.然而,上述多數(shù)方法輸出的因果結(jié)構(gòu)屬于馬爾科夫等價(jià)類,即它們不能夠找到唯一一個(gè)完整的有向無環(huán)圖(Directed Acyclic Graph,DAG)[15].

在線性系統(tǒng)下,為了解決因果結(jié)構(gòu)唯一性的問題,Shimizu等人[16,17]提出了線性非高斯無環(huán)模型(Linear Non-Gaussian Acyclic Models,LiNGAM).相較于傳統(tǒng)的方法相比,該模型引入了非高斯性的假設(shè)從而能夠有效區(qū)分馬爾科夫等價(jià)類而獲得唯一的因果網(wǎng)絡(luò).針對(duì)LiNGAM模型的估計(jì)方法包含了基于獨(dú)立成分分析(Independent Component Analysis,ICA)的ICA-LiNGAM算法[16],基于獨(dú)立性的直接估計(jì)因果次序的DirectLiNGAM算法[18],其改進(jìn)版本成對(duì)比較的Pairwise-LiNGAM算法[19]等.之后Xie等人[20]利用信息熵的方式,提出了兩階段迭代的Entropy-based Two-Phase Iterative Algorithm(EPTIA)算法,來估計(jì)LiNGAM模型.除此之外,研究學(xué)者從不同的角度對(duì)該模型進(jìn)行改進(jìn)分析:含隱變量的LiNGAM模型,如基于完備ICA的方法[21,22],RCD算法[23]等;時(shí)序數(shù)據(jù)的SVAR(Structural Vector Auto Regression)模型,如基于改進(jìn)LiNGLAM似然的方法[24],基于不等約束的方法[25]和基于廣義矩估計(jì)的方法[26];非線性的ANM模型[27,28];隱變量/因子(Latent Variables/Factors)的因果結(jié)構(gòu)學(xué)習(xí)[29,30];以及從評(píng)分的角度,提出改進(jìn)的似然函數(shù)進(jìn)行評(píng)分,從而學(xué)習(xí)因果結(jié)構(gòu),如Structural Equational Embedded Likelihood(SELF)[31]和Notears[32]算法等.

然而,上述的算法在學(xué)習(xí)無隱變量的結(jié)構(gòu)時(shí),大多數(shù)通常是以自頂向下的方式來估計(jì)因果次序,再學(xué)習(xí)因果結(jié)構(gòu).也就是說,它們通過優(yōu)先選擇根節(jié)點(diǎn)的方式來確定因果次序[18-20].這種自頂向下的估計(jì)方式會(huì)存在如下問題:在迭代確定因果次序的過程中,每次選擇完一個(gè)根節(jié)點(diǎn)后,它們都需要不斷地更新原始數(shù)據(jù),從而引入額外的誤差使得算法的識(shí)別準(zhǔn)確率降低[33].特別地來說,當(dāng)數(shù)據(jù)的維度越高時(shí),這個(gè)問題帶來的影響則會(huì)越明顯.為了解決這個(gè)問題,近來,Zeng等人[33]采取自底向上的方式來識(shí)別因果次序,并提出了優(yōu)先選擇葉子節(jié)點(diǎn)的算法(Giving Priority of Leaf Nodes,GPL).盡管文獻(xiàn)[33]提供了完整的理論和證明了GPL算法的準(zhǔn)確性,但是其理論和證明需要滿足一個(gè)額外的假設(shè),即數(shù)據(jù)背后真實(shí)的因果結(jié)構(gòu)滿足因果樹假設(shè).因果樹結(jié)構(gòu)是一類特殊的DAG,并具有以下性質(zhì):因果樹中的任意兩個(gè)節(jié)點(diǎn)有且僅有1條路徑.當(dāng)數(shù)據(jù)本身不滿足因果樹假設(shè)時(shí),GPL算法便會(huì)輸出不可靠的因果網(wǎng)絡(luò).

因此,針對(duì)以上所述問題,本文提出了一種基于葉節(jié)點(diǎn)性質(zhì)和互信息的因果結(jié)構(gòu)估計(jì)方法(Causal Structure estimate method based on Leaf and Mutual information),并簡(jiǎn)寫為CSLM.具體來說,考慮到非因果樹結(jié)構(gòu)下,任意兩個(gè)變量間可能存在混淆因子,為此本文利用變量與殘差間的獨(dú)立性去識(shí)別是否存在混淆因子,若存在需要剔除該混淆因子的因果影響;此外考慮到葉子節(jié)點(diǎn)在因果網(wǎng)絡(luò)中是一種特殊的節(jié)點(diǎn),即該節(jié)點(diǎn)不會(huì)影響剩余任意節(jié)點(diǎn),基于互信息的方式去度量變量間的獨(dú)立性從而找到獨(dú)立性最小的節(jié)點(diǎn)即為葉子節(jié)點(diǎn).本文的主要貢獻(xiàn)總結(jié)如下:

1)提出了一種新的估計(jì)LiNGLAM的CSLM方法.該CSLM算法以自底向上的方式估計(jì)因果次序.與經(jīng)典的自頂向下的算法相比,CSLM在數(shù)據(jù)維度較大的情況下具有更高的識(shí)別準(zhǔn)確率;

2)解決了自底向上的方法需要假設(shè)網(wǎng)絡(luò)為因果樹的形式,使得算法更加通用且更符合實(shí)際場(chǎng)景;

3)在虛擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行結(jié)構(gòu)學(xué)習(xí),與最新的方法相比,證明了CSLM算法的有效性.

2 預(yù)備知識(shí)

LiNGAM模型是由Shimizu等人[16,17]首次提出,該模型因其能夠打破傳統(tǒng)的馬爾可夫等價(jià)類,從而能夠識(shí)別變量間的因果方法而得到廣泛關(guān)注.LiNGAM模型的基本設(shè)定是:變量間的因果生成機(jī)制滿足線性結(jié)構(gòu)方程模型,不失一般性,假定變量的均值為0,那么可以表達(dá)為如下形式:

(1)

其中,i={1,…,n},xi表示可觀測(cè)變量;bij表示DAG中變量xj到xi的連接強(qiáng)度;ei表示噪聲變量,服從非零方差的非高斯分布,且彼此間相互獨(dú)立;K(i)表示變量xi的整個(gè)網(wǎng)絡(luò)中的因果次序.

當(dāng)數(shù)據(jù)滿足以下3個(gè)基本的假設(shè):1)數(shù)據(jù)產(chǎn)生過程滿足公式(1),即線性假設(shè);2)因果充分性假設(shè),即不存在隱藏變量;3)噪聲變量ei服從非零方差的非高斯分布.那么該模型為L(zhǎng)iNGAM模型.將式(1)寫成矩陣的形式如下:

X=BX+e

(2)

其中X=[x1,…,xn]T,e=[e1,…,en]T,連接矩陣B存儲(chǔ)了變量與變量之間的連接強(qiáng)度bij.

如考慮如圖1中所示因果結(jié)構(gòu),其因果生成機(jī)制可以表達(dá)為如下形式:

圖1 數(shù)據(jù)生成機(jī)制滿足LiNGLAM的示例

其中因果次序K=[1,2,3,4].

本文的目標(biāo)是如何有效地估計(jì)LiNGAM模型,尤其是高維網(wǎng)絡(luò).具體來講,在給定觀察數(shù)據(jù)X的情況下,求解因果次序K和連接矩陣B,進(jìn)而學(xué)習(xí)完整的因果結(jié)構(gòu).

3 基于葉節(jié)點(diǎn)性質(zhì)和互信息的因果結(jié)構(gòu)學(xué)習(xí)

為了使得算法能有效處理高維數(shù)據(jù),文獻(xiàn)[33]提出了通過自底向上的GPL算法,該方法巧妙地避開了傳統(tǒng)的自頂向下學(xué)習(xí)策略中需要迭代更新數(shù)據(jù)集帶來的級(jí)聯(lián)錯(cuò)誤,提高了高維網(wǎng)絡(luò)下因果網(wǎng)絡(luò)估計(jì)效果.不幸的是,除了LiNGAM模型的基本假設(shè)以外,該方法需要引入額外地假設(shè),即背后的因果網(wǎng)絡(luò)是因果樹(任意兩個(gè)節(jié)點(diǎn)有且僅有1條路徑).盡管有些時(shí)候可以由專家經(jīng)驗(yàn)知識(shí)支撐該假設(shè),但是在多數(shù)情況下,該假設(shè)的引入導(dǎo)致了該方法無法解決非樹模型的局限性.

在本章節(jié)中,首先在2.1小節(jié)中,通過一個(gè)簡(jiǎn)單的例子,說明因果樹假設(shè)帶來的估計(jì)問題,以及解決的方法.緊接著,在2.2小節(jié)中,會(huì)給出相應(yīng)的理論保證.最后,本文在2.3小節(jié)中,描述了基于葉節(jié)點(diǎn)性質(zhì)和互信息的因果結(jié)構(gòu)學(xué)習(xí)框架,該框架下不需要因果樹假設(shè)的引入,解決范圍更加廣泛.

3.1 直觀示例

接下來,考慮如圖2所示的因果網(wǎng)絡(luò).

圖2 一個(gè)具有3個(gè)節(jié)點(diǎn)的因果結(jié)構(gòu)

圖2所示的結(jié)構(gòu)是一個(gè)具有3個(gè)節(jié)點(diǎn)的因果網(wǎng)絡(luò).由于節(jié)點(diǎn)x1到節(jié)點(diǎn)x3有2條路徑,顯然該結(jié)構(gòu)不滿足因果樹假設(shè).從獨(dú)立性的角度出發(fā),可以發(fā)現(xiàn):

對(duì)于節(jié)點(diǎn)x1,有:

x1⊥x2-E(x2|x1)&x1⊥x3-E(x3|x1)

然而對(duì)于節(jié)點(diǎn)x2,有:

x2⊥/x1-E(x1|x2)&x2⊥/x3-E(x3|x2)

同時(shí)對(duì)于節(jié)點(diǎn)x3,有:

x3⊥/x1-E(x1|x3)&x3⊥/x2-E(x2|x3)

由文獻(xiàn)[33]的理論可知,在因果樹假設(shè)成立的條件下,葉子節(jié)點(diǎn)具有獨(dú)立性最弱的性質(zhì),即葉子節(jié)點(diǎn)xj均不獨(dú)立于與其余變量分別做回歸的所有殘差xj-E(xi|xj),i≠j.所以,在圖2不滿足因果樹假設(shè)的結(jié)構(gòu)中,節(jié)點(diǎn)x2和節(jié)點(diǎn)x3與其余變量對(duì)應(yīng)的殘差都不獨(dú)立.如果使用GPL算法來學(xué)習(xí)因果次序,則有可能會(huì)將節(jié)點(diǎn)x2作為葉子節(jié)點(diǎn)輸出.然而,x2并不是葉子節(jié)點(diǎn).因此,如果數(shù)據(jù)不滿足因果樹假設(shè),GPL算法的理論便會(huì)出現(xiàn)問題,且算法的識(shí)別準(zhǔn)確率會(huì)降低.其本質(zhì)原因在于x1是x2和x3間的混淆因子,影響了成對(duì)變量獨(dú)立性測(cè)試的結(jié)果.

為此,如果想解決非因果樹的結(jié)果,即去除該假設(shè),為此需要提前確定任意兩個(gè)變量間是否含有混淆因子,如果含有,需要提前局部地剔除該變量對(duì)其余變量的影響,從而避開混淆因子帶來的影響.例如重新考慮上述例子,發(fā)現(xiàn)x2和x3都可能是葉子節(jié)點(diǎn),這個(gè)時(shí)候,如果同時(shí)給定變量x1變量后,會(huì)幫助找到x3是葉子節(jié)點(diǎn),即:

x2⊥/x2-E(x2|x1,x3)&x3⊥x3-E(x3|x1,x2)

總結(jié)來說,為了讓算法更廣泛,需要測(cè)試變量間的混淆因子并剔除該混淆因子的影響,從而自底向上的學(xué)習(xí)整個(gè)網(wǎng)絡(luò).

3.2 理論分析

為了解決混淆因子所引起的因果樹假設(shè)問題,需要利用混淆因子的性質(zhì)來識(shí)別它們,并去除掉混淆因子對(duì)其余節(jié)點(diǎn)的影響.

首先給出了混淆因子的性質(zhì).在此之前,需要給出一個(gè)刻畫非高斯數(shù)據(jù)集獨(dú)立性的重要定理.

[D-S定理[34]]給定兩個(gè)隨機(jī)變量x1和x2是由獨(dú)立的隨機(jī)變量線性組合而成,即:

那么,如果存在獨(dú)立隨機(jī)變量ei服從非高斯分布且λiγy≠0,那么隨機(jī)變量x1和x2是統(tǒng)計(jì)依賴的.

定理1. 假設(shè)觀察數(shù)據(jù)集X滿足LiNGAM模型,當(dāng)且僅當(dāng)xi與xj之間存在混淆因子時(shí),xi⊥/xi-E(xi|xj)和xj⊥/xj-E(xj|xi)成立.

證明:定理1的證明,需要從充分性與必要性兩方面來證明.

首先考慮充分性.因?yàn)闂l件xi⊥/xi-E(xi|xj)和xj⊥/xj-E(xj|xi)都成立,那么變量xi與xj之間一定不獨(dú)立.根據(jù)D-S定理,得到變量xi與xj間一定含有至少一個(gè)相同的噪聲項(xiàng),假設(shè)為ek.根據(jù)線性模型的假設(shè),得到一定至少存在一個(gè)變量包含噪聲ek且同時(shí)指向變量xi與xj,由此可知,xi與xj之間存在混淆因子.

現(xiàn)在考慮xi與xj之間存在混淆因子的情況.假設(shè)該混淆因子為xk.那么根據(jù)線性回歸公式,殘差xi-E(xi|xj)和xj-E(xj|xi)一定含有xk的噪聲項(xiàng)exk.根據(jù)D-S定理,能夠得到xi⊥/xi-E(xi|xj)和xj⊥/xj-E(xj|xi)成立.

定理1證明完畢!

由定理1可知,給定任意兩個(gè)節(jié)點(diǎn)xi與xj,如果xi不獨(dú)立于xi-E(xi|xj),且xj不獨(dú)立于xj-E(xj|xi),則說明這兩個(gè)節(jié)點(diǎn)之間至少存在一個(gè)混淆因子.此時(shí),只需要在其余所有節(jié)點(diǎn)上依次對(duì)xi與xj做回歸,即可將混淆因子對(duì)節(jié)點(diǎn)xi與xj的影響去除,因?yàn)樵诜腔煜蜃由献龌貧w對(duì)原有節(jié)點(diǎn)與殘差之間的獨(dú)立性是沒有影響的.根據(jù)定理1,可以推斷出葉子節(jié)點(diǎn)的性質(zhì).

定理2. 假設(shè)觀察數(shù)據(jù)集X滿足LiNGAM模型,那么,對(duì)于變量xi和其余任意相關(guān)的變量xj,j≠i,不存在一個(gè)子集S∈X滿足xj⊥xj-E(xj|xi,S),那么xi為葉子節(jié)點(diǎn).換句話說,當(dāng)xi與其余所有的殘差都不獨(dú)立時(shí),xi為葉子節(jié)點(diǎn).

證明:從文獻(xiàn)[30]中的命題1可得,在給定某個(gè)變量,如xi的所有父節(jié)點(diǎn)Pa(xi)時(shí),xi⊥xi-E(xi|Pa(xi)),而給定其后代節(jié)點(diǎn)時(shí),xi⊥/xi-E(xi|Des(xi)).因?yàn)槿~子節(jié)點(diǎn)的性質(zhì),沒有后代節(jié)點(diǎn),那么不會(huì)存在后者的情況,即xi與其余所有的殘差都會(huì)不獨(dú)立.因此xi為葉子節(jié)點(diǎn).證畢!

定理2描述了葉子節(jié)點(diǎn)獨(dú)立性最弱的性質(zhì).值得注意的是,該定理無需假設(shè)數(shù)據(jù)是由因果樹生成的.

3.3 CSLM算法

根據(jù)2.2小節(jié)中的理論分析,本小節(jié)將介紹一種基于葉節(jié)點(diǎn)性質(zhì)和互信息的因果結(jié)構(gòu)估計(jì)方法,即CSLM.其基本框架為:

第1步.首先成對(duì)地計(jì)算每一個(gè)節(jié)點(diǎn)與其余任意節(jié)點(diǎn)做回歸后的每一個(gè)殘差之間的獨(dú)立性;考慮到連續(xù)數(shù)據(jù)的獨(dú)立性衡量,實(shí)際中采用核互信的方法衡量?jī)蓚€(gè)變量z1和z2的獨(dú)立性[35].具體來說,例如z1和z2的互信息可以表示為如下形式:

第2步.緊接著根據(jù)這成對(duì)的節(jié)點(diǎn)是否都與殘差獨(dú)立,來判斷是否存在混淆因子,一旦存在混淆因子,即xi⊥/xi-E(xi|xj)和xj⊥/xj-E(xj|xi)成立,則去除混淆因子對(duì)這對(duì)節(jié)點(diǎn)的影響;

第3步.根據(jù)獨(dú)立性強(qiáng)弱(核互信息的大小)以自底向上的方式確定因果次序;

第4步.最后,通過剪枝步驟,如基于Lasso的最小二乘回歸法,獲得最終的因果結(jié)構(gòu).

該算法的偽代碼詳細(xì)流程如下:

算法1.CSLM算法

輸入:數(shù)據(jù)集X

輸出:因果次序K和連接矩陣B

1.標(biāo)準(zhǔn)化處理數(shù)據(jù)集X并初始化獨(dú)立性矩陣M為零矩陣,因果次序K為空集,變量下標(biāo)集合U為空集;

2.Repeat:

3. 計(jì)算xi與xi-E(xi|xj)、xj與xj-E(xj|xi)的核互信息,用于衡量之間的獨(dú)立性,并分別存儲(chǔ)在Mij與Mji中;

4. ifxi不獨(dú)立于xi-E(xi|xj),且xj不獨(dú)立于xj-E(xj|xi)://尋找混淆因子;

5. Repeat:

6. 在xk,k≠i,j上分別對(duì)xi與xj做回歸;

7. Untilxi不獨(dú)立于xi-E(xi|xj)且xj不獨(dú)立于xj-E(xj|xi)不成立;//去除混淆因子對(duì)節(jié)點(diǎn)xi與xj的影響;

8. 重新計(jì)算xi與xi-E(xi|xj)、xj與xj-E(xj|xi)的核互信息,并存儲(chǔ)在矩陣Mij與Mji中;

9.Until 所有的成對(duì)變量都已考慮;

10.Repeat:

11. 通過公式(3),尋找獨(dú)立性最弱的變量xm作為葉子節(jié)點(diǎn):

(3)

12. 將m加入到K中;

13.Until 所有節(jié)點(diǎn)的下標(biāo)都已加入到K中;

14.輸入X與K,使用基于Lasso的最小二乘回歸法對(duì)因果結(jié)構(gòu)進(jìn)行剪枝,并輸出連接矩陣B.

復(fù)雜度分析:這里分析算法主體兩個(gè)部分的復(fù)雜度.令n為網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù),m為樣本量,P為整個(gè)網(wǎng)絡(luò)中最大父節(jié)點(diǎn)的個(gè)數(shù).那么在算法的第1步中需要遍歷任意一個(gè)變量與其余所有變量的核互信息,因此復(fù)雜度為O(mn3M2+n4M3),其中M?m為核獨(dú)立性中利用低秩分解找到的最大秩.在第2步驟中,對(duì)于任意一個(gè)變量,如果其父節(jié)點(diǎn)大于等于1個(gè)時(shí),需要找到其混淆節(jié)點(diǎn),因此其復(fù)雜度為O(Pmn3).注意到該過程依賴于父節(jié)點(diǎn)的最大值P,網(wǎng)絡(luò)越稀疏,那么其復(fù)雜度會(huì)越低.最壞的情況,假定網(wǎng)絡(luò)是全連接圖,此時(shí)算法復(fù)雜度將達(dá)到O(mn4).在實(shí)際中,由于大多數(shù)網(wǎng)絡(luò)往往是稀疏的,因此運(yùn)行中不會(huì)達(dá)到n的4次冪.

4 實(shí)現(xiàn)與結(jié)果分析

為了驗(yàn)證本文提出算法的有效性,本文使用了虛擬結(jié)構(gòu)數(shù)據(jù)集和真實(shí)結(jié)構(gòu)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).具體來說,在4.1小節(jié)中,使用了虛擬結(jié)構(gòu)數(shù)據(jù)集并選取了最新的GPL算法[33]進(jìn)行實(shí)驗(yàn)對(duì)比.GPL算法與本文算法都是以自底向上的方式來學(xué)習(xí)因果結(jié)構(gòu),但不同的是,GPL算法需要假設(shè)數(shù)據(jù)是服從因果樹假設(shè)的.因此,在這一小節(jié)中,通過改變因果樹假設(shè)的違背程度,來分析和比較當(dāng)假設(shè)違背時(shí)各個(gè)算法的結(jié)果.此外,在因果樹假設(shè)完全違背的情況下,也分析了算法受樣本量大小的影響.在4.2小節(jié)中,本文從貝葉斯網(wǎng)絡(luò)存儲(chǔ)庫中選擇了4種不同領(lǐng)域下的真實(shí)結(jié)構(gòu)來進(jìn)行實(shí)驗(yàn),并選取了主流的GPL算法[33]與ETPIA算法[20]進(jìn)行實(shí)驗(yàn)對(duì)比.與GPL和本文算法不同的是,ETPIA算法通過自頂向下的方式來學(xué)習(xí)因果結(jié)構(gòu).所以,3.2小節(jié)的目的是為了驗(yàn)證本文算法通過自底向上的方式來學(xué)習(xí)因果結(jié)構(gòu)的有效性.

此外,針對(duì)衡量標(biāo)準(zhǔn),本文選擇了貝葉斯因果網(wǎng)絡(luò)的常用指標(biāo)召回率、準(zhǔn)確率和F1得分.F1得分反映了因果網(wǎng)絡(luò)結(jié)構(gòu)的總體估計(jì)優(yōu)劣,具體為:

召回率=TP/(TP+FN)

準(zhǔn)確率=TP/(TP+FP)

其中,TP表示正確估計(jì)的邊的個(gè)數(shù);FP表示未估計(jì)到的邊的個(gè)數(shù);FN表示錯(cuò)誤估計(jì)的邊的個(gè)數(shù).結(jié)果取20次獨(dú)立實(shí)驗(yàn)的平均值.

4.1 仿真結(jié)構(gòu)數(shù)據(jù)

為了驗(yàn)證本算法在不滿足因果樹假設(shè)情況下的有效性,本小節(jié)主要進(jìn)行了因果樹假設(shè)不同違背程度下的仿真實(shí)驗(yàn).首先選取仿真因果結(jié)構(gòu)的維度大小,通過改變因果結(jié)構(gòu)的平均入度,來設(shè)置因果樹假設(shè)違背的不同程度,從而設(shè)計(jì)對(duì)應(yīng)的控制變量實(shí)驗(yàn).具體地說,設(shè)置仿真因果結(jié)構(gòu)的維度為{6,8,10,12,15},根據(jù)不同的平均入度{1,1.5,2,2.5}隨機(jī)產(chǎn)生相對(duì)應(yīng)的因果骨架.根據(jù)因果骨架與LiNGAM模型,隨機(jī)產(chǎn)生樣本量為{100,500,1000,2000}的實(shí)驗(yàn)數(shù)據(jù).其中,加粗的數(shù)值表示在各個(gè)控制實(shí)驗(yàn)中的默認(rèn)數(shù)值.

圖3(a)、圖3(c)、圖3(e)展示了不同平均入度下的仿真控制實(shí)驗(yàn)結(jié)果.平均入度的數(shù)值越大,意味著越違背因果樹假設(shè).當(dāng)仿真結(jié)構(gòu)的平均入度數(shù)較小時(shí),即因果樹假設(shè)的違背程度不明顯時(shí),GPL算法與本文的算法都取得了令人滿意的結(jié)果.但是,隨著仿真結(jié)構(gòu)的平均入度數(shù)增大,GPL算法的性能下降明顯,而本文算法對(duì)平均入度相對(duì)不敏感,這是因?yàn)楸疚牡乃惴ú恍枰鲆蚬麡涞募僭O(shè).本文的算法始終優(yōu)于對(duì)比算法,這驗(yàn)證了CSLM算法在不同平均入度下的有效性.圖3(b)、圖3(d)、圖3(f)顯示了不同樣本量下的仿真控制實(shí)驗(yàn)結(jié)果.從整體來看,在因果樹假設(shè)完全違背的控制條件下,隨著樣本量的不斷增加,兩種算法的性能也不斷提高.但對(duì)比算法的結(jié)果卻提高不明顯,這是由于GPL算法受制于因果樹假設(shè).而本文算法不需要做該假設(shè),所以效果更優(yōu)于GPL.

圖3 不同平均入度與不同樣本量下的仿真實(shí)驗(yàn)結(jié)果

圖4展示了不同維度下的仿真實(shí)驗(yàn)結(jié)果.當(dāng)因果結(jié)構(gòu)的維度增大時(shí),算法的F1得分都呈現(xiàn)下降的趨勢(shì).這是正常的現(xiàn)象,因?yàn)楫?dāng)固定樣本量與最大平均入度時(shí),維度的增大意味著結(jié)構(gòu)變得更加復(fù)雜且需要的樣本量本應(yīng)更多(但樣本量被固定),所以導(dǎo)致了算法學(xué)習(xí)能力的下降.盡管算法的效果不理想,但本文的CSLM算法始終至少是優(yōu)于對(duì)比算法的,因此體現(xiàn)了本文算法的有效性.

圖4 不同維度下的仿真控制實(shí)驗(yàn)結(jié)果

圖5 不同真實(shí)結(jié)構(gòu)與不同樣本量下的召回率

4.2 真實(shí)結(jié)構(gòu)數(shù)據(jù)

在本節(jié)中,為了說明自底向上學(xué)習(xí)方式的有效性,本文從貝葉斯網(wǎng)絡(luò)存儲(chǔ)庫中選擇了6種不同領(lǐng)域下的真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)來進(jìn)行實(shí)驗(yàn),相應(yīng)的公開數(shù)據(jù)鏈接為https://www.bnlearn.com/bnrepository/.6種真實(shí)結(jié)構(gòu)的主要統(tǒng)計(jì)信息如表1所示.

表1 真實(shí)結(jié)構(gòu)的統(tǒng)計(jì)信息

此處設(shè)計(jì)了不同樣本量{100,500,1000,2000}的對(duì)比實(shí)驗(yàn).對(duì)比方法包含了GPL算法[33]與ETPIA算法[20].實(shí)驗(yàn)結(jié)果在圖4～圖6中展示.

圖6 不同真實(shí)結(jié)構(gòu)與不同樣本量下的準(zhǔn)確率

由圖5～圖7所示,本文的CSLM算法和GPL算法在大多數(shù)情況下都是優(yōu)于EPTIA,這得益于CSLM和GPL算法都是通過自底向上的方式來學(xué)習(xí)因果結(jié)構(gòu)的,由此也說明了這種學(xué)習(xí)方式的有效性.除此之外,作者還發(fā)現(xiàn)CSLM算法在真實(shí)結(jié)構(gòu)SURVEY與SACHS上略優(yōu)于GPL算法,而在維度較大的真實(shí)結(jié)構(gòu)上,兩者的實(shí)驗(yàn)效果基本持平(盡管本文算法稍稍優(yōu)于),這是因?yàn)楫?dāng)真實(shí)結(jié)構(gòu)的平均入度不是很大時(shí)時(shí),GPL算法能保持其學(xué)習(xí)能力;而當(dāng)數(shù)據(jù)維度較大時(shí),兩者算法的學(xué)習(xí)能力同時(shí)又受到了復(fù)雜結(jié)構(gòu)的影響(由3.1小節(jié)的實(shí)驗(yàn)驗(yàn)證可知).

圖7 不同真實(shí)結(jié)構(gòu)與不同樣本量下的F1得分

總的來說,從自底向上的學(xué)習(xí)方式的角度上看,本文的算法至少能保持GPL算法解決高維數(shù)據(jù)的能力,優(yōu)于ETPIA算法;從是否需要做因果樹假設(shè)的角度上看,本文的算法優(yōu)于GPL算法,顯得更加通用與有效.因此,本節(jié)驗(yàn)證了本文算法的穩(wěn)定性與有效性.

5 結(jié)束語

本文針對(duì)現(xiàn)有的基于LiNGAM模型的因果結(jié)構(gòu)學(xué)習(xí)算法難以有效處理高維數(shù)據(jù)且需要額外樹狀假設(shè)的難題,提出了一種通用的因果結(jié)構(gòu)學(xué)習(xí)算法,該算法以自底向上的方式學(xué)習(xí)因果次序,且無需因果樹假設(shè).通過分析因果樹假設(shè)的本質(zhì),并從混淆因子的角度去除混淆因子的影響,從而使得算法更加通用與有效.此外,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的優(yōu)越性.下一步將考慮結(jié)構(gòu)型數(shù)據(jù)下的因果結(jié)構(gòu)學(xué)習(xí).