基于非穩(wěn)態(tài)加性噪聲模型的因果發(fā)現(xiàn)算法

郝志峰,丁凱培,蔡瑞初＊,陳薇

(1. 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,廣東 廣州 510006;2. 汕頭大學(xué)理學(xué)院,廣東 汕頭 515063)

0 引言

挖掘可觀測的時(shí)間序列之間的因果關(guān)系可以幫助人們理解復(fù)雜事物的本質(zhì)和規(guī)律。近年來,因果關(guān)系被廣泛應(yīng)用于深度學(xué)習(xí)[1]、生物信息學(xué)[2]、金融經(jīng)濟(jì)[3]、社會(huì)科學(xué)[4-5]等領(lǐng)域。通常來說,隨機(jī)實(shí)驗(yàn)是挖掘因果關(guān)系的黃金標(biāo)準(zhǔn)[6],但受限于經(jīng)濟(jì)成本和道德倫理方面的約束,隨機(jī)實(shí)驗(yàn)并不總是可行的。因此,如何從可觀測的時(shí)間序列中挖掘因果關(guān)系成為數(shù)據(jù)科學(xué)的主要問題。

當(dāng)前,研究人員已經(jīng)提出了多種恢復(fù)時(shí)序數(shù)據(jù)集的因果結(jié)構(gòu)的方法,常見的有基于約束的方法[7-9]、基于因果函數(shù)模型的方法[10-11]等。然而,大多數(shù)方法都未考慮數(shù)據(jù)集中非穩(wěn)態(tài)擾動(dòng)帶來的影響,進(jìn)而導(dǎo)致方法失效。非穩(wěn)態(tài)擾動(dòng)引起的數(shù)據(jù)分布偏移常見于真實(shí)的應(yīng)用環(huán)境中,由非穩(wěn)態(tài)擾動(dòng)所導(dǎo)致的統(tǒng)計(jì)誤差會(huì)一定程度上打亂數(shù)據(jù)分布,使數(shù)據(jù)分布難以表征。一些學(xué)者嘗試用數(shù)學(xué)工具刻畫非穩(wěn)態(tài)擾動(dòng)的規(guī)律,如文獻(xiàn)[12]提出基于約束的異構(gòu)/非平穩(wěn)因果發(fā)現(xiàn)(CD-NOD)算法,該算法通過引入代理變量從而對非穩(wěn)態(tài)擾動(dòng)進(jìn)行表征,并將包含代理變量的增廣變量集作為因果發(fā)現(xiàn)算法的輸入。CD-NOD算法首先利用PC(Peter-Clark)算法檢測局部因果機(jī)制發(fā)生變化的變量,并恢復(fù)變量的因果骨架圖,然后通過多項(xiàng)定向規(guī)則對因果骨架圖中的無向邊進(jìn)行定向。然而,CD-NOD算法額外假設(shè)數(shù)據(jù)集中非穩(wěn)態(tài)擾動(dòng)是彼此獨(dú)立的,該假設(shè)致使CD-NOD算法無法從不滿足非穩(wěn)態(tài)擾動(dòng)獨(dú)立的數(shù)據(jù)集中恢復(fù)因果結(jié)構(gòu),并且存在馬爾可夫等價(jià)類問題。

針對以上問題,本文基于非穩(wěn)態(tài)擾動(dòng)與時(shí)序信息存在高度相關(guān)性的規(guī)律,在加性噪聲模型的基礎(chǔ)上將非穩(wěn)態(tài)擾動(dòng)刻畫成一項(xiàng)關(guān)于時(shí)序信息的映射并融入模型中,從而提出一種非穩(wěn)態(tài)加性噪聲模型(Nons-ANM)。給出該函數(shù)模型的識別條件,并基于模型的識別條件提出一種兩階段的因果發(fā)現(xiàn)算法。第1階段基于因果結(jié)構(gòu)圖中葉子節(jié)點(diǎn)的噪聲與其余節(jié)點(diǎn)均獨(dú)立的性質(zhì)找到因果次序;基于前階段的因果次序先驗(yàn),第2階段進(jìn)一步移除冗余的父子關(guān)系,最終得到變量集的因果結(jié)構(gòu)。

1 相關(guān)工作

