一種基于高階累積量的因果結(jié)構(gòu)學(xué)習(xí)算法

摘 要：從觀測數(shù)據(jù)中學(xué)習(xí)因果結(jié)構(gòu)具有重要的應(yīng)用價值。目前，一類學(xué)習(xí)因果結(jié)構(gòu)的方法是基于函數(shù)因果模型假設(shè)，通過檢驗噪聲與原因變量的獨(dú)立性來學(xué)習(xí)因果結(jié)構(gòu)。然而，該類方法涉及高計算復(fù)雜度的獨(dú)立性檢驗過程，影響結(jié)構(gòu)學(xué)習(xí)算法的實(shí)用性和魯棒性。為此，提出了一種在線性非高斯模型下，利用高階累積量作為獨(dú)立性評估的因果結(jié)構(gòu)學(xué)習(xí)算法。該算法主要分為兩個步驟，第一個步驟是利用基于條件獨(dú)立性約束的方法學(xué)習(xí)到因果結(jié)構(gòu)的馬爾可夫等價類，第二個步驟是定義了一種基于高階累積量的得分，該得分可以判別兩個隨機(jī)變量的獨(dú)立性，從而可以從馬爾可夫等價類中搜索到最佳獨(dú)立性得分的因果結(jié)構(gòu)作為算法的輸出。該算法的優(yōu)勢在于：a）相比基于核方法的獨(dú)立性檢驗，該方法有較低的計算復(fù)雜度；b）基于得分搜索的方法，可以得到一個最匹配數(shù)據(jù)生成過程的模型，提高學(xué)習(xí)方法的魯棒性。實(shí)驗結(jié)果表明，基于高階累積量的因果結(jié)構(gòu)學(xué)習(xí)方法在合成數(shù)據(jù)中F1得分提高了5%，并在真實(shí)數(shù)據(jù)中學(xué)習(xí)到更多的因果方向。

關(guān)鍵詞：因果發(fā)現(xiàn)；結(jié)構(gòu)學(xué)習(xí)；高階累積量；線性非高斯模型

中圖分類號：TP181 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2023）06-016-1702-06

doi： 10.19734/j.issn.1001-3695.2022.10.0511

Higher-order cumulant-based algorithm for learning causal structure

Liao Weiguo

（Zhujiang College， South China Agricultural University， Guangzhou 510900， China）

Abstract：

Learning causal structure from observed data has important applications. An existing method for learning causal structure is to learn causal structure by testing the independence between noise and causal variables under the functional causal model assumption. However， such methods often involve highly computationally complex in process of testing independence， which affects the practicability and robustness of the structure learning algorithm. To this end， this paper proposed a causal structure learning algorithm that used higher-order cumulants as independence scores under a linear non-Gaussian model. The algorithm was mainly divided into two steps. The first step was to use the method based on conditional independence constraints to learn the Markov equivalence class of the causal structure. The second step was to define a score based on high-order cumulants， the score could determine the independence of two random variables so that the causal structure of the best independence score could be searched from the Markov equivalence class as the output of the algorithm. The advantages of this algorithm were： a）Compared with the independence test based on the kernel method， the method had lower computational complexity. b）The method based on score search could always obtain a model that best matches the data generation process， which improved the robustness of the learning method. Experimental results show that the high-order cumulant-based causal structure learning method improves the F1 score by 5% in synthetic data and learns more causal directions in real data.

Key words：causal discovery; structure learning; higher order cumulants; linear acyclic non-Gaussian model

0 引言

從觀察數(shù)據(jù)中發(fā)現(xiàn)變量之間的因果關(guān)系，也稱為因果發(fā)現(xiàn)［1］，已經(jīng)成為當(dāng)前的熱點(diǎn)問題，被廣泛應(yīng)用于智能運(yùn)維［2］、智慧交通［3］、金融交易［4］、社會科學(xué)［5］、氣候研究［6］等領(lǐng)域。

