基于正則線性模型的馬爾科夫邊學習算法

嚴 曙 胡曉波 王儒敬

1(中國科學院合肥智能機械研究所 安徽 合肥 230031)2(中國科學技術大學 安徽 合肥 230026)

0 引 言

從觀察數(shù)據(jù)集中發(fā)現(xiàn)變量之間的因果關系是所有學科的基礎，如計算機科學、醫(yī)學、統(tǒng)計學、經(jīng)濟學和社會科學等[1-4]，并且這個因果關系已被廣泛接受用于替代隨機對照實驗的最佳方案[5-7]。原因是在大多數(shù)情況下，獲取觀察數(shù)據(jù)的實驗可能成本過高、不道德或是不可能的[8-10]。貝葉斯網(wǎng)絡作為一種有向無環(huán)圖模型[4]，可以有效地表示圖中所有變量間的因果關系。具體而言，對于網(wǎng)絡中目標節(jié)點T，該節(jié)點僅與其父子節(jié)點和配偶節(jié)點相關，而與其他節(jié)點無關。父子節(jié)點和配偶節(jié)點的集合稱為變量T的馬爾科夫邊(毯)，目標節(jié)點僅與馬爾科夫邊(毯)相關的性質被廣泛用于貝葉斯網(wǎng)絡結構學習和機器學習領域中的分類和預測。

從貝葉斯網(wǎng)絡發(fā)現(xiàn)馬爾科夫邊(毯)是件容易的事，然而，從數(shù)據(jù)集中構建貝葉斯網(wǎng)絡已被學者證明是NP難題[11]。因此，研究人員提出了各種馬爾科夫邊(毯)的學習算法。據(jù)不完全統(tǒng)計，1996年至2013年之間，就有多達17種代表性的算法問世。這些學習算法大致可分為兩類[12]：基于約束學習方法和基于評分學習方法。近五年來，又涌現(xiàn)出更多的馬爾科夫邊(毯)學習算法[13-17]。但主流算法仍是基于約束學習的方法，主要原因是馬爾科夫邊(毯)的概率和拓撲特征信息有助于定義有效學習的約束條件，但不能幫助建立局部和全局得分之間的關聯(lián)[12]。

近年來，基于正則線性模型(正則線性模型方法也屬于基于約束學習方法)的馬爾科夫邊(毯)學習方法也開始被相關文獻報道。如：文獻[18]使用BIC評分機制在構建貝葉斯網(wǎng)絡的過程中借助拉索模型提出一種馬爾科夫邊(毯)的發(fā)現(xiàn)方法(L1MB)，文獻[19]通過對嶺回歸模型的修改，提出了一個嶺回歸模型的變種模型MRRLM，探尋解釋變量與響應變量的關系，具有較大的理論意義。

但是，文獻[19]提出的MRRLM中引入了解釋變量的協(xié)方差，在變量共線的情況下導致MRRLM無法求解，一個直覺的想法是：嶺回歸模型能代替MRRLM用于馬爾科夫邊發(fā)現(xiàn)嗎？如果能，則上述問題迎刃而解; 如果不能，有替代的其他正則線性模型或變種模型嗎？為回答上述問題，本文為此展開工作，通過實證的方式研究MRRLM與嶺回歸模型、拉索模型和彈性網(wǎng)絡模型的馬爾科夫邊(毯)發(fā)現(xiàn)效率之間的關系，并嘗試提出一個經(jīng)驗性模型NVRRLM, 試圖探索其在數(shù)據(jù)集上的適用性規(guī)律。實驗中結合置換檢驗方法正則線性模型能顯著提高馬爾科夫邊的發(fā)現(xiàn)效率，但也帶來運算代價過高的問題。因此，本文僅在低維(維數(shù)小于100)數(shù)據(jù)集上比較不同模型之間的發(fā)現(xiàn)性能。

1 相關工作

1.1 馬爾科夫邊(毯)學習算法

1996年，兩位斯坦福大學的學者Koller和Sahami將馬爾科夫邊(毯)與特征選擇結合起來[20]，開創(chuàng)了馬爾科夫邊(毯)的研究新熱潮，之后涌現(xiàn)了大批的馬爾科夫邊(毯)的學習算法。但是主流學習算法主要集中在基于約束的方法，因此，此類學習方法所占篇幅較大。