針對觀察數(shù)據(jù)特性的不同,因果發(fā)現(xiàn)方法又可以分為基于時(shí)序觀察數(shù)據(jù)的方法和基于非時(shí)序觀察數(shù)據(jù)的方法[13]。

在非時(shí)序方法中,基于約束的方法通常利用條件獨(dú)立和忠實(shí)性假設(shè)來恢復(fù)變量之間的因果結(jié)構(gòu),經(jīng)典的方法包括文獻(xiàn)[14]介紹的PC算法和文獻(xiàn)[15]介紹的IC(Inductive Causation)算法。這類方法無法解決馬爾可夫等價(jià)類的問題,因此算法最終得到的因果結(jié)構(gòu)圖中可能包含未確定方向的邊。為解決馬爾可夫等價(jià)類的問題,學(xué)者們提出了基于函數(shù)的方法。這種方法的核心思想在于:假設(shè)存在一種表達(dá)力較強(qiáng)的函數(shù)形式能夠刻畫變量之間的關(guān)系。在這種函數(shù)關(guān)系下,結(jié)果變量能夠由原因變量和噪聲變量的某種映射所表征。在一定的約束條件下,變量之間的因果關(guān)系能夠通過檢驗(yàn)原因變量和噪聲變量的獨(dú)立性得出。經(jīng)典的基于函數(shù)的方法包括文獻(xiàn)[16]介紹的非線性加性噪聲模型、文獻(xiàn)[17]介紹的線性非高斯無環(huán)模型和文獻(xiàn)[18]介紹的后非線性因果模型等。

時(shí)序觀察數(shù)據(jù)在時(shí)間維度上伴隨著“原因在前,結(jié)果在后”的特性[13],基于這項(xiàng)特性,非時(shí)序方法能夠向時(shí)序數(shù)據(jù)的場景拓展。典型的有文獻(xiàn)[7]提出的PC瞬時(shí)條件獨(dú)立性(PCMCI)算法,該算法在PC算法的基礎(chǔ)上拓展出恢復(fù)多元時(shí)序數(shù)據(jù)集的因果結(jié)構(gòu)的能力。具體來說,PCMCI算法首先使用 PC算法學(xué)習(xí)得到數(shù)據(jù)集的馬爾可夫等價(jià)類集合,然后再利用瞬時(shí)條件獨(dú)立性(MCI)檢驗(yàn)以降低因果關(guān)系的誤發(fā)現(xiàn)率。然而,PCMCI算法存在未考慮即時(shí)效應(yīng)和隱變量的局限性。因此,文獻(xiàn)[8]提出PCMCI+算法以解決即時(shí)效應(yīng)的問題;文獻(xiàn)[9]提出的LPCMCI算法進(jìn)一步解決了隱變量的問題。類似地,文獻(xiàn)[10]提出的TiMINo算法和文獻(xiàn)[11]提出的VarLiNGAM算法則是基于函數(shù)模型的方法在時(shí)序場景上的拓展。

當(dāng)前針對非穩(wěn)態(tài)數(shù)據(jù)的因果發(fā)現(xiàn)算法的研究仍處于初始階段,文獻(xiàn)[12]介紹的CD-NOD框架著力于在變量的分布發(fā)生變化的情況下恢復(fù)因果結(jié)構(gòu),該框架的關(guān)鍵部分為引入代理變量C充當(dāng)潛在變化因素的表征。CD-NOD能夠恢復(fù)非穩(wěn)態(tài)數(shù)據(jù)的因果骨架,但是非穩(wěn)態(tài)擾動(dòng)的獨(dú)立變化假設(shè)和馬爾可夫等價(jià)類難題限制了該算法對完整因果結(jié)構(gòu)的學(xué)習(xí)能力。具體來說,馬爾可夫等價(jià)類是指具有相同的因果骨架和條件概率分布,但無法確定方向的結(jié)構(gòu)。在CD-NOD算法的定向規(guī)則失效后,該算法最終僅能輸出由PC算法學(xué)習(xí)到的部分定向的因果結(jié)構(gòu)。

2 問題定義

