一種可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

綦小龍 高 陽 王 皓 宋 蓓 周春蕾 張友衛(wèi)

1(南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 南京 210046)2(伊犁師范學(xué)院電子與信息工程學(xué)院 新疆伊寧 835000)3 (江蘇方天電力技術(shù)有限公司 南京 211102) (qxl_0712@sina.com)

貝葉斯網(wǎng)絡(luò)是個(gè)有向無圈圖，圖中節(jié)點(diǎn)表示隨機(jī)變量，節(jié)點(diǎn)間的弧表示變量之間的直接依賴關(guān)系.每個(gè)節(jié)點(diǎn)都擁有一個(gè)概率分布，根節(jié)點(diǎn)所附的是它的邊緣分布，而非根節(jié)點(diǎn)所附的是條件概率分布[1].

近幾十年來，從數(shù)據(jù)中自動(dòng)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)受到研究者的普遍關(guān)注[2-7].一般來說，目前有2類結(jié)構(gòu)學(xué)習(xí)方式[2,8]:1)基于約束的結(jié)構(gòu)學(xué)習(xí).該方法根據(jù)整體Markov性，使用統(tǒng)計(jì)假設(shè)檢驗(yàn)對(duì)數(shù)據(jù)中的條件依賴和條件獨(dú)立性關(guān)系進(jìn)行檢驗(yàn)，找到對(duì)依賴和獨(dú)立關(guān)系最好解釋的某個(gè)結(jié)構(gòu)[9-10].2)基于優(yōu)化的結(jié)構(gòu)學(xué)習(xí).該方式定義了測(cè)量模型對(duì)觀測(cè)數(shù)據(jù)擬合程度的評(píng)分函數(shù)，如貝葉斯評(píng)分和最小描述長度(minimum description length, MDL)評(píng)分[2].結(jié)構(gòu)學(xué)習(xí)的任務(wù)是找到一個(gè)最大化該評(píng)分函數(shù)的結(jié)構(gòu).這2種方法有各自的優(yōu)缺點(diǎn)：基于約束的方式是有效的，但是它對(duì)個(gè)體獨(dú)立性檢驗(yàn)中的失敗敏感[8-9]；基于優(yōu)化的方法每次都考慮整個(gè)網(wǎng)絡(luò)，因此對(duì)于個(gè)體錯(cuò)誤并不敏感，但是搜索的結(jié)構(gòu)空間包含超指數(shù)個(gè)結(jié)構(gòu).一般來說，該問題是NP-hard問題[8,11].

針對(duì)上述2種方法的主要挑戰(zhàn)，學(xué)者們做了大量的研究.對(duì)于基于搜索-評(píng)分的學(xué)習(xí)方法，根據(jù)尋找到的解是全局最優(yōu)還是局部最優(yōu)提出了精確學(xué)習(xí)方式和近似學(xué)習(xí)方式：精確方式[3,6,12-13]的解是全局最優(yōu)，但是由于其指數(shù)級(jí)的時(shí)空復(fù)雜性，這些方法只適合于數(shù)據(jù)集規(guī)模小的領(lǐng)域；而近似方式[14-19]的解雖是局部最優(yōu)，但是易于擴(kuò)展到大規(guī)模數(shù)據(jù)上.

基于約束的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)一直以來不論是方法的研究[5,20-24]還是應(yīng)用[25-28]都受到了學(xué)者們的廣泛關(guān)注.然而，高階獨(dú)立性檢驗(yàn)、指數(shù)級(jí)的檢驗(yàn)次數(shù)、變量序的影響依然制約著現(xiàn)有算法的性能.為此，本文針對(duì)基于約束算法存在的部分問題，提出了一種基于度量信息矩陣的“偷懶”啟發(fā)式策略方法.新方法不僅與現(xiàn)有算法在時(shí)間和精度性能上是可比的，而且易于處理大規(guī)模的稀疏網(wǎng)絡(luò).

1 相關(guān)工作

經(jīng)典的基于約束的方法通常包含2個(gè)步驟：1)結(jié)構(gòu)的骨骼識(shí)別;2)邊定向.其中對(duì)于邊定向一般有2類策略:一類是評(píng)分-搜索策略[22]，這種策略也被稱之為混合策略;另一類是識(shí)別DAG的Markov等價(jià)類策略[5,20-24]，這類策略首先定向υ-結(jié)構(gòu)，再進(jìn)一步對(duì)其他邊定向.

