基于條件獨(dú)立性的LiNGAM模型剪枝算法

郝志峰　呂宏偉　蔡瑞初　袁　暢

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　廣東 廣州 510006)

?

基于條件獨(dú)立性的LiNGAM模型剪枝算法

郝志峰呂宏偉蔡瑞初袁暢

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東 廣州 510006)

如何根據(jù)觀察數(shù)據(jù)來推斷因果網(wǎng)絡(luò)結(jié)構(gòu)是統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)領(lǐng)域的重要問題。近年來學(xué)者們?nèi)〉昧嗽S多研究成果，LiNGAM算法是其中一種經(jīng)典的線性因果推斷算法。但LiNGAM算法采用的剪枝策略時(shí)間復(fù)雜度較高，且在稀疏圖上準(zhǔn)確率低。為此，提出一種基于條件獨(dú)立性測(cè)試的剪枝算法來解決這個(gè)問題。該算法首先將變量根據(jù)因果順序重新排列，再按照該次序采用偏相關(guān)系數(shù)檢驗(yàn)變量之間的條件獨(dú)立性。大量的實(shí)驗(yàn)結(jié)果表明，基于條件獨(dú)立性的剪枝算法在稀疏圖上比LiNGAM的剪枝算法獲得更高的準(zhǔn)確率與執(zhí)行效率。

線性因果關(guān)系偏相關(guān)條件獨(dú)立性剪枝

0　引　言

繼貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)之后，因果網(wǎng)絡(luò)結(jié)構(gòu)推斷受到廣泛的關(guān)注。在因果推斷中，因果關(guān)系的可識(shí)別性是因果推斷的基本前提。近些年的研究表明非高斯噪音與非線性關(guān)系對(duì)于因果關(guān)系識(shí)別有著重要作用[1,2]。Shimizu等人發(fā)現(xiàn)當(dāng)變量之間為線性連續(xù)的關(guān)系并且噪音均服從非高斯分布時(shí)，變量之間的因果關(guān)系是可識(shí)別的，并提出線性連續(xù)非高斯的因果推斷模型LiNGAM模型[1]。后續(xù)Hoyer等人[2]將LiNGAM模型擴(kuò)展為加噪因果模型，并指出若變量之間均是非線性關(guān)系或者變量中存在的噪音項(xiàng)均為非高斯分布，那么變量之間的因果關(guān)系是可識(shí)別的。

與LiNGAM算法和DirectLiNGAM算法所采用的剪枝方法不同，本文提出基于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的推斷算法采用的條件獨(dú)立性原理；將變量按照LiNGAM算法所得出的因果順序重新排列，采用偏相關(guān)系數(shù)檢驗(yàn)依次測(cè)試變量之間的條件獨(dú)立性的剪枝算法。若將SGS算法[6]或PC算法[7]等貝葉斯結(jié)構(gòu)推斷算法直接用作剪枝算法時(shí)存在著誤剪枝率高的問題。與基于條件獨(dú)立性原理的SGS算法[6]和PC算法[7]等貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)推斷的經(jīng)典方法不同，本文算法同時(shí)結(jié)合了因果順序與條件獨(dú)立性原理。大量的實(shí)驗(yàn)結(jié)果表明，本文算法準(zhǔn)確率高，且更為穩(wěn)定。

1　相關(guān)背景

1.1LiNGAM模型

LiNGAM是線性連續(xù)、非高斯、有向無環(huán)的因果模型。LiNGAM模型中的變量是按照因果順序依次生成的。因此將變量按照因果順序進(jìn)行排列后，位于后面的變量不可能是前面變量的因變量。在實(shí)際應(yīng)用中，觀察到的變量的排列是隨機(jī)的，與因果順序是不同的。本文根據(jù)觀察中樣本的排列次序(本文記為觀察順序)將變量依次記為{x1,x2,…,xn}，將因果順序記為k(i),i∈[1,n]。(i)∈[1,n]代表了觀察順序中第i個(gè)變量在因果順序中的位置，那么變量的生成過程可描述為：

