貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)總結(jié)

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)總結(jié)一、 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的原理從數(shù)據(jù)中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)就是對(duì)給定的數(shù)據(jù)集，找到一個(gè)與數(shù)據(jù)集擬合最好的網(wǎng)絡(luò)。首先定義一個(gè)隨機(jī)變量Sh，表示網(wǎng)絡(luò)結(jié)構(gòu)的不確定性，并賦予先驗(yàn)概率分布p(Sh)。然后計(jì)算后驗(yàn)概率分布p(ShID)。根據(jù)Bayesian定理有p(ShID)=p(Sh,D)/p(D)=p(Sh)p(DISh)/p(D)其中p(D)是一個(gè)與結(jié)構(gòu)無(wú)關(guān)的正規(guī)化常數(shù)，p(DISh)是邊界似然。于是確定網(wǎng)絡(luò)結(jié)構(gòu)的后驗(yàn)分布只需要為每一個(gè)可能的結(jié)構(gòu)計(jì)算數(shù)據(jù)的邊界似然。在無(wú)約束多項(xiàng)分布、參數(shù)獨(dú)立、采用Dirichlet先驗(yàn)和數(shù)據(jù)完整的前提下，數(shù)據(jù)的邊界似然正好等于每一個(gè)(i，j)對(duì)的邊界似然的乘積，即p(DISh)=HFI「號(hào)H「氣+%)-尸叫+N)k=1「氣)二、 貝葉斯網(wǎng)絡(luò)完整數(shù)據(jù)集下結(jié)構(gòu)學(xué)習(xí)方法貝葉斯網(wǎng)絡(luò)建模一般有三種方法：1)依靠專家建模；2)從數(shù)據(jù)中學(xué)習(xí)；3)從知識(shí)庫(kù)中創(chuàng)建。在實(shí)際建模過程中常常綜合運(yùn)用這些方法，以專家知識(shí)為主導(dǎo)，以數(shù)據(jù)庫(kù)和知識(shí)庫(kù)為輔助手段，揚(yáng)長(zhǎng)避短，發(fā)揮各自優(yōu)勢(shì)，來(lái)保證建模的效率和準(zhǔn)確性。但是，在不具備專家知識(shí)或知識(shí)庫(kù)的前提下，從數(shù)據(jù)中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)模型結(jié)構(gòu)的研究顯得尤為重要。常用的結(jié)構(gòu)學(xué)習(xí)方法主要有兩類，分別是基于依賴性測(cè)試的學(xué)習(xí)和基于搜索評(píng)分的學(xué)習(xí)。第一類方法是基于依賴性測(cè)試的方法，它是在給定數(shù)據(jù)集D中評(píng)估變量之間的條件獨(dú)立性關(guān)系，構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)。基于條件獨(dú)立測(cè)試方法學(xué)習(xí)效率最好，典型的算法包括三階段分析算法(TPDA)?；谝蕾囆詼y(cè)試的方法比較直觀，貼近貝葉斯網(wǎng)絡(luò)的語(yǔ)義，把條件獨(dú)立性測(cè)試和網(wǎng)絡(luò)結(jié)構(gòu)的搜索分離開，不足之處是對(duì)條件獨(dú)立性測(cè)試產(chǎn)生的誤差非常敏感。且在某些情況下條件獨(dú)立性測(cè)試的次數(shù)相對(duì)于變量的數(shù)目成指數(shù)級(jí)增長(zhǎng)。第二類方法是基于評(píng)分搜索的方法，其原理是在所有節(jié)點(diǎn)的結(jié)構(gòu)空間內(nèi)按照一定的搜索策略及評(píng)分準(zhǔn)則構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，這種算法雖然能夠搜索到精確的網(wǎng)絡(luò)結(jié)構(gòu)，但是由于結(jié)構(gòu)空間很大，從所有可能的網(wǎng)絡(luò)結(jié)構(gòu)空間搜索最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)被證明為NP-hard問題，所以一般需要使用啟發(fā)式算法，代表性算法有K2算法等。基于搜索評(píng)分的方法是一種統(tǒng)計(jì)驅(qū)動(dòng)的方法，試圖在準(zhǔn)確性、稀疏性、魯棒性等多個(gè)因素之間找個(gè)平衡點(diǎn)。但由于搜索方法的先天弱點(diǎn)，導(dǎo)致用搜索評(píng)分的方法不一定能找到最好的結(jié)構(gòu)，但是應(yīng)用范圍很廣。當(dāng)觀察到的數(shù)據(jù)足夠充分且計(jì)算次數(shù)足夠多時(shí)，基于搜索評(píng)分的方法和基于依賴性測(cè)試的方法都可以學(xué)到“正確”的網(wǎng)絡(luò)結(jié)構(gòu)。此外，有人結(jié)合上述兩種方法，提出了一些混合算法，這類算法首先利用獨(dú)立性測(cè)試降低搜索空間的復(fù)雜度，然后執(zhí)行評(píng)分搜索找到最佳網(wǎng)絡(luò)，如稀疏候選算法(sparsecandidate)及MMHC(max-minhill-climbing)算法等?；谝蕾囆詼y(cè)試結(jié)構(gòu)學(xué)習(xí)方法基于依賴性測(cè)試的結(jié)構(gòu)學(xué)習(xí)算法將貝葉斯網(wǎng)絡(luò)看作是編碼了變量間獨(dú)立性關(guān)系的圖結(jié)構(gòu)。它的核心思想是：通過樣本集D驗(yàn)證條件獨(dú)立性I(Xi，Xj|C)是否成立，若成立，則在網(wǎng)絡(luò)S中節(jié)點(diǎn)Xi和Xj被C有向分割，節(jié)點(diǎn)Xi和Xj之間不存在邊，若不成立，變量Xi和Xj是依賴的，網(wǎng)絡(luò)中節(jié)點(diǎn)Xi和Xj之間存在邊。然后，利用節(jié)點(diǎn)集之間的條件獨(dú)立性，建造一個(gè)有向無(wú)環(huán)圖，以盡可能多地覆蓋這些條件獨(dú)立性。常用的獨(dú)立性檢驗(yàn)的方法有X2檢驗(yàn)和基于互信息的檢驗(yàn)方法?；谝蕾囆詼y(cè)試的學(xué)習(xí)方法學(xué)習(xí)效率較高，而且能夠獲得全局最優(yōu)解；但存在以下問題：1.判斷兩個(gè)節(jié)點(diǎn)是否獨(dú)立或條件獨(dú)立是困難的，變量間條件獨(dú)立性檢驗(yàn)的次數(shù)是隨著變量的個(gè)數(shù)的增加指數(shù)級(jí)增長(zhǎng)的；2.高階的條件獨(dú)立性檢驗(yàn)的結(jié)果不夠可靠。1993年Sprites等提出的SGS算法是典型的以條件獨(dú)立性測(cè)試確定拓?fù)浣Y(jié)構(gòu)的算法。該算法從無(wú)向完全圖出發(fā)，如果相節(jié)點(diǎn)間存在無(wú)向分割集，則刪除它們間的邊；然后通過統(tǒng)計(jì)測(cè)試來(lái)確定剩余邊的方向。2002年，Cheng將信息論與統(tǒng)計(jì)測(cè)試相結(jié)合，使用相互信息代替了條件獨(dú)立性測(cè)試。經(jīng)過Drafting、Thickening、Thinning三個(gè)步驟，通過計(jì)算相互信息量來(lái)確定節(jié)點(diǎn)間的條件獨(dú)立性。從而構(gòu)造出多連接有向圖模型?；谠u(píng)分搜索的結(jié)構(gòu)學(xué)習(xí)方法：貝葉斯網(wǎng)絡(luò)基于評(píng)分搜索的結(jié)構(gòu)學(xué)習(xí)方法主要包括兩步模型選擇和模型優(yōu)化。模型選擇部分要制定模型選擇準(zhǔn)則，即評(píng)分函數(shù)目前較常用的幾個(gè)評(píng)分函數(shù)如下：最優(yōu)參數(shù)對(duì)數(shù)似然函數(shù)，CH評(píng)分，BIC評(píng)分等，還有MDL(minimumdescriptionlength),AIC(Akaikeinformationcriterion)評(píng)分函數(shù)，HVL(holdoutvalidationlikelihood)評(píng)分(驗(yàn)證數(shù)據(jù)似然度】CVL(crossvalidationlikelihood)評(píng)分(交叉驗(yàn)證)。模型優(yōu)化就是要根據(jù)模型選擇準(zhǔn)則，即評(píng)分函數(shù)，選擇出評(píng)分最高的網(wǎng)絡(luò)結(jié)構(gòu)，也就是搜索策略問題。從所有可能的網(wǎng)絡(luò)結(jié)構(gòu)空間搜索最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)被證明為NP-hard問題，所以一般使用啟發(fā)式搜索算法，主要有K2，hill-climbing算法；隨機(jī)重復(fù)爬山法(randomrestarthill-climbing)，禁忌搜索(tabusearch)，模擬退火(simulatedannealing)及遺傳算法(geneticalgorithm)等。常用的評(píng)分函數(shù)介紹如下：最優(yōu)參數(shù)對(duì)數(shù)似然函數(shù)結(jié)構(gòu)C與相應(yīng)的參數(shù)集合氣組成貝葉斯網(wǎng)絡(luò)(C，氣)。相對(duì)于數(shù)據(jù)9最優(yōu)的貝葉斯網(wǎng)(C*,°*)應(yīng)該使對(duì)數(shù)似然函數(shù)達(dá)到最大，即l(匚*,0**19)=maxsupl(匚,019)? 匚 °°, 匚在概念上尋找最優(yōu)的貝葉斯網(wǎng)絡(luò)的過程可以分為兩步：第一步尋找最優(yōu)結(jié)構(gòu)匚*，第二步尋找最優(yōu)參數(shù)0**0對(duì)任一網(wǎng)絡(luò)結(jié)構(gòu)0,定義1*(。IS)=supl(C，七IS)作為網(wǎng)絡(luò)結(jié)構(gòu)的函數(shù)，i*(CIS)稱為優(yōu)參對(duì)數(shù)似然函數(shù)，最優(yōu)結(jié)構(gòu)。*應(yīng)該使優(yōu)參對(duì)數(shù)似然函數(shù)達(dá)到最大，即l*(0*I9)=maxl*(。19)，這就是最大優(yōu)參似然準(zhǔn)則。0家族CH評(píng)分設(shè)定p(BID)=rfscore(i,pa) ---B表示網(wǎng)絡(luò)結(jié)構(gòu)，D表示一組變量TOC\o"1-5"\h\zS i si=1X1，X2，...,Xn的完整實(shí)例數(shù)據(jù)q r(a)r「(合+n)\o"CurrentDocument"其中score(i,pa)=11[ j 11 曲 ―]\o"CurrentDocument"i j=1叫*+NPk=1 叫)其中N.是D中滿足X=k，兀.=j的樣本個(gè)數(shù)，N,=客，8=?。ijk i i ij* ijkij* ijkk=1 k=1在使用CH評(píng)分之前，首先需要選定參數(shù)先驗(yàn)分布p(0BIBs)中超參數(shù)8亦。通常這并非易事，因?yàn)槔碚撋衔覀冃枰獙?duì)每一個(gè)可能的結(jié)構(gòu)都提供參數(shù)先驗(yàn)分布，然而結(jié)構(gòu)數(shù)目眾多，無(wú)法一一羅列。在實(shí)際中，人們往往規(guī)定一個(gè)等價(jià)樣本量8和一個(gè)先驗(yàn)貝葉斯旺Bs，利用下式得到P(0BIBs)的超參數(shù)8亦:8jk=8PB(Xi=kI兀i=j)。BIC評(píng)分，即貝葉斯信息準(zhǔn)則是在大樣本前提下對(duì)邊緣似然函數(shù)的一種近似，它有明確直觀的意義，而且使用方便，是實(shí)際中最常用的評(píng)分函數(shù)。dlogP(910)澆logP(910,0*)一一logm2這就是模型結(jié)構(gòu)0的BIC評(píng)分，記為BIC(°19)。BIC評(píng)分的第一項(xiàng)是模型0的優(yōu)參對(duì)數(shù)似然度，它度量的是結(jié)構(gòu)0與數(shù)據(jù)9的擬合程度。第二項(xiàng)是一個(gè)關(guān)于模型復(fù)雜度的罰項(xiàng)。若僅僅依據(jù)優(yōu)參似然度來(lái)選擇模型，會(huì)選到最復(fù)雜的完全貝葉斯網(wǎng)絡(luò)，導(dǎo)致過度擬合。由于附加了一個(gè)模型復(fù)雜度的罰項(xiàng)，BIC有效地避免了過度擬合，直觀上，基于BIC評(píng)分選擇模型就是要選擇既與數(shù)據(jù)擬合，又比較簡(jiǎn)單的模型。MDL評(píng)分它是最短描述長(zhǎng)度(minimumdescriptionlength)的簡(jiǎn)稱。這個(gè)準(zhǔn)則的基本思想如下：數(shù)據(jù)分析的目的是要找出蘊(yùn)含在數(shù)據(jù)中的規(guī)律，然后可以利用它們對(duì)數(shù)據(jù)進(jìn)行壓縮，從而降低數(shù)據(jù)的編碼(描述)長(zhǎng)度，所以，用貝葉斯網(wǎng)分析數(shù)據(jù)是否成功可以用數(shù)據(jù)和模型的編碼總長(zhǎng)度來(lái)度量。AIC評(píng)分它是Akaike信息準(zhǔn)則的簡(jiǎn)稱，他假設(shè)數(shù)據(jù)9是從一個(gè)概率分布P(X)中進(jìn)行獨(dú)立同分布抽樣而得到的。AIC評(píng)分的出發(fā)點(diǎn)是要找一個(gè)貝葉斯網(wǎng)B*=(C*,0*)，使得P(X)與P(X)之間°* B*的KL距離最短，即KL(P,P「<KL(P,P),VB，在一定光滑條件下做大樣本近似，可得如下結(jié)論，即B*的結(jié)構(gòu)匚*應(yīng)該滿足：AIC(C*19)>AIC(C19),V。，其中，AIC(C19)=logP(91。,0*)-dAIC評(píng)分與BIC評(píng)分都是優(yōu)參對(duì)數(shù)似然度加一個(gè)罰項(xiàng)，因此都稱為罰項(xiàng)似然度。MDL也是罰項(xiàng)似然度。HVL評(píng)分罰項(xiàng)的作用是防止過度擬合，還有一種防止過度擬合的方法，它的基本思想是把數(shù)據(jù)9隨機(jī)地分成訓(xùn)練數(shù)據(jù)9和驗(yàn)證數(shù)據(jù)9。對(duì)于一個(gè)模型結(jié)構(gòu)C，首先基于訓(xùn)練數(shù)據(jù)對(duì)其參數(shù)進(jìn)行t v估計(jì)，得到一個(gè)貝葉斯網(wǎng)(C,01)，然后計(jì)算驗(yàn)證數(shù)據(jù)9v對(duì)數(shù)似然度：HVL笆IS,9t)=logP(9I。,01)。這就是HVL評(píng)分函數(shù)。CVL評(píng)分，即交叉驗(yàn)證它的基本思想是多次計(jì)算模型的hvl評(píng)分，而每次都按照不同方式將9劃分為9t和9,然后計(jì)算各次所得評(píng)分的平均值，并將其作為模型的最后評(píng)分。CVL評(píng)分比HVL評(píng)分更具魯棒性，但其計(jì)算復(fù)雜度也高出HVL評(píng)分?jǐn)?shù)倍。在大樣本情況下，HVL準(zhǔn)則，CVL準(zhǔn)則都與AIC準(zhǔn)則等價(jià)。典型算法介紹：三階段算法：第一階段：Drafting，計(jì)算每對(duì)節(jié)點(diǎn)間的互信息，建立完整的無(wú)向圖；第二階段：Thickening，如果節(jié)點(diǎn)對(duì)不是d-分割的話，把這一點(diǎn)對(duì)加入到邊集中；第三階段：Thinning，檢察邊集中的每個(gè)點(diǎn)對(duì)，如果兩個(gè)節(jié)點(diǎn)是d-分割的，則移走這條邊。K2算法：K2算法用貪婪搜索處理模型選擇問題：先定義一種評(píng)價(jià)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)劣的評(píng)分函數(shù)，再?gòu)囊粋€(gè)網(wǎng)絡(luò)開始，根據(jù)事先確定的最大父節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)次序，選擇分值最高的節(jié)點(diǎn)作為該節(jié)點(diǎn)的父節(jié)點(diǎn)。K2算法使用后驗(yàn)概率作為評(píng)分函數(shù)：p(DIB)=rfscore(i,pa)i=1f 「(々「「(q，+nl其中score(i,pa)= I i 11 j 4]i 尸1「VN)k=1 E)K2算法偽代碼:k2(X,p,p,9)輸入：X={X1,X2，...,XJ 一組變量p 一個(gè)變量順序（設(shè)它與變量下標(biāo)一致）p 變量父親節(jié)點(diǎn)個(gè)數(shù)的上界9 一組完整的數(shù)據(jù)輸出：一個(gè)貝葉斯網(wǎng)匚J由節(jié)點(diǎn)X1，X2，...,Xn組成的無(wú)邊圖forj=1ton兀j7；VidJCH（<Xj，兀j>l9）;while（true）iJargmaxCH（<X,兀u{X}>l9）5吧 jjiV JCH（<Xj，兀ju{X}>l9）if（V>Vand仇jl<p）9 J%;兀jJ兀.u{X.};在9中加邊X.TXj；elsebreak;endifendwhileendfor估計(jì)C的參數(shù)^return（C用）;K2的出發(fā)點(diǎn)是一個(gè)包含所有節(jié)點(diǎn)、但卻沒有邊的無(wú)向圖。在搜索過程中，K2按順序逐個(gè)考察P中的變量，確定其父親節(jié)點(diǎn)，然后添加相應(yīng)的邊。對(duì)某一變量X，假設(shè)K2已經(jīng)j找到了它的一些父親節(jié)點(diǎn)兀j。如果l氣」<P，即Xj的父親節(jié)點(diǎn)個(gè)數(shù)還未達(dá)到上界p，那么就要繼續(xù)為它尋找父節(jié)點(diǎn)，具體做法是首先考慮哪些在P中排在Xj之前，但卻還不是Xj的父親節(jié)點(diǎn)的變量，從這些變量中選出Xj,它使得新家族CH評(píng)分七wJCHKXj.D{.}>19)達(dá)到最大；然后將Vnew與舊家族評(píng)分比較：如果Vnew>Void，則把X〔添加為Xj的父節(jié)點(diǎn)；否則停止為Xj尋找父親節(jié)點(diǎn)。Hill-climbing算法爬山法的目標(biāo)是要找出評(píng)分最高的模型，它從一個(gè)初始模型出發(fā)開始搜索，初始模型一般設(shè)為無(wú)邊模型，在搜索的每一步，它首先用搜索算子對(duì)當(dāng)前模型進(jìn)行局部修改，得到一系列候選模型；然后計(jì)算每個(gè)候選模型的評(píng)分，并將最優(yōu)候選模型與當(dāng)前模型進(jìn)行比較；若最優(yōu)候選模型的評(píng)分大，則以它為下一個(gè)模型，繼續(xù)搜索，否則，就停止搜索，并返回當(dāng)前模型。搜索算子有三個(gè)：加邊、減邊和轉(zhuǎn)邊。加邊和減邊算子的使用有個(gè)前提，就是不能在網(wǎng)絡(luò)中形成有向圈。爬山法可以使用任何評(píng)分函數(shù)。不同的評(píng)分函數(shù)有不同的要求：CH評(píng)分要求關(guān)于先驗(yàn)參數(shù)分布的超參數(shù)，而HVL及CVL評(píng)分則要求把數(shù)據(jù)分成訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)。因此，需要處理的算法細(xì)節(jié)也有所不同。爬山算法的偽代碼如下：LearnBN_HC(X,9,f,匚0)輸入：X 一組變量 9 一組關(guān)于X的完整數(shù)據(jù)f 一個(gè)罰項(xiàng)似然度評(píng)分函數(shù)；C0 一個(gè)初始貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)輸出：一個(gè)貝葉斯網(wǎng)絡(luò)1U。匚0；BjQ的參數(shù)的最大似然估計(jì)oldScoreJf(匚,019)；while(true)匚*Jnull;0*Jnull;newScoreJ sfor(每個(gè)對(duì)匚做一次加邊、減邊或轉(zhuǎn)邊而得到的模型結(jié)構(gòu)匚')0'J'的參數(shù)的最大似然估計(jì)；tempScoreJf(匚',0'19);if(tempScore>newScore)匚*J。';0*J0';newScoreJtempScore;endifendfor12if(newScore>oldScore)

。J。*;0jO*;oldScoreJnewScore;elsereturn(。,。);endifendwhile三、 貝葉斯網(wǎng)缺值數(shù)據(jù)下的結(jié)構(gòu)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)缺值數(shù)據(jù)下的結(jié)構(gòu)學(xué)習(xí)算法主要有SEM(structureEMlearningalgorithm)算法。它的基本思想是：從某初始模型結(jié)構(gòu)。。和參數(shù)O0出發(fā)開始迭代，在進(jìn)行了t次迭代得到了(。t,Ot)后，第t+1次迭代由以下兩個(gè)步驟組成：⑴基于(匚t,Ot)對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整；(2)基于修補(bǔ)后的完整數(shù)據(jù)9t對(duì)模型及參數(shù)進(jìn)行一部?jī)?yōu)化。得到(匚t+1,01