本文所考慮的問題為:給定非穩(wěn)態(tài)時(shí)間序列數(shù)據(jù)集D,如何有效地根據(jù)非穩(wěn)態(tài)擾動(dòng)的特征建模,并恢復(fù)非穩(wěn)態(tài)數(shù)據(jù)集D中n個(gè)變量的因果結(jié)構(gòu)。

3 非穩(wěn)態(tài)時(shí)序數(shù)據(jù)的因果結(jié)構(gòu)學(xué)習(xí)

針對所研究的問題,本節(jié)提出一種非穩(wěn)態(tài)加性噪聲模型,并給出該模型在非穩(wěn)態(tài)場景下的可識別性條件及其證明,隨后基于非穩(wěn)態(tài)加性噪聲模型的可識別性理論提出一種兩階段的因果關(guān)系發(fā)現(xiàn)算法。

3.1 非穩(wěn)態(tài)加性噪聲模型

在穩(wěn)態(tài)場景中,文獻(xiàn)[16]基于二元變量的因果關(guān)系提出非線性加性噪聲模型,并證明該模型在限定的函數(shù)和噪聲分布下具有可識別性。文獻(xiàn)[10-19]則進(jìn)一步將非線性加性噪聲模型推廣至?xí)r序數(shù)據(jù)場景和多元變量場景。然而,目前對于非穩(wěn)態(tài)加性噪聲模型的建模及其識別性仍然未知,本文首先給出非穩(wěn)態(tài)加性噪聲模型的定義,隨后給出模型的識別性條件及證明。

定義1(非穩(wěn)態(tài)加性噪聲模型) 給定一組觀測變量集X={X1,X2,…,Xn},若這組觀測變量滿足以下約束,則稱為非穩(wěn)態(tài)加性噪聲模型:

1)觀察變量具有一定的因果次序,因果次序在后的變量不能是次序在前的變量的原因;數(shù)據(jù)產(chǎn)生過程是遞歸的,變量間的因果關(guān)系可以表示為一個(gè)有向無環(huán)圖。

2)偽因果充分性[12]假設(shè):若存在未觀測到的混淆變量,則這個(gè)混淆變量可以用關(guān)于時(shí)序信息T的光滑函數(shù)表示。在任意時(shí)刻T=t,這項(xiàng)混淆變量的函數(shù)值是確定的。

3)觀測變量Xi∈X服從以下函數(shù)關(guān)系:

(1)

受文獻(xiàn)[19]提出的多元加性噪聲模型的可識別性條件啟發(fā),Nons-ANM的可識別性理論如定理1所示。在給出定理1之前,先引入(B,F)-IFMOC的識別理論。

引理1(B,F)-IFMOC的識別理論[19-20]:假設(shè)一組變量X的聯(lián)合分布p(X)是由以因果圖G表征的(B,F)-IFMOC的函數(shù)模型導(dǎo)出的,那么這組變量一定不存在兩個(gè)不同的(B,F)-IFMOC函數(shù)模型表征,同時(shí)也一定不能由兩個(gè)不同的因果圖G和G′表征。

定理1假設(shè)變量集X={X1,X2,…,Xn}滿足非穩(wěn)態(tài)加性噪聲模型,模型屬于(B,F)-IFMOC空間,且增廣變量集X∪{T}的因果結(jié)構(gòu)圖服從因果最小性假設(shè),那么變量集X的因果結(jié)構(gòu)能夠被唯一確定。

證明假設(shè)增廣變量集X∪{T}存在兩種不同的非穩(wěn)態(tài)加性噪聲模型表征,分別對應(yīng)兩個(gè)不同的因果結(jié)構(gòu)圖G和G0。

定理1提供了非穩(wěn)態(tài)加性噪聲模型的識別性條件,而對于模型中存在直接因果關(guān)系的變量對之間的非對稱性質(zhì),可由定理1推論而來。

證明在本文模型中,若兩個(gè)變量之間存在因果關(guān)系,如Xi→Xj,可分為兩種情況:1)存在時(shí)滯的因果關(guān)系;2)即時(shí)因果關(guān)系。兩種情況不會(huì)同時(shí)發(fā)生,因此分別證明在以上兩種情況下本文模型的非對稱性質(zhì)均成立。

