李　巖　王　挺　劉萬(wàn)偉　張曉艷

1(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院　長(zhǎng)沙　410073)2　　　(國(guó)防科學(xué)技術(shù)大學(xué)人文與社會(huì)科學(xué)學(xué)院　長(zhǎng)沙　410073)

?

ICIC_Target:目標(biāo)節(jié)點(diǎn)的局部因果關(guān)系網(wǎng)絡(luò)的發(fā)現(xiàn)算法

李巖1王挺1劉萬(wàn)偉1張曉艷2

1(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院長(zhǎng)沙410073)2(國(guó)防科學(xué)技術(shù)大學(xué)人文與社會(huì)科學(xué)學(xué)院長(zhǎng)沙410073)

(liyannayil@nudt.edu.cn)

摘要因果關(guān)系的研究在于揭示自然規(guī)律的和人類(lèi)社會(huì)發(fā)展本質(zhì)及其規(guī)律，對(duì)人類(lèi)長(zhǎng)久以來(lái)的生產(chǎn)生活和科學(xué)研究有著非常重要的作用.目前，因果關(guān)系的研究受到前所未有的廣泛關(guān)注，但仍存在諸多困難和挑戰(zhàn).致力于建立一個(gè)因果激勵(lì)?抑制模型以抽象地表示和解釋因果的作用機(jī)制，并在此基礎(chǔ)上提出用于目標(biāo)節(jié)點(diǎn)的局部因果關(guān)系網(wǎng)絡(luò)的自動(dòng)發(fā)現(xiàn)方法框架ICIC和算法ICIC_Target.該方法不預(yù)先設(shè)定因果結(jié)構(gòu)(如設(shè)定為無(wú)圈、隱含結(jié)構(gòu))，并根據(jù)對(duì)因果關(guān)系本質(zhì)的認(rèn)識(shí)，利用初始變量(exogenous variables)和初始團(tuán)樹(shù)(IClique)的概念，在判定邊和方向之前對(duì)變量進(jìn)行粗略地排序，從而提高了因果關(guān)系網(wǎng)絡(luò)發(fā)現(xiàn)的性能.在4個(gè)不同類(lèi)型的數(shù)據(jù)集上實(shí)現(xiàn)了與多種經(jīng)典方法，如HITON，IC，PC，PCMB等的對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明ICIC_Target方法適用范圍廣,有較好的魯棒性，同時(shí)，從理論上分析證實(shí)了ICIC_Target方法具有較好的穩(wěn)定性和較低的復(fù)雜度.

關(guān)鍵詞因果關(guān)系；因果關(guān)系網(wǎng)絡(luò)；局部因果關(guān)系發(fā)現(xiàn)；激勵(lì)因果；抑制因果

因果關(guān)系的研究在于揭示自然和人類(lèi)社會(huì)發(fā)展本質(zhì)及其規(guī)律，以解釋現(xiàn)象、控制存在、預(yù)測(cè)未來(lái)，對(duì)人類(lèi)的生產(chǎn)生活和科學(xué)研究有著非常重要的作用.因果關(guān)系的研究歷史悠久，研究方法經(jīng)歷了“手工”、 “半自動(dòng)”和“全自動(dòng)”的發(fā)展過(guò)程.自20世紀(jì)80年代以來(lái)，許多數(shù)學(xué)理論和方法相繼提出，因果關(guān)系研究正式成為可計(jì)算的研究領(lǐng)域.Pearl[1]和Spirtes等人[2]指出因(cause)和果(effect)可以是事件(event)、屬性(feature)、物體(object)等多種類(lèi)型的實(shí)體(entities).為采樣的可行和計(jì)算的高效，該領(lǐng)域研究普遍使用不同類(lèi)型的隨機(jī)變量(variables)表示因果實(shí)體，變量的取值對(duì)應(yīng)于實(shí)體的數(shù)值或狀態(tài)值.概率統(tǒng)計(jì)和圖模型普遍應(yīng)用于發(fā)現(xiàn)和表示因果關(guān)系.因?yàn)楦怕士梢院芎玫仄鹾献兞康碾S機(jī)性、因果關(guān)系發(fā)現(xiàn)過(guò)程的不確定性和因果斷言的語(yǔ)義.有向無(wú)圈圖(directed acyclic graph， DAG)或貝葉斯網(wǎng)絡(luò)(Bayesian network)這種最常用的圖模型，可以生動(dòng)準(zhǔn)確地表達(dá)因果關(guān)系結(jié)構(gòu)，其中網(wǎng)絡(luò)節(jié)點(diǎn)表示變量系統(tǒng)(簡(jiǎn)稱(chēng)系統(tǒng))，節(jié)點(diǎn)間的邊表示因果關(guān)系的存在，邊的方向表示因果關(guān)系的存在方式.但是貝葉斯網(wǎng)絡(luò)無(wú)法表示多變量間循環(huán)作用(圈)或2個(gè)變量間相互作用(雙向邊)的因果關(guān)系，而這些因果關(guān)系是真實(shí)存在且常見(jiàn)的，因此本文采用可以包容圈和雙向邊的寬松結(jié)構(gòu)(loose network)表示真實(shí)的因果關(guān)系網(wǎng)絡(luò).

因果關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)的發(fā)現(xiàn)是因果關(guān)系研究的重要內(nèi)容，即給定有限數(shù)量和范圍的實(shí)體及其采樣值，發(fā)現(xiàn)全局因果關(guān)系網(wǎng)絡(luò)或關(guān)于目標(biāo)實(shí)體的局部因果關(guān)系網(wǎng)絡(luò).大量真實(shí)環(huán)境下的因果關(guān)系發(fā)現(xiàn)問(wèn)題(causal problem， CP)僅僅需要確定給定的目標(biāo)變量周?chē)木植恳蚬W(wǎng)絡(luò)結(jié)構(gòu)，還有許多問(wèn)題涉及的全局網(wǎng)絡(luò)結(jié)構(gòu)過(guò)于龐大和復(fù)雜，全局網(wǎng)絡(luò)結(jié)構(gòu)的發(fā)現(xiàn)成了非常困難的任務(wù).因此發(fā)現(xiàn)給定目標(biāo)變量的若干層因果關(guān)系網(wǎng)絡(luò)成為了因果關(guān)系發(fā)現(xiàn)的常見(jiàn)任務(wù)，記為CP(Vo,vt,D)，即在已知數(shù)據(jù)集D上找出給定目標(biāo)變量vt在可觀測(cè)變量Vo中的父、子、配偶等變量以及這些變量之間的因果聯(lián)系.

Pearl[1]，Spirtes等人[2]，Cooper等人[3-4]在各自經(jīng)典著作中討論了如何在不同的應(yīng)用背景和數(shù)據(jù)類(lèi)型下正確高效發(fā)現(xiàn)因果關(guān)系，其中最核心的理論部分是因果關(guān)系的定義(尤其是Granger[5]和Pearl[1]提出的定義)、Markov條件、d-割準(zhǔn)則(d-separation criterion)和忠實(shí)性定理(faithfulness theorem).其中Markov條件獨(dú)立是貝葉斯網(wǎng)絡(luò)表示因果關(guān)系應(yīng)滿足的基本假設(shè)，也是本文提出的寬松結(jié)構(gòu)在表示有向無(wú)圈的真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)應(yīng)滿足的假設(shè).

目前，因果關(guān)系的研究受到廣泛關(guān)注[1,6]，但由于環(huán)境、人為因素的復(fù)雜多變并且不可控，真實(shí)環(huán)境下的因果關(guān)系發(fā)現(xiàn)仍存在諸多困難和挑戰(zhàn).這是因?yàn)椋赫鎸?shí)環(huán)境下因果關(guān)系發(fā)現(xiàn)獲得的數(shù)據(jù)來(lái)自人們對(duì)可觀測(cè)屬性“靜態(tài)”或“被動(dòng)”的觀測(cè)[4]，是真實(shí)環(huán)境下隨機(jī)因素與因果關(guān)系共同作用的結(jié)果，并按照某種方式在某些時(shí)刻采樣獲得，是關(guān)于真實(shí)世界的“靜態(tài)”片段，因此無(wú)法像在實(shí)驗(yàn)室環(huán)境下通過(guò)干預(yù)(intervention或manipulation)某些屬性的取值從而獲得其他屬性取值變化的“動(dòng)態(tài)”數(shù)據(jù)，也無(wú)法像使用實(shí)驗(yàn)室數(shù)據(jù)那樣可以根據(jù)先驗(yàn)知識(shí)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)做出合理的假設(shè)并做出驗(yàn)證；真實(shí)環(huán)境下因果關(guān)系還可能受到若干不可觀測(cè)因素(hidden features)的影響，僅考慮那些可觀測(cè)屬性(observational features)的因果關(guān)系網(wǎng)絡(luò)則不能完全正確地反映真實(shí)因果(underlying causality mechanism).如何僅從“靜態(tài)”觀測(cè)數(shù)據(jù)還原真實(shí)的因果關(guān)系網(wǎng)絡(luò)，且不做任何關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)的先驗(yàn)假設(shè)，如是否存在圈或隱含變量的假設(shè)，是非常困難的，甚至被認(rèn)為是在現(xiàn)有理論框架下不可能完成的任務(wù).