(1)

式中，ei為服從非高斯分布的噪音項(xiàng)，噪音項(xiàng)之間兩兩互相獨(dú)立；bij不為0表示存在xj指向xi的邊。LiNGAM模型用矩陣的形式表述為：

x=Bx+e

(2)

若采用置換矩陣P∈Rn×n來描述因果順序k(·)，求得B′=PBP，那么根據(jù)因果順序的意義可知，B′為嚴(yán)格的下三角矩陣且對(duì)角線的元素均為0。

1.2LiNGAM算法簡(jiǎn)述

LiNGAM算法是LiNGAM模型中結(jié)構(gòu)推斷的經(jīng)典算法?？偟膩碚f，LiNGAM算法分為估計(jì)與剪枝兩個(gè)階段。

第一階段是估計(jì)階段，該階段能夠得出因果順序以及初步估計(jì)出整個(gè)因果結(jié)構(gòu)(即矩陣系數(shù))。由式(2)可推出：Wx=e,W=(I-B),I為單位矩陣，W稱為混合矩陣。LiNGAM算法首先利用ICA算法根據(jù)觀察數(shù)據(jù)估計(jì)出分離矩陣W′，但是估計(jì)得到的W′矩陣存在兩個(gè)問題：(1)W′中對(duì)角線可能為0，這與W′的對(duì)角線全為1的約束相矛盾；(2)變量是隨機(jī)排列的，與因果順序不符。為了解決這兩個(gè)問題，LiNGAM算法對(duì)W′的行重新排序，使得W′對(duì)角線均不為0。然后，LiNGAM算法將W′每一行除以該行對(duì)角線的值(歸一化)得到W″，并計(jì)算出B=I-W″。再根據(jù)因果順序?qū)?yīng)的系數(shù)矩陣是對(duì)角線均為0的下三角矩陣這個(gè)約束，LiNGAM算法同時(shí)對(duì)B的行和列進(jìn)行重新排列得到B′，使得B′為下三角矩陣，從而得到因果順序。最后LiNGAM算法根據(jù)最小二乘法得出具體矩陣系數(shù)。估計(jì)階段所得出的關(guān)系矩陣B所對(duì)應(yīng)的有向無環(huán)圖是全相聯(lián)的，但是實(shí)際中常見的圖是稀疏的，因此對(duì)B剪枝是必要的步驟。

第二階段是剪枝階段，該階段是對(duì)估計(jì)階段得出的關(guān)系矩陣B中的每一條不為0的邊進(jìn)行檢驗(yàn)。在文獻(xiàn)[1]中，Shimizu等人提出了剪枝算法MODELFIT。該算法首先采用Wald檢驗(yàn)來檢驗(yàn)每條邊的顯著水平。對(duì)于每條未能通過Wald檢驗(yàn)的邊，MODELFIT均根據(jù)卡方檢驗(yàn)等方式檢驗(yàn)剪掉該邊前后的模型差異的顯著性。MODELFIT根據(jù)剪掉某條邊前后模型差異顯著水平來決定是否剪枝。該算法有兩個(gè)缺點(diǎn)：(1) MODELFIT每剪去一條邊，都需要檢驗(yàn)?zāi)Ｐ筒町惖娘@著性，這項(xiàng)操作需要大量耗時(shí)的矩陣求逆和矩陣求根等運(yùn)算(其復(fù)雜度皆為維度的立方)；(2)對(duì)比實(shí)驗(yàn)表明MODELFIT剪枝算法在稀疏圖上的準(zhǔn)確率相對(duì)較低。

1.3基于偏相關(guān)系數(shù)的條件獨(dú)立性測(cè)試

本文采用偏相關(guān)系數(shù)檢驗(yàn)作為條件獨(dú)立性測(cè)試的方法。下面引入幾個(gè)重要的定義。