基于約束的方法又可細分為二類[15]：基于條件獨立設計的算法(I類)和基于拓撲信息設計的算法(Ⅱ類)?；跅l件獨立設計的算法按照馬爾科夫邊(毯)的定義直接構建算法，因此，搜索策略簡單，時間效率高，但是樣本效率不佳。I類算法最早可追溯到K&S算法[20]和GSMB算法[21]，一些學者對GSMB算法進行優(yōu)化后，隨后相繼出現(xiàn)了IAMB[22]及其派生算法(如fast_IAMB,k_IAMB,λ_IAMB)[23-25]。但IAMB及其派生算法推導過程基本上繼承了GSMB算法增長、裁剪兩階段框架，難以根本上解決樣本低效的問題?；谕負湫畔⒌脑O計算法實際上是結合貝葉斯網(wǎng)絡的拓撲信息，將推導過程分解成推導父子節(jié)點和推導配偶節(jié)點兩個子過程，其學習效率相對I類較高，但更復雜的啟發(fā)式規(guī)則也帶來較高的時間成本問題。Ⅱ類算法典型代表是MMMB和HITON-MB算法[26-27]，隨后又出現(xiàn)了改進算法PCMB[24]和IPC-MB[28]，或結合I類的改進算法MBOR[29]算法和DOS算法[30]等。

基于評分的方法實際就是基于打分和搜索的策略。雖然基于評分的方法在貝葉斯網(wǎng)絡結構學習中應用非常普遍，但鮮有應用于馬爾科夫邊(毯)學習的報道。直到2013年才有文獻報道馬爾科夫邊(毯)學習兩個算法DMB和RPDMB[31]，據(jù)文中實驗報告顯示RPDMB算法相比PCMB算法有競爭性的準確率，但所需時間成本要多?？紤]到IPC-MB的時間效率比PCMB高，可以合理預測IPC-MB算法時間效率遠勝于RPDMB算法。即便如此，上述兩個算法仍不失一個重要的嘗試。

近年來，基于回歸模型的馬爾科夫邊(毯)學習方法也開始有文獻報道。相關工作雖不多，但為馬爾科夫邊(毯)學習方法提供了新的思路。文獻[18]使用BIC評分機制在構建貝葉斯網(wǎng)絡的過程中借助拉索模型提出一種馬爾可夫毯的發(fā)現(xiàn)方法(L1MB),但作者并沒有進一步給出理論證明。文獻[19]通過對嶺回歸模型進行修改，提出了正則線性模型MRRLM在滿足一定條件下尋找解釋變量與響應變量的關系，并從理論上回答了模型的非零解所對應的變量就是馬爾可夫邊(子集)。據(jù)其實驗結果報道，在基因數(shù)據(jù)集NOTCH1和RELA上該算法與最新的算法有競爭性的發(fā)現(xiàn)效率。

1.2 特征選擇與正則線性模型

特征選擇又稱變量選擇，是從特征集中選出最小特征子集(特征變量)滿足系統(tǒng)特定度量指標的最優(yōu)，在機器學習領域常用于提高分類器或回歸模型的預測數(shù)據(jù)的準確性以及數(shù)據(jù)生產(chǎn)過程的解釋能力。特征選擇有許多方法，而正則線性模型是其中一種重要的特征選擇方法。正則線性模型是在一般線性回歸模型的損失函數(shù)基礎上添加正則化項(或懲罰項)實現(xiàn)的。常見的正則線性模型有嶺回歸模型和LASSO模型，具體來說，正則化項為L1范數(shù)的稱為拉索模型(LASSO)，而正則化項為L2范數(shù)的稱為嶺回歸模型(RRLM)。通過調整懲罰系數(shù)，將參數(shù)系數(shù)壓縮至零或趨向于零，刪除掉與其對應的變量，達到變量選擇的目的，所以又稱系數(shù)壓縮法[32-33]。在上述兩類特征選擇方法的基礎上，后來相繼派生出一系列的算法模型，如群拉索、稀疏拉索和彈性網(wǎng)絡等[34-38]。

2 符號約定和背景知識

為了后續(xù)工作的展開，需要一些相關概念的定義和定理。本節(jié)內(nèi)容主要來源于文獻[19，40]。