針對(duì)以上問(wèn)題，本文基于Pearl等人提出的因果關(guān)系經(jīng)典理論和方法，通過(guò)分析因果關(guān)系發(fā)生和作用的本質(zhì)特性，利用初始變量(exogenous or instr-umental variable)、初始團(tuán)樹(shù)(initial clique of an exo-genous variable， IClique)和Markov條件獨(dú)立判定來(lái)解決真實(shí)環(huán)境下局部因果關(guān)系發(fā)現(xiàn)問(wèn)題(詳見(jiàn)2.1節(jié))，并提出了性能更高、魯棒性更強(qiáng)的局部因果關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法ICIC_Target(詳見(jiàn)2.3節(jié)).該方法主要用于目標(biāo)節(jié)點(diǎn)的因果關(guān)系網(wǎng)絡(luò)的發(fā)現(xiàn)，同時(shí)針對(duì)二值數(shù)據(jù)系統(tǒng)區(qū)別了激勵(lì)因果(stimulating causality)和抑制因果(inhibiting causality)兩種因果模型，發(fā)現(xiàn)了一些新型的因果關(guān)系.不同于IC和PC等經(jīng)典方法假設(shè)因果網(wǎng)絡(luò)為無(wú)圈和無(wú)隱含變量(hidden variable)，ICIC_Target方法不預(yù)先設(shè)定因果結(jié)構(gòu)，從而提高了方法的性能和魯棒性.ICIC_Target不僅在理論上具有可靠性、穩(wěn)定性，在多數(shù)據(jù)集、多評(píng)估體系下與多種經(jīng)典方法實(shí)驗(yàn)結(jié)果的比較同樣具有優(yōu)越的性能.另外，本文將因果研究常用的小品集LUCAS(lung cancer simple set)[7-8]作為應(yīng)用樣本以清晰展示ICIC_Target方法的細(xì)節(jié).

1相關(guān)工作

因果關(guān)系研究正式成為可計(jì)算的研究領(lǐng)域后，各種因果表示模型、因果發(fā)現(xiàn)預(yù)測(cè)方法大量出現(xiàn)，并逐漸形成兩大學(xué)派：以圖靈獎(jiǎng)獲得者Pearl[1]為代表人物的UCLA & CMU學(xué)派和Cooper等人[9]為代表的Stanford學(xué)派，他們出版于1999年的專(zhuān)著為因果關(guān)系研究奠定了堅(jiān)實(shí)基礎(chǔ).

1.1IC，PC，LCD和IC*，F(xiàn)CI方法

對(duì)于多變量系統(tǒng)，Pearl等人的研究思路是從找出條件獨(dú)立的片斷開(kāi)始，最后將各個(gè)片斷合成為全局的因果關(guān)系結(jié)構(gòu)，最具代表性的經(jīng)典方法有Pearl[1]的IC(inductive causation)方法和Spirtes等人[2]的PC方法.而Cooper等人[4,9]的研究思路是對(duì)于給定的數(shù)據(jù)和參數(shù)，先為一個(gè)貝葉斯網(wǎng)絡(luò)(即候選因果網(wǎng)絡(luò))指派先驗(yàn)概率，然后根據(jù)因果關(guān)系網(wǎng)絡(luò)與數(shù)據(jù)的擬合度打分，在可能的結(jié)構(gòu)空間上搜索具有最大后驗(yàn)概率的結(jié)構(gòu)，用于更新網(wǎng)絡(luò)，以達(dá)到最優(yōu).Cooper等人[4]提出的LCD(local causal discovery)屬于此類(lèi)方法.該方法需要輸入一個(gè)或多個(gè)初始變量作為因果網(wǎng)絡(luò)結(jié)構(gòu)的根節(jié)點(diǎn)，如性別、年齡等變量是研究疾病問(wèn)題公認(rèn)的初始變量.這樣可以充分利用問(wèn)題本身提供的關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)的先驗(yàn)知識(shí)，實(shí)驗(yàn)證明初始變量有助于提高發(fā)現(xiàn)的準(zhǔn)確性和效率[4]，但對(duì)于大量無(wú)法預(yù)知初始變量的問(wèn)題，LCD方法的局限性顯而易見(jiàn).Stanford學(xué)派的研究思路應(yīng)用廣泛，但Pearl[1]認(rèn)為此類(lèi)方法有很高的復(fù)雜性，事實(shí)上只能從局部到局部最優(yōu)且不適用于小樣本數(shù)據(jù)，不能靈活處理存在不確定、不可觀測(cè)變量的情況，并且該研究思路假定參數(shù)獨(dú)立.而Pearl等人的IC，PC方法復(fù)雜度相對(duì)較低，對(duì)樣本數(shù)據(jù)大小要求不高.

以上方法均不適用于存在隱含變量的因果關(guān)系發(fā)現(xiàn)問(wèn)題.因此，Pearl[1]和Spirtes等人[2]提出了IC*(inductive causation with latent variable)和FCI(fast causal inference algorithm)方法.隱含變量的存在導(dǎo)致可觀測(cè)變量之間的因果關(guān)系發(fā)生不同程度的變化，因此在IC*和FCI方法中修改了邊的方向表示，使用雙向邊、“*”或“o”等符號(hào)以增強(qiáng)邊所能表達(dá)的語(yǔ)義.根據(jù)邊的語(yǔ)義變化，IC*和FCI方法在IC和PC方法上調(diào)整了因果的判定規(guī)則并做了其他較大改進(jìn)，以適應(yīng)可能存在隱含變量的情況，同時(shí)改善了算法的性能.IC*和FCI方法與本文提出的ICIC_Target方法都適用于隱含變量因果關(guān)系發(fā)現(xiàn)問(wèn)題，但I(xiàn)C*和FCI發(fā)現(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)的語(yǔ)義復(fù)雜、算法復(fù)雜度高.

1.2PCMB，IAMB，HITON系列方法

HITON-PC(HITON_parents & children)和HITON-MB(HITON_Markov blanket)方法是Aliferis等人[10]于2003年提出經(jīng)典的特征選擇方法，用于發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)(target variable)的父子節(jié)點(diǎn)(記為PCset)和包含目標(biāo)節(jié)點(diǎn)及其父子節(jié)點(diǎn)和配偶節(jié)點(diǎn)的Markov毯(Markov blanketboundary，MBset)，這些節(jié)點(diǎn)對(duì)于預(yù)測(cè)目標(biāo)節(jié)點(diǎn)的取值有著重要的作用，因此HITON也可看作是局部因果關(guān)系發(fā)現(xiàn)方法.2006年Tsamardinos等人[11]提出HITON等方法缺少“對(duì)稱(chēng)性校正(symmetry correction)”，在理論上不正確.但HITON-PC方法仍成為NIPS 2008舉辦的第2屆Causality Challenge中LOCANET(uncover the local causal network around the target)任務(wù)的標(biāo)準(zhǔn)(state-of-the-art)因果發(fā)現(xiàn)算法，用以獲得質(zhì)量保證測(cè)試的基準(zhǔn)結(jié)果(baseline results)[12].Aliferis等人[13]在2010年的綜述文章中解釋說(shuō)HITON使用了啟發(fā)式搜索方法作為后處理步驟(a wrapping post-processing)，在原理上可以去掉錯(cuò)誤的正例，因此未做對(duì)稱(chēng)性校正的HITON方法仍具有優(yōu)越的性能.2007年P(guān)ea等人[14]提出了理論上正確的PCMB方法，用于發(fā)現(xiàn)PCset或MBset.Pea等人將PCMB方法與同樣在理論上正確但數(shù)據(jù)低效(data inefficient)的IAMB方法進(jìn)行了比較.

美國(guó)Vanderbilt大學(xué)的生物醫(yī)學(xué)信息系開(kāi)發(fā)的因果關(guān)系發(fā)現(xiàn)工具Causal Explorer library[15-16]，用matlab實(shí)現(xiàn)了HITON，IAMB等多種經(jīng)典方法.Pea用C++實(shí)現(xiàn)了PCMB和IAMB方法[17].然而這些方法的輸出是PCset或MBset而非網(wǎng)絡(luò)結(jié)構(gòu)，因此無(wú)法表達(dá)更詳細(xì)更準(zhǔn)確的因果作用機(jī)制.

1.3GC系列方法

早在1969年，諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)獲得者Granger[5]就給出了時(shí)序問(wèn)題的因果關(guān)系(Granger causality，GC)定義：若用時(shí)間序列U的歷史信息預(yù)測(cè)時(shí)序變量X好于在U中排除時(shí)序Y后的歷史信息預(yù)測(cè)X的結(jié)果，則Y是X原因，記為Y→X.Granger認(rèn)為“因”有助于提高對(duì)“果”預(yù)測(cè)的性能.GC含義明確、可操作性強(qiáng)，被時(shí)序問(wèn)題研究領(lǐng)域的研究人員所接受，并在此基礎(chǔ)上做了很多改進(jìn)，取得了大量成果[18-20].其中具有代表性的是2004年?yáng)|京大學(xué)的研究[18]，將GC中的方差改進(jìn)為轉(zhuǎn)移熵(transfer entropy)，并將因果關(guān)系描述為：Y是X的原因，若時(shí)序Y的歷史信息為預(yù)測(cè)時(shí)序X提供了顯著的幫助.這種改進(jìn)的因果關(guān)系定義和GCTE方法可以幫助研究不同類(lèi)型的時(shí)序變量間的因果關(guān)系.

但是“利于預(yù)測(cè)”并不是因果關(guān)系的本質(zhì)，為此Pearl[1]反駁道GC應(yīng)該歸為統(tǒng)計(jì)學(xué)范疇而非因果關(guān)系.因?yàn)樵诓荒苊鞔_時(shí)序時(shí)，滿足GC的X和Y之間的方向不明確.即使Y→X，此時(shí)已知X的歷史信息Y也會(huì)被更好地預(yù)測(cè)，即X→Y同樣成立.

1.4其他方法