在這里，我們關(guān)注結(jié)構(gòu)骨骼的識(shí)別，即通過一系列條件獨(dú)立性檢驗(yàn)確定潛在DAG結(jié)構(gòu)是否存在邊.常用的條件獨(dú)立性檢驗(yàn)方法有統(tǒng)計(jì)假設(shè)檢驗(yàn)或互信息、條件互信息等[10].

根據(jù)采用的不同條件獨(dú)立性檢驗(yàn)策略，我們將基于約束的學(xué)習(xí)方式大致分為基于啟發(fā)式策略學(xué)習(xí)[21-22]和基于PC(Peter-Clark)算法策略學(xué)習(xí)[5,20-24]兩類.下面，我們分別對(duì)這2類方法中具有代表性的方法進(jìn)行概述.

基于啟發(fā)式的策略通過設(shè)置某種啟發(fā)式函數(shù)來實(shí)現(xiàn)減少檢驗(yàn)次數(shù)的目的或減少假陰性節(jié)點(diǎn)的目的，主要包括以下2種.

1) 文獻(xiàn)[21]給出了一種三階段依賴分析算法TPDA.該算法在Monotone DAG-faithful假定下，通過逐漸縮小條件集規(guī)模的啟發(fā)式策略來減少獨(dú)立性檢驗(yàn)次數(shù).雖然該算法的條件獨(dú)立性測(cè)試次數(shù)是O(n4)，但是Monotone DAG-faithful假定和DAG-faithful假定是不相容的[2].

2) 文獻(xiàn)[22]中的MMHC(max-min hill-climbing)雖然采用了一種可納的啟發(fā)式策略，但是也產(chǎn)生了大量的假陽性節(jié)點(diǎn).為了減少假陽性節(jié)點(diǎn)，該方法對(duì)目標(biāo)變量的CPC(candidate parents and children)中所有元素執(zhí)行條件獨(dú)立性檢驗(yàn)，該檢驗(yàn)次數(shù)是CPC規(guī)模的指數(shù)級(jí).

除了基于啟發(fā)式策略的學(xué)習(xí)方法外，也有很多學(xué)者通過改進(jìn)經(jīng)典的PC算法來進(jìn)行結(jié)構(gòu)學(xué)習(xí).他們?cè)O(shè)計(jì)邊排序方法[23]或序獨(dú)立方法[24]來解決PC算法中變量序?qū)撛诮Y(jié)構(gòu)的影響.然而，這類方法雖然在一定程度上緩解了假陰節(jié)點(diǎn)問題，卻無法很好地解決假陽性節(jié)點(diǎn)問題或檢驗(yàn)次數(shù)指數(shù)級(jí)問題.

首先，介紹眾所周知的PC算法[20].該算法也被廣泛應(yīng)用于解決實(shí)際問題，尤其在生物信息學(xué)[25-27]、關(guān)系型數(shù)據(jù)的因果模型挖掘[28]等領(lǐng)域.PC算法從一個(gè)由節(jié)點(diǎn)構(gòu)成的完全無向圖開始，隨著條件集規(guī)模的增長，檢驗(yàn)每一個(gè)變量對(duì).主要特點(diǎn)是條件集隨著完全無向圖呈動(dòng)態(tài)變化，這樣避免了高階獨(dú)立性檢測(cè).但是為了防止假陽性節(jié)點(diǎn)的產(chǎn)生，在相同條件集規(guī)模下，除非變量的鄰居集合的某個(gè)子集使得變量對(duì)獨(dú)立，否則，還要考慮另一變量的鄰居集合的子集情況.這樣一來，條件獨(dú)立性檢驗(yàn)次數(shù)顯著增加.另外，檢驗(yàn)過程對(duì)變量順序非常敏感，嚴(yán)重影響了PC算法的性能[25].

文獻(xiàn)[23]提出了使用BDe(Bayesian Dirichlet extension)評(píng)分函數(shù)測(cè)量每條邊的強(qiáng)度并根據(jù)強(qiáng)度執(zhí)行條件獨(dú)立性檢驗(yàn)的方法.因?yàn)榇嬖跊]有進(jìn)行獨(dú)立性檢測(cè)變量對(duì)(邊)，算法不能保證添加到最終圖的變量對(duì)就是正確的決策.

