張 浩

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

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

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

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

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

1.1 因果網(wǎng)絡(luò)

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

1.2 d-分離準(zhǔn)則

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

(1)w在P上有—個(gè)碰撞箭頭，即→w←(此時(shí)稱w為碰撞點(diǎn))，且w及其后代結(jié)點(diǎn)都不在Z中.

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

1.3 條件獨(dú)立性測(cè)試

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

1.4 互信息理論

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

2 因果推斷算法

2.1 算法的基本框架

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

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

2.2 第一部分:搜索目標(biāo)節(jié)點(diǎn)的父子節(jié)點(diǎn)集

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

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

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

步驟3:應(yīng)用進(jìn)一步的條件獨(dú)立性測(cè)試:Ind(y;xi|S)，S為PC(y)xi的任意一個(gè)子集合，刪掉非父子節(jié)點(diǎn).

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

2.3 第二部分:對(duì)目標(biāo)節(jié)點(diǎn)和其父子節(jié)點(diǎn)集PC(y)中每個(gè)節(jié)點(diǎn)進(jìn)行方向識(shí)別

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

3 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

4 結(jié)論

本文提出了一種可以適應(yīng)于高維數(shù)據(jù)的因果網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法，首先通過基于條件獨(dú)立性測(cè)試和互信息的方法對(duì)數(shù)據(jù)集進(jìn)行初步結(jié)構(gòu)學(xué)習(xí)，然后再利用ANM算法對(duì)數(shù)據(jù)集中每兩點(diǎn)間的邊進(jìn)行方向識(shí)別，從而得到一個(gè)具體的因果網(wǎng)絡(luò)結(jié)構(gòu).通過仿真表明，在維數(shù)增加時(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］陳錫樞.基于貝葉斯網(wǎng)絡(luò)下的遺傳算法［J］.廣東工業(yè)大學(xué)學(xué)報(bào)，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.