2.1 符號約定

本文符號約定如表1所示。

表1 符號表示約定

續(xù)表1

2.2 馬爾科夫邊理論

定義1馬爾科夫邊(毯)：在隨機變量集(Y;X)上，目標變量Y和變量集M?X,如果滿足Y⊥XM|M,則M稱為變量Y的馬爾科夫毯，記為MB(Y)；如果對于?F?M,均不滿足Y⊥XM|M,，則M稱為變量Y的馬爾科夫邊。

定義2相交屬性：聯(lián)合概率分布為P的變量集X及其任何子集A、B、C和D，如果下式成立：A⊥B|(CD)及A⊥D|(C∪B)?A(BD)|C，則稱聯(lián)合概率分布P滿足相交屬性。

定理1[39]如果變量集X上的聯(lián)合概率分布P滿足相交屬性，則對于變量集中任何變量V均存在唯一的馬爾科夫邊。

定義3全局馬爾科夫條件：在有向圖G=〈H,E〉中，聯(lián)合概率分布P滿足全局馬爾科夫條件當且僅當H中任何不相交的子集A、B和C，如果給定C的情況下，A與Bd-分離，則有A⊥B|C。

定理2[39]有向圖G中，如果聯(lián)合概率分布P滿足全局馬爾科夫條件，則圖中目標節(jié)點Y的父節(jié)點、子節(jié)點及配偶節(jié)點構成馬爾科夫邊(毯)。

2.3 充分降維理論

定義4充分降維：對于條件概率分布為P的變量集(Y;X)，其中Y為一維行變量，X=(X1;X2;…;Xp)。如果存在降維矩陣η∈Rp×d(d≤p)，有Y⊥X|ηTX，則X的空間由p維降為d維。

定義5降維子空間：如果Y⊥X|ηTX成立，則η的列向量構成的子空間，稱為Y|X的降維子空間(DRS)，記S(η);如果SY|X是一個降維子空間并且S|Y|X?SDRS(SDRS為任意的DRS子空間)，則稱子空間S|Y|X是Y|X的中心降維子空間。

定理3[19]如果變量集(Y;X)的聯(lián)合概念分布P滿足線性相交屬性，則存在唯一的中心降維子空間SY|X。

下面介紹馬爾可夫邊理論與充分降維理論之間的關系。

假設M是聯(lián)合概率分布P的變量集X的馬爾科夫邊，PM為M的變量數(shù)量，降維矩陣η=(ηM;ηXM),其中，η∈Rp×d(d≤p)，矩陣ηM行數(shù)為pM，矩陣ηXM的行數(shù)為p-pM。有以下兩個定理：

定理4[19]如果變量集(Y;X)滿足線性相交屬性，則變量集(Y；M)存在中心降維子空間S(ηM),而且S(η)也是變量集(Y;X)的中心降維子空間，其中,ηXM為零矩陣。

2.4 特征變量與馬爾科夫邊

特征變量也稱預測向量，本節(jié)介紹預測向量與馬爾科夫邊(毯)之間的關系。

定理6[19,40]給定數(shù)據(jù)集D(樣本服從聯(lián)合分布P)上的變量(Y；X)，一個學習算法L和一個評估學習性能度量M，對于任何變量V?X:(1) 如果在預測Y時變量V使性能度量M最大或最小，則V是Y的最優(yōu)預測向量；(2) 如果不存在V的子集變量滿足Y的最優(yōu)預測向量，則V是Y的最小最優(yōu)預測向量；(3) 如果V是最小最優(yōu)的預測向量且基數(shù)最小，那么V是Y的最佳預測向量。

性能度量M的例子包括最大似然估計、負均方誤差等損失函數(shù)。

定理7[19,40]如果條件概率分布P(Y|X)可以準確估計，性能度量M能最優(yōu)化，并且算法L可以近似任意條件概率分布，則:(1)M是變量Y的一個馬爾科夫毯當且僅當M是Y的最優(yōu)預測向量；(2)M是變量Y的一個馬爾可夫邊當且僅當M是Y的最小最優(yōu)預測向量;(3)M是Y的最小基數(shù)的馬爾可夫邊當且僅當M是Y的最佳預測向量。