傳統(tǒng)的因果發(fā)現(xiàn)算法主要有基于測試條件獨(dú)立性約束的方法和基于得分搜索的方法。基于測試條件獨(dú)立性約束的方法通過檢驗變量之間的條件獨(dú)立性約束來學(xué)習(xí)因果結(jié)構(gòu)，代表方法有PC［7］、IC［8］、FCI［9］等算法。基于得分的方法通過搜索最優(yōu)條件概率分解的因果圖來學(xué)習(xí)因果結(jié)構(gòu)，如GES［10］算法等。然而這兩類方法都僅利用條件獨(dú)立約束來學(xué)習(xí)因果結(jié)構(gòu)，存在馬爾可夫等價類［7］的問題，無法學(xué)習(xí)到唯一的因果結(jié)構(gòu)，特別是無法識別兩個變量之間的因果方向。為了緩解這一問題，部分工作引入加性噪聲模型，通過判別原因變量和噪聲的獨(dú)立性來識別因果方向，代表方法有線性非高斯無環(huán)模型（linear non-Gaussian acyclic model，LiNGAM）［11］和非線性加性噪聲模型（non-linear additive noise model， NL-ANM）［12］。然而為了檢驗噪聲與原因變量的獨(dú)立性，需要用到一些基于核的獨(dú)立性檢驗方法，如HSIC、KCI等［13，14］，這些方法在樣本量大的時候計算復(fù)雜度很高，降低了在大數(shù)據(jù)下因果發(fā)現(xiàn)算法的實(shí)用性。

因此，尋找一種代替基于核的獨(dú)立性檢驗方法備受青睞［15］。這一類方法主要是在線性非高斯無環(huán)模型下，研究非高斯分布中高階統(tǒng)計量所蘊(yùn)涵的獨(dú)立性約束。早期，文獻(xiàn)［15］提出了一種基于對數(shù)似然比的因果方向識別方法，該方法通過對比兩個不同方向的似然來選擇正確的因果方向，并且提供了計算該似然的一些近似方法。受此工作的啟發(fā)，近來，Cai等人［16］提出了基于峭度的識別因果結(jié)構(gòu)的方法；Xie等人［17］提出了基于信息熵的方法來學(xué)習(xí)因果結(jié)構(gòu)。雖然這些方法一定程度上推動了基于加性噪聲模型方法的應(yīng)用范圍，但是還存在以下兩個問題：a）這些方法主要是通過比較不同方向上統(tǒng)計量的大小來選擇因果方向，它們無法從理論上斷言原因變量和噪聲是否是相互統(tǒng)計獨(dú)立的；b）這些方法通過迭代學(xué)習(xí)根節(jié)點(diǎn)的方式來學(xué)習(xí)因果結(jié)構(gòu)，存在如果前面迭代過程中根節(jié)點(diǎn)學(xué)錯，后面的因果方向?qū)W習(xí)都受到影響的問題。

本文研究在線性非高斯無環(huán)模型下，利用高階累積量學(xué)習(xí)因果結(jié)構(gòu)的問題。經(jīng)研究發(fā)現(xiàn)，利用高階累積量可以定義一種四階互累積量之和（sum of all fourth order cross-cumlant，SFOC）的統(tǒng)計量，可以從理論上回答原因變量和噪聲變量是否相互統(tǒng)計獨(dú)立的問題。基于SFOC，本文設(shè)計了一種基于得分搜索的算法來學(xué)習(xí)觀測變量間的因果結(jié)構(gòu)。該算法在PC算法［6］得到的馬爾可夫等價類的基礎(chǔ)上，通過枚舉所有的馬爾可夫等價類的因果圖，利用SFCO去評估每一個圖的噪聲獨(dú)立性得分，選取最優(yōu)得分的因果圖作為算法的輸出。該算法的優(yōu)勢在于：a）相比基于核方法的獨(dú)立性檢驗，該方法有較低的計算復(fù)雜度；b）基于得分搜索的方法，可以得到一個最匹配數(shù)據(jù)生成過程的模型，降低局部結(jié)構(gòu)學(xué)習(xí)錯誤對于整個因果結(jié)構(gòu)學(xué)習(xí)的影響，提高學(xué)習(xí)方法的魯棒性。最后，模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)也都證實(shí)了本文方法的正確性和有效性。

1 相關(guān)工作