2006年Shimizu等人[21]提出了一種全新的因果關(guān)系發(fā)現(xiàn)方法LiNGAM(linear non-Gaussian acyclic model).該方法利用獨(dú)立成份分析的方法估計(jì)方程組x=Ae中的混合矩陣A，以獲得變量間相互作用的線性方程，其中x是各變量的觀測(cè)值組成的矩陣，e由各變量自帶的隨機(jī)擾動(dòng)(disturbance variables)組成.LiNGAM計(jì)算A使得e的分量盡可能滿足兩兩獨(dú)立，但前提是這些隨機(jī)擾動(dòng)是兩兩獨(dú)立且服從非高斯分布，同時(shí)因果關(guān)系非循環(huán)(無(wú)圈結(jié)構(gòu))且滿足線性方程，否則方法可能會(huì)產(chǎn)生錯(cuò)誤結(jié)果.

SI(similarity index)是Arnhold等人[22]提出的另一類(lèi)針對(duì)時(shí)序數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)方法，通過(guò)計(jì)算2個(gè)時(shí)間序列在同一起始時(shí)刻開(kāi)始的相同長(zhǎng)度片斷上的平均相似程度來(lái)判斷時(shí)序變量是否存在因果關(guān)系.我們認(rèn)為該方法對(duì)于同步和異步變化的2個(gè)時(shí)間序列的相似判定都非常適用，但因果關(guān)系的方向難以判斷，并且需要給定參數(shù)R，該參數(shù)與算法的性能和復(fù)雜度密切相關(guān).文獻(xiàn)[23]指出SI的最大缺點(diǎn)是很難判定弱因果結(jié)構(gòu)和帶噪音時(shí)序的因果.

2因果關(guān)系發(fā)現(xiàn)方法ICIC_Target

針對(duì)真實(shí)環(huán)境下局部因果關(guān)系發(fā)現(xiàn)，即未知真實(shí)網(wǎng)絡(luò)是否存在隱含變量(IC，PC方法假設(shè)網(wǎng)絡(luò)不含隱含變量)、是否是無(wú)圈網(wǎng)絡(luò)(IC，PC，LiNGAM方法均假設(shè)網(wǎng)絡(luò)為DAG)、是否存在初始變量(LCD方法不適用無(wú)初始變量的問(wèn)題)、是否帶噪音(LiNGAM方法假設(shè)噪音兩兩獨(dú)立且服從非高斯分布，SI方法對(duì)帶噪音時(shí)序的因果判定困難)等，為提高因果發(fā)現(xiàn)性能(GC方法易產(chǎn)生冗余關(guān)系，HITON等方法沒(méi)有明確網(wǎng)絡(luò)結(jié)構(gòu))、增強(qiáng)算法的魯棒性(IC等方法適用于案例數(shù)據(jù)，GC和SI方法適用于時(shí)序數(shù)據(jù))，本節(jié)通過(guò)分析因果關(guān)系發(fā)生和作用的本質(zhì)特性，利用初始變量和初始團(tuán)樹(shù)，提出了性能更高、魯棒性更強(qiáng)的局部因果關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)方法ICIC_Target，并形式化介紹該方法的框架和技術(shù)細(xì)節(jié)，包括方法涉及的理論基礎(chǔ)、技術(shù)特點(diǎn)、方法流程、程序偽代碼和因果關(guān)系分析.

2.1因果關(guān)系的本質(zhì)和分類(lèi)

因果關(guān)系的本質(zhì)是因果關(guān)系研究的首要問(wèn)題，所有因果發(fā)現(xiàn)方法都基于研究者對(duì)因果關(guān)系的理解.1999年P(guān)earl[1]給出了經(jīng)典的因果關(guān)系的描述：在某個(gè)相對(duì)穩(wěn)定的系統(tǒng)中，重復(fù)控制并改變(inter-vention)其中的某個(gè)或某些變量X時(shí)，另一些變量Y總是隨之發(fā)生變化，則X是Y的原因(前驅(qū))，Y是X的結(jié)果(后繼)，其中X和Y均表示變量集合.Pearl的描述符合人類(lèi)對(duì)因果的認(rèn)知，適用于不同領(lǐng)域，不針對(duì)特定數(shù)據(jù)，具有一般性，因此得到了廣泛認(rèn)可.但Pearl的描述只能為判定因果關(guān)系提供思路，在實(shí)際應(yīng)用中可操作性不強(qiáng).

基于Pearl的描述，我們對(duì)因果關(guān)系有著更深層次的認(rèn)識(shí)：

1) 因果關(guān)系是客觀存在的自然現(xiàn)象和事物間相互作用的約束規(guī)則，無(wú)需第三方的操控(intervention)因果也會(huì)發(fā)生.

2) 因果關(guān)系不能改變果變量Y的本質(zhì)屬性，但可以改變Y在這些屬性上的概率，即Y從原有狀態(tài)PY,t(時(shí)刻t時(shí)Y的概率分布)變化為PY,t′(時(shí)刻t′>t時(shí)Y的概率分布)，因此只要變量X使得Y在若干屬性(而不是全部屬性)上的概率發(fā)生變化即可認(rèn)為X,Y存在因果關(guān)系.與Pearl的基本思想吻合但略有不同，我們認(rèn)為果變量取值的改變只是因果關(guān)系的表象，究其根本是因果關(guān)系導(dǎo)致果變量的概率分布的改變，這是真實(shí)環(huán)境下基于大量觀測(cè)數(shù)據(jù)發(fā)現(xiàn)因果關(guān)系的基礎(chǔ).

3) 因果關(guān)系可分為2種基本類(lèi)型：激勵(lì)因果和抑制因果.因果關(guān)系使果變量Y的某些關(guān)注屬性(focused features)發(fā)生的概率增加(我們稱(chēng)這樣的因果關(guān)系為激勵(lì)因果)或減少(稱(chēng)為抑制因果)，同時(shí)在另一些屬性上概率減少(稱(chēng)為因果關(guān)系對(duì)屬性的抑制作用)或增加(稱(chēng)為激勵(lì)作用).

4) 原始概率分布(original probability distribution)PX,O是一類(lèi)最基本的原有狀態(tài)，即變量X未受任何因果關(guān)系作用時(shí)的概率分布，我們稱(chēng)其為自由態(tài)下的概率分布，此時(shí)只有隨機(jī)擾動(dòng)和變量固有的概率分布決定變量的取值.

2.2基本符號(hào)和概念

2.2.1基本符號(hào)

一個(gè)因果關(guān)系系統(tǒng)(causality system， CS)，如癌癥預(yù)防與檢測(cè)系統(tǒng)等，通常包含一個(gè)變量系統(tǒng)V和關(guān)于V的因果關(guān)系邊集E?V×V.一個(gè)因果關(guān)系發(fā)現(xiàn)問(wèn)題CP通常會(huì)給定可觀測(cè)變量系統(tǒng)Vo?V、目標(biāo)變量(target variable)vt∈Vo和Vo的一組采樣數(shù)據(jù)D.常見(jiàn)任務(wù)是發(fā)現(xiàn)目標(biāo)變量的3層因果關(guān)系網(wǎng)絡(luò)，即vt的父、子、配偶變量以及這些變量之間的因果聯(lián)系.在因果關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)(causal network)中，點(diǎn)代表變量，邊表示因果關(guān)系，邊的方向是從因變量指向果變量.我們使用斜體小寫(xiě)字母，如a，b表示可觀測(cè)變量.用小寫(xiě)字母，如a表示變量a的某個(gè)取值(或狀態(tài))；對(duì)于二值系統(tǒng)，通常用a表示取值為1(或真)，用a表示取值為0(或假)，pa表示變量a取值為1的概率，pa|b表示條件概率P(a=1|b=1).若v∈V，則用Pred(v)表示v在V中的所有前驅(qū)(predecessor)節(jié)點(diǎn)集合，即E中存在從前驅(qū)節(jié)點(diǎn)到v的有向路徑；Parents(v)表示v在V中的父節(jié)點(diǎn)集合，即v的直接前驅(qū)集合；用Descend(v)表示v的后繼(descendant)節(jié)點(diǎn)集合；Children(v)表示v在V中的子節(jié)點(diǎn)集合，即v的直接后繼集合.對(duì)于2節(jié)點(diǎn)a，b之間的無(wú)向邊，我們用a—b表示；有向邊則為a→b.

2.2.2數(shù)據(jù)集類(lèi)型

因果關(guān)系問(wèn)題CP(Vo,D)的觀測(cè)數(shù)據(jù)集D對(duì)因果關(guān)系發(fā)現(xiàn)十分重要.一般地，D以矩陣的形式呈現(xiàn)，列代表變量，行代表觀測(cè)值，一行觀測(cè)值也稱(chēng)為一個(gè)采樣(sample).如圖1所示，D的收集方式有2種：1)案例采樣(case sampling)，即從不同的個(gè)體上對(duì)相同的變量進(jìn)行采樣獲得;2)序列采樣(sequences ampling)，即對(duì)指定個(gè)體上的變量在時(shí)間軸上進(jìn)行持續(xù)采樣.2種方式的采樣獲取的C型和S型數(shù)據(jù)有很大的差別.由于S型數(shù)據(jù)能夠發(fā)現(xiàn)諸如某變量的歷史信息影響自身或其他變量的當(dāng)前狀態(tài)的情況，網(wǎng)絡(luò)結(jié)構(gòu)中常常會(huì)出現(xiàn)自圈(self-loop)、雙向邊(bi-directed edge)甚至更大的圈(cycle).因此，預(yù)先限定因果關(guān)系問(wèn)題的網(wǎng)絡(luò)結(jié)構(gòu)為有向無(wú)圈圖(DAG)是不可行的.根據(jù)2.1節(jié)的描述，我們認(rèn)為網(wǎng)絡(luò)結(jié)構(gòu)是有向圖(directed graph， DG)更合理.本文的實(shí)驗(yàn)數(shù)據(jù)集包含C型、S型以及兩者混合型M型(詳見(jiàn)3.1.1節(jié)關(guān)于SIGNET數(shù)據(jù)集的介紹)，那些預(yù)先設(shè)定網(wǎng)絡(luò)結(jié)構(gòu)為DAG的方法在S型和M型數(shù)據(jù)集上無(wú)法獲得較好的實(shí)驗(yàn)結(jié)果.