由定理7可知，如果只存在一個馬爾可夫邊，如相交屬性成立時，馬爾可夫邊是最小最優(yōu)的預測向量，反之亦然。如果存在多個馬爾可夫邊，則馬爾可夫邊且基數(shù)最小是最佳預測向量，反之亦然。

3 變種嶺回歸模型

本節(jié)在介紹變種嶺回歸模型之前，首先介紹數(shù)據(jù)集上變量共線與協(xié)方差矩陣奇異之間的關系。

3.1 變量共線與協(xié)方差矩陣奇異

對于設計矩陣X=(X1,X2,…,Xp),Xi∈Rn，i=1,2,…,p,變量共線即意味著存在不為零的向量k=(k1,k2,…,kp)T和常量C，使下式成立：

k1X1+k2X2+…+kpXp=C或kTX=C

容易得：Var(kTX)=kT∑Xk=Var(C)=0。

又因為∑X=VDVT，其中，V由協(xié)方差的特征向量組成，VVT=E(單位陣)，D是對角線元素為特征值對角陣，因此，當存在變量共線時至少存在一個λi=0，此時協(xié)方差矩陣為奇異陣，反之也然。

3.2 變種嶺回歸模型

線性回歸模型：Y=α+βTX+ε，其中：Y∈RK×n,X∈Rp×n,α∈RK×n，β∈Rp×K,ε～N(0,σ2I)。

定義7GJMW條件： (1) 全局馬爾科夫條件成立；(2) 聯(lián)合概率分布(Y;X)滿足線性相交屬性；(3) 設計矩陣X的協(xié)方差矩陣正定;(4) 當Y⊥X|ηTX時，E(X|ηTX)是ηTX的線性函數(shù)。

注：GJMW條件命名取四個條件的英文首字母。

3.2.1修改的嶺回歸模型(MRRLM)

修改的嶺回歸模型源于文獻[19]，該模型實際上是嶺回歸模型的一個變種。

定理8[19]如果GJMW條件成立，令K為α、β的維數(shù)，k∈[1,2,…,K],β為非零矩陣，并且α,β的估計值α*,β*使下式取得最小值:

arg minE{u(α+βTX,Y)}+λtr(βT∑Xβ)

(1)

在實際應用中，變量Y通常為一維變量即K=1，此時，對應的α、β也是一維變量。令β為非零向量且β=(∑X)-1/2γ，則式(1)等價于下列嶺回歸模型：

arg minE{u(α+γTZ,Y)}+λγTγZ=(∑X)-1/2X

(2)

上述定理給出了該模型的解與降維矩陣之間的關系，同時也給出了該模型只能發(fā)現(xiàn)馬爾科夫邊子集的原因。由定理4、定理5、定理7和定理8知：變量Y的馬爾科夫邊變量子集可以從β矩陣非零(行)系數(shù)選出。從式(2)可以看出，協(xié)方差矩陣是非奇異的。換句話說，對于變量共線的數(shù)據(jù)集，該模型理論上無法應用。

3.2.2新變種嶺回歸模型(NVRRLM)

由上節(jié)知，對于變量共線數(shù)據(jù)集，MRRLM理論上無法處理或實際應用效果不佳，本節(jié)提出一種新的變種嶺回歸模型(NVRRLM)試圖解決該問題。

如果GJMW成立，α、β為一維向量，且β≠0，并且α*,β*使下式取得最小值：

arg minE{u(α+βTX,Y)}+λtr(βT(∑X+δ2I)β)

(3)

則有S(β*)?S(η)。其中，S(η)是任意降維子空間，u為凸函數(shù)，δ為調控參數(shù)，λ>0為模型參數(shù)。

顯然新模型NVRRLM是在MRRLM的基礎上修改而得，此時協(xié)方差奇異并不影響模型的應用，因此，在滿足一定條件下，既可適用共線數(shù)據(jù)集，也可適用非共線數(shù)據(jù)集。

3.3 算法及分析