定義1偏相關(guān)系數(shù)隨機(jī)變量x、y在給定受控變量的集合Z時(shí)的偏相關(guān)系數(shù)是Rxz與Ryz之間的相關(guān)系數(shù)，其中Rxz為變量x與Z線性回歸的殘差，Ryz為變量y與Z線性回歸的殘差。

偏相關(guān)系數(shù)是指兩個(gè)變量在通過線性回歸的方式消除受控變量影響后的相關(guān)系數(shù)。若所涉及的隨機(jī)變量均為高斯分布，隨機(jī)變量x、y在給定受控變量的集合Z時(shí)的偏相關(guān)系數(shù)等于0，等價(jià)于變量x與變量y在條件集Z上條件獨(dú)立；在其他情況下，偏相關(guān)系數(shù)是條件獨(dú)立性的一種近似的計(jì)算方式。判斷偏相關(guān)系數(shù)是否嚴(yán)格為0常采用假設(shè)檢驗(yàn)的方式。Fisher Z 變換與T檢驗(yàn)是常見的兩種方式。

定義2條件獨(dú)立性設(shè)隨機(jī)變量集合為V={x1,x2,…,xn},X、Y、Z是V的任意非空子集。若有P(X|Y,Z)=P(X|Z),并且(Y,Z)>0，那么稱X、Y在給定Z時(shí)條件獨(dú)立。

定義3d-分離準(zhǔn)則設(shè)X、Y、Z是貝葉斯網(wǎng)絡(luò)G中任意三個(gè)互不相交的節(jié)點(diǎn)集合，稱Z在圖G中d-分離節(jié)點(diǎn)集X和Y。若對(duì)任意的從X的節(jié)點(diǎn)到Y(jié)的一個(gè)節(jié)點(diǎn)的路徑P均被Z阻斷，也就是路徑P上存在一個(gè)結(jié)點(diǎn)xi滿足下列其中一個(gè)條件：

(1)xi在P上形成碰撞，即→xi←，且xi及其后代結(jié)點(diǎn)都不在Z中；

(2)xi在P上不存在碰撞，即→xi→或←xi←，且xi在Z中。

定義4馬爾科夫毯設(shè)貝葉斯網(wǎng)絡(luò)G=，集合V代表節(jié)點(diǎn)，集合E代表邊。設(shè)xi是G中任意節(jié)點(diǎn)，xi的馬尓科夫毯是由該節(jié)點(diǎn)的所有的父親節(jié)點(diǎn)、孩子節(jié)點(diǎn)以及配偶節(jié)點(diǎn)(xi每個(gè)孩子節(jié)點(diǎn)的其他父親節(jié)點(diǎn)，稱為xi的配偶節(jié)點(diǎn))組成的集合。

貝葉斯網(wǎng)中，節(jié)點(diǎn)xi、xj在節(jié)點(diǎn)集合Z上條件獨(dú)立等價(jià)于Z阻隔xi、xj之間的所有的路徑，即Z集合d-分離了xi、xj。若貝葉斯網(wǎng)中的節(jié)點(diǎn)xi、xj之間不存在邊，那么必定存在集合Zd-分離了xi、xj；反之，必不存在集合Zd-分離了xi、xj。因此通過逐一測(cè)試集合V/{xi,xj}的子集能否d-分離xi、xj，就可斷定xi、xj之間關(guān)系。該方法稱為條件獨(dú)立性測(cè)試。本文中的條件獨(dú)立性測(cè)試是基于偏相關(guān)系數(shù)，其判斷Z集合是否d-分離了節(jié)點(diǎn)xi、xj時(shí)，根據(jù)樣本計(jì)算節(jié)點(diǎn)xi、xj在給定集合Z時(shí)的偏相關(guān)系數(shù)。若偏相關(guān)系數(shù)顯著為0，那么Z集合d-分離了節(jié)點(diǎn)xi、xj；反之，Z集合未能d-分離節(jié)點(diǎn)xi、xj。節(jié)點(diǎn)的馬爾科夫毯d分離了該節(jié)點(diǎn)與任意不在其馬爾科夫毯中的節(jié)點(diǎn)。本文將節(jié)點(diǎn)xi的馬爾科夫毯記為PC(xi)。

