1、貝葉斯網(wǎng)絡(luò)（Bayesian Network，BN）屬于概率圖模型，是一種有效的不確定知識表達(dá)和推理工具-除了能直觀而緊湊（定性和定量）地表示變量間的相互關(guān)系，BN還提供強大的推導(dǎo)能力，包括基于完整觀測值或帶缺失值的觀測樣本。BN在諸多領(lǐng)域獲得了廣泛的應(yīng)用，特別是診斷和決策場景。應(yīng)用BN的前提是獲得準(zhǔn)確的模型，包括結(jié)構(gòu)和參數(shù)，而結(jié)構(gòu)學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)研究中的重點和難點。常見的結(jié)構(gòu)學(xué)習(xí)途徑有兩種：（1）由領(lǐng)域?qū)＜一趯I(yè)知識和經(jīng)驗完成；（2

2、）基于學(xué)習(xí)算法從樣本數(shù)據(jù)蘊含的信息中推導(dǎo)/恢復(fù)。前者不適合于大規(guī)模應(yīng)用，后者是目前的主流方式，而后者又可進(jìn)一步分三個不用的方向：（1）基于依賴統(tǒng)計分析的方法，又稱基于約束的搜索（Constraint Based Search）；（2）基于評分搜索（Scoring and Search）；（3）結(jié)合上述兩種方法的混合搜索算法。每類策略已知皆有多種實現(xiàn)（算法），但復(fù)雜度都為指數(shù)級，即BN的結(jié)構(gòu)學(xué)習(xí)屬于NP困難問題，這直接限制了目前BN可解決

3、的問題規(guī)模。
　　分類是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的基本任務(wù)，屬于目標(biāo)變量為離散型的預(yù)測技術(shù)–是基于自變量的觀測值向量預(yù)測目標(biāo)變量的取值。根據(jù)目標(biāo)變量的個數(shù)可分為單維和多維分類，傳統(tǒng)的分類任務(wù)默認(rèn)指得是單維分類。分類可視為特殊的推導(dǎo)任務(wù)，將BN應(yīng)用于單維分類任務(wù)時，許多經(jīng)典的簡化模型被提出以降低學(xué)習(xí)代價，比如樸素貝葉斯（Naive Bayes，NB）及其諸多增強版本（樹增益樸素貝葉斯（TAN）等）。雖然這些特殊的BN所要求的假設(shè)在現(xiàn)實中并

4、不成立，但這些簡化的貝葉斯網(wǎng)絡(luò)分類器（Bayesian Network Classifier，BNC）取得了驚人的成功，包括經(jīng)濟(jì)的學(xué)習(xí)成本和有競爭力的預(yù)測性能。
　　關(guān)于多維分類的研究源于人們逐漸意識到該應(yīng)用場景在現(xiàn)實世界中廣泛存在。例如，一個人若患有“高血壓”，將伴隨出現(xiàn)多種并發(fā)癥狀，包括心臟并發(fā)癥（如左心室肥厚/心絞痛/心肌梗死/心力衰竭）、腦卒中（出血性腦卒中/缺血性腦卒中/高血壓腦?。?、大小動脈（動脈硬化/主動脈夾層）、高

5、血壓性腎損害（小動脈性腎硬化癥/惡性小動脈腎硬化癥/慢性腎功能衰竭）等。這些不同維度的具體癥狀相互關(guān)聯(lián)而非相互獨立，既是基于自變量的觀測值被預(yù)測的對象，也影響著相互之間的預(yù)測。由于預(yù)測任務(wù)是多個目標(biāo)的最可能組合，而非逐個目標(biāo)的推導(dǎo)，多維分類可實現(xiàn)更符合實際的預(yù)測性能。多標(biāo)簽分類屬于多維分類的特殊情況，前者僅能預(yù)測目標(biāo)標(biāo)簽的存在與否（二值預(yù)測）。
　　貝葉斯網(wǎng)絡(luò)在2006年首次被研究人員應(yīng)用到多維分類問題，所提出的模型被命名為多維貝

6、葉斯網(wǎng)絡(luò)分類器（Multi-dimensional Bayesian Network Classifier，MBNC）。為了避免高昂的學(xué)習(xí)代價，MBNC被限制為兩偶圖（Bi-partitie Graph），即可分解為三個獨立的子圖：類子圖（Class Sub-graph）、特征子圖（Feature Sub-graph）和連接它們的橋接子圖（Bridge Sub-graph）。傳統(tǒng)的MBNC中目標(biāo)變量的父結(jié)點僅允許是（其他）目標(biāo)變量，類子