如算法1所示，X和Y為輸入數(shù)據(jù)集，其中X=(X1,X2,…,Xp)，Xi為n維行向量，Y為一維行向量;Ref_mb_num是指參考算法返回的馬爾科夫邊中的變量數(shù);NumPermute是置換檢驗中的重復計算數(shù)量;crp_mb是算法1返回的結果。算法1的第一行是正常嶺回歸模型的求解問題，有許多現(xiàn)有的工具和軟件可以求解。本文使用Glmnet工具包中的cvglmnet函數(shù)并且選擇10次交叉驗證來選擇模型參數(shù)λ和估計系數(shù)β0；第2行到第9行是使用置換檢驗[41]的方法計算p值；第10行是將p值從小到大排序得到的X變量的索引序列。第12行返回p值序列中前面Ref_mb_num個變量的索引集crp_mb。根據(jù)定理4、定理5、定理7和定理8,crp_mb為馬爾科夫邊的子集。

算法1正則線性模型馬爾科夫邊發(fā)現(xiàn)的通用算法

INPUT: X,Y,Ref_mb_num,NumPermute

OUTPUT: crp_mb

1: Calculate β0and λ with ridge regression(or LASSO etc)

2: Calculate the number of the column of XT:p;

3: Set the matrix mat_p(p,NumPermute),

4: For k=0 to NumPermute do

5: Random perm Y.

6: Calculate β with ridge regression(or LASSO etc)

7: Calculate mat_p(:k)=(abs(β)≥abs(β0))

8: End for

9: Calculate p_value:(sum(Mat_pT)+1)./(NumPermute+1)

10: Calculate index sequence of p_value_index from small to larger

11: Obtaining crp_mb: p_value_index(1:Ref_mb_num)

12: return crp_mb

在算法1基礎上增加了協(xié)方差運算和變量變換很容易寫出MRRLM的算法實現(xiàn)，具體實現(xiàn)算法如算法2所示。

算法2MRRLM馬爾科夫邊發(fā)現(xiàn)算法

INPUT: X,Y,Ref_mb_num,NumPermute

OUTPUT: crp_mb

1: Calculate covariance matrix: xCov

2: Data transformation: X=xCov-0.5X

3: Calculate γ0and λ with ridge regression

4: Calculate original β0=xCov-0.5γ0.

5: Calculate number of the row ofX: p

6: Set the matrix mat_p(p,NumPermute)

7: For k=0 to NumPermute do

8: Random perm Y

9: Calculate γ with ridge regression

10: Calculate original β=xCov-0.5γ

11: Calculate mat_p(:, k)=(abs(β) ≥abs(β0))

12: End for

13: Calculate p_value=(sum(Mat_pT) + 1)./(NumPermute+1)

14: Calculate index sequence of p_value_index from small to larger

15: Calculate crp_mb: p_value_index(1:Ref_mb_num)16: return crp_mb

新變種嶺回歸模型(NVRRLM)馬爾科夫發(fā)現(xiàn)算法與算法2基本上一致，只要按照式(3)修改協(xié)方差矩陣就可以了，此處不在贅述。

4 實驗模擬與分析

圍繞實驗目標，考慮置換檢驗運算成本太高及數(shù)據(jù)集的代表性，選擇數(shù)據(jù)集維數(shù)低于100來源于十個行業(yè)的標準數(shù)據(jù)集，借助工具軟件DAGlearn[18]產(chǎn)生10個連續(xù)數(shù)據(jù)集和10個二值離散數(shù)據(jù)集，數(shù)據(jù)樣本數(shù)分別是{300, 600, 900, 1 200, 1 500}，相當于100個數(shù)據(jù)集。其數(shù)據(jù)集屬性見表2，MB表示馬爾可夫邊。

表2 數(shù)據(jù)集及其屬性

4.1 實驗設計

從圖1和圖2可以看出，在連續(xù)數(shù)據(jù)集上IAMB算法整體發(fā)現(xiàn)性能和準確率最好，而在二值離散數(shù)據(jù)集上HITON-MB整體性能和準確率最好，因此，分別選取IAMB和HITON-MB作為正則性線性模型的參照算法。

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖1 傳統(tǒng)算法在數(shù)據(jù)集上平均F-Score

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖2 傳統(tǒng)算法在數(shù)據(jù)集上平均準確率

實驗設計如下：

(1) 選取合適的模型。依據(jù)實驗目標，分別選取MRRLM、嶺回歸模型、拉索模型和彈性網(wǎng)絡模型(參數(shù)α取值分別為{0.3,0.6,0.8})。

