基于全局和局部回歸的因果定向改進(jìn)算法

潘孟姣 蔡青松

(北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院 北京 100048)

0 引 言

因果關(guān)系[1]是普遍存在于事物間的聯(lián)系，它從本質(zhì)上描述了何種原因直接、間接或較大程度上導(dǎo)致了某種結(jié)果，因此比相關(guān)關(guān)系[2]對某種現(xiàn)象的發(fā)生具有更好的解釋性[3]。然而在實(shí)際中，鑒于工具的缺乏及耗費(fèi)的代價過大等因素，人們通常只能依據(jù)有限的觀測數(shù)據(jù)和經(jīng)驗(yàn)知識來分析并推斷事物產(chǎn)生的根源，其結(jié)果往往具有明顯的局限性及不確定性。近年來基于人工智能的數(shù)據(jù)分析方法得到了快速發(fā)展，進(jìn)而推動了因果關(guān)系推斷領(lǐng)域在理論和實(shí)踐上的進(jìn)步。自20世紀(jì)80年代以來，基于觀測數(shù)據(jù)的因果關(guān)系推斷獲得了顯著的研究成果，大量文獻(xiàn)表明[4-7]，對已獲取的數(shù)據(jù)進(jìn)行因果關(guān)系推斷是一個基礎(chǔ)科學(xué)問題，在諸多領(lǐng)域均有著潛在的重要應(yīng)用價值。例如，在醫(yī)學(xué)診斷領(lǐng)域，基于就診者的各項(xiàng)檢查數(shù)據(jù)進(jìn)行因果分析，有利于對其健康狀況做出準(zhǔn)確的判定，對指導(dǎo)后續(xù)行為具有重要意義。

采用傳統(tǒng)的因果網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法[8-9]可以識別觀測數(shù)據(jù)間的部分因果關(guān)系，但此類方法大多無法對馬爾科夫等價類[10]進(jìn)行準(zhǔn)確地判斷，即無法對變量之間的因果方向進(jìn)行準(zhǔn)確地判定。推斷觀測數(shù)據(jù)間的因果方向(也稱因果定向[11])，是當(dāng)前因果關(guān)系推斷領(lǐng)域的重要研究熱點(diǎn)之一。

近年來，針對觀測數(shù)據(jù)間一對一因果關(guān)系的定向問題，學(xué)者們提出了多種方法[12-16]。其中，加性噪聲模型ANM(Additive Noise Model)[12,17]是解決這類問題的初步嘗試，它假定結(jié)果變量由原因變量及與原因無關(guān)的加性噪聲決定，然后通過檢驗(yàn)所假設(shè)的原因變量與加性噪聲之間的獨(dú)立性來進(jìn)行因果定向。在這種強(qiáng)假設(shè)下提出的方法在特定仿真數(shù)據(jù)上表現(xiàn)出高準(zhǔn)確率，但實(shí)際中將會存在兩個方向都符合或都不符合假設(shè)的情況，使其在真實(shí)數(shù)據(jù)集上的準(zhǔn)確率受限[12,16]。一些基于獨(dú)立性假設(shè)[10]的研究工作也采用獨(dú)立性測試進(jìn)行因果定向，如DC算法[13]。根據(jù)獨(dú)立性假設(shè)，如果變量X和變量Y間的因果方向?yàn)閄→Y，則邊緣分布P(X)和條件分布P(Y|X)是相互獨(dú)立的，反之則不獨(dú)立。DC算法在多元分類數(shù)據(jù)上計(jì)算P(X)和P(Y|X)之間以及P(Y)和P(X|Y)之間的距離相關(guān)系數(shù)，將具有較小相關(guān)性的方向推斷為可能的因果方向，此算法僅適用于多分類數(shù)據(jù)。