(a) Feature choosing

CasesVariable1Variable2…VariablenCase1(person1)dC(1,1)dC(1,2)…dC(1,n)Case2(person2)dC(2,1)dC(2,2)…dC(2,n)????Casem(personm)dC(m,1)dC(m,2)…dC(m,n)Total:mpersons;sizeofdatasetC:m×n.(b)Casesampling:CtypeTimeVariable1Variable2…Variablent1dS(1,1)dS(1,2)…dS(1,n)t2dS(2,1)dS(2,2)…dS(2,n)????tmdS(m,1)dS(m,2)…dS(m,n)Total:mtimemoments;sizeofdatasetS:m×n.(c)Sequencesampling:Stype

Fig. 1The illustration of C type and S type of datasets from two processes of case sampling and sequence sampling.
圖1C型和S型數(shù)據(jù)集示意圖

2.2.3基本概念

給定一個(gè)因果關(guān)系系統(tǒng)(V,E)和其因果關(guān)系圖G，我們將定義涉及ICIC_Target方法的若干重要概念.

Fig. 2　Causal network of LUCAS and redundant edges ICIC discovered.圖2　LUCAS的真實(shí)因果網(wǎng)絡(luò)結(jié)構(gòu)和ICIC發(fā)現(xiàn)的冗余邊

定義4. 初始模式(exogenous pattern， EVP).evpi(i=0,1,…,m)是初始模式當(dāng)且僅當(dāng)evp0=(v1,v2,…,vm)，evpi=(v1,…vi-1,vi,vi+1,…,vm)1≤i≤m，其中,是初始變量個(gè)數(shù).表示圖G的所有初始模式的集合.圖3(b)中evp0=(v3,v4,v5,v10)，evp2=(v3,v4,v5,v10).

定義5. 模式(pattern).定義任意2個(gè)變量vi,vj∈V的模式為Patterni,j=(vi1,…,vi l,vj1,…,vjk)，其中Parents(vi){vj}={vi1,vi2,…,vi l}，Parents(vj){vi}={vj1,vj2,…,vjk}.圖3(b)中，Pattern0,1=(v3,v4,v5).定義任意變量vi∈V的模式為Patterni=(vi1,vi2,…,vi l′)，其中Parents(vi)={vi1,vi2,…,vi l′}.

Fig. 3　ICliques and ICliques graph of LUCAS .圖3　LUCAS的初始團(tuán)樹(shù)和初始團(tuán)樹(shù)圖

2.3ICIC方法框架

為提高因果發(fā)現(xiàn)算法的魯棒性，降低復(fù)雜性，ICIC方法框架在數(shù)據(jù)預(yù)處理之后包含5個(gè)核心步驟：1)確定初始變量；2)構(gòu)建初始團(tuán)樹(shù)；3)發(fā)現(xiàn)無(wú)向圖；4)添加方向；5)刪除冗余邊.

鑒于IC等經(jīng)典方法生成v結(jié)構(gòu)(v-structure)和添加方向規(guī)則造成的諸多問(wèn)題，如算法復(fù)雜性高、魯棒性低等，ICIC步驟1)、步驟2)通過(guò)發(fā)現(xiàn)初始變量和初始團(tuán)樹(shù)獲取因果網(wǎng)絡(luò)的大體分支和層次結(jié)構(gòu).實(shí)驗(yàn)和理論分析證明，這樣可以在v結(jié)構(gòu)形成之前獲得關(guān)于方向的粗略信息，使得發(fā)現(xiàn)無(wú)向圖和添加的方向更合理，算法運(yùn)行速度也會(huì)明顯提升.

ICIC步驟3)利用改進(jìn)的d-割判定條件獲得帶有冗余邊的無(wú)向圖.以常見(jiàn)的二值離散變量系統(tǒng)為例，ICIC利用d-割判定公式獲取d-割集，將判定條件由IC方法在各種取值組合下d-割判定公式(式(1))都成立更改為式(2)～(5)各式之一成立即可判定a，b之間無(wú)邊.ICIC方法對(duì)二值離散變量系統(tǒng)區(qū)分生成激勵(lì)和抑制因果無(wú)向圖.我們通常認(rèn)定對(duì)果變量1值的提升是激勵(lì)因果關(guān)系，對(duì)1值的降低是抑制因果關(guān)系，這符合人們的習(xí)慣.對(duì)于多值變量系統(tǒng)，可以通過(guò)用戶(hù)指定關(guān)注值獲得激勵(lì)和抑制因果結(jié)構(gòu).

(1)

(2)

P(a|

(3)

P(a|b,c)=P(

(4)

P(a|b,c)=P(a|c),c=0 or 1.

(5)

ICIC步驟4)根據(jù)前3步的結(jié)果添加方向后，在步驟5)回溯所有可能的冗余邊，確定為冗余后刪除該邊.我們遍歷所有三角形結(jié)構(gòu)中每一條非公共邊作為可能的冗余邊，見(jiàn)圖2(b)所示，ICIC將保留那些至少2個(gè)三角形結(jié)構(gòu)公有邊(加粗實(shí)邊)，虛線邊是判定為冗余的邊，其作用可以由其他邊替代.ICIC方法不預(yù)先限定因果關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)，因此對(duì)存在雙向邊或圈等結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)的發(fā)現(xiàn)結(jié)果更有效.

2.4初始變量與初始團(tuán)樹(shù)

2.4.1初始變量的發(fā)現(xiàn)

初始變量的發(fā)現(xiàn)是ICIC方法框架的步驟1)和重要步驟.在Vo中尋找初始變量EV是二值分類(lèi)問(wèn)題，特征也看似很明顯.但在大多數(shù)應(yīng)用中，初始變量的發(fā)現(xiàn)并非易事.首先，所有變量的原有分布PZ,t未知；其次，在未知初始變量的前提下，任何變量之間的條件概率pa|b都不能輕易地認(rèn)為等同于pa|do(b).因此本文初始變量的發(fā)現(xiàn)方法EVD主要基于2點(diǎn)：1)根據(jù)初始變量的基本性質(zhì)，通過(guò)所有已知變量參與投票的方式找出最可能的初始變量；2)區(qū)分激勵(lì)和抑制可以幫助化簡(jiǎn)初始變量的發(fā)現(xiàn)難度.EVD方法的具體實(shí)現(xiàn)見(jiàn)算法1，其中利用已發(fā)現(xiàn)的初始變量尋找其他初始變量的步驟需要計(jì)算初始團(tuán)樹(shù)(詳見(jiàn)EVD的Step2.2)，計(jì)算方法詳見(jiàn)函數(shù)computeIClique()，其具體含義和解釋則見(jiàn)2.4.2節(jié).

算法1. EVD.

輸入:變量集V、數(shù)據(jù)集D;

Step2. while (|currentV|的值減少)

Step2.1. if (vi∈currentV,vi是常量)R←R∪{vi};

else if (max(P1)?min(P1))

if (pvi i-min(P1)<β||

if (?va(currentVs.t.

(|pvi i|va-pvi i|va|-|pva|vi i-

pva|vi i|)<β)

R←R∪{vi i,va};

endif

elseR←R∪{vi i};

endif

endfor

endif

else

P0←computeOneOne(currentV,

Step2.2. for ?vi∈R

ICliquei{Vi,Hi}←

endfor

else

{ICliquei{Vi,Hi}};

endif

Step2.3.currentV←currentVVi;

Step3. if (|currentV|>0)

if ((pvk|vi-pvk|vi)?0)

Vi←Vi∪{vk},

currentV←currentV{vk};

endif

endfor

endif

FunctioncomputeOneOne(currentV,P1,D)

Step1. 初始化P0←?;

Step2. for ?vi∈currentV

num←samples {v0,…,vi-1,vi,

p←num(|D|×pvi), where

pvi∈P1;P0←P0∪{p};

endfor

Step3. returnP0;

Step1. 初始化Vi←{vi},Hi←?;

hvi j←pvj|evpi-pvj|evp0;

if (hvi j>β)Vi←Vi∪{vj},Hi←Hi∪{hvi j};

endif

endfor

Step3. returnICliquei{Vi,Hi};

以發(fā)現(xiàn)激勵(lì)因果為例，對(duì)任意變量a：1)a=1(關(guān)注值)的概率pa越小，則a受激勵(lì)的機(jī)會(huì)越??；2)vi∈V{a}，|pa|vi-pa|vi||Q11iQ10i|越小，則a受V中其他變量激勵(lì)的可能越??；3)?b∈V{a}，|pa|b-pa|b|?|pb|a-pb|a|，則b越有可能受a激勵(lì)，而非a受b激勵(lì).以上判斷顯示a有可能是激勵(lì)因果網(wǎng)絡(luò)的初始或孤立變量，如圖4中的變量v5.還有一類(lèi)變量b，盡管pb值足夠小，但b存在已確定的因變量，因此不是初始變量，如圖4中的變量v6.為了剔除這樣的變量和孤立變量，本文EVD方法在確定某變量v是初始變量前計(jì)算該變量的ICliquev.若ICliquev只包含根v，則表明v是孤立變量；若ICliquev包含其他變量vi，則vi是v的后繼，且算法將不再遍歷vi，即當(dāng)前活躍變量集currentV不再包含v和vi.另外，在數(shù)據(jù)集中取值為常數(shù)的變量也符合初始變量的特性.若因果關(guān)系網(wǎng)絡(luò)不含初始變量，則該網(wǎng)絡(luò)一定有圈.這種情況下，由若干概率值或以彼此作為條件的概率值較接近的變量形成的圈起到了初始變量的作用，這些變量的初始團(tuán)樹(shù)將包含圈內(nèi)的鄰接變量.當(dāng)所有變量的概率值都非常接近時(shí)，我們比較這些變量的“非激勵(lì)影響”，即變量取1而其他變量為0的概率，詳見(jiàn)算法1的函數(shù)computeOneOne().擁有最小“非激勵(lì)影響”的變量vj暫時(shí)加入初始變量集，計(jì)算獲得其ICliquej，并依據(jù)Vj包含的非初始變量對(duì)currentV中剩余變量的“影響力”(詳見(jiàn)算法1的Step3)，判斷哪些變量添加至ICliquej.重復(fù)以上過(guò)程，直到currentV為空.

Fig. 4　Exogenous variables discovery for LUCAS.圖4　LUCAS的初始變量發(fā)現(xiàn)示意圖

2.4.2初始團(tuán)樹(shù)的計(jì)算

初始團(tuán)樹(shù)ICliqueev是以初始變量ev為根的分支，其非根節(jié)點(diǎn)都是ev的后繼.初始團(tuán)樹(shù)的計(jì)算見(jiàn)EVD算法的函數(shù)computeIClique().在本文方法中，構(gòu)建初始團(tuán)樹(shù)起到了3個(gè)作用：1)在初始變量發(fā)現(xiàn)過(guò)程中，幫助算法從currentV中排除非初始變量；2)區(qū)分初始變量和孤立變量；3)避免IC等經(jīng)典方法生成v結(jié)構(gòu)和添加方向規(guī)則造成的諸多問(wèn)題，如算法復(fù)雜性高、魯棒性低等，并利用初始團(tuán)樹(shù)獲取因果網(wǎng)絡(luò)的大體分支和層次結(jié)構(gòu).不僅如此，初始團(tuán)樹(shù)有很多性質(zhì)(性質(zhì)1～5)，可以幫助我們更快地發(fā)現(xiàn)因果關(guān)系.