(2) 確定目標變量數(shù)?；谶\算成本考慮，采取隨機抽取若干目標節(jié)點的方法來評估數(shù)據(jù)集的發(fā)現(xiàn)效率。本實驗采用的規(guī)則是：如果數(shù)據(jù)集變量(維數(shù))數(shù)大于15，則隨機抽取15個目標節(jié)點，否則抽取所有數(shù)據(jù)集變量作為目標變量。

(3) 確定置換數(shù)和模型參數(shù)。置換檢驗方法中，理論上置換數(shù)越高，發(fā)現(xiàn)效率越準確，但同樣帶來時間效率的問題，本實驗置換數(shù)設定為199。同樣的原因，在置換檢驗方法重復計算估計參數(shù)時，正則線性模型的模型參數(shù)使用首次交叉驗證法所得的模型參數(shù)。

(4) 生成P值序列。當估計參數(shù)T分布存在時，先采用T分布計算P值，再用置換檢驗方法計算P值，目的是考察兩種P值計算方法對于發(fā)現(xiàn)效率的影響；當估計參數(shù)T分布不存在時，則采用置換檢驗方法計算P值。

(5) 確定模型評價指標。常用的評價指標有準確率(Precision)、召回率(Recall)以及兩者加權調和平均(F-Score)。本實驗僅考察模型的準確率、F-Score和運行時間。F-Score計算公式為：F-Score=2×precision×recall/(precision+recall)。

顯然，F(xiàn)-Score數(shù)值越大，發(fā)現(xiàn)效率越好。由于部分數(shù)據(jù)集上真實馬爾可夫邊的個數(shù)為零，影響相關評價指標的計算，因此，約定如表3所示。

表3 評價指標約定

表3所述的“返回MB數(shù)”是模型返回的MB中變量數(shù)量，“真實MB數(shù)”為數(shù)據(jù)集上已知真實的MB中變量數(shù)量，未知的數(shù)據(jù)集MB長度可事先估計給定。本實驗輸出結果還包括運算時間。

完成上述過程，將10個二值離散數(shù)據(jù)集上的馬爾科夫邊發(fā)現(xiàn)效率匯總平均后，作為低維二值離散數(shù)據(jù)集上各模型的馬爾科夫邊發(fā)現(xiàn)效率。同樣，將10個連續(xù)數(shù)據(jù)集上的馬爾科夫邊發(fā)現(xiàn)效率匯總平均后，作為低維連續(xù)數(shù)據(jù)集上各模型的馬爾科夫邊發(fā)現(xiàn)效率。

4.2 結果分析

4.2.1MRRLM(-P)與RRLM(-P)比較

MRRLM(-P)與RRLM(-P)的比較結果如圖3-圖5所示。

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖3 MRRLM(-P)與RRLM(-P)之F-Scroe關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖4 MRRLM(-P)與RRLM(-P)之準確率關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖5 MRRLM(-P)與RRLM(-P)之運行時間關系圖

由圖3-圖5可以看出，在二值離散數(shù)據(jù)集上，除了運算時間有差別外， 從準確率和總體性能(F-Score)來看，MRRLM(或MRRLM-P)與RRLM (或RRLM-P)馬爾科夫邊(子集)的發(fā)現(xiàn)效率基本相近；而在連續(xù)數(shù)據(jù)集上， MRRLM馬爾科夫邊(子集)的發(fā)現(xiàn)效率則遠遠高于嶺回歸模型。從圖中還可看出，兩種回歸模型采用置換檢驗后，各自的發(fā)現(xiàn)效率均有了顯著提高。如在連續(xù)數(shù)據(jù)集上，采用T分布方法的MRRLM的F-Score值在0.5以下，而采用置換檢驗方法的MRRLM-P的F-Score數(shù)值快速提升至0.9以上，表明置換檢驗對模型發(fā)現(xiàn)效率有著重要作用。從運算時間來看，MRRLM和RRLM的運算時間均很小并且很相近，結合置換檢驗后，MRRLM-P和RRLM-P的運算時間明顯增加，并且隨著樣本數(shù)的增加運算時間也逐漸增加。

4.2.2正則線性模型與傳統(tǒng)算法比較