除采用獨(dú)立性測試進(jìn)行因果定向外，另一類方法則主要采用柯氏復(fù)雜度作為基礎(chǔ)。算法的馬爾科夫條件指出，兩個隨機(jī)變量X和Y之間具有最低柯氏復(fù)雜度的方向是最有可能的因果方向[10]。但由于停機(jī)問題(即一個程序是否能在有限的時間之內(nèi)結(jié)束運(yùn)行)，柯氏復(fù)雜度無法計(jì)算。ORIGO算法[14]采用最小描述長度MDL原理[18]來估計(jì)柯氏復(fù)雜度。該算法建立在基于MDL原理的PACK算法[19]上，并使用決策樹來編碼布爾型數(shù)據(jù)，通過近似計(jì)算柯氏復(fù)雜度來推斷因果方向，適用于二分類數(shù)據(jù)。CISC算法[15]將數(shù)據(jù)視為服從多項(xiàng)分布的隨機(jī)變量，通過改變參數(shù)產(chǎn)生不同的分布，用于構(gòu)建概率分布的模型類。此算法通過使用隨機(jī)復(fù)雜度來估計(jì)柯氏復(fù)雜度，進(jìn)而推斷因果方向，適用于多分類數(shù)據(jù)。該隨機(jī)復(fù)雜度是數(shù)據(jù)相對于對應(yīng)模型類的最小描述長度。

文獻(xiàn)[16]遵循基于柯氏復(fù)雜度的信息理論方法，通過構(gòu)建回歸模型，采用MDL原理估計(jì)兩個變量相互回歸所需柯氏復(fù)雜度的大小，以此判定兩者間可能的因果方向，并實(shí)例化為SLOPE算法。相對于其他類型的算法，該算法在分類、線性及非線性數(shù)據(jù)上都具有較高的推斷準(zhǔn)確率。鑒于實(shí)際中遇到的不僅僅是分類問題，兩個變量間可能存在線性或更復(fù)雜的非線性關(guān)系。因此相對于其他算法，其更適用于觀測數(shù)據(jù)的因果定向。但此算法在遍歷回歸模型計(jì)算對應(yīng)描述長度時需消耗大量時間成本，影響算法效率。

因此，本文針對這個問題，對原始的因果定向算法進(jìn)行改進(jìn)，提出一種基于全局和局部回歸的因果定向改進(jìn)算法ISLOPE(Improved SLOPE)。該方法嘗試根據(jù)模型的特征分別構(gòu)建全局和局部回歸模型。與原模型相比，減少了部分不符合對應(yīng)特征的冗余模型，降低了遍歷回歸模型計(jì)算對應(yīng)描述長度時所需的時間成本，進(jìn)而提高了原算法的效率。實(shí)驗(yàn)結(jié)果表明，相較于其他對比算法，所提出的算法在合成數(shù)據(jù)及真實(shí)觀測數(shù)據(jù)上都具有較好的性能。

1 理論基礎(chǔ)

因果定向算法的目的是判定兩個變量間因果關(guān)系的方向，即在兩者中推斷并區(qū)分原因變量和結(jié)果變量。采用基于柯氏復(fù)雜度的方法進(jìn)行因果方向判定是因果定向研究的主要方法之一。

1.1 柯氏復(fù)雜度

字符串s的柯氏復(fù)雜度K(s)是通用圖靈機(jī)U產(chǎn)生s并停機(jī)的最短二進(jìn)制程序p*的長度，記為K(s)=|p*|。y相對于x的條件柯氏復(fù)雜度K(y|x)是當(dāng)x作為程序的輸入被提供時產(chǎn)生y并停機(jī)的最短二進(jìn)制程序p*的長度[20]。概率分布P的柯氏復(fù)雜度是在U上輸入x和精度ε后產(chǎn)生符合精度的P(x)然后停機(jī)的最短二進(jìn)制程序p*的長度，條件概率分布的柯氏復(fù)雜度定義類似。

下面使用柯氏復(fù)雜度進(jìn)行因果推斷。雖然此推理規(guī)則的理論基礎(chǔ)堅(jiān)固，但由于停機(jī)問題，柯氏復(fù)雜度不可計(jì)算。

定理1(柯氏復(fù)雜度因果推斷[21]) 若變量X和Y間的因果方向?yàn)閄→Y，則有：

K(P(X))+K(P(Y|X))≤K(P(Y))+K(P(X|Y))

(1)

1.2 MDL原理