7、圖和特征子圖是相對獨立的有向無環(huán)圖（Directed Acyclic Graph，DAG），故經(jīng)典的MBNC兩偶圖可以表示為-。為了進(jìn)一步降低學(xué)習(xí)代價，研究人員不同程度地添加了對類子圖和特征子圖的約束，-相應(yīng)變?yōu)?Empty>-、-和-等。此外，經(jīng)典MBNC默認(rèn)針對所有特征變量建模，可能包含冗余變量和/或無關(guān)變量。

8、>　　本文提出一種新的多維貝葉斯網(wǎng)絡(luò)分類器-通用多維貝葉斯網(wǎng)絡(luò)分類器（General MBNC，GMBNC），它允許any-to-any的依賴關(guān)系。GMBNC與傳統(tǒng)MBNC相比存在兩大差異：（1）不要求模型是兩偶圖，只需滿足一般DAG的約束；（2）默認(rèn)僅包含對目標(biāo)變量預(yù)測有效的變量集合-目標(biāo)變量的馬爾科夫毯（Markov Blanket）組合，因而GMBNC實際上是全局BN的一個局部結(jié)構(gòu)。由于支持最一般的依賴關(guān)系，GMBNC從理論上看較

9、MBNC更能實現(xiàn)對客觀不確定世界的精準(zhǔn)建模，這是準(zhǔn)確預(yù)測的基礎(chǔ)。同時，GMBNC繼承了作為BN所具備的直觀建模和強大靈活的推導(dǎo)能力。
　　根據(jù)定義，學(xué)習(xí)GMBNC的一種可行途徑是先學(xué)習(xí)關(guān)于目標(biāo)變量和所有特征變量的全局貝葉斯網(wǎng)絡(luò)，而后根據(jù)定義可容易“讀出”目標(biāo)GMBNC?，F(xiàn)有BN結(jié)構(gòu)學(xué)習(xí)算法皆可供選擇用于全局貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的推導(dǎo)，但由于BN結(jié)構(gòu)學(xué)習(xí)的指數(shù)級復(fù)雜度，該方法可支持的多維分類應(yīng)用規(guī)模將非常有限。本項目根據(jù)已知的GMBNC的

10、拓?fù)涮卣鳎岢龌诰植克阉鞯腉MBNC結(jié)構(gòu)學(xué)習(xí)算法，僅學(xué)習(xí)預(yù)測所必要的結(jié)構(gòu)，既避免了學(xué)習(xí)全局BN所引起的不必要消耗，還能在完成GMBNC結(jié)構(gòu)輸出的同時實現(xiàn)特征子集選擇（類似經(jīng)典的決策樹推導(dǎo)算法）。由于利用了統(tǒng)計方法分析變量間的依賴關(guān)系，并輔以 GMBNC的拓?fù)湫畔砑s束搜索范圍，本項目提出的三個GMBNC結(jié)構(gòu)學(xué)習(xí)算法故都屬于基于約束的搜索。
　　第一個算法為 IPC-GMBNC（Iterative Parents Children

11、 based induction of GMBNC），它依次搜索目標(biāo)變量的馬爾科夫毯，而在搜索馬爾科夫毯時則通過迭代推導(dǎo)相關(guān)變量的直接相連結(jié)點（即父/子結(jié)點），因而得名。關(guān)于馬爾科夫毯的推導(dǎo)算法很多，包括IAMB、PCMB、IPC-MB等，它們僅考慮單個結(jié)點的馬爾科夫毯的推導(dǎo)。IPC-GMBNC算法則綜合考慮多個目標(biāo)變量的馬爾科夫毯之間存在相互重疊的邊界，在算法中設(shè)計了兩個邊集合容器，分別緩存搜索過程中確定刪除的邊和候選留存的邊。若一條

12、邊（在先前的統(tǒng)計測試中）已經(jīng)確認(rèn)應(yīng)該刪除，則被放入刪除邊的集合，未來搜索中將直接被忽略（避免了重復(fù)計算）；而一條尚未被確認(rèn)刪除的邊則通過關(guān)于邊兩端變量（結(jié)點）充分的統(tǒng)計測試將最終被判斷為應(yīng)該刪除或應(yīng)該保留。由于執(zhí)行廣度優(yōu)先搜索的策略，且基于GMBNC的拓?fù)湫畔⑺阉魃疃认拗圃冢ㄏ鄬δ繕?biāo)變量結(jié)點）不超過兩層，IPC-GMBNC執(zhí)行的是局部搜索，避免了傳統(tǒng)學(xué)習(xí)全局BN算法的弊端。該算法那可被證明為正確，而實驗顯示它較經(jīng)典的BN結(jié)構(gòu)學(xué)習(xí)算法P