文獻(xiàn)[24]設(shè)計(jì)了一種序獨(dú)立的PC-Stable算法，即條件獨(dú)立性檢驗(yàn)不會(huì)受到變量序的影響.該算法和PC算法的本質(zhì)區(qū)別在于對(duì)相同條件集規(guī)模下的變量對(duì)執(zhí)行條件獨(dú)立性檢驗(yàn)后，暫不更新無向圖；而是當(dāng)條件集規(guī)模增加后，再相應(yīng)地更新無向圖.相比之下，雖然減少了假陽性節(jié)點(diǎn)，卻需要執(zhí)行更多的條件獨(dú)立性測(cè)試而且易于遭遇高階獨(dú)立性檢驗(yàn)，效率比PC算法低.

為了提高其執(zhí)行效率，文獻(xiàn)[5]基于PC-Stable算法提出了一種多核并行化的處理方式.根據(jù)無向圖的變化規(guī)律，將變量的鄰接邊分配到不同的處理器上，由于遵循了PC-Stable算法更新無向圖的策略，所以在并行化計(jì)算條件獨(dú)立性時(shí)，沒有額外的通信開銷.雖然極大地提升了PC-Stable算法效率，但是假陰性點(diǎn)依然沒有得到好的解決.

上述方法的共同點(diǎn)是盲目地對(duì)到來的變量對(duì)立刻執(zhí)行條件獨(dú)立性檢測(cè)，并沒有考慮合適的時(shí)機(jī)；此外，由于條件集的選擇也是盲目的，只要是變量鄰居就有可能成為條件集元素，也會(huì)導(dǎo)致學(xué)習(xí)錯(cuò)誤.

因此，本文提出了可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法，創(chuàng)新點(diǎn)如下：1)提出了一種無需任何先驗(yàn)知識(shí)僅從樣本中為每個(gè)變量自動(dòng)地學(xué)習(xí)相應(yīng)的變量序的方法，該方法稱之為度量信息矩陣學(xué)習(xí)；2)根據(jù)度量信息矩陣提出了一種用于條件獨(dú)立性檢驗(yàn)的可靠啟發(fā)式策略.該策略在度量信息矩陣的指導(dǎo)下，不僅能夠合理地選擇執(zhí)行條件獨(dú)立性檢驗(yàn)的變量對(duì)，而且能合理地為其選擇條件集.

2 BNSvo-learning算法

2.1 算法描述

數(shù)據(jù)中表現(xiàn)出來的變量間的依賴性包括直接依賴和間接依賴，我們期望在貝葉斯網(wǎng)絡(luò)中評(píng)分最高的變量對(duì)就是直接依賴的變量對(duì).測(cè)量變量對(duì)依賴強(qiáng)度的方法有互信息、偏相關(guān)性[29].

雖然全局最佳網(wǎng)絡(luò)的學(xué)習(xí)是NP-hard問題，但是我們可以尋找一個(gè)近似最佳的網(wǎng)絡(luò).為此，選擇高依賴關(guān)系的變量對(duì)(X,Y)并用這些邊作為創(chuàng)建網(wǎng)絡(luò)的啟發(fā)式是合理的.因此，我們提出了一種可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法，簡(jiǎn)稱為BNSvo-learning.該方法與以往方法的本質(zhì)區(qū)別在于不是盲目地執(zhí)行條件獨(dú)立性檢測(cè)，而是根據(jù)度量信息利用“偷懶”啟發(fā)式策略有序進(jìn)行.該方法主要包含度量信息矩陣學(xué)習(xí)和“偷懶”啟發(fā)式策略2部分.

度量信息矩陣學(xué)習(xí)過程從給定的數(shù)據(jù)中使用互信息度量了所有變量之間依賴程度.根據(jù)該依賴程度，它為每個(gè)變量分配了一個(gè)變量序.我們把這些變量序組成的矩陣稱之為度量信息矩陣mn×n.