MDL原理為柯氏復(fù)雜度的近似計(jì)算提供了合理的手段，它規(guī)避了柯氏復(fù)雜度的可計(jì)算性問題，將程序限制在可終止的且足以捕捉大部分規(guī)則的程序上。在MDL理論中，程序通常被稱為模型。使用模型m∈M編碼數(shù)據(jù)X時，X總的描述長度為模型m的長度加上編碼后長度[18]，即：

L(X,m)=L(m)+L(X|m)

(2)

MDL原理表明，給定數(shù)據(jù)X和模型類M，最佳的統(tǒng)計(jì)模型mo∈M將為數(shù)據(jù)X產(chǎn)生最小的描述長度。

1.3 加性噪聲模型

定義1(加性噪聲模型[17]) 假設(shè)變量X和變量Y滿足以下條件，則稱X到Y(jié)符合ANM。

Y=f(X)+NN⊥X

(3)

式中：f是任意函數(shù)，N是獨(dú)立于X的加性噪聲。

對于變量X和Y，當(dāng)X到Y(jié)符合一個ANM，但Y到X不符合時，稱X是Y的原因，Y是X的結(jié)果，即因果方向?yàn)閄→Y。

2 因果定向方法及改進(jìn)算法

2.1 模型及指標(biāo)構(gòu)建

回歸模型類M由多個子模型類Ms構(gòu)成。每個Ms對應(yīng)一個線性或非線性函數(shù)，單個模型類Ms由多個不同參數(shù)的子模型m構(gòu)成。單個子模型m的描述長度定義如下：

(4)

將回歸模型的參數(shù)類Υ中的每一個參數(shù)γ編碼到一定的精度ε，用最小的整數(shù)δ來設(shè)定參數(shù)γ，使其滿足γ×10δ≥10ε。用Lo表示整數(shù)z(z≥1)的MDL最優(yōu)編碼[22]，如式中的Lo(δ)表示整數(shù)δ的MDL最優(yōu)編碼。

已知兩組相關(guān)的數(shù)據(jù)變量X={x1,x2,…,xn}和Y={y1,y2,…,yn}，假設(shè)沒有混雜變量[23]的影響，即X和Y沒有隱藏的共同原因Z。使用子模型m∈M將變量X向變量Y回歸，并將它產(chǎn)生的誤差視為服從高斯分布的噪聲。根據(jù)MDL原理在回歸模型類M中選出X向Y回歸的最優(yōu)子模型mo。由加性噪聲模型Y=f(X)+N可知，一個出現(xiàn)多次的值將對應(yīng)一系列服從N同類型分布的Y值。

變量X和變量Y之間的整體關(guān)系使用全局模型mo來擬合，而對于一個x值匹配多個Y值的情形(附加數(shù)據(jù))，增加局部模型類Ma來擬合。具體而言，對于對應(yīng)多個Y值的xi，將其變換為服從均勻分布的序列:

Xi={-v,…,v} |Xi|=|Yi|,v∈N*

(5)

式中：Yi為映射到xi上的Y值升序排列后的序列，N*為正整數(shù)。

原始的因果定向算法在模型類M中選出Xi向Yi回歸的最優(yōu)子模型ma。由于其全局和局部回歸模型統(tǒng)一構(gòu)建，故而模型類M中的所有子模型既都屬于全局回歸模型又都屬于局部回歸模型。

改進(jìn)后模型類M=mo∪Ma的描述長度由下式給出：

L(M)=Lo(|M|)+lb((|Ma|-1)?(|X|-1))+

(6)

即：首先描述所選用的模型的個數(shù)，其次將局部模型類Ma映射到與之對應(yīng)的數(shù)據(jù)X上(其中?表示此映射)，然后分別使用lb(|M|)比特、lb(|Ma|)比特標(biāo)記所選用全局子模型及局部子模型的類型，最后描述所選模型自身。

變量X的描述長度定義如下：

L(X)=-nlbd

(7)

d=min{|xk+1-xk|||xk+1≠xk|,k=1,2,…,n-1}

(8)

式中：d表示X中相鄰元素間的最短距離(忽略零值)。

已知M、X的條件下Y的描述長度定義如下：

(9)

