多重高斯有向圖模型結(jié)構(gòu)學(xué)習(xí)

王 琦 趙 強(qiáng)

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，250358，濟(jì)南 )

1 引 言

當(dāng)圖模型中節(jié)點(diǎn)表示高斯隨機(jī)變量的時(shí)候，隨機(jī)變量之間的條件獨(dú)立性可以通過高斯隨機(jī)變量的逆協(xié)方差陣中的零元素反映.因此，估計(jì)高斯無向圖等價(jià)于估計(jì)隨機(jī)變量的逆協(xié)方差陣.近年來，已經(jīng)有大量的算法相繼被提出用于估計(jì)高斯無向圖.Meinshausen[1]通過節(jié)點(diǎn)之間的相關(guān)性建立回歸模型，考慮到節(jié)點(diǎn)關(guān)系的稀疏性，使用 Lasso 懲罰項(xiàng)估計(jì)稀疏的逆協(xié)方差陣并證明了該算法在一定條件下的高恢復(fù)率.在文獻(xiàn)[2]、[3]和[4]中，根據(jù)逆協(xié)方差陣的極大似然估計(jì)模型，在不同的數(shù)據(jù)背景下基于不同的懲罰項(xiàng)估計(jì)逆協(xié)方差陣，在數(shù)值模擬和真實(shí)數(shù)據(jù)兩種情況下均取得了較好的效果.在大數(shù)據(jù)時(shí)代，某些時(shí)候需要對多個(gè)高斯無向圖進(jìn)行聯(lián)合估計(jì).Guo[5]等提出了一種帶有階級化懲罰項(xiàng)的極大似然估計(jì)模型，該懲罰項(xiàng)的作用是為了使得多重圖中具有相關(guān)性的節(jié)點(diǎn)同時(shí)展現(xiàn)出有邊或者無邊的性質(zhì)，從而降低了算法的可行解空間.Zhu[6]、Danaher[7]和Ma[8]等人針對高斯多重圖模型的聯(lián)合估計(jì)提出了不同的懲罰項(xiàng)，比如:group Lasso，fused Lasso 等等.

當(dāng)一個(gè)貝葉斯網(wǎng)絡(luò)中的隨機(jī)變量具有自然偏序先驗(yàn)的時(shí)候，估計(jì)貝葉斯網(wǎng)絡(luò)就轉(zhuǎn)換為估計(jì)貝葉斯網(wǎng)絡(luò)的框架.這也就極大地降低了估計(jì)貝葉斯網(wǎng)絡(luò)的復(fù)雜度.對于帶有偏序先驗(yàn)的高斯有向圖模型, 文獻(xiàn)[9]中，通過建立帶有 Lasso 約束項(xiàng)的優(yōu)化模型求解鄰接矩陣從而用于估計(jì)高斯有向圖.Yuan[10]等人建立多重高斯有向圖的極大似然估計(jì)模型，通過 DC 算法和增廣拉格朗日算法估計(jì)多重高斯有向圖.

估計(jì)多重高斯圖的時(shí)候，不同高斯圖之間往往具有相似性結(jié)構(gòu).充分利用不同圖節(jié)點(diǎn)之間的相關(guān)性，能夠降低優(yōu)化問題的病態(tài)程度.因此，假設(shè)K重高斯有向圖之間具有相似性結(jié)構(gòu)，每一個(gè)高斯有向圖有p個(gè)節(jié)點(diǎn)，每一個(gè)圖分別有nk,k=1,...K次觀測，在自然偏序先驗(yàn)條件下，本文建立了帶有組相似性結(jié)構(gòu)的極大似然估計(jì)模型，充分利用組相似性結(jié)構(gòu)的先驗(yàn)信息構(gòu)建懲罰函數(shù)，從而降低了高維數(shù)據(jù)中的解的可行空間，本文利用坐標(biāo)下降方法求解該優(yōu)化模型并得到了較好的高斯有向圖估計(jì).該算法的時(shí)間復(fù)雜度為O(max(nk)Kp2).數(shù)值實(shí)驗(yàn)展示了該算法估計(jì)多重高斯有向圖的有效性.本文能充分利用圖之間的相關(guān)性，聯(lián)合估計(jì)出更加精確的高斯有向圖模型結(jié)構(gòu).