度量信息矩陣刻畫了變量間依賴程度的強(qiáng)弱，我們認(rèn)為這是一種粗粒度上的刻畫.原因是它并沒有進(jìn)一步刻畫這種依賴程度是直接依賴還是間接依賴.此外，在實(shí)驗(yàn)觀察中，我們發(fā)現(xiàn)互信息強(qiáng)的變量對(duì)在真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)中并不存在邊，反而互信息相對(duì)弱的變量對(duì)在真實(shí)的網(wǎng)絡(luò)中存在邊.為了高效地獲得潛在結(jié)構(gòu)中真實(shí)的邊，我們?cè)O(shè)計(jì)了一種“偷懶”啟發(fā)式策略.根據(jù)度量信息矩陣，對(duì)變量序中任意一對(duì)變量執(zhí)行條件獨(dú)立性檢驗(yàn)時(shí)，任意階條件獨(dú)立性斷言都不依賴于序中前面的變量，除非該變量與行變量不獨(dú)立.

算法具體描述如下：首先初始化了2個(gè)由節(jié)點(diǎn)構(gòu)成的無向圖矩陣mn×n和Gn×n.其中，mn×n是由變量序構(gòu)成的度量信息矩陣.該矩陣中的每一行暗含了與行變量對(duì)應(yīng)的變量的檢驗(yàn)順序.其中m(i,j)=k指示了矩陣的第i行、第j列元素變量k與變量i的依賴強(qiáng)度排在第j個(gè)位置.矩陣mn×n是動(dòng)態(tài)變化，條件集的規(guī)模以及獨(dú)立性計(jì)算由它決定.矩陣Gn×n刻畫了最終每個(gè)變量的鄰居集合，它隨著度量信息矩陣變化.初始化時(shí)，i=j,G(i,j)=0，否則G(i,j)=1.在這里，0表示變量對(duì)之間沒有邊，1表示有邊.

算法根據(jù)度量信息首先選擇依賴程度最弱的變量對(duì)(i,m(i,j))執(zhí)行條件獨(dú)立性檢測(cè)Ind(i,m(i,j)|S)，S?V{i,m(i,j)}，如果Ind(i,m(i,j)|S)=1，則設(shè)置G(i,m(i,j))=0同時(shí)設(shè)置m(i,j)=0；如果矩陣m中有0元素出現(xiàn)，那么后續(xù)變量的條件獨(dú)立性檢驗(yàn)的條件集就不再考慮該元素.即當(dāng)處理變量對(duì)(i,m(i,j+k))時(shí)，如果?j∈[1,j+k-1]滿足m(i,j)=0,則S?V{i,m(i,j),m(i,j+k)}，否則S?V{i,m(i,j+k)}.

算法1. 基于變量序的貝網(wǎng)結(jié)構(gòu)學(xué)習(xí)算法BNSvo-learning.

輸入：數(shù)據(jù)集data;

輸出：BNS結(jié)構(gòu)G.

① 初始化矩陣Gn×n;

② 根據(jù)互信息學(xué)習(xí)信息度量矩陣mn×n;

③ for對(duì)矩陣m中的元素執(zhí)行獨(dú)立性檢驗(yàn)

④ 初始化條件集規(guī)模:order←0;

⑤ 獲取當(dāng)前的條件集S;

⑥ while |S|

⑦ 執(zhí)行條件獨(dú)立性檢驗(yàn);

⑧ if條件獨(dú)立性檢驗(yàn)

⑨G(i,m(i,j))←0;*更新矩陣G和m*

⑩m(i,j)←0;

2.2 理論分析

BNSvo-learning算法根據(jù)度量信息矩陣執(zhí)行條件獨(dú)立性檢驗(yàn)時(shí)，實(shí)際上采用了一種“偷懶”啟發(fā)式的檢驗(yàn)策略.下面分析該算法的一些重要性質(zhì).

在給出這些性質(zhì)之前，先介紹需用到的信息論知識(shí)：H(X)指示了一個(gè)離散隨機(jī)變量X的熵；H(X|Y)指示了2個(gè)隨機(jī)變量X和Y之間的條件熵；I(X;Y)指示了2個(gè)隨機(jī)變量X和Y之間的互信息.

定理1. 對(duì)任意2個(gè)隨機(jī)變量X和Y，有:

1)I(X;Y)≥0;

2)H(X|Y)≤H(X).

上面兩式當(dāng)且僅當(dāng)X和Y相互獨(dú)立時(shí)等號(hào)成立[1].

定理2. 對(duì)任意3個(gè)離散隨機(jī)變量X,Y和Z有:

1)I(X;Y|Z)≥0;

2)H(X|Y,Z)≤H(X|Z).

上面兩式當(dāng)且僅當(dāng)X和Y相互獨(dú)立時(shí)等號(hào)成立[1].

定理3. BNSvo-learning算法中，當(dāng)I(X;Y)>I(X;Z)，給定Z時(shí)，X和Y不滿足條件獨(dú)立性.

證明. 充分條件，反證法.假定I(X;Y|Z)=0成立.

由定理2可得：

H(X|Y,Z)=H(X|Z)，

由I(X;Y)=H(X)-H(X|Y)可得：

H(X|Z)=H(X)-I(X;Z).

由H(X|Z,Y)=H(X)-I(X;Z,Y)可得：

H(X)-I(X;Z)=H(X)-I(X;Z,Y).

由I(X;Z)=I(X;Z,Y)可得：

I(X;Z)>I(X;Y).

與已知I(X;Y)>I(X;Z)相矛盾，充分條件得證.

必要條件：

由I(X;Y|Z)=H(X|Z)-H(X|Z,Y)，
且H(X|Z)=H(X)-I(X,Z)可得：
I(X;Y|Z)=H(X)-I(X;Z)-H(X|Z,Y)，
由H(X|Z,Y)≤H(X|Y)
且H(X)-I(X;Z)-H(X|Z,Y)≥
H(X)-I(X;Z)-H(X)+I(X;Y)可得：
H(X)-I(X;Z)-H(X|Z,Y)≥
I(X;Y)-I(X;Z).
由I(X;Y)>I(X;Z)可得：
H(X)-I(X;Z)-H(X|Z,Y)>0，
可得：I(X:Y|Z)>0.

證畢.

定理3證明了在一階條件獨(dú)立性檢驗(yàn)過程中，互信息強(qiáng)的變量對(duì)是否獨(dú)立一定不依賴于互信息弱的變量.為此，BNSvo-learning算法對(duì)任意一變量對(duì)執(zhí)行一階條件獨(dú)立性檢驗(yàn)時(shí)，沒有考慮變量序中前面的變量作為其條件集.

為了進(jìn)一步說明BNSvo-learning算法的有效性，我們給出定理4和推論1.

定理4. BNSvo-learning算法中，當(dāng)I(X;Y)>I(X;Z)，I(X;Y)>I(X;W)且I(X;Z|Φ)=0或I(X;W|Φ)=0時(shí),給定Z，X和Y不滿足條件獨(dú)立性.

證明.

由I(X;Y)>I(X;Z)，
I(X;Y)>I(X;W)，
I(X;Z|Φ)=0可得：
I(X;Z,W)

由定理3可知，定理4成立.

證畢.

定理4說明了邊緣獨(dú)立的變量對(duì)和互信息弱的變量組合得到高階的條件集不能影響互信息強(qiáng)的變量對(duì)的條件獨(dú)立性斷言.為此，在檢驗(yàn)過程中算法不考慮這樣的條件集.

推論1. 當(dāng)I(X;Y)

直觀上來說，該啟發(fā)式策略遵循：如果互信息強(qiáng)的變量組合的條件集不能使得變量對(duì)獨(dú)立，那么含有強(qiáng)度弱的變量的條件集也不能使得變量對(duì)獨(dú)立.形式化說明如下：

假定I(X;W)0,那么I(X;Y|Z,W)>0或者I(X;Y|W,H)>0.尤其當(dāng)條件集的規(guī)模較大時(shí)，弱的變量提供的信息會(huì)更少.

在做條件獨(dú)立性斷言的決策時(shí)，我們期望2種情況出現(xiàn)：①I(X;Y|Φ)=0,這意味著無論2個(gè)隨機(jī)變量X和Y在矩陣mn×n中的順序如何，二者滿足邊緣獨(dú)立.②對(duì)于變量X而言，S?V{X,Y}，?I(X;Y)

定義1. 不一致性斷言.隨機(jī)變量X和Y分別執(zhí)行完條件獨(dú)立性檢驗(yàn)后，存在X∈adj(Y),Y?adj(X)，我們稱隨機(jī)變量X和Y之間的條件獨(dú)立性斷言為不一致性斷言.