加性噪聲模型（additive noise model，ANM）假設(shè)數(shù)據(jù)產(chǎn)生過程服從一種函數(shù)因果關(guān)系，如對于因果關(guān)系X→Y，ANM假設(shè)因果機(jī)制滿足Y=f（X）+ε_y，其中ε_y是變量Y的噪聲，滿足獨(dú)立性約束X⊥ε_y， f是其映射函數(shù)。由于ANM引入了噪聲變量與原因變量的獨(dú)立性約束，使得因果方向是唯一可識別的，解決了傳統(tǒng)因果發(fā)現(xiàn)方法存在馬爾可夫等價類的問題［7］。目前主要有兩類經(jīng)典的ANM：a）假設(shè)映射函數(shù)是非線性函數(shù)的非線性加性噪聲模型［12］（NL-ANM）；b）假設(shè)映射函數(shù)是線性函數(shù)和噪聲變量服從非高斯分布的線性非高斯無環(huán)模型［11］（LiNGAM）。在NL-ANM中，對于滿足因果方向的ANM，回歸殘差與原因變量相互統(tǒng)計獨(dú)立，而對于非因果方向，不存在擬合函數(shù)可以使得回歸殘差與回歸變量相互統(tǒng)計獨(dú)立，因此，根據(jù)這種獨(dú)立性的不對稱性，因果方向可識別。在此框架下的一些相關(guān)的拓展有后非線性加性噪聲模型（post-NonLinear，PNL）［18］、離散數(shù)據(jù)下的加性噪聲模型等［19］。

在LiNGAM下，由于假設(shè)了數(shù)據(jù)服從非高斯分布，對于非因果方向的回歸殘差與回歸變量統(tǒng)計不獨(dú)立，即獨(dú)立性的不對稱性仍然成立，從而可以識別因果方向。在LiNGAM下學(xué)習(xí)因果結(jié)構(gòu)主要有基于獨(dú)立成分分析的ICA-LiNGAM［20］和基于噪聲獨(dú)立約束測試的Direct-LiNGAM［11］兩類方法。ICA-LiNGAM利用函數(shù)優(yōu)化的方法學(xué)習(xí)因果結(jié)構(gòu)，在此框架下的一些相關(guān)拓展工作有允許隱變量存在的Lv-LiNGAM［21］等。該類方法存在的主要問題是在變量維度較大的時候容易陷入局部極值。Direct-LiNGAM主要通過測試噪聲與原因變量的獨(dú)立性約束，通過迭代學(xué)習(xí)依次學(xué)習(xí)因果序的方法來學(xué)習(xí)因果結(jié)構(gòu)。在該框架下的一些拓展工作有基于高階統(tǒng)計量學(xué)習(xí)代替獨(dú)立性檢驗的方法［15～17］和允許混淆因子影響的方法，如Parce-LiNGAM［22］及其他變體等［23］。在Direct-LiNGAM框架下存在的主要問題是獨(dú)立性檢驗往往需要較高的計算復(fù)雜度和迭代學(xué)習(xí)的方法，存在每一次迭代的結(jié)果都會影響后面的迭代學(xué)習(xí)的問題，容錯的能力較差。

2 基于高階累積量的因果結(jié)構(gòu)學(xué)習(xí)

2.1 問題定義

2.2 基于高階累積量的因果方向識別

2.3 基于高階累積量的因果結(jié)構(gòu)學(xué)習(xí)

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

為了驗證本文所提理論和SFOC-LiNGAM算法的有效性，本章將分別使用模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗，并與基準(zhǔn)方法進(jìn)行了對比。所對比的基準(zhǔn)算法有基于核的獨(dú)立性測試（如HSIC）的HSIC-LiNGAM［11］、基于似然比的Likelihood-LiNGAM［5］、基于信息熵的方法Entropy-LiNGAM［17］和基于遞歸的方法repetitive causal discovery（RCD）［28］。