推論1提供了本文模型中原因變量和結(jié)果變量之間的非對稱性質(zhì)?；谏鲜隼碚?第3.2節(jié)將提出面向非穩(wěn)態(tài)數(shù)據(jù)的因果發(fā)現(xiàn)算法。

3.2 非穩(wěn)態(tài)數(shù)據(jù)的因果發(fā)現(xiàn)算法

基于定理1提供的非穩(wěn)態(tài)加性噪聲模型的識別性條件,本節(jié)提出一種兩階段的因果發(fā)現(xiàn)算法。算法的初始輸入為觀測變量的時(shí)序數(shù)據(jù)集,最終輸出為表征觀測變量因果結(jié)構(gòu)的有向無環(huán)圖,算法框架如圖1所示。

圖1 Nons-ANM算法框架Fig.1 Nons-ANM algorithm framework

算法第1階段主要基于有向無環(huán)圖的匯點(diǎn)的性質(zhì):對于一個(gè)有向無環(huán)圖,必然存在出度為0的葉子節(jié)點(diǎn),本文將其稱為“匯點(diǎn)”。在因果結(jié)構(gòu)圖中,若Xsink為匯點(diǎn),則其噪聲變量為Nsink,它將擁有以下性質(zhì):

Nsink⊥{Xk|Xk∈X{Xsink}}

(2)

對于因果結(jié)構(gòu)圖中的匯點(diǎn)Xsink,其噪聲Nsink將獨(dú)立于變量集中其余所有變量,這是因?yàn)槠溆嗟淖兞縓k均為匯點(diǎn)Xsink的非后裔節(jié)點(diǎn),因此可由不包含匯點(diǎn)Xsink成分的獨(dú)立同分布噪聲變量集N〗{Nsink}的某種映射所表征。

基于上述性質(zhì),變量的因果次序可通過迭代尋找匯點(diǎn)的方法來獲得。具體來說,對于未確定因果次序的變量Xs∈X,利用變量集中其余未確定因果次序的變量{Xk|Xk∈X{Xs}}對Xs進(jìn)行回歸并計(jì)算得到殘差rs,隨后計(jì)算該殘差與其余變量的獨(dú)立性得分IND(rs,{Xk|Xk∈X{Xs}}),該得分衡量了變量間的獨(dú)立性強(qiáng)弱,衡量方法IND(·)可根據(jù)數(shù)據(jù)性質(zhì)靈活選擇,本節(jié)列舉了一些參考方法。重復(fù)上述步驟,選出獨(dú)立性得分最高的變量作為匯點(diǎn),將匯點(diǎn)插入因果次序中,并將匯點(diǎn)的數(shù)據(jù)從數(shù)據(jù)集中移除。算法偽代碼如算法1所示。

算法1因果次序?qū)W習(xí)

輸入觀測變量的時(shí)序數(shù)據(jù)集D={x1,x2,…,xn},最大時(shí)延p

輸出觀測變量的因果次序Π

1.初始化變量索引集S={1,2,…,n},因果次序Π為空集

2.WHILE !is Empty(S):

3.FOR s in S:

5.計(jì)算IND(rs,{xk|k∈S{s})并記錄

6.END FOR

7.選出獨(dú)立性得分最高的變量XM,從變量索引集S中移除M,在因果次序Π中添加M

8.END WHILE

9.RETURN Π

算法1可以學(xué)習(xí)得到變量集X的因果次序Π,基于因果次序Π可以生成變量集X的部分因果結(jié)構(gòu)。具體來說,在因果次序中,次序在后的變量不能是次序在前的變量的原因。這就意味著,因果次序中包含的確定信息為不存在由次序在后的節(jié)點(diǎn)指向次序在前的節(jié)點(diǎn)的有向邊;而未確定的信息為次序在前的節(jié)點(diǎn)可能存在指向次序在后的節(jié)點(diǎn)的有向邊,同時(shí)也可能不存在有向邊。因此,因果次序僅表征了因果結(jié)構(gòu)的部分信息,需要進(jìn)一步消除冗余信息,從而得到最終的因果結(jié)構(gòu)圖。

消除冗余因果關(guān)系的步驟如下:

1)對于各節(jié)點(diǎn)Xi∈X,以Xi為結(jié)果變量,以因果次序在Xi之前的全部節(jié)點(diǎn)為原因變量,連接原因變量和結(jié)果變量,初始化變量集X的部分因果結(jié)構(gòu)G*。

