嚴(yán) 曙 胡曉波 王儒敬

1(中國(guó)科學(xué)院合肥智能機(jī)械研究所 安徽 合肥 230031)2(中國(guó)科學(xué)技術(shù)大學(xué) 安徽 合肥 230026)

0 引 言

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

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

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

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

1 相關(guān)工作

1.1 馬爾科夫邊(毯)學(xué)習(xí)算法

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

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

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

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

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

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

2 符號(hào)約定和背景知識(shí)

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

2.1 符號(hào)約定

本文符號(hào)約定如表1所示。

表1 符號(hào)表示約定

續(xù)表1

2.2 馬爾科夫邊理論

定義1馬爾科夫邊(毯)：在隨機(jī)變量集(Y;X)上，目標(biāo)變量Y和變量集M?X,如果滿足Y⊥XM|M,則M稱為變量Y的馬爾科夫毯，記為MB(Y)；如果對(duì)于?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滿足相交屬性，則對(duì)于變量集中任何變量V均存在唯一的馬爾科夫邊。

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

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

2.3 充分降維理論

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

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

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

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

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

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

2.4 特征變量與馬爾科夫邊

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

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

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

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

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

3 變種嶺回歸模型

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

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

對(duì)于設(shè)計(jì)矩陣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。

又因?yàn)椤芚=VDVT，其中，V由協(xié)方差的特征向量組成，VVT=E(單位陣)，D是對(duì)角線元素為特征值對(duì)角陣，因此，當(dāng)存在變量共線時(shí)至少存在一個(gè)λi=0，此時(shí)協(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) 設(shè)計(jì)矩陣X的協(xié)方差矩陣正定;(4) 當(dāng)Y⊥X|ηTX時(shí)，E(X|ηTX)是ηTX的線性函數(shù)。

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

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

修改的嶺回歸模型源于文獻(xiàn)[19]，該模型實(shí)際上是嶺回歸模型的一個(gè)變種。

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

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

(1)

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

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

(2)

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

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

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

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

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

(3)

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

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

3.3 算法及分析

如算法1所示，X和Y為輸入數(shù)據(jù)集，其中X=(X1,X2,…,Xp)，Xi為n維行向量，Y為一維行向量;Ref_mb_num是指參考算法返回的馬爾科夫邊中的變量數(shù);NumPermute是置換檢驗(yàn)中的重復(fù)計(jì)算數(shù)量;crp_mb是算法1返回的結(jié)果。算法1的第一行是正常嶺回歸模型的求解問題，有許多現(xiàn)有的工具和軟件可以求解。本文使用Glmnet工具包中的cvglmnet函數(shù)并且選擇10次交叉驗(yàn)證來選擇模型參數(shù)λ和估計(jì)系數(shù)β0；第2行到第9行是使用置換檢驗(yàn)[41]的方法計(jì)算p值；第10行是將p值從小到大排序得到的X變量的索引序列。第12行返回p值序列中前面Ref_mb_num個(gè)變量的索引集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基礎(chǔ)上增加了協(xié)方差運(yùn)算和變量變換很容易寫出MRRLM的算法實(shí)現(xiàn)，具體實(shí)現(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í)驗(yàn)?zāi)M與分析

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

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

實(shí)驗(yàn)設(shè)計(jì)如下：

(1) 選取合適的模型。依據(jù)實(shí)驗(yàn)?zāi)繕?biāo)，分別選取MRRLM、嶺回歸模型、拉索模型和彈性網(wǎng)絡(luò)模型(參數(shù)α取值分別為{0.3,0.6,0.8})。

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

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

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

(5) 確定模型評(píng)價(jià)指標(biāo)。常用的評(píng)價(jià)指標(biāo)有準(zhǔn)確率(Precision)、召回率(Recall)以及兩者加權(quán)調(diào)和平均(F-Score)。本實(shí)驗(yàn)僅考察模型的準(zhǔn)確率、F-Score和運(yùn)行時(shí)間。F-Score計(jì)算公式為：F-Score=2×precision×recall/(precision+recall)。

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

表3 評(píng)價(jià)指標(biāo)約定

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

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

4.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.4NVRRLM與MRRLM比較

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

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

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

從表5可以看出，雖然理論上MRRLM無法應(yīng)用變量共線的數(shù)據(jù)集，但在實(shí)際應(yīng)用時(shí)僅是發(fā)現(xiàn)效率降低。原因在于數(shù)值“0”在計(jì)算機(jī)數(shù)值存儲(chǔ)時(shí)與定義的小數(shù)位多少有關(guān)，通常當(dāng)數(shù)值小于10-12時(shí)，該數(shù)值為零。但此時(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)效率基本相等。因此，作者大膽推測(cè)NVRRLM完全可以代替MRRLM用于變量共線數(shù)據(jù)集上馬爾科夫邊的發(fā)現(xiàn)，同時(shí)也可適用于變量非共線數(shù)據(jù)集。

5 結(jié) 語

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

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