其中HSIC-LiNGAM和Likelihood-LiNGAM是LiNGAM模型下的一些經(jīng)典的學(xué)習(xí)方法，它們分別是基于核的獨(dú)立性檢驗和基于對數(shù)似然比得分的結(jié)構(gòu)學(xué)習(xí)算法；Entropy-LiNGAM是近來對LiNGAM模型的一個較為有效的拓展工作，該方法通過信息熵得分來學(xué)習(xí)因果結(jié)構(gòu)，RCD-LiNGAM是在LiNGAM模型下對于存在隱變量的因果結(jié)構(gòu)學(xué)習(xí)（近一年來對于LiNGAM模型的拓展大多數(shù)在于存在未觀測變量問題的研究，本文選取RCD算法為代表作為對比基準(zhǔn)）。

3.1 模擬數(shù)據(jù)實(shí)驗

3.2 真實(shí)數(shù)據(jù)實(shí)驗

3.2.1 數(shù)據(jù)集說明

本節(jié)將本文方法應(yīng)用于由文獻(xiàn)［29］提供的真實(shí)數(shù)據(jù)集——慢性疲勞綜合征 （CFS） 中的認(rèn)知和衰老數(shù)據(jù)集。該數(shù)據(jù)集包含六個變量，共 161 條有效樣本（清理了含缺失值的樣本），這些變量分別是疲勞（fat）、專注程度 （foc）、對疲勞的控制感 （sens）、客觀活動 （obj）、物理活動 （phy） 和身體機(jī)能 （func）。這個數(shù)據(jù)集旨在研究導(dǎo)致疲勞的原因是什么，即探索其他變量和疲勞（fat）的關(guān)系。此外，文獻(xiàn)［27］經(jīng)過控制實(shí)驗分析提供了關(guān)于數(shù)據(jù)背后的真實(shí)因果關(guān)系，指出物理活動、對疲勞的控制感、專注程度和身體機(jī)能是導(dǎo)致疲勞的直接原因，而客觀活動不是導(dǎo)致疲勞的直接原因。在真實(shí)數(shù)據(jù)集中，仍然采用準(zhǔn)確率、召回率和F₁得分作為評價指標(biāo)。此外，對于SFOC-LiNGAM和HSIC-LiNGAM的置信閾值，設(shè)置為0.03。

3.2.2 實(shí)驗結(jié)果分析

實(shí)驗結(jié)果如表1所示。從表1中可看出，SFOC-LiNGAM算法的三個評價指標(biāo)都比基準(zhǔn)方法好。本文方法的F₁得分高達(dá)93%，說明了本文方法幾乎正確學(xué)習(xí)了整個真實(shí)的因果結(jié)構(gòu)，其原因在于本文方法在基于條件獨(dú)立約束方法的基礎(chǔ)上進(jìn)行得分搜索，相當(dāng)于在其骨架圖上進(jìn)行定向，降低了結(jié)構(gòu)學(xué)習(xí)的錯誤率。其次，本文方法選擇全局得分最優(yōu)的因果結(jié)構(gòu)，降低了局部結(jié)構(gòu)錯誤率的影響。而HSIC-LiNGAM算法比其他基準(zhǔn)方法有更高的F₁得分，因為相比于通過比較大小來定向的方法，獨(dú)立性檢驗工具有可調(diào)節(jié)置信區(qū)間的優(yōu)勢來選擇相對正確的結(jié)構(gòu)。此外，RCD算法幾乎無法學(xué)習(xí)到因果方向，留下了大量的雙向邊無法定向，這是由于在真實(shí)數(shù)據(jù)下，樣本量較小的情況下，RCD算法涉及大量的獨(dú)立性檢驗來識別因果序，使得該算法在實(shí)際應(yīng)用中的穩(wěn)定性較差。其更加具體的結(jié)構(gòu)學(xué)習(xí)結(jié)果如圖4所示。其中實(shí)線表示正確發(fā)現(xiàn)的因果邊；虛線表示錯誤發(fā)現(xiàn)的因果邊。

從圖4可以看到，SFOC-LiNGAM方法可以正確學(xué)習(xí)到所有導(dǎo)致疲勞的直接原因，這個結(jié)果與文獻(xiàn)［30］提供的一致。此外，學(xué)習(xí)到客觀活動是物理活動的原因也是合理的，因為物理活動屬于一種客觀活動的范疇。此外，由于專注程度和對疲勞的控制感之間的真實(shí)因果關(guān)系目前沒有確切文獻(xiàn)給出，所以本文設(shè)置其真實(shí)結(jié)構(gòu)為雙向邊，從而導(dǎo)致本文算法在這兩者之間學(xué)到的因果方向顯示出錯。而對于其他基準(zhǔn)方法，都無法完全正確學(xué)到導(dǎo)致疲勞的直接原因。實(shí)驗結(jié)果也說明了本文方法的有效性和魯棒性。