我們不期望不一致性斷言的出現(xiàn).因?yàn)槲覀兒茈y對(duì)該類斷言做出合理的決策.如果選擇獨(dú)立性成立，那么可能造成假陰性邊，否則造成假陽性邊.事實(shí)上，選擇不成立是可靠的.最糟糕的情況就是執(zhí)行條件獨(dú)立性檢測(cè)后，變量X的鄰居集合沒有任何變化，簡(jiǎn)單地說，花了大量的時(shí)間做了無用功，但是這至少保證了沒有假陰性邊，保證了存在找到最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的可能性.

定理5. BNSvo-learning算法是可納的.

算法采用的啟發(fā)式策略避免了由高階獨(dú)立性檢驗(yàn)造成的假陰性節(jié)點(diǎn).另外，對(duì)任意變量對(duì)(X,Y)執(zhí)行條件獨(dú)立性檢驗(yàn)時(shí)，如果獨(dú)立，則對(duì)X的鄰居集合修訂adj(X)=adj(X)Y；變量Y的鄰居集合adj(Y)保持不變.換句話說，對(duì)于變量Y而言，它和X是否條件獨(dú)立只與Y和其對(duì)應(yīng)的變量序有關(guān).這樣防止由變量X的誤判對(duì)變量Y的影響.

為了進(jìn)一步減少時(shí)間代價(jià)，算法在保證質(zhì)量的前提下，對(duì)BNSvo-learning算法做了進(jìn)一步的改進(jìn)，當(dāng)m(i,j)=0，對(duì)于變量m(i,j)而言，在變量i的索引iindex滿足iindex

這樣做的想法很直觀，對(duì)于變量X而言,如果變量對(duì)(X,Y)條件獨(dú)立性成立，那么對(duì)于變量Y而言，如果變量X之后仍有許多互信息強(qiáng)的變量，那么(X,Y)條件獨(dú)立性成立的概率很大.

算法2. 改進(jìn)后的學(xué)習(xí)算法IBNSvo-learning.

輸入:數(shù)據(jù)集data;

輸出：更新后的m.

① for矩陣m中第m(i,j)行的每一個(gè)元素

② if變量i在第m(i,j)行中的索引為iindex

④m(m(i,j),iindex)←0;

⑤G(m(i,j),i)←0;

⑥ end if

⑦ end if

⑧ end for

⑨ returnm.

改進(jìn)后算法的實(shí)現(xiàn)，只需將IBNSvo-learning算法的行①～⑨嵌入在BNSvo-learning算法的行⑩～之間即可.

3 實(shí) 驗(yàn)

為了說明BNSvo-learning算法的性能，我們從貝葉斯網(wǎng)絡(luò)知識(shí)庫(the Bayesian network repository, BNR)[30]中選擇了5個(gè)不同規(guī)模的網(wǎng)絡(luò).同時(shí)也使用了拼貼技術(shù)[31]生成了一個(gè)適中規(guī)模網(wǎng)絡(luò)Insurance 1和大網(wǎng)絡(luò)Insurance 2.表1展示了7個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)、弧數(shù)、最大父節(jié)點(diǎn)數(shù)和最大狀態(tài)數(shù).

Table 1 Bayesian Networks Used in the Evaluation Study表1 在評(píng)估研究中使用的貝葉斯網(wǎng)絡(luò)

3.1 實(shí)驗(yàn)結(jié)果對(duì)比

為了說明算法的可靠性，我們從以下4個(gè)方面來驗(yàn)證算法：1)變量的狀態(tài)數(shù)少，屬性數(shù)少，樣本量10 000時(shí)(Asia-8,Sachs-11)； 2)變量的狀態(tài)數(shù)多，屬性數(shù)適中，樣本量10 000時(shí)(Alarm-37，Child-20)；3)變量狀態(tài)數(shù)多，屬性數(shù)多，樣本量5 000時(shí)(Insurance1，Insurance2);4)變量的狀態(tài)數(shù)少，屬性數(shù)多，樣本量5 000時(shí)(Pigs-441).

我們采用了邊評(píng)分的評(píng)價(jià)方法來驗(yàn)證算法的精度性能即計(jì)算缺失邊數(shù)(Missing)、多余邊數(shù)(Additional)以及反向邊數(shù)(Reverse).Edge Type越低表明算法的性能越好.表2給出了學(xué)習(xí)結(jié)構(gòu)的邊評(píng)分結(jié)果,其中，HC(Hill-Climbing)是指經(jīng)典的基于評(píng)分方式的近似結(jié)構(gòu)學(xué)習(xí)算法[1].