性質(zhì)4. 若vi∈Vi{v1}，v1是IClique1的初始變量，則v1∈Pred(vi).

性質(zhì)5. 在不同初始團(tuán)樹(shù)中的同一條邊有相容的方向,如圖5(d)所示.

這些性質(zhì)可以幫助快速確定邊的方向和節(jié)點(diǎn)所在的分支，減少算法復(fù)雜度并提高準(zhǔn)確性.性質(zhì)1和性質(zhì)2可由初始變量的定義推出.性質(zhì)3是Markov鏈的性質(zhì).性質(zhì)4描述了IClique1是初始變量v1在網(wǎng)絡(luò)結(jié)構(gòu)中的影響力范圍.性質(zhì)5中相容方向是指具有相同單方向的邊.由初始變量和初始團(tuán)樹(shù)的計(jì)算可知，不同于IC等方法在確定v結(jié)構(gòu)后再形成分支，ICIC方法在發(fā)現(xiàn)初始變量及其分支的過(guò)程中，自然形成各個(gè)分支的交匯點(diǎn).3條規(guī)則可以從以上性質(zhì)推導(dǎo)出來(lái)，能幫助添加方向和優(yōu)化程序，如圖6所示.

Fig. 5　Directions properties within IClique or between ICliques.圖5　初始團(tuán)樹(shù)和初始團(tuán)樹(shù)間方向的性質(zhì)

Fig. 6　Rules for directing edges quickly.圖6　添加方向的優(yōu)化規(guī)則

規(guī)則1. 若vi→vj，vi—vjj，hvj?hvjj，其中vj，vjj∈V2{v2}，V2是IClique2的節(jié)點(diǎn)集，則vi→vjj,如圖6(a)所示.

規(guī)則2. 若vi i→vjj，vi—vjj，hvi?hvi i，其中vi，vi i∈V1{v1}，V1是IClique1的節(jié)點(diǎn)集，則vi→vjj,如圖6(b)所示.

規(guī)則3. 若vi→vj，vi i—vjj，hvi i≥hvi，hvj≥hvjj，其中vi，vi i∈V1{v1}，vj，vjj∈V2{v2}，V1和V2是IClique1和IClique2的節(jié)點(diǎn)集，則vi i→vjj,如圖6(c)所示.

2.5目標(biāo)節(jié)點(diǎn)的因果網(wǎng)絡(luò)發(fā)現(xiàn)算法ICIC_Target

本文針對(duì)目標(biāo)變量(target variable)的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)提出了ICIC_Target算法，參見(jiàn)算法2.目標(biāo)節(jié)點(diǎn)的因果關(guān)系網(wǎng)絡(luò)發(fā)現(xiàn)問(wèn)題CP(Vo,vt,D)中Vo一般十分龐大，極大地增加了計(jì)算復(fù)雜性，算法2的Step2對(duì)數(shù)據(jù)進(jìn)行相關(guān)性分析，以適當(dāng)?shù)亟稻S，盡早將無(wú)關(guān)變量限定在計(jì)算范圍之外.其中ICIC_Structure函數(shù)可以用于全局因果關(guān)系發(fā)現(xiàn)算法，使用的不等式有：

(6)

(7)

P(b|a,Patternb)-P(b|

(8)

Fig. 7　Two shapes of triangle structure (a,b,c) T.a, T.b with one redundant edge a→b noted as dash arrow.圖7　帶圈三角形的集合T.a和非圈三角形集合T.b示意圖

算法2. ICIC_Target.

輸入:變量集V、目標(biāo)變量vt、數(shù)據(jù)集D;

輸出:G.

Step1. 初始化G←?,Vt←{vt};

Step2. for ?vi∈V{vt}

if((pvi|vt-pvi|vt)>β)Vt←Vt∪{vi};

endif

endfor

Step3. for ?vj∈Vt{vt}

for ?vk∈VVt

if ((pvk|(vj,vt)-pvk|vj)>β)

Vt←Vt∪{vk};

endif

endfor

endfor

Step4.G←ICIC_Structure(Vt,D);

Step5. returnG;

FunctionICIC_Structure(V,D)

Step1. 初始化G←complete graph;

if(?edgevi—va,vi是ICliquei的初始變量)

directvi→va根據(jù)Property 1,

endif

endfor

endfor

directva→vb根據(jù)式(6),(7);

endfor

if (所有va—vb添加方向?yàn)関a→vb)

endif

endfor

Step5. forva—vb∈IClique

directva→vb根據(jù)式(6),(7);

endfor

Step6. for ?va—vb不在一個(gè)IClique中

directva→vb根據(jù)式(7),Rule 1,2;

endfor

Step7. {T.a,T.b}←FindTriangle(G);

Step8. while (T.a≠?)

for ?d=(va→vb)∈t∈T.a

if(?t1∈T.b, s.t.d∈t1)

continue;

endif

if (式(8)成立)

從G中刪除d,更新T.a,T.b,

break;

endif

endfor

while (T.b≠?)

for ?d=(va→vb)∈t∈T.b

if (t1(T.b, s.t.d(t1)

continue;

endif

if (式(8)成立)

從G中刪除d, 更新T.b,

break;

endif

endfor

Step9. returnG.

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

本文從理論和實(shí)驗(yàn)2方面對(duì)ICIC方法進(jìn)行了分析和驗(yàn)證.我們通過(guò)實(shí)驗(yàn)途徑說(shuō)明了ICIC_Target方法在不同實(shí)驗(yàn)數(shù)據(jù)上具有更好的性能和魯棒性，并通過(guò)理論途徑分析了ICIC_Target方法的穩(wěn)定性和低復(fù)雜性.

3.1實(shí)驗(yàn)與分析

3.1.1實(shí)驗(yàn)設(shè)計(jì)

本文利用由WCCI 2008的“Causation and Predic-tion”競(jìng)賽[24]和NIPS 2008 Causality Workshop[6,12]正式發(fā)布的各領(lǐng)域的大小類(lèi)型不同、或噪音、或操控的數(shù)據(jù)集(如表1所示，列出了數(shù)據(jù)集的性質(zhì))，與多種有代表性的方法進(jìn)行對(duì)比實(shí)驗(yàn).根據(jù)數(shù)據(jù)集和算法的特點(diǎn)，我們選擇可比較的部分組成相應(yīng)的實(shí)驗(yàn)組.所有參與對(duì)比實(shí)驗(yàn)的算法已在本文第1節(jié)做了介紹.對(duì)比實(shí)驗(yàn)涉及10個(gè)分實(shí)驗(yàn)，如表2所示，說(shuō)明了實(shí)驗(yàn)設(shè)計(jì)的情況.

Table 1　Properties of Datasets Used in Experiments

Table 2　Experiments Designed for Causality Discovery Research

REGED[7]數(shù)據(jù)集來(lái)自醫(yī)學(xué)領(lǐng)域，目的是通過(guò)發(fā)現(xiàn)觸發(fā)肺癌疾病的基因和肺癌造成改變的基因，預(yù)測(cè)肺癌的發(fā)病狀況.REGED包含的基因表達(dá)量(gene expression data)數(shù)據(jù)由真實(shí)的DNA微陣列數(shù)據(jù)(DNA microarray data)訓(xùn)練出的模擬器生成.該數(shù)據(jù)集的3個(gè)子任務(wù)REGED0，REGED1，REGED2均有相同的1個(gè)目標(biāo)變量和999個(gè)其他變量，其中REGED1和REGED2的測(cè)試數(shù)據(jù)中某些變量受到操控，以模擬藥物或RNA抑制(RNA silencing)治療的情況.MARTI[7,10]是REGED加入噪音的版本，有1024個(gè)變量，其中25個(gè)是校正變量，用于幫助剔除噪音影響.MARTI的因果網(wǎng)絡(luò)結(jié)構(gòu)與REGED相同.二者的設(shè)計(jì)初衷是檢測(cè)目標(biāo)變量(binary類(lèi)型)預(yù)測(cè)算法的性能，本文的實(shí)驗(yàn)?zāi)康氖菣z測(cè)因果關(guān)系結(jié)構(gòu)發(fā)現(xiàn)算法的性能，因此在WCCI 和NIPS公布了REGED和MARTI所在系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)后，我們將它們的一個(gè)訓(xùn)練集和3個(gè)測(cè)試集都用來(lái)評(píng)估因果結(jié)構(gòu)發(fā)現(xiàn)算法在有操控或有噪音的數(shù)據(jù)集上的性能.由于測(cè)試集的目標(biāo)變量結(jié)果至今未公開(kāi)，本文利用SimplePredict算法(見(jiàn)算法3)和已公布的網(wǎng)絡(luò)結(jié)構(gòu)將目標(biāo)變量的值(即表2中l(wèi)ist_vt)補(bǔ)充完整.