正則線性模型與傳統(tǒng)算法的比較結果如圖6-圖8所示。

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖6 正則化算法與傳統(tǒng)算法之F-Score關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖7 正則化算法與傳統(tǒng)算法之準確率關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖8 正則化算法與傳統(tǒng)算法之運行時間關系圖

由于拉索模型估計參數(shù)的T分布，因此本次僅局限于結合置換檢驗的圖中所示正則線性模型。由圖6-圖7可以看出，在連續(xù)數(shù)據(jù)集中傳統(tǒng)算法IAMB無論在準確率還是總整性能(F-Score)方面，其馬爾科夫邊的發(fā)現(xiàn)效率均高于正則線性模型。例如在連續(xù)數(shù)據(jù)集上，傳統(tǒng)算法IAMB的準確率在97%以上，召回率在95%以上。結合置換檢驗的MRRLM-P和LASSA-P的準確率在96%以上，召回率在93%以上，均略低于傳統(tǒng)算法IAMB的發(fā)現(xiàn)效率；而結合置換檢驗方法RRLM的準確率在80%～85%之間，召回率74%～83%之間，也遠低于傳統(tǒng)算法IAMB。而在二值離散數(shù)據(jù)集上，圖中所示的幾種算法的評價指標基本相近，但HITON算法發(fā)現(xiàn)效率略高于正則線性模型。兩類數(shù)據(jù)集上總體發(fā)現(xiàn)效率均隨著樣本數(shù)增加而增加。從圖8中的運行時間來看，傳統(tǒng)算法用時最少，而正則線性模型算法普遍用時過長，并且連續(xù)數(shù)據(jù)集上的運行時普遍高于二值離散數(shù)據(jù)集。但在低維數(shù)據(jù)集上正則線性模型的運行時間還在可接受的范圍之內(nèi)。

4.2.3不同參數(shù)的彈性網(wǎng)絡模型間比較

不同參數(shù)的彈性網(wǎng)絡模型之間的比較結果如圖9-圖11所示。

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖9 不同參數(shù)彈性網(wǎng)絡模型之F-Score關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖10 不同參數(shù)彈性網(wǎng)絡模型之準確率關系圖

注：實線代表連續(xù)數(shù)據(jù)集，虛線代表二值離散數(shù)據(jù)集圖11 不同參數(shù)彈性網(wǎng)絡模型之運行時間關系圖

由于彈性網(wǎng)絡模型(參數(shù)等于0除外)不存在T分布，因此，只考察采用置換檢驗方法的彈性網(wǎng)格模型。由圖9、圖10可以看出，從準確率和整體性能來說，不同參數(shù){0,0.3,0.6,0.8,1}對應的彈性網(wǎng)絡模型在二值離散數(shù)據(jù)集上形成一束走勢基本相同的曲線族，說明彈性網(wǎng)絡模型的發(fā)現(xiàn)效率基本相近；而在連續(xù)數(shù)據(jù)集上，參數(shù)等于0即為嶺回歸模型時除外，其他彈性網(wǎng)絡模型與二值離散數(shù)據(jù)集上也有類似的結論。從圖中還可看出連續(xù)數(shù)據(jù)集上，相同參數(shù)的彈性網(wǎng)絡模型的總體發(fā)現(xiàn)效率高于二值離散數(shù)據(jù)集上的發(fā)現(xiàn)效率，說明連續(xù)數(shù)據(jù)集更適合使用彈性網(wǎng)絡模型發(fā)現(xiàn)馬爾科夫邊(毯)。從運算時間上來看，連續(xù)數(shù)據(jù)集上彈性網(wǎng)絡模型運算成本比二值離散數(shù)據(jù)集更高，說明發(fā)現(xiàn)效率的提高是以犧牲時間效率為代價的。所有的模型的運算時間整體上均隨著樣本數(shù)的增加而呈逐漸上升，這與人們的認識保持一致。

4.2.4NVRRLM與MRRLM比較

為驗證新模型NVRRLM在數(shù)據(jù)集上的馬爾可夫毯的發(fā)現(xiàn)能力，選取四個變量共線離散數(shù)據(jù)集和對照的四個變量非共線離散數(shù)據(jù)集。數(shù)據(jù)集對應用數(shù)據(jù)源文件如表4所示，數(shù)據(jù)集上模型的評價指標結果如表5所示。