2)對于G*中可能存在的冗余邊,采用回歸計(jì)算得到殘差然后進(jìn)行獨(dú)立性檢驗(yàn)的方式消除,即對于各節(jié)點(diǎn)Xi∈X,依次假設(shè)因果次序在Xi之前的某個(gè)節(jié)點(diǎn)Xj∈{Xj|Xj∈X{Xi},Π(j)<Π(i)}不是Xi的直接原因;在特征數(shù)據(jù)集中移除Xj的數(shù)據(jù)后再對Xi的回歸計(jì)算得到殘差ri,隨后檢驗(yàn)殘差ri與變量集{Xj|Xj∈X{Xi},Π(j)<Π(i)}的獨(dú)立性。若獨(dú)立性仍然成立,則認(rèn)為Xj不是Xi的直接原因,并移除冗余邊Xj→Xi;否則認(rèn)為Xj是Xi的直接原因,并保留連接邊。算法偽代碼如算法2所示。

算法2移除冗余因果邊

輸入因果次序Π,觀測變量的時(shí)序數(shù)據(jù)集D={x1,x2,…,xn},最大時(shí)延p,顯著性水平α

輸出因果結(jié)構(gòu)圖G

1.基于因果次序Π初始化有向無環(huán)圖G*。

2.FOR i in Π:

3.FOR j in {j|Π(j)<Π(i)}:

5.IF IND(ri,{xk|Π(k)<Π(i))>α:

6.刪除G*中的有向邊Xj→Xi,更新父親節(jié)點(diǎn)集PAi=PAi{j}

7.END IF

8.END FOR

9.END FOR

10.RETURN G*

根據(jù)數(shù)據(jù)集特征,算法中的回歸方法和獨(dú)立性檢驗(yàn)方法可以相應(yīng)調(diào)整。在因果發(fā)現(xiàn)中常見的回歸方法有高斯過程回歸(GPR)、向量自回歸模型(VAR)等;常見的獨(dú)立性檢驗(yàn)方法有偏相關(guān)檢驗(yàn)[22]、希爾伯特-施密特獨(dú)立性準(zhǔn)則(HSIC)[23-24]、互信息(Ml)[25]、核條件獨(dú)立性檢驗(yàn)(KCI-test)[26]等。本文算法的實(shí)際表現(xiàn)受回歸工具和獨(dú)立性檢驗(yàn)工具的影響,統(tǒng)計(jì)學(xué)的難題會(huì)影響算法的實(shí)際表現(xiàn),例如高維變量集、小樣本量等場景。

對本文算法進(jìn)行復(fù)雜度分析:算法1和算法2的時(shí)間復(fù)雜度均為O(n2·Or(n,l)·Oi(n,l)),其中,n為觀測變量的個(gè)數(shù),l為時(shí)序數(shù)據(jù)集的樣本量,Or(n,l)表示算法選用的回歸方法的時(shí)間復(fù)雜度,Oi(n,l)表示算法選用的獨(dú)立性檢驗(yàn)方法的時(shí)間復(fù)雜度。

4 實(shí)驗(yàn)

本節(jié)將分別基于仿真數(shù)據(jù)集和真實(shí)因果結(jié)構(gòu)數(shù)據(jù)集開展隨機(jī)實(shí)驗(yàn),從而對本文算法的有效性進(jìn)行評估。另外采用CD-NOD算法、LPCMCI算法和TiMINo算法作為對比方法,其中CD-NOD算法為非穩(wěn)態(tài)因果關(guān)系學(xué)習(xí)算法,LPCMCI算法是學(xué)習(xí)含有即時(shí)因果效應(yīng)和隱變量的因果關(guān)系學(xué)習(xí)算法,TiMINo算法則是經(jīng)典的基于函數(shù)因果模型的時(shí)序因果關(guān)系學(xué)習(xí)算法。

仿真數(shù)據(jù)集實(shí)驗(yàn)和真實(shí)因果結(jié)構(gòu)數(shù)據(jù)集實(shí)驗(yàn)中的對比算法均使用官方實(shí)現(xiàn)的開源代碼,算法參數(shù)均設(shè)置為默認(rèn)值。本文算法Nons-ANM采用高斯過程回歸作為回歸方法,采用基于希爾伯特-施密特獨(dú)立性準(zhǔn)則的假設(shè)檢驗(yàn)作為獨(dú)立性檢驗(yàn)方法。實(shí)驗(yàn)中所有方法的顯著性水平α均設(shè)置為0.05。

在實(shí)驗(yàn)部署環(huán)境方面,仿真數(shù)據(jù)集實(shí)驗(yàn)和真實(shí)因果結(jié)構(gòu)數(shù)據(jù)集實(shí)驗(yàn)均執(zhí)行于內(nèi)存為8 GB、CPU型號為Intel i7-7700、操作系統(tǒng)為Windows的環(huán)境。

4.1 仿真數(shù)據(jù)集實(shí)驗(yàn)

在仿真數(shù)據(jù)集實(shí)驗(yàn)中,本文基于Erdos-Renyi模型隨機(jī)生成不同的有向無環(huán)圖來表示因果結(jié)構(gòu),并設(shè)計(jì)了5組控制變量實(shí)驗(yàn),具體設(shè)置為:變量數(shù)量為{5,10, 15, 20},平均入度為{1.0,1.5, 2.0, 2.5},樣本數(shù)量為{1 000,2000, 3 000, 4 000},非穩(wěn)態(tài)變量的占比為{0.0,0.4, 0.8, 1.0},最大時(shí)延為{0, 2, 4},花括號中的加粗參數(shù)為默認(rèn)的參數(shù)設(shè)置。變量集中的變量分為穩(wěn)態(tài)和非穩(wěn)態(tài)兩類,對于穩(wěn)態(tài)的變量,其時(shí)序數(shù)據(jù)基于函數(shù)因果模型生成,如式(3)所示:

(3)

對于非穩(wěn)態(tài)擾動(dòng)的變量,其時(shí)序數(shù)據(jù)的生成則基于函數(shù)因果模型,如式(4)所示:

(4)

實(shí)驗(yàn)的評價(jià)指標(biāo)選用準(zhǔn)確率(P)、召回率(R)和F1值(F1),各評價(jià)指標(biāo)的計(jì)算公式如下:

(5)

(6)

(7)

其中:TP表示學(xué)習(xí)正確的連接邊的數(shù)量;FN表示原結(jié)構(gòu)不存在邊,且算法結(jié)果中也沒有邊的數(shù)量;FP表示原結(jié)構(gòu)不存在邊,但算法結(jié)果存在邊的數(shù)量。在這套評價(jià)算法中,正確率是指學(xué)習(xí)的因果結(jié)構(gòu)圖中正確的邊數(shù)占比;召回率表示正確識別的邊數(shù)在所有真實(shí)存在的正確邊數(shù)中的占比;而F1值結(jié)合正確率和召回率,能夠綜合地衡量一種算法的有效性。

本文算法與CD-NOD、LPCMCI和TiMINo算法的實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 各算法在不同參數(shù)下的實(shí)驗(yàn)結(jié)果Fig.2 Experimental results of each algorithms in different parameters

1)圖2(a)～圖2(c)給出不同變量數(shù)量下的實(shí)驗(yàn)結(jié)果。可以看出,本文算法在所有變量數(shù)量的設(shè)定下均取得最高的準(zhǔn)確率、召回率和F1值,這驗(yàn)證了本文算法的魯棒性。CD-NOD算法的實(shí)驗(yàn)結(jié)果呈現(xiàn)出準(zhǔn)確率高于召回率的特點(diǎn),原因是CD-NOD算法的定向規(guī)則中的獨(dú)立擾動(dòng)假設(shè)造成了定向誤差。LPCMCI算法擁有從包含隱變量的數(shù)據(jù)集中恢復(fù)因果結(jié)構(gòu)的能力,這項(xiàng)能力幫助LPCMCI算法在實(shí)驗(yàn)?zāi)J(rèn)設(shè)置下取得了0.56的F1值,但其總體實(shí)驗(yàn)結(jié)果略低于CD-NOD算法,這是因?yàn)長PCMCI算法針對隱變量的能力并不完全適用于非穩(wěn)態(tài)擾動(dòng)的場景。TiMINo算法采用了保守的策略,當(dāng)算法無法確定因果關(guān)系時(shí)將執(zhí)行熔斷機(jī)制;由圖3(a)可知,TiMINo算法在實(shí)驗(yàn)?zāi)J(rèn)設(shè)置下熔斷率為0.8;而當(dāng)變量數(shù)量增至20時(shí),其熔斷率達(dá)到1.0,即TiMINo算法無法恢復(fù)任何一組仿真數(shù)據(jù)集的因果結(jié)構(gòu)。由此可知,經(jīng)典的時(shí)序因果發(fā)現(xiàn)方法難以直接應(yīng)用于非穩(wěn)態(tài)場景。