4 結(jié)束語

本文提出了一種在線性非高斯無環(huán)模型下，基于高階累積量的因果發(fā)現(xiàn)算法 SFOC-LiNGAM，通過利用高階累積量作為一種噪聲獨(dú)立性評分，從基于條件獨(dú)立性約束的方法得到的等價類中選取最優(yōu)得分的因果圖來學(xué)習(xí)因果結(jié)構(gòu)。本文進(jìn)行了充足的理論分析，提供了基于高階累積量的因果方向的識別性定理及其證明，并在實(shí)驗數(shù)據(jù)中證明了算法的有效性。相比基于核的獨(dú)立性檢驗結(jié)構(gòu)學(xué)習(xí)方法，本文算法有較低的計算復(fù)雜度。而相比于現(xiàn)有基于Direct-LiNGAM框架下的學(xué)習(xí)算法，本文算法在結(jié)構(gòu)學(xué)習(xí)中有更好的容錯能力。但是，LiNGAM模型下的一些假設(shè)限制了其學(xué)習(xí)算法的應(yīng)用范圍，后續(xù)工作將對此問題展開進(jìn)一步的研究，提出更加一般化假設(shè)下的因果發(fā)現(xiàn)算法。

參考文獻(xiàn)：

［1］蔡瑞初，陳薇，張坤，等. 基于非時序觀察數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)綜述［J］. 計算機(jī)學(xué)報，2017，40（6）： 1470-1490. （Cai Ruichu，Chen Wei，Zhang Kun，et al. Summary of causal relationship discovery based on non-time series observation data［J］. Chinese Journal of Computers，2017，40（6）： 1470-1490.）

［2］Liu Zitong，Sun Jiachen，Shen Feng，et al. Topology sensing of wireless networks based on Hawkes process［J］. Mobile Networks and Applications，2020，25（6）： 2459-2470.

［3］Zhu Shixiang，Ding Ruyi，Zhang Minghe，et al. Spatio-temporal point processes with attention for traffic congestion event modeling［J］. IEEE Trans on Intelligent Transportation Systems，2022，23（7）： 7298-7309.

［4］Da Fonseca J，Zaatour R. Hawkes process： fast calibration，application to trade clustering，and diffusive limit［J］. Journal of Futures Markets，2014，34（6）： 548-579.

［5］Runge J，Bathiany S，Bollt E，et al. Inferring causation from time series in earth system sciences［J］. Nature Communications，2019，10（1）： 1-13.

［6］Cai Ruichu，Zhang Zhenjie，Hao Zhifeng，et al. Understanding social causalities behind human action sequences［J］. IEEE Trans on Neural Networks and Learning Systems，2017，28（8）： 1801-1813.

［7］Spirtes P，Glymour C N，Scheines R. Causation，prediction，and search［M］. 2nd ed. Cambridge： MIT Press，2000.

［8］Verma T，Pearl J. Equivalence and synthesis of causal models［C］// Proc of the 6th Annual Conference on Uncertainty in Artificial Intelligence. USA： Elsevier Science Inc.，1990： 255-270.

［9］Spirtes P，Meek C，Richardson T. An algorithm for causal inference in the presence of latent variables and selection bias［C］// Proc of the 11th Conference on Uncertainty in Artificial Intelligence. San Francisco，CA： Morgan Kaufmann Publishers Inc.，1995： 499-506.

［10］Chickering D M. Optimal structure identification with greedy search［J］. The Journal of Machine Learning Research，2002，3： 507-554.

［11］Shimizu S，Inazumi T，Sogawa Y，et al. DirectLiNGAM： a direct method for learning a linear non-Gaussian structural equation model［J］. Journal of Machine Learning Research，2011，12（2）： 1225-1248.