2　基于條件獨(dú)立性的LiNGAM剪枝算法

2.1剪枝問題描述

設(shè)LiNGAM模型中變量為{x1,x2,…,xn}，樣本矩陣X∈Rn×m，n為樣本中變量個(gè)數(shù)或稱為樣本維度，m為樣本個(gè)數(shù)。LiNGAM算法的估計(jì)階段的所得到的關(guān)系矩陣為B，因果順序?yàn)閗(·)。剪枝算法是根據(jù)上述已知條件，對(duì)B進(jìn)行剪枝，返回剪枝后的關(guān)系矩陣。按因果順序k(·)排列變量后，式(1)變?yōu)椋?/p>

(3)

其中i、j是變量在因果順序中的位置。剪枝問題與原結(jié)構(gòu)推斷問題的不同之處是因果順序是已知條件，因此式(3)中的系數(shù)矩陣B是對(duì)角線均為0的下三角矩陣，并且是稀疏的。

2.2剪枝算法流程

在已知因果順序基礎(chǔ)上，本文提出了基于條件獨(dú)立性測(cè)試的剪枝算法，流程如算法1中所示。

算法1基于條件獨(dú)立性測(cè)試的剪枝算法

輸入:樣本矩陣X∈Rn×m,因果順序k(·)與待剪枝系數(shù)矩陣B。

輸出:剪枝后的矩陣B′(bij=0表示xi與xj之間不存在邊)。

預(yù)處理:首先計(jì)算B′=PBP,X′=PX,P為因果順序k(·)所對(duì)應(yīng)的置換矩陣。再按照B′中變量的順序，從變量x1開始剪枝，直到xn結(jié)束。記當(dāng)前處理的變量為xi,i∈[1,n]。

步驟1：根據(jù)條件獨(dú)立性測(cè)試，逐一判斷當(dāng)前處理變量xi與xj∈{x1,x2,…,xi-1}的關(guān)系。具體做法是根據(jù)樣本計(jì)算每個(gè)變量xj,j∈[1,i)與變量xi在給定PC(xi)時(shí)的偏相關(guān)系數(shù)，并判斷偏相關(guān)系數(shù)是否顯著為0。若偏相關(guān)系數(shù)為0，則令bij=0。

步驟2：對(duì)集合PC(xi)中的變量進(jìn)行內(nèi)部的條件獨(dú)立性測(cè)試。具體做法是通過計(jì)算每個(gè)變量xt∈PC(xi)與變量xi在給定Z=PC(xi)/xt時(shí)的偏相關(guān)系數(shù)，再次判斷xi、xt的關(guān)系。若偏相關(guān)系數(shù)的P值高于顯著水平(0.05)，則令bit=0。

步驟3：若已處理完所有變量那么剪枝完畢，返回剪枝后的B′，否則返回步驟一并繼續(xù)處理下一個(gè)變量。

在剪枝之前，本文將B按照因果順序k(·)重新排列為B′,采用逐步擴(kuò)展的方式剪枝。

在步驟1中，變量{x1,x2,…,xi-1}之間的關(guān)系是已知的，僅有xj∈{x1,x2,…,xi-1}與當(dāng)前處理變量xi的關(guān)系是需要進(jìn)行判定的。在變量{x1,x2,…,xi}組成的有向無環(huán)圖中，xi是最后一個(gè)變量，它的馬爾科夫毯僅由其父變量組成，因此步驟1初步得出了PC(xi)。假設(shè)檢驗(yàn)采用了Fisher Z變換，顯著水平為0.05。