表4 數(shù)據(jù)源文件名和NVRRLM調控參數(shù)

表5 兩組數(shù)據(jù)集上NVRRLM與MRRLM比較

從表5可以看出，雖然理論上MRRLM無法應用變量共線的數(shù)據(jù)集，但在實際應用時僅是發(fā)現(xiàn)效率降低。原因在于數(shù)值“0”在計算機數(shù)值存儲時與定義的小數(shù)位多少有關，通常當數(shù)值小于10-12時，該數(shù)值為零。但此時馬爾科夫邊的發(fā)現(xiàn)效率隨著協(xié)立差矩陣接近零程度不同而不同程度下降。NVRRLM的發(fā)現(xiàn)效率普遍高于MRRLM，而且有些數(shù)據(jù)集上發(fā)現(xiàn)效率提高很明顯。如在Gene數(shù)據(jù)集上，F(xiàn)-Scroe從0.131 0能提高到0.481 2。在變量非共線數(shù)據(jù)集上，兩者模型的發(fā)現(xiàn)效率基本相等。因此，作者大膽推測NVRRLM完全可以代替MRRLM用于變量共線數(shù)據(jù)集上馬爾科夫邊的發(fā)現(xiàn)，同時也可適用于變量非共線數(shù)據(jù)集。

5 結 語

本文通過實驗的方式求證的MRRLM與RRLM的馬爾科夫邊(毯)發(fā)現(xiàn)效率之間的關系，并參照傳統(tǒng)算法，考察拉索模型以及彈性網(wǎng)絡不同參數(shù)模型間的馬爾科夫邊(毯)的發(fā)現(xiàn)效率。實驗結果表明：在低維二值離散數(shù)據(jù)集上，嶺回歸模型、拉索模型和彈性網(wǎng)絡模型與MRRLM有著相近的馬爾科夫邊(毯)的發(fā)現(xiàn)效率，因此，嶺回歸模型、拉索模型和彈性網(wǎng)絡模型完全可以替代MRRLM用于馬爾科夫邊(毯)發(fā)現(xiàn)，解決了MRRLM由于協(xié)方差奇異而無法求解問題；而在低維連續(xù)數(shù)據(jù)集上，結合置換檢驗方法的拉索模型和彈性網(wǎng)絡模型(參數(shù)為零除外)的發(fā)現(xiàn)效率與MRRLM基本相近，并逼近傳統(tǒng)算法的發(fā)現(xiàn)效率，完全可以替代MRRLM用于馬爾科夫邊(毯)發(fā)現(xiàn)，解決了變量共線數(shù)據(jù)集求解問題，但結合置換檢驗方法的RRLM馬爾科夫邊(毯)發(fā)現(xiàn)效率最低，遠低于結合置換檢驗方法的MRRLM。此外，實驗結果顯示本文新提出的經(jīng)驗模型NVRRLM完全可代替MRRLM適用于變量共線數(shù)據(jù)集和變量非共線數(shù)據(jù)集上馬爾科夫邊(毯)的發(fā)現(xiàn)。

結合置換檢驗統(tǒng)計方法的正則線性模型，雖然解決了解釋變量協(xié)方差矩陣的奇異問題或者變量共線問題， 但是也存在一些缺陷。首先，置換檢驗方法適用于分布未知的小樣本數(shù)據(jù)，對大樣本或高維數(shù)據(jù)由于所需時間太長，而失去應用價值；其次，用于發(fā)現(xiàn)馬爾科夫邊的正則線性模型需要事先指定馬爾科夫邊(毯)期望值，與早期的K&S相似；再次，正則線性模型僅在某些數(shù)據(jù)集發(fā)現(xiàn)性能與當前最優(yōu)的算法有竟爭性，從實驗結果來看，均低于當前最優(yōu)算法，因此，迫切需要提出該模型的發(fā)現(xiàn)性能。同時，P值的不同求解方法，對提高模型的發(fā)現(xiàn)效率有著顯著的影響，如何構造高效的P值計算方法是提高馬爾科夫邊(毯)發(fā)現(xiàn)效率的關鍵，也是下一步需要努力的方向。