算法3. SimplePredict.

輸入:目標(biāo)變量vt、局部網(wǎng)絡(luò)NL、測(cè)試數(shù)據(jù)集DT;

輸出:目標(biāo)結(jié)果值列表list_vt.

Step1. for ?samplei∈DT

if(?v∈Parents(vt) s.t.v=1 insamplei)

list_vt.add(1);

endif

list_vt.add(1);

endif

else

list_vt.add(-1);

endfor

Step2. returnlist_vt;

WebLog來(lái)自Grozea和Romania[25]設(shè)計(jì)的網(wǎng)頁(yè)瀏覽實(shí)驗(yàn)的真實(shí)數(shù)據(jù).在該實(shí)驗(yàn)中，有20個(gè)網(wǎng)頁(yè)供人們?yōu)g覽，每個(gè)網(wǎng)頁(yè)有到另19個(gè)網(wǎng)頁(yè)的鏈接.實(shí)驗(yàn)收集了512 d的瀏覽日志，將每一天每一個(gè)網(wǎng)頁(yè)的瀏覽數(shù)統(tǒng)計(jì)出來(lái)作為WebLog數(shù)據(jù)集.實(shí)驗(yàn)作者發(fā)現(xiàn)某些網(wǎng)頁(yè)可以激發(fā)人們?nèi)g覽某些其他網(wǎng)頁(yè)，人們的這些行為被記錄和統(tǒng)計(jì)下來(lái)，作為實(shí)驗(yàn)的真實(shí)因果網(wǎng)絡(luò)結(jié)構(gòu).該結(jié)構(gòu)存在雙向邊，這是因?yàn)橐粋€(gè)網(wǎng)頁(yè)pagea能激發(fā)人們?yōu)g覽pageb, 同時(shí)pageb也能激發(fā)人們?yōu)g覽pagea.Weblog的設(shè)計(jì)初衷是發(fā)現(xiàn)因果關(guān)系網(wǎng)絡(luò)，因此該數(shù)據(jù)集無(wú)測(cè)試數(shù)據(jù)，SIGNET數(shù)據(jù)集亦是同樣的情況，表1用空格表示.

SIGNET是模擬數(shù)據(jù)集，它的真實(shí)網(wǎng)絡(luò)是一個(gè)生物信號(hào)網(wǎng)絡(luò)的布爾模型.Jenkins和Soni[26]對(duì)43個(gè)生物信號(hào)變量進(jìn)行了案例和序列2種方式的采樣，變量中有38個(gè)可變變量、5個(gè)常數(shù)變量.該數(shù)據(jù)集總共300個(gè)序列采樣組,每組包含21個(gè)序列采樣，其中第1個(gè)采樣由43個(gè)變量的初始值組成，其他20個(gè)采樣是后續(xù)時(shí)間點(diǎn)上變量的變化情況.SIGNET對(duì)單純的案例數(shù)據(jù)因果發(fā)現(xiàn)方法(如IC)和序列數(shù)據(jù)因果發(fā)現(xiàn)方法(如SI)都是較大的挑戰(zhàn).

我們參考NIPS 2008提出的代價(jià)矩陣得分(score of cost matrix)[12]作為實(shí)驗(yàn)結(jié)果的評(píng)估標(biāo)準(zhǔn)之一，其中代價(jià)矩陣的元素是局部網(wǎng)絡(luò)結(jié)構(gòu)中不同位置上出現(xiàn)錯(cuò)誤變量的代價(jià)權(quán)重，具體取值如圖8所示.變量在網(wǎng)絡(luò)中的位置離正確位置越遠(yuǎn)，錯(cuò)誤的代價(jià)越高；出錯(cuò)越多，代價(jià)累計(jì)值越高.因此該值越小，結(jié)果網(wǎng)絡(luò)結(jié)構(gòu)越相近正確.由于HITON，PCMB，IAMB方法輸出的是PCset或MBset而非網(wǎng)絡(luò)結(jié)構(gòu)，無(wú)法直接計(jì)算PC和MB的代價(jià)矩陣得分，因此我們將PCset或MBset中包含的正確的父節(jié)點(diǎn)、子節(jié)點(diǎn)和配偶節(jié)點(diǎn)對(duì)應(yīng)放置在目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)和配偶節(jié)點(diǎn)位置上，集合中其余錯(cuò)誤的節(jié)點(diǎn)均放在子節(jié)點(diǎn)位置，這樣獲得的網(wǎng)絡(luò)結(jié)構(gòu)是最接近正確答案的結(jié)構(gòu)，由此計(jì)算的代價(jià)矩陣得分是HITON等方法的最小代價(jià)值，實(shí)際的代價(jià)值不會(huì)小于這個(gè)值，因此表3和表4中用“≥”表示HITON等方法的實(shí)驗(yàn)結(jié)果.

DepthDesired112×ObtainedRelationshipParentsChildrenSpousesOther1Parents01121Children10122Spouses1102×Other2220

Fig. 8The cost matrix of MB and PC.
圖8MB和PC代價(jià)矩陣

在本文的實(shí)驗(yàn)結(jié)果評(píng)測(cè)中，對(duì)于IC

*

和FCI結(jié)果中存在帶有標(biāo)記的邊，以及IC和ICIC_Target方法結(jié)果中不確定方向邊(表示為無(wú)向邊)或雙向邊，這些在NIPS 2008競(jìng)賽中未做明確規(guī)定的情況.在生成網(wǎng)絡(luò)結(jié)構(gòu)的鄰接矩陣時(shí)，我們按3個(gè)原則處理：1)2個(gè)端點(diǎn)方向均明確者(如單向邊和雙向邊),按原有方向處理.2)一端方向不明確者(如FCI方法標(biāo)記為“o”的邊(

a

o→

b

)則表明

a

端點(diǎn)方向尚不明確；IC

*

方法的有向邊

a

→

b

意味著

a

到

b

方向已確定或

a

，

b

存在同一個(gè)隱含原因，因此

a

→

b

仍是

a

端方向不明確)，該端按不存在該方向處理.3)2個(gè)端點(diǎn)方向均不明確者(如無(wú)向邊),按2個(gè)端點(diǎn)均有方向處理.為適應(yīng)實(shí)驗(yàn)結(jié)果存在雙向、圈等網(wǎng)絡(luò)結(jié)構(gòu)的問(wèn)題，關(guān)于代價(jià)矩陣得分的計(jì)算，我們采用4個(gè)原則處理：1)對(duì)NIPS2008提出的規(guī)定范圍內(nèi)的錯(cuò)誤代價(jià)按原有代價(jià)矩陣中的值處理，如圖8所示；2)對(duì)既在正確位置出現(xiàn)又在PC或MB中錯(cuò)誤位置出現(xiàn)的變量，給予相應(yīng)減半的懲罰；3)對(duì)未在正確位置出現(xiàn)、但多次在MB的其他位置出現(xiàn)的變量，給予累加懲罰；4)Weblog和SIGNET上的實(shí)驗(yàn)結(jié)果是以任意變量為目標(biāo)計(jì)算的代價(jià)矩陣平均得分.

Table 3　Results of Score of Cost Matrix in REGED

Table 4　Results of Score of Cost Matrix in MARTI

3.1.2目標(biāo)變量的網(wǎng)絡(luò)發(fā)現(xiàn)實(shí)驗(yàn)結(jié)果及分析

本節(jié)將進(jìn)一步說(shuō)明在多數(shù)據(jù)集和多任務(wù)下的因果網(wǎng)絡(luò)發(fā)現(xiàn)的實(shí)驗(yàn)細(xì)節(jié)和實(shí)驗(yàn)結(jié)果，得出分析結(jié)論.

本實(shí)驗(yàn)使用文獻(xiàn)[27]提出的突發(fā)檢測(cè)算法BSE，將連續(xù)數(shù)據(jù)轉(zhuǎn)化為離散數(shù)據(jù)后再進(jìn)行各算法結(jié)果的比較和評(píng)估.ICIC_Target方法多處涉及用χ2假設(shè)檢驗(yàn)(或參數(shù)β)以判定顯著差異、邊的方向以及隱含因變量的存在.假設(shè)檢驗(yàn)的置信水平越高或β值越大則意味著ICIC方法發(fā)現(xiàn)的因果關(guān)系越強(qiáng).本文中設(shè)置α=0.05，β=0.1.參數(shù)ε0是足夠小的正值，本文取值ε0=0.000 5.

