一種高維數(shù)據(jù)的因果推斷算法

張 浩

(廣東工業(yè)大學應用數(shù)學學院，廣東廣州510520)

如何有效地分析數(shù)據(jù)之中的因果關系，進行因果推斷一直是數(shù)據(jù)分析研究領域的一個很重要的問題.雖然近年來很多學者提出了很多相關的研究成果［1-8］，但如何在高維數(shù)據(jù)間推斷其中的因果關系仍然沒有一個有效的方法.

因果推斷方法可以被分為兩大類:貝葉斯網絡結構學習算法［9-10］和基于加噪聲模型的因果推斷算法［11-13］.其中，貝葉斯網絡結構學習算法主要有兩種方法.第一種是基于打分－搜索的貝葉斯網絡結構學習方法，第二種是基于依賴分析的學習算法.然而，由于一個因果網絡可能存在很多馬爾科夫等價類.如果用評分函數(shù)去評價是同樣的分數(shù)，從依賴關系來看，馬爾科夫等價類間滿足同樣的條件獨立性，因而沒辦法區(qū)分出哪個結構才是數(shù)據(jù)間真正的結構.在基于加噪聲模型的算法方面，Shohei等人提出了一種基于線性ANM的算法［11］，可以從數(shù)據(jù)集中構建出具體的因果網絡圖.然而這種算法只適用于線性加噪聲模型，無法解決非線性問題.針對非線性問題，Hoyer等人提出了一種在基于非線性加噪聲模型的適用于連續(xù)數(shù)據(jù)的算法(ANM)［12］，Jonas Peters等人提出了一種基于非線性ANM的算法去解決離散數(shù)據(jù)的問題［13］.然而，這兩種非線性加噪聲模型算法都只適用很低維的數(shù)據(jù)集，一旦數(shù)據(jù)集的維度較大(n＞8)，準確度就會降到很低.近來，Janzing D等人提出了一種基于信息熵的因果推斷算法IGCI［14］，這種算法可以適用于有無噪聲的情況，但類似地，IGCI也無法處理高維數(shù)據(jù)，只要維數(shù)超過2，方法就失效.因而，目前還沒有能適用于高維數(shù)據(jù)集有效的因果推斷算法.

為了克服在高維數(shù)據(jù)中無法進行有效的因果推斷的缺點，本文提出了一種基于條件獨立性測試和互信息的因果網絡結構學習算法.該算法首先利用條件獨立性測試和互信息，求出每一個節(jié)點的父子節(jié)點，然后利用ANM算法，對目標節(jié)點與其每一個父子節(jié)點進行方向識別，然后得到每一個節(jié)點和其父子節(jié)點之間具體的因果關系，數(shù)據(jù)集中的所有變量都迭代完后得到數(shù)據(jù)集的一個完整因果網絡圖.數(shù)值實驗表明，該算法在高維數(shù)據(jù)下，精確度和時間花費都要優(yōu)于IGCI和基于加噪模型的因果網絡結構學習算法.

1 預備知識

1.1 因果網絡

因果網絡是表示變量間概率依賴關系的有向無環(huán)圖(DAG)，它可表示為一個三元組G=(N，E，P).其中，N={x1，x2，...，xn}表示DAG中的所有節(jié)點的集合，每個節(jié)點代表一個變量(屬性).E={e(xi，xj)|xi，xj∈N}表示DAG中每兩個節(jié)點間的有向邊的集合.其中，e(xi，xj)表示xi，xj間存在依賴關系xi→xj.P={P(xi|xj)|xi，xj∈N}是一組條件概率的集合，其中P(xi|xj)表示xi的父節(jié)點集xj對xi的影響.因果網絡實質上就是一個聯(lián)合概率分布P(x1，x2，…，xn)所有條件獨立性的圖形化表示.

1.2 d-分離準則

d-分離準則是描述因果網絡圖的一個重要圖性質.設X、Y、Z是因果無向圖G中任意3個互不相交的節(jié)點的集合，稱Z在圖G中d-分離節(jié)點集X和Y，記為X⊥Y|Z，如果對任意的從X的節(jié)點到Y的一個節(jié)點的路P均被Z阻斷，也就是路徑P上存在一個結點w滿足下列其中一個條件:

(1)w在P上有—個碰撞箭頭，即→w←(此時稱w為碰撞點)，且w及其后代結點都不在Z中.

(2)w在P上無碰撞箭頭，即→w→或←w←或←w→，且w∈Z.

1.3 條件獨立性測試