對于數(shù)據(jù)對(X,Y)，X到Y(jié)的總描述長度LX→Y定義為X的描述長度、所選用的模型類M的描述長度及已知M、X的條件下Y的描述長度之和，即：

LX→Y=L(X)+L(M)+L(Y|M,X)

(10)

Y到X的總描述長度LY→X的定義類似。

2.2 因果方向推論規(guī)則

使用上述描述長度指標(biāo)，得出以下因果推論規(guī)則。

(1) 如果LX→Y

(2) 如果LX→Y>LY→X，則推斷出因果方向?yàn)閅→X。

(3) 如果LX→Y=LY→X，則無法確定。

也就是說，如果“先描述X，然后給定X再描述Y”較“先描述Y，然后給定Y再描述X”容易，則推斷出X很可能是Y的原因；如果反過來，則推斷出Y很可能是X的原因；否則無法判斷。

2.3 算法描述

算法1改進(jìn)型因果定向算法ISLOPE

輸入：數(shù)據(jù)對(X,Y)；

輸出：總描述長度LX→Y。

步驟1由公式計(jì)算X的描述長度L(X)。

步驟2初始化模型類M為空，LX→Y=L(X)。

步驟3在回歸模型類M中匹配X向Y回歸的最優(yōu)子模型mo，并將其添加到模型類M中，由公式計(jì)算并更新此時的LX→Y。

步驟6輸出LX→Y。

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

為驗(yàn)證改進(jìn)算法ISLOPE的性能，采用合成數(shù)據(jù)及真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。并使用原始的SLOPE算法[16]進(jìn)行對比。此外，為更全面地驗(yàn)證該算法的性能，實(shí)驗(yàn)部分還分別選擇基于柯氏復(fù)雜度的CISC算法[15]及基于獨(dú)立性假設(shè)的DC算法[13]進(jìn)行對比。

所有實(shí)驗(yàn)均在運(yùn)行Linux的內(nèi)存為4 GB、處理器是Intel?CoreTM2 Quad CPU Q9400 @2.66 GHz×4的計(jì)算機(jī)上執(zhí)行。

3.1 合成數(shù)據(jù)及參數(shù)設(shè)置

合成數(shù)據(jù)是使用加性噪聲模型Y=f(X)+N生成的因果方向?yàn)閄→Y的數(shù)據(jù)，變量X分別從表1的分布中進(jìn)行采樣，函數(shù)f分別從表2的函數(shù)中選擇，N使用獨(dú)立生成的均勻分布噪聲{-t,…,t},其中t={1,2,…,7}。

表1 數(shù)據(jù)分布及參數(shù)設(shè)置

表2 函數(shù)及參數(shù)設(shè)置

3.2 準(zhǔn)確率

對X服從表1中不同分布、f取表2中不同函數(shù)的多種組合分別生成100組因果對，每組樣本量為500條。在圖1中，將ISLOPE算法在不同組合下的推斷準(zhǔn)確率與原算法SLOPE以及CISC、DC算法作對比。

圖1 不同分布不同函數(shù)下算法準(zhǔn)確率對比

如圖1(a)所示，當(dāng)生成模型遵循文獻(xiàn)[15]將結(jié)果變量映射為多分類數(shù)據(jù)時，算法ISLOPE和SLOPE與CISC算法的準(zhǔn)確率接近，且兩者在所有分布上均優(yōu)于DC算法。當(dāng)f為線性函數(shù)時，如圖1(b)所示，在多種分布類型下ISLOPE和SLOPE均優(yōu)于CISC和DC。當(dāng)f為非線性函數(shù)時，如圖1(c)所示，對比算法CISC及DC已經(jīng)不再適用，而ISLOPE和SLOPE依舊保持高準(zhǔn)確率且準(zhǔn)確率略有提升。當(dāng)f混合使用表2中的五種函數(shù)時，如圖1(d)所示，ISLOPE和SLOPE均優(yōu)于CISC和DC。在圖1所示的多種組合方式中，改進(jìn)算法ISLOPE近似保持原算法SLOPE的準(zhǔn)確率不變。

3.3 效 率