我們對(duì)ICIC_Target與HITON，IC等方法在目標(biāo)節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)上的性能進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表3～7所示.表中空白處對(duì)應(yīng)任務(wù)上無(wú)實(shí)驗(yàn)結(jié)果的情況有2種可能的原因：1)方法未獲得任何PC節(jié)點(diǎn)或MB節(jié)點(diǎn)(如表3和表4所示的PCMB方法在REGED和MARTI的測(cè)試集上得不出結(jié)果)；2)方法不適用于該項(xiàng)任務(wù)(如表5和表6所示的LCD2方法，因?yàn)閃eblog的網(wǎng)絡(luò)結(jié)構(gòu)中沒(méi)有真正的初始變量，即Cooper[4]所指的instrumental variable，因此LCD2方法在實(shí)驗(yàn)ET.S.Weblog中無(wú)法獲得有效結(jié)果).表3～6中粗體數(shù)字為同一評(píng)測(cè)標(biāo)準(zhǔn)下的最好成績(jī).以實(shí)驗(yàn)ET.C.REGED.Train(如表3所示)為例，ICIC_Target方法在父子網(wǎng)絡(luò)結(jié)構(gòu)(PC結(jié)構(gòu))和父子配偶網(wǎng)絡(luò)結(jié)構(gòu)(MB結(jié)構(gòu))發(fā)現(xiàn)2項(xiàng)任務(wù)中的代價(jià)矩陣得分(9.0和21.5)分別小于HITON_PC方法的得分(大于等于18.0)和HITON_MB方法的得分(大于等于40.0)，因此本文方法在該實(shí)驗(yàn)中存在性能優(yōu)勢(shì).在實(shí)驗(yàn)ET.S.Weblog和ET.M.SIGNET中，我們以每個(gè)變量為目標(biāo)變量計(jì)算得到|V|個(gè)局部網(wǎng)絡(luò)結(jié)構(gòu)，并以代價(jià)矩陣得分的均值作為性能評(píng)估標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果如表5和表6所示.表7展示了本文方法在實(shí)驗(yàn)ET.M.SIGNET中發(fā)現(xiàn)的激勵(lì)因果和抑制因果的情況，并與IC方法進(jìn)行了比較.其中“×”表示算法發(fā)現(xiàn)的錯(cuò)誤的因果關(guān)系，“√”表示正確的因果關(guān)系.表格上半部是存在抑制因果的等式，表格下半部是只有激勵(lì)因果的等式，各等式等號(hào)右邊變量為因變量，等號(hào)左邊為果變量.

Table 5Results of Mean PC Score of Cost Matrix in Weblog and SIGNET Experiments

表5　Weblog和SIGNET的PC實(shí)驗(yàn)結(jié)果

Table 6Results of Mean MB Score of Cost Matrix in Weblog and SIGNET Experiments

表6　Weblog和SIGNET的MB實(shí)驗(yàn)結(jié)果

Table 7　Comparison of Stimulating and Inhibiting Causalities Discovered by ICIC_Target and IC in ET.M.SIGNET

表7　ICIC_Target與IC的ET.M.SIGNET實(shí)驗(yàn)結(jié)果(激勵(lì)抑制因果)對(duì)比

Table 7　Comparison of Stimulating and Inhibiting Causalities Discovered by ICIC_Target and IC in ET.M.SIGNET

TrueEquations(Boolean)ICIC_TargetICStimulatingInhibitingStimulatingInhibitingCAIM=ROSandnotDEPOLAR×CAIM=…andnotCLOSURE√CAIM=…andnotDEPOLARATRBOH=OSTandROP2andnotABI×CLOSUREHATPase=notPH√HATPase=…andnotPH×HATPase=…andnotCLOSUREActin=notRAC×Actin=…orCLOSURE√Actin=…ornotRACABI=notPAandnotROSKAP=notPH√KAP=…andnotPH×KAP=…andnotCLOSURECa=(CAIMorCIS)andnotCaATPaseAnionEM=notABIorCa×ATRBOHDEPOLAR=KEVorAnionEMornotHATPaseornotKOUTorCa×DEPOLAR=…orPH×DEPOLAR=…orCLOSURE×DEPOLAR=…orROS√DEPOLAR=…ornotHATPaseNO=NIA12andNOS×CaATPase×KEV,√N(yùn)OSCLOSURE=(KOUTorKAP)andAnionEMandActin√CLOSURE=…orKOUT√CLOSURE=…orActin√CLOSURE=…andKAPcADPR=ADPRc√ADPRcIP6=InsPK√IP6=…orInsPK×IP6=…orCLOSURENIA12=RCN√N(yùn)IA12=…orRCN×NIA12=…orCLOSUREROP2=PA×ATRBOHS1P=SPHK√S1P=…orSPHK

Note: Symbol “×” means wrong equation has been discovered by ICIC_Target or IC method, and “√” means right equation has been discovered.

本文10組對(duì)比實(shí)驗(yàn)的結(jié)果(如表3～7所示)展示了ICIC_Target方法良好的性能，該方法的準(zhǔn)確性在大多數(shù)據(jù)集上領(lǐng)先.在實(shí)驗(yàn)過(guò)程中，該方法表現(xiàn)出了很好的魯棒性和穩(wěn)定性，能較好地處理不同類(lèi)型和特性的數(shù)據(jù)，程序運(yùn)行速度快，尤其表現(xiàn)在處理REGED和MARTI測(cè)試數(shù)據(jù)(涉及上千個(gè)變量和上萬(wàn)條采樣記錄)這樣的大規(guī)模因果系統(tǒng)上，ICIC_Target方法平均耗時(shí)明顯低于HITON方法，達(dá)到了150(相同的運(yùn)算環(huán)境下，ICIC_Target方法耗時(shí)2～5 min，由Causal Explorer實(shí)現(xiàn)的HITON方法平均耗時(shí)達(dá)到2 h).另外，本文方法能更好地發(fā)現(xiàn)和區(qū)分激勵(lì)因果和抑制因果，如表7所示，可以進(jìn)一步為后續(xù)分析或應(yīng)用提供更多有用的信息.

3.2算法的穩(wěn)定性、復(fù)雜性分析

3.2.1穩(wěn)定性分析

本文將分析算法2在輸入有誤差或錯(cuò)誤時(shí)能否保持合理的可靠性.文獻(xiàn)[2]提出了算法穩(wěn)定性概念：若輸入小錯(cuò)誤產(chǎn)生了輸出的大錯(cuò)誤，則算法不穩(wěn)定.

算法2首先通過(guò)判定V中與目標(biāo)變量“相關(guān)”的變量子集對(duì)所有變量進(jìn)行過(guò)濾.若該步驟將某個(gè)PC或MB變量排除在相關(guān)子集外，則該變量及其父子變量很難會(huì)對(duì)其他PC 或MB變量的判定產(chǎn)生影響，因此此類(lèi)誤差不會(huì)破壞算法的穩(wěn)定性.然而，該步驟通常會(huì)將判定條件設(shè)定的非常寬松，這就在相關(guān)子集中引入了大量非PC或MB變量.對(duì)這類(lèi)誤差，后續(xù)步驟的目標(biāo)就是逐步細(xì)化相關(guān)子集、縮小誤差影響的過(guò)程，因此ICIC_Target算法的整體穩(wěn)定性主要依賴(lài)ICIC_Structure方法.

ICIC_Target算法的核心ICIC_Structure函數(shù)的Step3(相當(dāng)于IC算法[1]第1步或PC算法[2]的step A的功能)若存在小錯(cuò)誤，則很可能是某些d-割關(guān)系被錯(cuò)誤地包含或排除在下一步的輸入中.本文2.3節(jié)已說(shuō)明，該步可能產(chǎn)生冗余邊，即確定2個(gè)節(jié)點(diǎn)間的d-割關(guān)系比確定二者d-connection更苛刻，因此ICIC_Structure在Step8回溯并刪除冗余邊.可見(jiàn)ICIC_Target算法能控制產(chǎn)生冗余邊的問(wèn)題，在最終輸出時(shí)盡量減少錯(cuò)誤.另一個(gè)可能的錯(cuò)誤是ICIC_Structure的Step2輸出時(shí)錯(cuò)誤地包含或遺漏某些初始變量.被遺漏的初始變量會(huì)在后續(xù)程序中被逐漸找回，而包含偽初始變量的錯(cuò)誤會(huì)在后續(xù)程序中被放大，因?yàn)殄e(cuò)誤的初始變量將影響一部分邊的方向判定.為限制該類(lèi)錯(cuò)誤，EVD算法設(shè)計(jì)的盡可能?chē)?yán)格地判定初始變量.其他步驟產(chǎn)生小錯(cuò)誤或受小錯(cuò)誤影響的情況有限，因此ICIC_Target方法具有較好的穩(wěn)定性.

3.2.2復(fù)雜性分析

實(shí)際上，這些判定的平均數(shù)量還會(huì)遠(yuǎn)遠(yuǎn)小于該上限值，因?yàn)镮CIC只需判定2個(gè)節(jié)點(diǎn)是否被d-割，無(wú)需知道誰(shuí)d-割了它們(不同于PC需要知道d-割集Sepset(vi,vj)，就要遍歷完所有的變量和變量組合)，因此最壞情況出現(xiàn)的概率遠(yuǎn)遠(yuǎn)小于PC等算法.另外，我們還可以通過(guò)優(yōu)先遍歷高度數(shù)節(jié)點(diǎn)優(yōu)化算法.