傳統(tǒng)的貝葉斯結構學習算法主要是基于條件獨立性測試，雖然這些算法無法區(qū)分馬爾科夫等價類，從而無法發(fā)現(xiàn)數(shù)據(jù)間所蘊含的具體的因果關系，但在一定程度上，識別出了網絡結構數(shù)據(jù)間的相關性，這對因果網絡結構學習提供了很大的幫助.d-分離準則為圖論和統(tǒng)計學間架設了一座橋梁，設X、Y、Z是因果無向圖G中任意3個互不相交的節(jié)點的集合，如果Zd-分離節(jié)點集X和Y，那么在給定Z的情況下，X和Y統(tǒng)計獨立.

1.4 互信息理論

互信息是信息論中的一個重要概率，描述了某個變量取值對另外一個變量的取值能力.兩個變量間的互信息越大，表明它們之間的關系緊密，反則越小.當且僅當X和Y互相獨立的時候，它們之間的互信息I(X;Y)=0.

2 因果推斷算法

2.1 算法的基本框架

算法主要分為兩部分，如圖1所示，算法的第一部分主要是利用條件獨立性測試找出每一個目標節(jié)點的父子節(jié)點集，也就是一個以目標節(jié)點為中心的無向圖.算法的第二部分是在已找出目標節(jié)點父子節(jié)點集的情況下，利用ANM算法對目標節(jié)點和每一個父子節(jié)點進行方向判別，得到一個目標節(jié)點與其父子節(jié)點間的具體因果關系.然后將該節(jié)點與其父子節(jié)點的因果結構更新到整個數(shù)據(jù)集的因果網絡，直到每個節(jié)點和其父子節(jié)點集PC(y)的因果圖都被更新完.最終得到一個完整地表現(xiàn)出數(shù)據(jù)間因果關系的因果網絡圖，從而推斷出了數(shù)據(jù)間具體的因果關系.算法的兩部分具體如下描述.

圖1 算法的基本框架Fig.1 Algorithm framework

2.2 第一部分:搜索目標節(jié)點的父子節(jié)點集

如上述所說，這部分目的是找出每一個節(jié)點的父子節(jié)點.對于任意一個變量集X={x1，x2，...，xn}，在X中選出一個變量y作為目標節(jié)點，然后PC(y)表示y的候選的父子節(jié)點集.在算法開始時候，令PC(y)=X.

步驟1:對PC(y)中的每一個節(jié)點{x1，x2，...，xn}和X進行獨立性測試，如果xi和y獨立，表明xi不是y的父子節(jié)點，將xi從PC(y)中移除.

步驟2:對PC(y)中的每對節(jié)點(xi，xj|xi，xj∈PC(y))進行條件獨立性測試:Ind(y;xi|xj)，如果xi和y在給定xj情況下條件獨立，則表明xi不是y的父子節(jié)點.在經過獨立性測試和條件獨立性測試后，PC(y)維數(shù)已經降低很多，但依然有很多非父子節(jié)點沒被移除.

步驟3:應用進一步的條件獨立性測試:Ind(y;xi|S)，S為PC(y)xi的任意一個子集合，刪掉非父子節(jié)點.

步驟4:由于條件獨立性測試在給定條件集太大的情況下精確度會降低，從而可能導致非父子節(jié)點被錯誤地當做了父子節(jié)點，所以此時算法采取基于一個互信息的策略，對一部分錯誤加入到PC(y)的節(jié)點進行修剪.由于變量間依賴性可以用互信息描述，假設xi是y的父子節(jié)點，那xi和y之間的互信息不會太低，所以可以設定一個閾值p，計算PC(y)中每一個變量與y之間的互信息，如果它們之間的互信息小于p，則認為該變量不是y的父子節(jié)點，然后從PC(y)中刪掉.

2.3 第二部分:對目標節(jié)點和其父子節(jié)點集PC(y)中每個節(jié)點進行方向識別

在這部分，采用ANM算法對每個目標節(jié)點和其父子節(jié)點集間的邊的方向進行判定.雖然ANM算法沒辦法解決超過8維的因果網絡結構學習問題，但由于在算法第一部分已經得到了目標節(jié)點y的父子節(jié)點集合PC(y)，然后利用ANM對PC(y)中的每一個變量和y間進行方向判別，這等同于在兩點間應用ANM，從而保證了它的有效性.

3 數(shù)值實驗