［12］Hoyer P O，Janzing D，Mooij J，et al. Nonlinear causal discovery with additive noise models［C］// Proc of the 21st International Conference on Neural Information Processing Systems. Red Hook，NY： Curran Associates Inc.，2009： 689-696.

［13］Gretton A，F(xiàn)ukumizu K，Teo C H，et al. A kernel statistical test of independence［C］// Proc of the 20th International Conference on Neural Information Processing Systems. 2007： 585-592.

［14］Zhang Kun，Peters J，Janzing D，et al. Kernel-based conditional independence test and application in causal discovery［C］// Proc of the 27th Conference on Uncertainty in Artificial Intelligence. Arlington，Virginia： AUAI Press，2011： 804-813.

［15］Hyvrinen A，Smith S M. Pairwise likelihood ratios for estimation of non-Gaussian structural equation models［J］. Journal of Machine Learning Research，2013，14（1）： 111-152.

［16］Cai Ruichu，Xie Feng，Chen Wei，et al. An efficient kurtosis-based causal discovery method for linear non-Gaussian acyclic data［C］// Proc of the 25th International Symposium on Quality of Service. Piscataway，NJ： IEEE Press，2017： 1-6.

［17］Xie Feng，Cai Ruichu，Zeng Yan，et al. An efficient entropy-based causal discovery method for linear structural equation models with IID noise variables［J］. IEEE Trans on Neural Networks and Lear-ning Systems，2020，31（5）： 1667-1680.

［18］Zhang Kun，Hyvrinen A. On the identifiability of the post-nonlinear causal model［C］// Proc of the 25th Conference on Uncertainty in Artificial Intelligence. Arlington，Virginia： AUAI Press，2009： 647-655.

［19］Peters J，Janzing D，Scholkopf B. Causal inference on discrete data using additive noise models［J］. IEEE Trans on Pattern Analysis and Machine Intelligence，2011，33（12）： 2436-2450.

［20］Shimizu S，Hoyer P O，Hyvrinen A，et al. A linear non-Gaussian acyclic model for causal discovery［J］. The Journal of Machine Lear-ning Research，2006，7： 2003-2030.

［21］Hoyer P O，Shimizu S，Kerminen A J，et al. Estimation of causal effects using linear non-Gaussian causal models with hidden variables［J］. International Journal of Approximate Reasoning，2008，49（2）： 362-378.

［22］Tashiro T，Shimizu S，Hyvrinen A，et al. ParceLiNGAM： a causal ordering method robust against latent confounders［J］. Neural Computation，2014，26（1）： 57-83.

［23］陳薇，蔡瑞初，伍運(yùn)金，等. 基于多組典型相關(guān)變量的因果關(guān)系發(fā)現(xiàn)算法［J］. 計算機(jī)應(yīng)用研究，2021，38（1）： 53-56. （Chen Wei，Cai Ruichu，Wu Yunjin，et al. Causal relationship discovery algorithm based on multiple groups of typical related variables［J］. Application Research of Computers，2021，38（1）： 53-56.）

［24］Spirtes P，Zhang Kun. Causal discovery and inference： concepts and recent methodological advances［J］. Applied Informatics，2016，3（1）： 1-28.

［25］Girolami M. Self-organising neural networks ： independent component analysis and blind source separation［M］. London： Springer，1999： 5-34.

［26］Hyvrinen A，Oja E. Independent component analysis： algorithms and applications［M］. New York： Wiley，2001： 411-430.

［27］Ord J K. Characterization problems in mathematical statistics［J］. Journal of the Royal Statistical Society，1975，138（4）： 576-577.

［28］Maeda T N，Shimizu S. Repetitive causal discovery of linear non-Gaussian acyclic models in the presence of latent confounders［J］. International Journal of Data Science and Analytics，2022，13（2）： 77-89.

［29］Heins M J，Knoop H，Burk W J，et al. The process of cognitive beha-viour therapy for chronic fatigue syndrome： which changes in perpetuating cognitions and behaviour are related to a reduction in fatigue？［J］. Journal of Psychosomatic Research，2013，75（3）： 235-241.

［30］Rahmadi R，Groot P，Heins M，et al. Causality on cross-sectional data： stable specification search in constrained structural equation mo-deling［J］. Applied Soft Computing，2017，52： 687-698.