13、C算法能節(jié)省十分可觀的計算量。例如在一個包含100個結(jié)點的實驗中，IPC-GMBNC較PC節(jié)省了約85％的計算量，但學(xué)習(xí)質(zhì)量兩者相當(dāng)。另外，因為 IPC-GMBNC算法在執(zhí)行統(tǒng)計測試時優(yōu)先執(zhí)行低維度（條件集合?。┑臈l件獨立統(tǒng)計測試，該算法可以最大程度避免此類算法由于樣本不足以支持高維度統(tǒng)計測試而帶來的誤判風(fēng)險。雖然隨著網(wǎng)絡(luò)密度的提高 IPC-GMBNC將需要消耗更多的統(tǒng)計測試，但PC算法所需要的計算同樣激增，所以IPC-GMBNC相對于

14、PC算法仍然保持一致的優(yōu)勢。
　　第二個算法為 DOS-GMBNC（Dynamic Order Search based induction of GMBNC）。DOS-GMBNC繼承了IPC-GMBNC的整體搜索框架，與后者以隨機(jī)的順序執(zhí)行候選條件獨立統(tǒng)計測試不同，DOS-GMBNC動態(tài)調(diào)整待執(zhí)行的統(tǒng)計測試的順序，并優(yōu)先執(zhí)行能給學(xué)習(xí)過程帶來期望信息的測試。這得益于DOS-GMBNC進(jìn)一步挖掘并利用拓?fù)湫畔⒌哪芰?一個變量出現(xiàn)在統(tǒng)

15、計測試的條件集內(nèi)的頻次間接反映了該變量“分割”/“阻斷”有向邊的能力。通過統(tǒng)計每個變量的該信息，我們將可以“區(qū)別”不同變量“分割”有向邊的相對能力。由于我們執(zhí)行的是后向搜索（Backward Selection，即若發(fā)現(xiàn)存在一對變量之間的分割集，它們之間的假正（False Positive）邊即刻被刪除，剩余的其他候選分割集將無需繼續(xù)被測試），在執(zhí)行新的統(tǒng)計測試時，我們將針對性地優(yōu)先執(zhí)行包含高頻（扮演分割）變量的測試，這有助于（1）更快

16、識別一條“假正”候選邊，（2）較傳統(tǒng)的方法忽略更多的候選分割集，從而達(dá)到節(jié)省計算量的目的。DOS-GMBNC算法同樣可被證明為正確，實驗顯示DOS-GMBNC和IPC-GMBNC相比在時間效率方面有顯著的提升。例如在一個包含100個結(jié)點的實驗中，DOS-GMBNC比IPC-GMBNC節(jié)省了約45%的計算量，而學(xué)習(xí)質(zhì)量相當(dāng)。因此，這樣的動態(tài)搜索策略是有效且經(jīng)濟(jì)的。
　　第三個算法為 LAS-GMBNC（Local Adaptive

17、Search based induction of GMBNC）。LAS-GMBNC是 DOS-GMBNC的升級版本，因此也間接繼承了IPC-GMBNC的整體搜索框架。LAS-GMBNC較DOS-GMBNC采集了更精細(xì)的拓?fù)湫畔⒉⒂靡詧?zhí)行動態(tài)排序時參考-在統(tǒng)計和更新變量扮演“分割”有向邊的頻率時，綜合考慮了“分割集”的實際大?。捍蟆胺指罴敝袉蝹€變量的貢獻(xiàn)權(quán)重顯然低于小“分割集”里單個變量的貢獻(xiàn)度。實驗顯示了該策略的有效性，例如在一個A

18、larm網(wǎng)絡(luò)的實驗中，LAS-GMBNC較DOS-GMBNC節(jié)省了約34%的計算量，而學(xué)習(xí)質(zhì)量相當(dāng)。我們也證明了LAS-GMBNC的正確性。
　　我們提出的三個結(jié)構(gòu)學(xué)習(xí)算法普遍基于以下假設(shè)：（1）忠實（Faithfulness）；（2）觀測值完整；（3）統(tǒng)計測試正確。這也是一般貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法所需要的假設(shè)。當(dāng)觀測樣本沒有缺失值時，參數(shù)學(xué)習(xí)相比于結(jié)構(gòu)學(xué)習(xí)沒有難度，故本文著重研究GMBNC的結(jié)構(gòu)學(xué)習(xí)。IPC-GMBNC展示了基于

19、局部搜索的可行性和顯著效果，而DOS-GMBNC和LAS-GMBNC除了繼承IPC-GMBNC局部搜索的優(yōu)勢，更在如何更充分利用拓?fù)湫畔砑铀倩诩s束的搜索方面做了有益的探索。我們相信這個方向值得未來持續(xù)探索。
　　相比全局貝葉斯網(wǎng)絡(luò)，GMBNC是關(guān)于目標(biāo)多個變量的局部結(jié)構(gòu)。雖然三個算法都將目標(biāo)定在局部而有效的搜索，但DOS-GMBNC和LAS-GMBNC所實現(xiàn)的動態(tài)搜索策略將同樣適于常規(guī)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)。我們也做了相關(guān)的工作