對X服從表1中偶數(shù)位置的不同分布、f取表2中第二和第三位置的線性及非線性函數(shù)的多種組合分別生成樣本量為500條的因果對。

在圖2中，將ISLOPE算法在不同組合下推斷一組數(shù)據(jù)對所需運(yùn)行時間與對比算法作比較。DC和CISC算法在多種情形下的運(yùn)行時間都很低，ISLOPE及SLOPE算法的運(yùn)行時間為數(shù)秒到數(shù)十秒不等，且改進(jìn)算法ISLOPE在每種情形下的運(yùn)行時間都低于原算法，約為原算法的50%。

圖2 不同分布不同函數(shù)下算法運(yùn)行時間對比

3.4 穩(wěn)定性

設(shè)置變量X服從均勻分布，函數(shù)取f(X)=aX。在分別生成100對樣本量為500i(i=1,2,…,10)條的合成數(shù)據(jù)集的情況下，將ISLOPE算法在不同樣本量下的準(zhǔn)確率情況與對比算法作比較，如圖3(a)所示，ISLOPE算法的準(zhǔn)確率均值約為65%，與SLOPE算法相同，高于其余對比算法。

在分別生成100i(i=1,2,…,10)組樣本量為500條的合成數(shù)據(jù)集的情況下，將本文算法在不同數(shù)據(jù)對數(shù)下的準(zhǔn)確率情況與對比算法作比較，如圖3(b)所示，ISLOPE算法的準(zhǔn)確率均值約為72%，與SLOPE算法相同，高于其余對比算法。從圖3中可知，四種算法在不同樣本量及不同數(shù)據(jù)對數(shù)下的準(zhǔn)確率都比較集中。

圖3 不同樣本量或不同數(shù)據(jù)對數(shù)下的算法性能對比

3.5 真實(shí)數(shù)據(jù)

真實(shí)數(shù)據(jù)采用95組已知因果方向的來自不同領(lǐng)域的觀測數(shù)據(jù)集[7]，每組樣本量為幾百到幾萬條不等，這些數(shù)據(jù)是對因果定向算法進(jìn)行測試的基準(zhǔn)數(shù)據(jù)。

由圖4可知，ISLOPE的準(zhǔn)確率與SLOPE算法保持一致，高于其余對比算法，且在全部數(shù)據(jù)集上的準(zhǔn)確率約74%，較CISC算法高出10%。ISLOPE及SLOPE算法在全部數(shù)據(jù)集上的運(yùn)行時間如表3所示，改進(jìn)算法的時間消耗約比原算法降低50%。

圖4 真實(shí)數(shù)據(jù)算法準(zhǔn)確率對比

表3 真實(shí)數(shù)據(jù)算法運(yùn)行時間對比

4 結(jié) 語

本文從探索和發(fā)現(xiàn)蘊(yùn)含在觀測數(shù)據(jù)間的因果關(guān)系這一角度出發(fā)，針對一對一因果關(guān)系的定向問題進(jìn)行研究。最近的科研結(jié)果表明基于全局和局部回歸的SLOPE算法在因果定向問題上表現(xiàn)出較好的性能。但模型冗余使得該算法在效率上存在一定的局限性。本文提出根據(jù)模型特征分別構(gòu)建全局和局部回歸模型的方法，該方法可以避免原算法中的冗余模型引起的時間消耗，降低算法的運(yùn)行時間，進(jìn)而提高原算法的效率。并在此方法的基礎(chǔ)上提出一個改進(jìn)的因果定向算法ISLOPE。實(shí)驗(yàn)部分對改進(jìn)算法進(jìn)行性能驗(yàn)證，結(jié)果顯示，所提出的算法能夠在保持原算法準(zhǔn)確率近似不變的前提下將運(yùn)行時間降低一半左右，且該算法的整體性能優(yōu)于其他兩種對比算法。

僅針對一對一因果關(guān)系的定向問題進(jìn)行研究仍然不足，為更深入地挖掘蘊(yùn)含在觀測數(shù)據(jù)間的因果關(guān)系，下一步研究工作將在多變量因果定向問題(如多對一、一對多、多對多)上進(jìn)行。