數(shù)值實驗是在Matlab2010b中完成，本文提出的算法被記為CIHD.實驗中的條件獨立性測試使用算法KCI-test［14］，計算互信息用Kraskov Mutual Information Estimator［16］.在實驗開始階段，分兩階段生成實驗數(shù)據(jù).(1)生成因果網絡圖;(2)按照該圖生成數(shù)據(jù).在因果網絡圖生成階段，分別生成15、25、50、80、150個節(jié)點的因果網絡圖，用來測試該算法在不同的高維數(shù)據(jù)下的實驗效果.在數(shù)據(jù)生成階段，每個節(jié)點的數(shù)據(jù)由因果網絡圖中節(jié)點的拓撲序列依照函數(shù)y=w1sin(x1)+w2sin(x2)+ε生成.其中w1、w2為每個函數(shù)的權值，隨機取值于0.3與0.7之間，x1、x2為y的父親節(jié)點，ε為權值為5%且均勻分布的添加噪聲.為了有效地評價該算法的性能，引入了3個評價參數(shù)Precision、Recall和F-value，定義如下:

從上面的定義可以看出，參數(shù)Precision用來衡量因果網絡圖中節(jié)點間本來不存在的邊被錯誤添加的程度，而參數(shù)Recall用來衡量節(jié)點間存在的邊沒有被發(fā)現(xiàn)的程度.參數(shù)F-value是前兩個評價參數(shù)的有機結合，因而可以用來評價因果網絡結構學習算法的總體優(yōu)劣.

實驗分別用15、25、50、80、150維的數(shù)據(jù)集對算法CIHD和基于非線性加噪模型的算法(ANM)以及IGCI進行對比，結果見圖2.

圖2 在不同維數(shù)下3種算法的評分參數(shù)Fig.2 Different dimension of sample

從圖2的實驗結果可以看出，在數(shù)據(jù)集維度都較高的情況下，ANM算法和IGCI算法的學習準確度都很低，而CIHD算法在高維增加的情況下3個評價參數(shù)依然保持著較高的分數(shù)，說明在高維數(shù)據(jù)中，CIHD要大大優(yōu)于另外兩種算法.

4 結論

本文提出了一種可以適應于高維數(shù)據(jù)的因果網絡結構學習算法，首先通過基于條件獨立性測試和互信息的方法對數(shù)據(jù)集進行初步結構學習，然后再利用ANM算法對數(shù)據(jù)集中每兩點間的邊進行方向識別，從而得到一個具體的因果網絡結構.通過仿真表明，在維數(shù)增加時，該算法大大優(yōu)于其他因果推斷算法.

［1］Pearl J.Causality:models，reasoning and inference［M］.Cambridge:MIT Press，2000.

［2］Spirtes P，Glymour C，Scheines R.Causation，prediction，and search［M］.Cambridge:MIT Press，2000.

［3］Uhler C，Raskutti G，Bühlmann P，et al.Geometry of the faithfulness assumption in causal inference［J］.The Annals of Statistics，2013，41(2):436-463.

［4］Cai R，Zhang Z，Hao Z.BASSUM:A Bayesian semi-supervised method for classification feature selection［J］.Pattern Recognition，2011，44(4):811-820.

［5］Shimizu S，Hoyer P O，Hyv?rinen A.Estimation of linear non-Gaussian acyclic models for latent factors［J］.Neurocomputing，2009，72(7):2024-2027.

［6］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.

［7］Janzing D，Scholkopf B.Causal inference using the algorithmic Markov condition［J］.IEEE Transactions on Information Theory，2010，56(10):5168-5194.

［8］陳錫樞.基于貝葉斯網絡下的遺傳算法［J］.廣東工業(yè)大學學報，2007，24(1):19-21.Chen X S.The genetic algorithm based on bayesian Net［J］.Journal of Guangdong University of Tehnology，2007，24(1):19-21.

［9］Tsamardinos I，Brown L E，Aliferis C F.The max-min hillclimbing Bayesian network structure learning algorithm［J］.Machine learning，2006，65(1):31-78.

［10］Shimizu S，Hoyer P O，Hyv?rinen A，et al.A linear non-Gaussian acyclic model for causal discovery［J］.The Journal of Machine Learning Research，2006，7:2003-2030.

［11］Hoyer P O，Janzing D，Mooij J M，et al.Nonlinear causal discovery with additive noise models［C］∥Advances in Neural Information Processing Systems.Vancouver，Canada:MIT Press，2009:689-696.

［12］Peters J，Janzing D，Scholkopf B.Causal inference on discrete data using additive noise models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33(12):2436-2450.

［13］Janzing D，Mooij J，Zhang K，et al.Information-geometric approach to inferring causal directions［J］.Artificial Intelligence，2012，56(10):5168-5194.

［14］Zhang K，Peters J，Janzing D，et al.Kernel-based conditional independence test and application in causal discovery［EB/OL］.(2012-02-14)［2013-10-24］.http:∥arxiv.org/ftp/arxiv/papers/1202/1202.3775.pdf.

［15］Kraskov A，St?gbauer H，Grassberger P.Estimating mutual information［J］.Physical Review E，2004，69(6):066138-066154.