Table 2 Results Comparison of Our Method with Classic Algorithms表2 和經(jīng)典算法的對(duì)比實(shí)驗(yàn)結(jié)果

表2中的空白項(xiàng)表示由于內(nèi)存不足或時(shí)間代價(jià)過高沒有得到最終解.對(duì)于HC算法，在實(shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)數(shù)據(jù)維數(shù)超過200時(shí)，就警示“內(nèi)存不足”.其原因是：當(dāng)前結(jié)構(gòu)的候選鄰居接近n2，每一個(gè)候選鄰居都是一個(gè)n×n的矩陣，故需要n4的存儲(chǔ)空間.對(duì)于PC和PC-Stable以及MMHC算法，時(shí)間代價(jià)過高.究其原因：隨著數(shù)據(jù)維數(shù)的增加以及變量對(duì)的非獨(dú)立性關(guān)系的成立，導(dǎo)致條件集規(guī)模迅速增大，從而使得獨(dú)立性檢測(cè)次數(shù)的指數(shù)級(jí)增長速度很快.

然而，本文提出的BNSvo-learning算法不僅不會(huì)遭遇到上述其他算法內(nèi)存不足或時(shí)間代價(jià)高的情況，而且通過和真實(shí)結(jié)構(gòu)的對(duì)比，除了Child數(shù)據(jù)外，解的質(zhì)量?jī)?yōu)于對(duì)比算法.這不僅表現(xiàn)在簡(jiǎn)單的數(shù)據(jù)集Asia和Sachs上，而且對(duì)于高維稀疏的數(shù)據(jù)集Pigs依然出色.

為了說明BNSvo-learning算法在有限樣本條件下的可靠性，我們分別在屬性數(shù)是370，樣本量是500，1 000，5 000的Alarm數(shù)據(jù)集[31]上進(jìn)行了驗(yàn)證.由表3可以看出，在處理樣本量小、屬性數(shù)多的數(shù)據(jù)集時(shí)，BNSvo-learning算法依然表現(xiàn)良好.

Table3ResultsComparisonofOurMethodwithConstraint-BasedAlgorithms

表3 與經(jīng)典基于約束的算法的對(duì)比實(shí)驗(yàn)結(jié)果

3.2 時(shí)間代價(jià)對(duì)比實(shí)驗(yàn)結(jié)果

本文提出的BNSvo-learning算法不僅在網(wǎng)絡(luò)的結(jié)構(gòu)質(zhì)量上有保障，而且在時(shí)間的需求上也合理.下面我們分別從實(shí)驗(yàn)和理論進(jìn)行驗(yàn)證和說明.表4給出了和經(jīng)典算法在時(shí)間需求上的對(duì)比實(shí)驗(yàn).

Table 4 Performance Comparison of Algorithms in Time Cost表4 算法在時(shí)間代價(jià)上的性能比較 s

從表4中可以看出，所提算法BNSvo-learning在時(shí)間性能上顯著優(yōu)于經(jīng)典的算法，尤其在處理高維稀疏數(shù)據(jù)集Pigs時(shí)，該算法能在6 943 s中求解，而對(duì)比算法在以天為單位的時(shí)間內(nèi)得不到解.其原因在之前的精度性能實(shí)驗(yàn)中已作了分析，這里不再贅述.

3.3 BNSvo-learning及其改進(jìn)算法時(shí)間代價(jià)對(duì)比

我們分別選取了不同規(guī)模的數(shù)據(jù)集，從時(shí)間代價(jià)層面展示了2種算法的性能，如表5所示.從表5中可以看出，隨著數(shù)據(jù)集屬性數(shù)的增多，改進(jìn)后的算法明顯優(yōu)于BNSvo-learning算法.

IBNSvo-learning算法時(shí)間代價(jià)小的主要原因有2點(diǎn)：1)當(dāng)設(shè)置m(m(i,j),iindex)=0，算法沒有再對(duì)變量對(duì)(m(i,j),i)執(zhí)行條件獨(dú)立性檢測(cè).具體而言，假設(shè)對(duì)于變量m(i,j)而言，還有w個(gè)待檢變量，那么最壞的情況可能要執(zhí)行2w次條件獨(dú)立性檢測(cè).2)變量m(i,j)對(duì)應(yīng)的其他變量的條件獨(dú)立性檢測(cè)次數(shù)減少.如果沒有置0，最壞的情況下，條件獨(dú)立性檢測(cè)次數(shù)是2w+1；置0，最壞的情況下是2w.

