嚴 曙 胡曉波 王儒敬

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

0 引 言

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

2 符號約定和背景知識

為了后續(xù)工作的展開，需要一些相關概念的定義和定理。本節(jié)內容主要來源于文獻[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相交屬性：聯合概率分布為P的變量集X及其任何子集A、B、C和D，如果下式成立：A⊥B|(CD)及A⊥D|(C∪B)?A(BD)|C，則稱聯合概率分布P滿足相交屬性。

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

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

定理2[39]有向圖G中，如果聯合概率分布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)的聯合概念分布P滿足線性相交屬性，則存在唯一的中心降維子空間SY|X。

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

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

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

2.4 特征變量與馬爾科夫邊

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

定理6[19,40]給定數據集D(樣本服從聯合分布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)的預測向量且基數最小，那么V是Y的最佳預測向量。

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

定理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的最小基數的馬爾可夫邊當且僅當M是Y的最佳預測向量。

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

3 變種嶺回歸模型

本節(jié)在介紹變種嶺回歸模型之前，首先介紹數據集上變量共線與協(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) 聯合概率分布(Y;X)滿足線性相交屬性；(3) 設計矩陣X的協(xié)方差矩陣正定;(4) 當Y⊥X|ηTX時，E(X|ηTX)是ηTX的線性函數。

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

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

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

定理8[19]如果GJMW條件成立，令K為α、β的維數，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ā)現馬爾科夫邊子集的原因。由定理4、定理5、定理7和定理8知：變量Y的馬爾科夫邊變量子集可以從β矩陣非零(行)系數選出。從式(2)可以看出，協(xié)方差矩陣是非奇異的。換句話說，對于變量共線的數據集，該模型理論上無法應用。

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

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

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

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

(3)

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

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

3.3 算法及分析

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

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

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的算法實現，具體實現算法如算法2所示。

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

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ā)現算法與算法2基本上一致，只要按照式(3)修改協(xié)方差矩陣就可以了，此處不在贅述。

4 實驗模擬與分析

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

表2 數據集及其屬性

4.1 實驗設計

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

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

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

實驗設計如下：

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

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

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

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

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

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

表3 評價指標約定

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

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

4.2 結果分析

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

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

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

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

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

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

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

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

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

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

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

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

4.2.3不同參數的彈性網絡模型間比較

不同參數的彈性網絡模型之間的比較結果如圖9-圖11所示。

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

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

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

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

4.2.4NVRRLM與MRRLM比較

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

表4 數據源文件名和NVRRLM調控參數

表5 兩組數據集上NVRRLM與MRRLM比較

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

5 結 語

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

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