圖3 TiMINo算法在不同參數(shù)設(shè)置下的未識別率Fig.3 Unrecognition rate of TiMINo algorithm under different parameter settings

2)從圖2(d)～圖2(f)可以看出,實(shí)驗(yàn)中的所有算法對樣本數(shù)量都比較敏感。在樣本數(shù)量逐漸增加的過程中,本文算法的F1值逐漸提升,這是因?yàn)楦邩颖緮?shù)量能降低統(tǒng)計(jì)誤差,從而幫助本文算法逼近理論效果。在所有樣本數(shù)量的實(shí)驗(yàn)設(shè)置下,本文算法均取得了最高的F1值,這體現(xiàn)了本文算法的優(yōu)越性。

3)圖2(g)～圖2(i)展示了不同平均入度下的實(shí)驗(yàn)結(jié)果?？梢钥闯?CD-NOD算法和LPCMCI算法對平均入度較敏感,兩個(gè)算法的F1值隨著平均入度增加而明顯下降,這表明稠密的因果結(jié)構(gòu)更易于暴露算法的不足。TiMINo算法的熔斷率在所有設(shè)定中均不小于0.7,這表明了TiMINo算法對非穩(wěn)態(tài)數(shù)據(jù)集的學(xué)習(xí)能力不足。相比之下,本文算法在所有設(shè)置下的均表現(xiàn)穩(wěn)定且優(yōu)勢明顯,這表示本文算法能夠有效地學(xué)習(xí)稠密的因果結(jié)構(gòu)。

4)圖2(j)～圖2(l)給出了不同非穩(wěn)態(tài)節(jié)點(diǎn)占比的實(shí)驗(yàn)結(jié)果。可以看出,在所有算法中本文算法擁有最好的非穩(wěn)態(tài)因果關(guān)系學(xué)習(xí)能力,即使在非穩(wěn)態(tài)節(jié)點(diǎn)占比為1.0時(shí),本文算法依然能取得0.81的F1值。隨著非穩(wěn)態(tài)擾動(dòng)節(jié)點(diǎn)占比的增加,其余3個(gè)算法的實(shí)驗(yàn)結(jié)果均大幅降低,這進(jìn)一步體現(xiàn)了本文算法的魯棒性和優(yōu)越性。

5)圖2(m)～圖2(o)給出了不同最大時(shí)延下的實(shí)驗(yàn)結(jié)果。最大時(shí)延的增加會(huì)增大時(shí)序因果網(wǎng)絡(luò)的復(fù)雜性,進(jìn)而增大因果發(fā)現(xiàn)算法的學(xué)習(xí)難度。從圖中可以看出,CD-NOD算法、LPCMCI算法和TiMINo算法在最大時(shí)延為4時(shí)難以取得有效的實(shí)驗(yàn)結(jié)果,這是因?yàn)橐陨?種算法均沒有學(xué)習(xí)復(fù)雜的時(shí)序因果網(wǎng)絡(luò)的能力。而本文算法在所有最大時(shí)延的實(shí)驗(yàn)設(shè)置下表現(xiàn)穩(wěn)定,實(shí)驗(yàn)結(jié)果顯著優(yōu)于其他3種算法,說明了本文算法的有效性。