本文的結(jié)構(gòu)如下，第二節(jié)將介紹基本知識和帶有自然偏序的隱變量模型，第三節(jié)將介紹高斯有向圖模型和本文的算法，第四節(jié)為數(shù)值實(shí)驗(yàn)，最后是總結(jié)與展望.

2 基本概念和基礎(chǔ)知識

2.1基礎(chǔ)知識考慮一個(gè)圖模型G=(V,E),其中V為圖中節(jié)點(diǎn)，節(jié)點(diǎn)個(gè)數(shù)為p.E?V×V,為圖中節(jié)點(diǎn)的邊集.每一個(gè)節(jié)點(diǎn)都代表了一個(gè)隨機(jī)變量X1,…，Xp，Xi和Xj是否有邊代表兩個(gè)節(jié)點(diǎn)是否有聯(lián)系.有向邊指的是如果(i,j)∈E, 那么(j,i)?E.而無向邊指的是如果(i,j)∈E,那么(j,i)∈E.對于有向圖或無向圖，如果在圖模型中不能形成回路，則該圖模型稱為無環(huán)圖.本文所討論的圖均為無環(huán)圖.在圖模型中,Pai指的是節(jié)點(diǎn)i的父節(jié)點(diǎn)所組成的集合，如果j∈Pai,記作j→i.有向圖的框架指的是將有向圖中的有向邊換為無向邊.通常用鄰接矩陣A∈Rp×p表示邊集E的條件相關(guān)性, 如果Aij=0, 則意味著Xi和Xj條件獨(dú)立.

2.2自然偏序的隱變量模型在貝葉斯網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)具有自然偏序，即邊的方向只能由序號低的節(jié)點(diǎn)Xi指向序號高的節(jié)點(diǎn)Xj(i>j). 此時(shí)，對于隨機(jī)變量的因果推斷通常用結(jié)構(gòu)等式模型進(jìn)行說明[11]:

Xi=fi(Pai,Zi)，i=1,…，p，

(1)

其中，Zi為Xi的隱變量.為了建立節(jié)點(diǎn)Xi之間的聯(lián)系，本文討論fi是一個(gè)線性函數(shù)，從而得到下列等式：

(2)

其中，ρij表示的是Xj節(jié)點(diǎn)和Xi節(jié)點(diǎn)的相關(guān)系數(shù).當(dāng)Xi,i=1,...,p服從高斯正態(tài)分布的時(shí)候，(1)和(2)等價(jià)[11].(2)式可以寫成矩陣向量形式，X=ΛZ,其中Λ為影響矩陣，X∈Rp,Z∈Rn.舉個(gè)例子，考慮圖1中的高斯有向圖，其影響矩陣Λ∈Rp×p,如(3)式所示.

(3)

圖1 有向圖

3 高斯有向圖模型

3.1帶懲罰項(xiàng)的高斯有向圖考慮數(shù)據(jù)矩陣∈Rn×p是由(2)中的隱變量模型所生成的，不失一般性，假設(shè)Xi～N(0,1),Ω=Σ-1為逆協(xié)方差陣，對于Ω的極大似然估計(jì)表示如下[1]:

(4)

(5)

3.2多重高斯有向圖估計(jì)假設(shè)有K個(gè)高斯有向圖，從每個(gè)圖中得到一個(gè)觀測數(shù)據(jù)k∈Rp×nk,k=1,...,K，因此，依據(jù)(5)式，針對K個(gè)圖的聯(lián)合估計(jì)可以表達(dá)為:

(6)