步驟2是進(jìn)一步測(cè)試PC(xi)中的變量是否滿足馬爾科夫毯的定義。雖然步驟1中已經(jīng)求出了PC(xi),但是實(shí)驗(yàn)表明總體準(zhǔn)確率較低，這意味著步驟所求得的PC(xi)中仍存在不屬于PC(xi)的變量未能被剪除。從另外一個(gè)角度，算法的步驟1是根據(jù)PC(xj)去判斷xi、xj的關(guān)系，步驟2則是利用PC(xi)去判斷xi、xj之間的關(guān)系。步驟2中采用了T檢驗(yàn)來計(jì)算P值。

2.3正確性分析

根據(jù)條件獨(dú)立性的定義，在n個(gè)變量組成的貝葉斯網(wǎng)絡(luò)中判定兩個(gè)變量是否存在邊所需的測(cè)試次數(shù)最多為2n-2次。本文基于引理一將所需測(cè)試的變量集合減小為變量的馬爾可夫毯，這大幅度降低了所需測(cè)試的次數(shù)。本文進(jìn)一步結(jié)合剪枝問題中因果順序的已知條件將判斷兩個(gè)變量關(guān)系所需的條件獨(dú)立性測(cè)試次數(shù)減少為兩次。實(shí)驗(yàn)表明有效地降低了誤剪枝率。

引理1在貝葉斯網(wǎng)中，對(duì)于任意兩個(gè)不存在邊節(jié)點(diǎn)xi、xj，一定存在PC(xi)的子集(或PC(xj)的子集)Zd-分離了xi、xj。

根據(jù)引理1，判斷LiNGAM模型中任意兩個(gè)變量xi、xj的關(guān)系，需要逐一測(cè)試的集合是xi或xj的馬爾科夫毯集合的所有子集。若存在集合Z是PC(xi)的子集(或PC(xj)的子集)使得xi、xj條件獨(dú)立，那么xi、xj不存在邊；若不存在這樣的集合Z，那么xi、xj存在邊。采用類似方法的還有BASSUM[9]與HITON[10]等。該方法有效減少了所需的條件獨(dú)立性測(cè)試次數(shù)，同時(shí)準(zhǔn)確率高，然而存在容易誤剪枝的問題。這是因?yàn)樽兞康臈l件獨(dú)立性一般是根據(jù)樣本采用某種方法估計(jì)得出的，存在一定的誤差。同時(shí)由于每一條保留的邊均需要經(jīng)過多次條件獨(dú)立性測(cè)試，這使得原本存在的邊有較高概率被錯(cuò)誤剪掉。若將PC等貝葉斯算法用作剪枝算法也存在類似的誤剪枝率高的問題。

由引理1得出的剪枝方法仍存在誤剪枝率高的問題，核心問題是如何減少條件獨(dú)立性測(cè)試次數(shù)。結(jié)合因果順序，本文提出按照因果順序依次剪枝，有效地減少了所需條件獨(dú)立性測(cè)試次數(shù)。

引理2設(shè)變量{x1,x2,…,xn}符合LiNGAM模型，B為系數(shù)矩陣，因果順序k(·)與觀察順序{1,2,…,n}是一致的,那么?xt,t∈[1,n]，{x1,x2,…,xt}組成了一個(gè)完整的LiNGAM模型。

證明：對(duì)于?xt,t∈[1,n]，根據(jù)因果順序的定義可知?xj,j∈[t+1,n]不會(huì)是?xi,i∈[1,t]的因變量。這使得xt后面的變量xj不會(huì)對(duì)xt以及xt前面的變量xi產(chǎn)生影響，因此{(lán)x1,x2,…,xt}是一個(gè)完整的LiNGAM模型。

由引理2可知，判斷變量xi、xj之間是否存在關(guān)系時(shí)，那些位于后面的變量xk,max{i,j}

上文按照因果順序剪枝，縮減了剪枝問題的規(guī)模。這里進(jìn)一步結(jié)合引理1與引理2，提出了僅需兩次獨(dú)立性測(cè)試判定兩個(gè)變量之間關(guān)系的方法。實(shí)驗(yàn)表明，該方法能夠有效剪枝，并且誤剪枝率較低。