6)圖3表示TiMINo算法在不同控制實(shí)驗(yàn)中觸發(fā)熔斷策略的數(shù)據(jù)集比率,即TiMINo算法的未識別率?？梢钥闯?TiMINo算法頻繁觸發(fā)了熔斷機(jī)制:在所有控制實(shí)驗(yàn)中,TiMINo的未識別率均不小于0.7;而在部分復(fù)雜的因果結(jié)構(gòu)中的未識別率達(dá)到1.0,例如20個(gè)節(jié)點(diǎn)和非穩(wěn)態(tài)節(jié)點(diǎn)占比達(dá)到1.0等。這進(jìn)一步表明,未考慮非穩(wěn)態(tài)擾動(dòng)的時(shí)序因果發(fā)現(xiàn)算法難以直接應(yīng)用于非穩(wěn)態(tài)場景中。

4.2 真實(shí)因果結(jié)構(gòu)數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)采用3種不同規(guī)格的真實(shí)因果結(jié)構(gòu)進(jìn)行實(shí)驗(yàn),相關(guān)的真實(shí)因果結(jié)構(gòu)信息可參考開源網(wǎng)站:https:∥www.bnlearn.com/bnrepository/。本節(jié)實(shí)驗(yàn)中選用的真實(shí)因果網(wǎng)絡(luò)的參數(shù)表1如所示。

表1 真實(shí)因果網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)Table 1 Real causal network structure parameters

本節(jié)實(shí)驗(yàn)中采用的算法參數(shù)和實(shí)驗(yàn)參數(shù)均與仿真數(shù)據(jù)集實(shí)驗(yàn)相同,同樣采用準(zhǔn)確率、召回率以及F1值作為算法效果的評價(jià)指標(biāo)。

各算法的實(shí)驗(yàn)結(jié)果如圖4所示。由圖4可知,本文算法在所有數(shù)據(jù)集中均取得了最優(yōu)的實(shí)驗(yàn)結(jié)果。特別地,本文算法在sachs結(jié)構(gòu)的數(shù)據(jù)集中取得的F1值為0.86,相比CD-NOD的0.52提升了65.4%,相比LPCMCI的0.53提升了62.3%,這是因?yàn)閟achs結(jié)構(gòu)比較稠密,而本文算法在稠密的因果結(jié)構(gòu)下更加能夠體現(xiàn)其優(yōu)越性。而對于變量個(gè)數(shù)少且相對稀疏的因果結(jié)構(gòu)(如survey結(jié)構(gòu)),本文算法和其他對比算法的F1值接近,這則是因?yàn)楹唵蔚囊蚬Y(jié)構(gòu)難以體現(xiàn)非穩(wěn)態(tài)擾動(dòng)造成的影響?？傮w而言,真實(shí)因果結(jié)構(gòu)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性。TiMINo算法在不同真實(shí)結(jié)構(gòu)下的未識別率如圖5所示。

圖4 不同算法的真實(shí)結(jié)構(gòu)實(shí)驗(yàn)結(jié)果Fig.4 Experimental results of real structures of different algorithms

圖5 TiMINo算法在不同真實(shí)結(jié)構(gòu)下的未識別率Fig.5 Unrecognition rate of TiMINo algorithm under different real structures

5 結(jié)束語

現(xiàn)有因果發(fā)現(xiàn)方法難以恢復(fù)非穩(wěn)態(tài)數(shù)據(jù)集的因果結(jié)構(gòu),本文提出非穩(wěn)態(tài)加性噪聲模型,并基于該模型的識別性理論提出一種魯棒的兩階段算法,從而為非穩(wěn)態(tài)數(shù)據(jù)集的因果結(jié)構(gòu)學(xué)習(xí)難題提供解決方案。為驗(yàn)證本文算法有效性,引入CD-NOD算法、LPCMCI算法和TiMINo算法,分別在仿真數(shù)據(jù)集和真實(shí)結(jié)構(gòu)數(shù)據(jù)集上部署實(shí)驗(yàn),最終的實(shí)驗(yàn)結(jié)果體現(xiàn)了本文算法相較于主流因果發(fā)現(xiàn)算法在準(zhǔn)確率和魯棒性等方面的優(yōu)勢。下一步將對模型的加性噪聲假設(shè)進(jìn)行弱化并優(yōu)化算法流程,以擴(kuò)展本文方法的適用范圍。