Table 5 Performance Comparison of Algorithms in Time Cost表5 算法在時(shí)間代價(jià)上的性能比較 s

3.4 真實(shí)世界實(shí)驗(yàn)

為了評(píng)估所提出算法在實(shí)際應(yīng)用中的效果，我們用真實(shí)的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn).該數(shù)據(jù)集來源于供熱機(jī)組3個(gè)月全工況監(jiān)測(cè)數(shù)據(jù).其中數(shù)據(jù)維數(shù)為50，每個(gè)月的樣本量分別為43 200，44 640，44 641條，變量的最大狀態(tài)數(shù)是10.由于沒有真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)，我們僅在時(shí)間代價(jià)性能上做了對(duì)比實(shí)驗(yàn).表6給出了在真實(shí)的電力數(shù)據(jù)集上關(guān)于需求時(shí)間的對(duì)比實(shí)驗(yàn).

Table 6 Performance Comparison of Algorithms in Time Cost表6 算法在時(shí)間代價(jià)上的性能比較 s

從表6可以看出，當(dāng)數(shù)據(jù)維數(shù)適中、樣本量較大時(shí)，所提算法依然能夠在合理的時(shí)間內(nèi)求解，這表明BNSvo-learning算法能夠很好地?cái)U(kuò)展到大樣本量的數(shù)據(jù)集上.此外，經(jīng)典的爬山算法表現(xiàn)得相對(duì)很差，主要原因是樣本量過大使得評(píng)分函數(shù)需要的計(jì)算時(shí)間加長.

4 總結(jié)與展望

本文的貢獻(xiàn)如下：1)首次嘗試提出使用變量間互信息來刻畫變量序的度量信息矩陣，以實(shí)現(xiàn)條件獨(dú)立性檢驗(yàn)不是盲目地選擇變量對(duì)，而是依賴于度量信息矩陣提供的信息有選擇地進(jìn)行；2)基于度量信息矩陣提議了一種合理的“偷懶”啟發(fā)式策略，有效地避免高階獨(dú)立性，減少檢驗(yàn)次數(shù)，保證了檢驗(yàn)可靠性.我們從理論上證明算法的有效性，從實(shí)驗(yàn)上驗(yàn)證了算法的高效性和可靠性.但是由于在定向階段我們采用了與PC算法類似的方式，這種方式對(duì)個(gè)體定向錯(cuò)誤敏感，尤其是υ-結(jié)構(gòu)的定向，后期將探討采用評(píng)分-搜索的策略解決定向問題；另外，對(duì)于數(shù)據(jù)集Child，本文所提算法雖然在時(shí)間性能和Missing上優(yōu)于對(duì)比算法，但會(huì)導(dǎo)致過多的Additional和Reverse.跟蹤實(shí)驗(yàn)發(fā)現(xiàn)，Additional主要是由于當(dāng)樣本數(shù)小于自由度時(shí)(相關(guān)概念讀者可查閱文獻(xiàn)[20])經(jīng)典的算法和所提算法都采用了選擇依賴的方法，后期我們將針對(duì)該問題進(jìn)行研究.

QiXiaolong, born in 1981. PhD candidate and lecturer. His main research interests include probabilistic graphical models, machine learning.

GaoYang, born in 1972. PhD, professor, PhD supervisor. Committee member of CCF. His main research interests include reinforcement learning, agent theory (belief revision) and multi-agent systems, intelligent system, image process and video surveillance.

WangHao, born in 1983. PhD, assistant researcher. His main research interests include rank-aware query processing, reco-mmender systems, reinforcement learning & transfer learning (wanghao@nju.edu.cn).

SongBei, born in 1994. Master candidate. Her main research interests include industrial big data analysis, probabilistic graph model (songbei07@gmail.com).

ZhouChunlei, born in 1973. Engineer. Her main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (13913918185@163.com).

ZhangYouwei, born in 1986. Engineer. His main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (15905166639@163.com).