對每一個(gè)K分別求取鄰接矩陣Ak，從而可以估計(jì)出K個(gè)高斯有向圖.考慮到在實(shí)際中，這些圖之間會有已知的相似性結(jié)構(gòu)，在優(yōu)化函數(shù)中加入相似性結(jié)構(gòu)的約束進(jìn)行聯(lián)合估計(jì)能夠提高估計(jì)的準(zhǔn)確度.優(yōu)化模型如(7)，所示:

(7)

(8)

圖2 四個(gè)高斯無向圖的鄰接矩陣

(9)

表1 算法1：多重高斯有向圖聯(lián)合估計(jì)

在實(shí)驗(yàn)中，需要對參數(shù)λijs進(jìn)行估計(jì).有兩種方法可以對λijs進(jìn)行估計(jì).第一，根據(jù)已知的先驗(yàn)信息，對每一個(gè)三元組(i,j,s)選擇特定的參數(shù)λijs.第二，對所有的λijs選取同一個(gè)λ作為參數(shù). 在數(shù)值實(shí)驗(yàn)中，本文主要按照第二種方式進(jìn)行參數(shù)選擇.相比于CV方法和AIC方法，使用BIC方法進(jìn)行參數(shù)選擇在本數(shù)值實(shí)驗(yàn)中會有較好的效果.

4 數(shù)值實(shí)驗(yàn)

本節(jié)將通過數(shù)值實(shí)驗(yàn)驗(yàn)證算法1在估計(jì)多重高斯有向圖的有效性.數(shù)值實(shí)驗(yàn)中有兩個(gè)高斯有向圖，每一個(gè)圖中均有50個(gè)節(jié)點(diǎn).高斯有向圖的生成方法：首先建立一個(gè)相似性結(jié)構(gòu)(圖3)，即以0.009的概率在一個(gè)50×50的無邊圖上按照偏序先驗(yàn)進(jìn)行加邊.然后，對這個(gè)相似性結(jié)構(gòu)分別隨機(jī)地加邊，最終使得加邊得到的兩個(gè)圖的邊的數(shù)量約為61.

根據(jù)生成圖的鄰接矩陣，按照文獻(xiàn)[12]引理2.1中等式就可以計(jì)算得到兩個(gè)高斯有向圖的協(xié)方差陣.根據(jù)高斯有向圖的均值和協(xié)方差陣，對兩個(gè)圖分別生成5 000個(gè)觀測值.利用算法就可以得到兩個(gè)高斯有向圖的估計(jì).本實(shí)驗(yàn)也同樣使用PC算法作為對比,結(jié)果如圖3所示.

分別計(jì)算兩種算法的FPR,FNR,CZ三種指標(biāo).這三種指標(biāo)的定義為：

圖3 實(shí)驗(yàn)結(jié)果

從圖3可以看到,較PC算法，本文算法所估計(jì)出的有向邊明顯更多.另外從兩種算法的恢復(fù)情況(表2)，可以看到，本文算法1的FPR較PC算法較高，這也意味著本文算法1估計(jì)出了多余的信息，但是本文算法1的FNR較低，這也說明了本文算法1能將原有向圖中的信息盡可能的估計(jì)出來，從而為下一步分析奠定了基礎(chǔ).綜上實(shí)驗(yàn)，可以說明本文提出的算法1能夠較好地聯(lián)合估計(jì)多重高斯有向圖.

表2 恢復(fù)情況

5 結(jié) 論

本文主要針對多重高斯有向圖進(jìn)行聯(lián)合估計(jì).在具有自然偏序的條件下，當(dāng)節(jié)點(diǎn)滿足隱變量模型的時(shí)候，根據(jù)極大似然估計(jì)構(gòu)建回歸模型，通過坐標(biāo)下降聯(lián)合估計(jì)圖的鄰接矩陣.數(shù)值實(shí)驗(yàn)證明了該方法能夠較高效地聯(lián)合估計(jì)高斯有向圖.