ICIC_Target方法增加了初始變量的判定和IClique的計(jì)算，我們認(rèn)為這些是在保證準(zhǔn)確性、增強(qiáng)魯棒性的前提下可以接受的代價(jià).因?yàn)镋VD極少得到比真實(shí)nev多的初始變量，因此最壞情況下以上2個(gè)步驟運(yùn)算的次數(shù)是：nev和(n-nev)nev，且每個(gè)初始變量的判定都需要遍歷數(shù)據(jù)集.因此EVD算法的復(fù)雜度為O((m+n)nev).在添加方向和刪除冗余邊的2個(gè)步驟中，考慮以下2種極端情況：1)若ICIC在條件獨(dú)立判定步驟之后得到的無(wú)向圖仍是完全無(wú)向圖，則刪邊的復(fù)雜度可以忽略；2)若添加方向步驟后得到的有向圖有最多的三角形結(jié)構(gòu)、最少的初始變量、最少的公共邊(同時(shí)處于至少2個(gè)三角形結(jié)構(gòu)中的邊)，則刪邊步驟就遇到了最壞情況，此步的復(fù)雜度為O(n)，與此同時(shí)添加方向步驟的復(fù)雜度為O(n).這2個(gè)步驟的最壞情況不會(huì)同時(shí)出現(xiàn)，因此復(fù)雜度上限為O(n2)，更精確些為O(nk).此外，ICIC_Target判定相關(guān)子集的步驟還可以大大降低后續(xù)算法的復(fù)雜度.綜上所述，算法的復(fù)雜度為O(n4+mnev).

4結(jié)束語(yǔ)

本文針對(duì)真實(shí)環(huán)境下局部因果關(guān)系發(fā)現(xiàn)問(wèn)題，通過(guò)分析因果關(guān)系的作用機(jī)制，利用初始變量和初始團(tuán)樹(shù)，提出了性能更高、魯棒性更強(qiáng)的局部因果關(guān)系網(wǎng)絡(luò)發(fā)現(xiàn)方法ICIC_Target.實(shí)驗(yàn)和理論分析表明，該方法具有更好的穩(wěn)定性、復(fù)雜度、魯棒性.該方法克服了傳統(tǒng)方法由于受限于邊的不確定性、雙向邊、圈、v結(jié)構(gòu)等不足，降低了復(fù)雜性，且無(wú)需基于過(guò)多的前提和先驗(yàn)知識(shí)，因此更加適用于真實(shí)環(huán)境下的因果關(guān)系發(fā)現(xiàn).

下一步將改進(jìn)或優(yōu)化初始變量的發(fā)現(xiàn)算法以提高算法的準(zhǔn)確率、降低復(fù)雜度，進(jìn)一步開(kāi)展因果關(guān)系發(fā)現(xiàn)后的因果關(guān)系分析，包括因果的演化模型、隱含變量發(fā)現(xiàn)與分析，以及因變量合作競(jìng)爭(zhēng)機(jī)制、遺傳機(jī)制等方面的研究.

參考文獻(xiàn)

[1]Pearl J. Causality: Models, Reasoning, and Inference [M]. Cambridge, UK: Cambridge University Press, 1999

[2]Spirtes P, Glymour C, Scheines R. Causation, Prediction, and Search[M]. 2nd ed. Cambridge, MA: MIT Press, 2000

[3]Cooper G F, Herskovits E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning, 1992, 9(4): 309-347

[4]Mani S, Cooper G F. A study in causal discovery from population -based infant birth and death records[C]Proc of the American Medical Informatics Association (AMIA) Annual Fall Symp. Philadelphia, PA: AMIA, 1999: 315-319

[5]Granger C W J. Investigating causal relations by econometric models and cross-spectral methods[J]. Econometrica, 1969, 37(3): 424-438

[6]Guyon I. NIPS 2008 Workshop on Causality: Workshop Information Publishing[EBOL]. (2008-12-12)[2013-07-11]. http:www.clopinet.comisabelleProjectsNIPS2008

[7]The Causality Workbench Team of NIPS 2008. Challenges in machine learning—Causality challenge #1: Causation and prediction [EBOL]. (2008-12-12)[2013-07-11]. http:www.causality.inf.ethz.chchallenge.php?page=datasets

[8]The Causality Workbench Team of NIPS 2008. LUCAS and LUCAP are lung cancer toy datasets: Dataset Description[EBOL]. (2008-06-06)[2013-07-10]. http:www.causality.inf.ethz.chdataLUCAS.html

[9]Glymour C, Cooper G F. Computation, Causation, and Discovery [M]. Menlo Park, CA: AAAI Press, 1999

[10]Aliferis C F, Tsamardinos I, Statnikov A. HITON, a novel Markov blanket algorithm for optimal variable selection[C]Proc of the American Medical Informatics Association (AMIA) Annual Symp. Washington, DC: AMIA, 2003: 21-25

[11] Tsamardinos I, Brown L E, Aliferis C F. The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65(1): 31-78

[12] Guyon I, Aliferis C F, Cooper G F, et al. Design and analysis of the causation and prediction challenge[J]. Journal of Machine Learning Research: Workshop and Conf Proc, 2008, 3: 1-33

[13] Aliferis C F, Statnikov A, Tsamardinos I, et al. Local causal and Markov blanket induction for causal discovery and feature selection for classification part i: Algorithms and empirical evaluation[J]. Journal of Machine Learning Research, 2010, 11: 171-234

[15] Aliferis C F, Tsamardinos I, Statnikov A R. Causal explorer: A probabilistic network learning toolkit for biomedical discovery[C]Proc of Int Conf Mathematics and Engineering Techniques in Medicine and Biological Sciences (METMBS). Las Vegas: CSREA Press, 2003: 371-376

[16] Aliferis C F. Causal Explorer Download: Register Page[CPOL]. (2003-06-26)[ 2013-08-01]. http:www.dsl-lab.orgcausal_explorer

[18]Shibuya T, Harada T, Kuniyoshi Y. Causality quantification and its applications: Structuring and modeling of multivariate time series[C]Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 787-796

[19] Lozano A C, Abe N, Liu Yan. Grouped graphical Granger modeling methods for temporal causal modeling[C]Proc of the 15th ACM SIGKDD Int Conf Knowledge Discovery and Data Mining. New York: ACM, 2009: 577-586

[20] Ancona N, Marinazzo D, Stramaglia S. Radial basis function approach to nonlinear Granger causality of time series [J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2004, 70(5): 148-168

[21] Shimizu S, Hoyer P O, Hyv?rinen A, et al. A linear non-Gaussian acyclic model for causal discovery [J]. Journal of Machine Learning Research, 2006, 7: 2003-2030

[22] Arnhold J, Grassberger P, Lehnertz K, et al. A robust method for detecting interdependences: Application to intracranially recorded EEG [J]. Physica D, 1999, 134(4): 419-430

[23] Lungarella M, Ishiguro K, Kuniyoshi Y. Methods for quantifying the causal structure of bivariate time series [J]. International Journal of Bifurcation and Chaos (IJBC), 2007, 17(3): 903-921

[24]The Causality Workbench Team of NIPS 2008. Home page of challenges in machine learning—Causality challenge #1: Causation and prediction [EBOL]. (2008-12-12) [2013-07-11]. http:www.causality.inf.ethz.chchallenge.php?page

[25] The Causality Workbench Team of NIPS 2008. The causal discovery in Web logs: Problem and datasdet[EBOL]. (2008-06-06) [2013-07-10]. http:www.phobos.rodataindex.html

[26]The Causality Workbench Team of NIPS 2008. SIGNET abscisic acid signaling network: Desciption of problem and dataset[EBOL]. (2008-06-06) [2013-09-23]. http:www.causality.inf.ethz.chrepository.php?id=5

[27]Sun Jing, Yin Jianping, Wang Ting, et al. A novel model of bursts in event sequences[C]Proc of the Int Conf on Consumer Electronics, Communications and Networks (CECNet). Piscataway, NJ: IEEE, 2012: 816-821

Li Yan, born in 1979. PhD. Her main research interests include text mining and natural language processing.

Wang Ting, born in 1967. Professor and PhD supervisor. His main research interests include artificial intelligence and computer software.

Liu Wanwei, born in 1980. PhD and associate professor. His main research interests include formal method and verification.

Zhang Xiaoyan, born in 1981. PhD and experimentalist. Her main research interests include text mining and natural language processing.

收稿日期：2014-11-14；修回日期：2015-09-06

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61170287,60873097)

中圖法分類(lèi)號(hào)TP391

ICIC_Target: A Novel Discovery Algorithm for Local Causality Network of Target Variable

Li Yan1, Wang Ting1, Liu Wanwei1, and Zhang Xiaoyan2

1(CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha410073)2(CollegeofHumanitiesandSocialSciences,NationalUniversityofDefenseTechnology,Changsha410073)

AbstractCausality research aims to reveal the law of evolution of nature, society and human. Nowadays, the causality research receives widespread attention for its important applications of human life and science research, but there are still many difficulties and challenges. This paper presents a unified model to explain the stimulating and inhibiting causalities. Based on this model, we also present a framework ICIC and a novel algorithm ICIC_Target to infer the local causal structure of a target variable from observational data without any limitation of some assumptions, such as assumption of acyclic structure, hidden variables and so on. Following our descriptions of causality essence and properties, as well as several classical theories proposed by Judea Pearl, Gregory F. Cooper and so on, we introduce concepts of exogenous variable and clique-like structure (IClique) to get rough ordering of variables, which are necessary for revealing the causality accurately and efficiently. To evaluate our approach, several experiments compared with HITON, IC, PC, PCMB and several methods based on four datasets with different data types have been done. The results demonstrate the higher performance and stronger robustness of our algorithm ICIC_Target. In this paper, we also discuss the advantages of stability and complexity of ICIC_Target.

Key wordscausality; causal network; local causal network discovery; stimulating causality; inhibiting causality

This work was supported by the National Natural Science Foundation of China (61170287,60873097).