基于全局和局部回歸的因果定向改進算法

潘孟姣 蔡青松

(北京工商大學計算機與信息工程學院 北京 100048)

0 引 言

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

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

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

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

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

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

1 理論基礎

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

1.1 柯氏復雜度

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

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

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

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

(1)

1.2 MDL原理

MDL原理為柯氏復雜度的近似計算提供了合理的手段，它規(guī)避了柯氏復雜度的可計算性問題，將程序限制在可終止的且足以捕捉大部分規(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)計模型mo∈M將為數(shù)據(jù)X產(chǎn)生最小的描述長度。

1.3 加性噪聲模型

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

Y=f(X)+NN⊥X

(3)

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

對于變量X和Y，當X到Y符合一個ANM，但Y到X不符合時，稱X是Y的原因，Y是X的結果，即因果方向為X→Y。

2 因果定向方法及改進算法

2.1 模型及指標構建

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

(4)

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

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

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

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

(5)

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

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

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

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

(6)

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

變量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的總描述長度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ī)則

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

(1) 如果LX→Y

(2) 如果LX→Y>LY→X，則推斷出因果方向為Y→X。

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

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

2.3 算法描述

算法1改進型因果定向算法ISLOPE

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

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

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

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

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

步驟6輸出LX→Y。

3 實驗驗證

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

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

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

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

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

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

3.2 準確率

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

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

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

3.3 效 率

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

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

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

3.4 穩(wěn)定性

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

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

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

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

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

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

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

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

4 結 語

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

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