引理3 在變量{x1,x2,…,xn}組成的LiNGAM模型中，設(shè)因果順序k(·)與觀察順序{1,2,…,n}是一致的，變量{x1,x2,…,xt}是已知的子模型。對(duì)于?xi,i∈[1,t]，變量xi、xt+1存在邊近似等價(jià)于集合PC(xi)未能d-分離xi、xt+1且集合PC(xt+1)/xi未能d-分離xi、xt+1。

證明：引理3中，判斷xi、xt+1的關(guān)系時(shí)，首先根據(jù)已知條件能夠判斷PC(xi)是否d-分離xi,xt+1。根據(jù)馬爾科夫毯的性質(zhì)可知,PC(xi)未能d-分離xi、xt+1表明變量之間有較高的可能性存在邊，由此可估計(jì)得出xt+1的所有父變量集合，記為Pa(xt+1)。在變量{x1,x2,…,xt,xt+1}組成的模型中，根據(jù)馬爾科夫毯的定義可知PC(xt+1)=Pa(xt+1)。同時(shí)，若PC(xt+1)/xi未能d-分離xi、xt+1，進(jìn)一步表明xi、xt+1之間可能存在邊。反之，若xi、xt+1之間存在邊，引理三中所描述的d-分離性質(zhì)是必須滿足的。

依據(jù)引理3，判斷任意兩個(gè)變量xi、xj的關(guān)系僅需兩次測(cè)試。該方法優(yōu)點(diǎn)是僅需兩次條件獨(dú)立性測(cè)試即可判斷邊是否存在；缺點(diǎn)是由于只是一種近似的判斷，可能將少數(shù)不存在的邊誤判為存在。然而實(shí)驗(yàn)表明，該策略在準(zhǔn)確率上并無明顯劣勢(shì)，相反降低了誤剪枝率。

根據(jù)條件獨(dú)立性測(cè)試解決剪枝問題的難點(diǎn)是如何降低誤剪枝率。設(shè)當(dāng)前處理的變量為xt+1，變量{x1,x2,…,xt}是結(jié)構(gòu)已知的LiNGAM模型。根據(jù)引理3即可判斷出xt+1與?xi,i∈[1,t]之間的關(guān)系，得出變量{x1,x2,…,xt′,xt′+1}的完整結(jié)構(gòu)，從而可以按照因果順序繼續(xù)處理下一個(gè)變量。本文選取變量的馬爾科夫毯作為條件獨(dú)立性測(cè)試的條件集合，提出僅需兩次獨(dú)立性測(cè)試來判斷兩個(gè)變量之間的因果關(guān)系的方法，較好地解決了誤剪枝率高的問題。

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

實(shí)驗(yàn)中本文的剪枝算法與Resampling、OLSBOOT、MODELFIT和Adaptive Lasso四種剪枝方法在模擬數(shù)據(jù)上做了充分的比較[1]。綜合考慮剪枝后關(guān)系矩陣的準(zhǔn)確率與召回率(召回率高，表明剪枝算法誤剪枝率低)，本文采用F1-score作為評(píng)價(jià)標(biāo)準(zhǔn)。本文算法在實(shí)驗(yàn)中命名為PaC與PaCOneStep。PaCOneStep是僅采用步驟1的剪枝算法。Resampling、MODELFIT、OLSBOOT與Adpative Lasso是文獻(xiàn)[1,4]中的所采用的剪枝算法。OLSBOOT與Resampling算法均是重采樣的方法，其中OLSBOOT是基于BOOTSTRAP的方法。

本文實(shí)驗(yàn)在MATLAB 2011b中完成，硬件配置為4 GB內(nèi)存，酷睿雙核2.0 GHz 。

3.1模擬數(shù)據(jù)的生成以及參數(shù)

本文實(shí)驗(yàn)中采用了兩種方式生成模擬數(shù)據(jù)。第一種是LiNGAM算法中所提供的模擬數(shù)據(jù)的生成算法[1]。該算法在高斯分布的基礎(chǔ)上采用了隨機(jī)選取的方式使得干擾變量分布服從超高斯或亞高斯分布。模擬數(shù)據(jù)在生成后，變量的排列順序是隨機(jī)排列的，這使得觀察順序與因果順序不一致。第二種生成模擬數(shù)據(jù)的方式是DirectLiNGAM算法[4]所采用的，該算法僅可生成稀疏結(jié)構(gòu)的數(shù)據(jù)。

模擬數(shù)據(jù)的幾個(gè)主要參數(shù)為變量的最大入度v(變量最多可以存在的父變量個(gè)數(shù))，變量數(shù)n，樣本數(shù)m。

3.2實(shí)驗(yàn)效果

首先，圖1是在不同稀疏程度下各個(gè)剪枝算法對(duì)比的實(shí)驗(yàn)結(jié)果。變量數(shù)n=10，樣本數(shù)目m=1000，變量最大入度v={1,2,3,4,5,FULL}；v=FULL表示采用了全相聯(lián)關(guān)系。將正確的因果順序作為了已知條件。 由圖1中可看出本文算法僅在變量最大入度v=1時(shí)(此時(shí)的結(jié)構(gòu)退化為直線片段)稍差于Resampling，在其他情況下均優(yōu)于其他算法。PaCOneStep與Adaptive Lasso算法在變量最大入度v較小的情況下，準(zhǔn)確率很低。MODELFIT也存在類似問題。在全相聯(lián)的結(jié)構(gòu)上各個(gè)剪枝算法的表現(xiàn)反應(yīng)了其誤剪枝的情況，由圖1可看出本文算法誤剪枝率最低。

圖1　第一種數(shù)據(jù)產(chǎn)生方式下各個(gè)算法的F1-Score性能比較。

其次，圖2-圖5是各個(gè)剪枝算法作為L(zhǎng)iNGAM算法的剪枝算法時(shí)在兩種不同數(shù)據(jù)生成方式下對(duì)比的實(shí)驗(yàn)結(jié)果。圖2、圖3的數(shù)量數(shù)n=10。圖4、圖5的數(shù)量數(shù)n=100,下標(biāo)1表示給出正確的因果順序，下標(biāo)2表示采用LiNGAM估計(jì)因果順序。本文剪枝算法在兩種數(shù)據(jù)生成方式中都得到較優(yōu)的結(jié)果，僅在第二種數(shù)據(jù)生成方式下略差于Resampling。相比之下，其余剪枝算法存在著不穩(wěn)定或不適用于變量較多的情況等問題。圖2中，MODELFIT、OLSBOOT略差于本文算法；圖3中，本文算法僅差于Resampling，OLSBOOT與本文算法的剪枝結(jié)果仍然是接近的。Resampling算法在采用第一種數(shù)據(jù)生成方式時(shí)，其剪枝結(jié)果是最差的，因此是不穩(wěn)定的。在變量數(shù)目較少時(shí)，OLSBOOT與本文算法均能取得較好的剪枝結(jié)果，但是OLSBOOT不適于變量多的情況，圖4、圖5驗(yàn)證了這一點(diǎn)。變量數(shù)目為100且采用LiNGAM估計(jì)因果順序時(shí)，Resampling與本文算法的剪枝結(jié)果是較為接近的，在已知正確的因果順序后，本文算法具有較大的優(yōu)勢(shì)。

圖2　采用第一種數(shù)據(jù)生成方式1

圖3　采用第二種數(shù)據(jù)生成方式1

圖4　采用第一種數(shù)據(jù)生成方式2

圖5　采用第二種數(shù)據(jù)生成方式2

最后，表1是各剪枝算法的耗時(shí)情況的比較。本文剪枝算法時(shí)間復(fù)雜度小于Adaptive Lasso與MODELFIT，高于Resampling與OLSBOOT。本文算法的基本步驟是偏相關(guān)系數(shù)的計(jì)算，其時(shí)間復(fù)雜度是條件集合中變量個(gè)數(shù)的三次方。在稀疏圖中，變量xi的馬爾科夫毯中變量個(gè)數(shù)遠(yuǎn)小于n，記為mi,0≤mi≤n-2。本文算法時(shí)間復(fù)雜度的上界為O(n2×(max{m1,m2,…,mn})3)。

表1　算法所耗時(shí)間T的變化(單位：秒，-代表耗時(shí)過長(zhǎng))

4　結(jié)　語

不同于MODELFIT、Adaptive Lasso等剪枝算法，本文算法依據(jù)馬爾科夫毯的相關(guān)性質(zhì)，充分利用LiNGAM模型的因果順序，減少了所需條件獨(dú)立性測(cè)試的次數(shù)，較好地解決了將PC等算法作為剪枝算法所存在的誤剪枝率高的問題。實(shí)驗(yàn)表明，與LiNGAM算法和DirectLiNGAM算法所采用的剪枝算法相比，本文的剪枝算法具有更高的準(zhǔn)確率和穩(wěn)定性。

本文算法在模擬數(shù)據(jù)集上進(jìn)行了充分的對(duì)比實(shí)驗(yàn)，得到了較優(yōu)的結(jié)果。下一步的重要研究?jī)?nèi)容是本文算法在真實(shí)數(shù)據(jù)上的表現(xiàn)。同時(shí)，由于高維度下正確的因果順序較難獲得，高維空間的因果順序推斷算法與不依賴于因果順序的剪枝算法也是未來的主要研究方向。

[2] Hoyer P O,Janzing D,Mooij J M,et al.Nonlinear causal discovery with additive noise models[C]//Advances in neural information processing systems.2009:689-696.

[5] Shimizu S,Inazumi T,Sogawa Y,et al.DirectLiNGAM:A direct method for learning a linear non-gaussian structural equation model[J].The Journal of Machine Learning Research,2011,12(2):1225-1248.

[6] Glymour C,Spirtes P,Scheines R.Causal inference[J].Erkenntnis,1991,35(1-3):151-189.

[7] Spirtes P,Glymour C N,Scheines R.Causation,prediction,and search [M].MIT press,2000.

[8] Pearl J.Causality:models,reasoning and inference [M].Cambridge:MIT press,2000.

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

[10] Aliferis C F,Tsamardinos I,Statnikov A.HITON:a novel Markov Blanket algorithm for optimal variable selection[C]//AMIA Annu Symp Proc.,2003:21-25.

LINGAM MODEL PRUNING ALGORITHM BASED ON CONDITIONAL INDEPENDENCE

Hao ZhifengLü HongweiCai RuichuYuan Chang

(FacultyofComputerScience,GuangdongUniversityofTechnology,Guangzhou510006，Guangdong,China)

How to conjecture causal network structure according to the observed data is an important problem in the field of statistics and machine learning.Quite a few research achievements have been gained by scholars in recent years,among them LiNGAM algorithm is a classical linear causal inference algorithm.However the pruning policy employed in LiNGAM algorithm requires high runtime complexity and provides poor accuracy on sparse graphs.Therefore in this paper we present a novel pruning method to solve this problem,it is based on conditional independence testing.The algorithm first rearranges the variables according to causal order and then employs partial correlation coefficient to check the conditional independence between variables according to new order.Numerous experimental results indicate that the pruning algorithm based on conditional independence proposed in the paper achieves higher accuracy with better running time on sparse graph than the one of LiNGAM.

Linear causalityPartial correlationConditional independencePruning method

2015-03-12。國(guó)家自然科學(xué)基金項(xiàng)目(61472089)。郝志峰，教授，主研領(lǐng)域：算法設(shè)計(jì)與分析，組合優(yōu)化與算法研究，仿生算法的數(shù)學(xué)理論，代數(shù)學(xué)及其應(yīng)用。呂宏偉，碩士。蔡瑞初，副教授。袁暢，碩士。

TP3

A

10.3969/j.issn.1000-386x.2016.08.056