貝葉斯網(wǎng)絡(luò)教材

第5章貝葉斯網(wǎng)絡(luò)

1貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò)(BayesianNetworks)結(jié)合圖論和統(tǒng)計(jì)學(xué)方面的知識(shí)，提供了一種自然表達(dá)因果信息的方法，用于表達(dá)隨機(jī)變量之間復(fù)雜的概率不確定性，發(fā)現(xiàn)數(shù)據(jù)間的潛在關(guān)系。本章介紹如下幾個(gè)方面的內(nèi)容：貝葉斯網(wǎng)絡(luò)基本概念不確定性推理與聯(lián)合概率分布貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系貝葉斯網(wǎng)絡(luò)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)分類器2引言貝葉斯網(wǎng)絡(luò)將圖論和統(tǒng)計(jì)學(xué)相結(jié)合，用于表達(dá)隨機(jī)變量之間復(fù)雜的概率不確定性，發(fā)現(xiàn)數(shù)據(jù)間的潛在關(guān)系。優(yōu)點(diǎn)：(1)知識(shí)表示形式更加直觀。(2)對(duì)于問題域的建模，當(dāng)條件或行為等發(fā)生變化時(shí)，不需要修正模型。(3)以圖形化表示隨機(jī)變量間的聯(lián)合概率，處理不確定性信息。(4)沒有確定的輸入或輸出結(jié)點(diǎn)，結(jié)點(diǎn)之間相互影響，可以用于估計(jì)預(yù)測(cè)。(5)將知識(shí)表示與知識(shí)推理結(jié)合統(tǒng)一為整體。1988年，Pearl建立了貝葉斯網(wǎng)基礎(chǔ)理論體系，將概率理論和圖論有機(jī)結(jié)合，用一種緊湊的形式表示聯(lián)合概率分布。3貝葉斯網(wǎng)絡(luò)基本概念給定一個(gè)隨機(jī)變量集X={X1,X2,…,Xn}，其中Xi是一個(gè)m維向量。貝葉斯網(wǎng)絡(luò)說明X上的聯(lián)合條件概率分布。定義為G是有向無環(huán)圖，節(jié)點(diǎn)分別對(duì)應(yīng)于有限集X中的隨機(jī)變量X1,X2,…,Xn

，每條弧代表一個(gè)函數(shù)依賴關(guān)系。如果有一條由變量Y到X的弧，則Y是X的雙親(直接前驅(qū))，X是Y的后繼。Xi的所有雙親變量用集合Pa(Xi)表示。一旦給定雙親，圖G中的每個(gè)變量就與其非后繼節(jié)點(diǎn)相獨(dú)立。代表用于量化網(wǎng)絡(luò)的一組參數(shù)。對(duì)于Xi的取值xi，參數(shù)貝葉斯網(wǎng)絡(luò)表明變量集合X上的聯(lián)合條件概率分布：4貝葉斯網(wǎng)絡(luò)基本概念貝葉斯網(wǎng)絡(luò)提供一種方便表示因果知識(shí)的途徑。網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)可以選作“輸出”節(jié)點(diǎn)，代表類標(biāo)號(hào)屬性?？梢杂卸鄠€(gè)輸出節(jié)點(diǎn)。分類過程返回類標(biāo)號(hào)屬性的概率分布，預(yù)測(cè)每個(gè)類的概率。5不確定性推理與聯(lián)合概率分布不確定性的主要來源：⑴領(lǐng)域?qū)＜覍?duì)自己掌握知識(shí)的不確定性；⑵所要建模的領(lǐng)域本身內(nèi)在的不確定性；⑶知識(shí)工程師試圖翻譯、表示知識(shí)所產(chǎn)生的不確定性；⑷關(guān)于知識(shí)自身的精確性和知識(shí)獲取方面存在的不確定性。使用概率方法進(jìn)行不確定性推理的步驟：①將待處理問題域抽象為一組隨機(jī)變量的集合X={X1,X2,…,Xn}；②把關(guān)于該問題的知識(shí)表示為一個(gè)聯(lián)合概率分布P(X)；按照概率論原則進(jìn)行推理計(jì)算。例（Alarm問題）：Pearl教授的家里裝有警鈴，地震和盜竊都可能觸發(fā)警鈴。聽到警鈴后，兩個(gè)鄰居Marry和John可能會(huì)打電話給他。如果Pearl教授接到Mary的電話，說聽到他家警鈴響，那么Pearl教授家遭盜竊的概率是多大?6不確定性推理與聯(lián)合概率分布5個(gè)隨機(jī)變量：盜竊(Burgle，B)接到John的電話(JohnCall，J)地震(EarthQuake，E)接到Marry的電話(MarryCall，M)警鈴響(Alarm，A)7不確定性推理與聯(lián)合概率分布從聯(lián)合概率P(A,B,E,J,M)出發(fā)，先計(jì)算邊緣分布（5.4）得到聯(lián)合概率邊緣化分布：再按照條件概率定義，得到8不確定性推理與聯(lián)合概率分布問題：隨著變量數(shù)目增加，聯(lián)合概率分布的參數(shù)個(gè)數(shù)成指數(shù)級(jí)增長(zhǎng)。n個(gè)二值隨機(jī)變量的聯(lián)合概率分布包含2n-1個(gè)獨(dú)立參數(shù)。當(dāng)變量很多時(shí)，聯(lián)合概率的獲取、存儲(chǔ)和運(yùn)算都十分困難。在六、七十年代，大多數(shù)學(xué)者認(rèn)為概率論不適合于解決人工智能中的不確定性問題。9貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系利用變量間的條件獨(dú)立關(guān)系可以將聯(lián)合概率分布分解成多個(gè)復(fù)雜度較低的概率分布，從而降低模型復(fù)雜度，提高推理效率。例如：由鏈規(guī)則可以把聯(lián)合概率分布P(A,B,E,J,M)改寫為：

獨(dú)立參數(shù)：1+2+4+8+16=31E與B相互獨(dú)立，即P(E|B)=P(E)給定A時(shí)，J與B和E相互獨(dú)立，即P(J|B,E,A)=P(J|A)給定A時(shí)，M與J、B和E都相互獨(dú)立，即P(M|J,A,B,E)=P(M|A)則有：獨(dú)立參數(shù)：l+2+4+2+2=1110貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系利用鏈規(guī)則將包含n個(gè)變量的聯(lián)合分布寫為：

對(duì)于任意Xi，如果存在Pa(Xi)∈{X1，…，Xi-1}，使得己知Pa(Xi)條件下，Xi與{X1，…，Xi-1}中的其它變量條件獨(dú)立，即則聯(lián)合概率分布可改寫為獨(dú)立性可以減少表示聯(lián)合概率分布所需的信息量。獨(dú)立性斷言通常來源于領(lǐng)域知識(shí)。貝葉斯網(wǎng)絡(luò)中存在三類獨(dú)立關(guān)系：條件獨(dú)立因果影響?yīng)毩h(huán)境獨(dú)立11貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系(一)條件獨(dú)立貝葉斯網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)表達(dá)節(jié)點(diǎn)間的條件獨(dú)立關(guān)系。三種局部結(jié)構(gòu)順連(serialconnection)分連(divergingconnection)匯連(convergingconnection)12貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系(二)有向分離和條件獨(dú)立貝葉斯網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的條件獨(dú)立關(guān)系可由有向分離來判斷。定義5.1設(shè)E為節(jié)點(diǎn)集合，X和Y是不在E中的兩個(gè)節(jié)點(diǎn)。X和Y之間的通路α如果滿足下面條件之一，則稱α被E所阻塞1.α上存在一個(gè)順連節(jié)點(diǎn)Z，且Z在E中；2.α上存在一個(gè)分連節(jié)點(diǎn)Z，且Z在E中；3.α上存在一個(gè)匯連節(jié)點(diǎn)Z，且Z和Z的后代節(jié)點(diǎn)均不在E中。13貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系定義5.2X，Y，E是三個(gè)互不相交的節(jié)點(diǎn)集，說E有向分離X和Y，當(dāng)且僅當(dāng)X和Y之間的通路都被E所阻塞。推論5.3設(shè)X和Y為貝葉斯網(wǎng)絡(luò)中的兩個(gè)變量。Z為貝葉斯網(wǎng)絡(luò)中一個(gè)不包含X和Y的節(jié)點(diǎn)集合。如果Z分離X和Y，則X和Y在給定Z的條件下相互獨(dú)立。推論5.4一個(gè)節(jié)點(diǎn)的馬爾科夫覆蓋包括該節(jié)點(diǎn)的父節(jié)點(diǎn)，子節(jié)點(diǎn)，以及子節(jié)點(diǎn)的父節(jié)點(diǎn)。推論5.5在一個(gè)貝葉斯網(wǎng)中，給定變量X的馬爾可夫覆蓋時(shí)，則X條件獨(dú)立于網(wǎng)絡(luò)中所有其它變量。推論5.6在一個(gè)貝葉斯網(wǎng)中，給定變量X的父節(jié)點(diǎn)Pa(X)，則X條件獨(dú)立于它的所有非后代節(jié)點(diǎn)。14貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系(三)因果影響?yīng)毩?causalindependence)

因果影響?yīng)毩⒅傅氖嵌鄠€(gè)原因獨(dú)立地影響同一個(gè)結(jié)果。定義5.7節(jié)點(diǎn)Y的各個(gè)父親節(jié)點(diǎn)X1,X2,…,Xn對(duì)于Y是因果影響?yīng)毩⒌?，如果?duì)應(yīng)于X1,X2,…,Xn存在和Y有相同取值范圍的隨機(jī)變量，并且下面兩個(gè)條件成立：1.對(duì)任意i，依賴于Xi，在Xi已知條件下，獨(dú)立于所有其它的和(j≠i)；2.在ΩY上存在一個(gè)滿足交換律和結(jié)合律的二元算子*，使得15貝葉斯網(wǎng)絡(luò)中的獨(dú)立關(guān)系(四)環(huán)境獨(dú)立(contextindependence)環(huán)境獨(dú)立是指在特定環(huán)境下才成立的條件獨(dú)立關(guān)系。一個(gè)環(huán)境是一組變量及其取值的組合。設(shè)環(huán)境中涉及變量的集合用C表示，C的一種取值用c表示，則C=c表示一個(gè)環(huán)境。定義5.8設(shè)X，Y，Z，C是4個(gè)兩兩交空的變量集合，如果

P(X,Y,Z,C=c)>0且P(X|Y,Z,C=c)=P(X|Z,C=c)則稱X,Y在環(huán)境C=c下關(guān)于Z條件獨(dú)立。若Z為空，則稱X,Y在環(huán)境C=c下環(huán)境獨(dú)立。16貝葉斯網(wǎng)絡(luò)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)由結(jié)構(gòu)(有向無環(huán)圖)和參數(shù)(條件概率)兩部分構(gòu)成，分別用于定性與定量地描述依賴關(guān)系。網(wǎng)絡(luò)中的有向邊具有因果語義。貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的核心問題是結(jié)構(gòu)學(xué)習(xí)，包括結(jié)構(gòu)和數(shù)據(jù)集參數(shù)。有時(shí)網(wǎng)絡(luò)學(xué)習(xí)和結(jié)構(gòu)學(xué)習(xí)不加區(qū)分。(一)結(jié)構(gòu)學(xué)習(xí)目標(biāo)是基于訓(xùn)練數(shù)據(jù)找到數(shù)據(jù)匹配程度最高的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。無約束貝葉斯網(wǎng)絡(luò)可歸結(jié)為在給定數(shù)據(jù)集T后，尋找具有極大似然P(G|T)的結(jié)構(gòu)G的問題。有n個(gè)變量的問題域，對(duì)應(yīng)的網(wǎng)結(jié)構(gòu)空間為n個(gè)結(jié)點(diǎn)構(gòu)成的所有可能的有向無環(huán)圖，結(jié)構(gòu)空間大小是n的指數(shù)次。貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法：基于打分搜索的方法基于依賴關(guān)系分析的方法17貝葉斯網(wǎng)絡(luò)學(xué)習(xí)(1)基于打分搜索的學(xué)習(xí)算法采用某個(gè)評(píng)分標(biāo)準(zhǔn)，評(píng)判網(wǎng)絡(luò)結(jié)構(gòu)反映出的獨(dú)立及依賴關(guān)系和數(shù)據(jù)的匹配程度。給定一個(gè)關(guān)于結(jié)構(gòu)的測(cè)度后，在結(jié)構(gòu)空間中按照一定的搜索策略，依次計(jì)算各結(jié)構(gòu)的測(cè)度值，選擇測(cè)度值最優(yōu)的結(jié)構(gòu)。兩類評(píng)分標(biāo)準(zhǔn)：①

基于編碼理論最小描述長(zhǎng)度(MinimumDescriptionLength，MDL)貝葉斯信息標(biāo)準(zhǔn)(BayesianInformationCriterion，BIC)②源于貝葉斯統(tǒng)計(jì)BDe評(píng)分方法最小描述長(zhǎng)度函數(shù)MDLMDL原理認(rèn)為最優(yōu)模型是總描述長(zhǎng)度最短的模型。貝葉斯網(wǎng)絡(luò)B=<G,θ>描述每一個(gè)樣本Di的概率，按編碼策略對(duì)每個(gè)樣本Di進(jìn)行編碼。網(wǎng)絡(luò)結(jié)構(gòu)G要使得網(wǎng)絡(luò)描述長(zhǎng)度和數(shù)據(jù)D的編碼長(zhǎng)度之和最小，必須在網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性與網(wǎng)絡(luò)結(jié)構(gòu)的準(zhǔn)確性之間確定平衡點(diǎn)。18貝葉斯網(wǎng)絡(luò)學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的MDL測(cè)度由3部分組成：1.網(wǎng)絡(luò)結(jié)構(gòu)的描述長(zhǎng)度：保存網(wǎng)絡(luò)結(jié)構(gòu)G，要記錄各節(jié)點(diǎn)的父節(jié)點(diǎn)的編號(hào)。貝葉斯網(wǎng)絡(luò)包含n個(gè)節(jié)點(diǎn)，|πXi|為節(jié)點(diǎn)Xi的父節(jié)點(diǎn)數(shù)目。網(wǎng)絡(luò)結(jié)構(gòu)的描述長(zhǎng)度是：

2.參數(shù)的描述長(zhǎng)度：為描述局部條件概率表，須存貯每個(gè)節(jié)點(diǎn)的條件概率表的所有參數(shù)。Xi的條件概率表需要存貯|πXi|(|Xi|-1)個(gè)參數(shù)，|Xi|表示變量Xi所有可能狀態(tài)的數(shù)目。存儲(chǔ)每個(gè)參數(shù)，需要logn/2二進(jìn)制位，其中N是訓(xùn)練樣本的數(shù)目。3.數(shù)據(jù)集合的描述長(zhǎng)度：將數(shù)據(jù)D中每個(gè)樣本Di建立Huffman編碼，每個(gè)碼字的確切長(zhǎng)度依賴于P(Di|G,θ)，其概率越大，編碼長(zhǎng)度越小，概率越小，編碼長(zhǎng)度越大。Di的二進(jìn)制編碼長(zhǎng)度近似等于log(1/P(Di|G,θ))。因而數(shù)據(jù)集合的描述長(zhǎng)度為：其中H(Xi|πXi)為條件熵。綜上，結(jié)構(gòu)MDL測(cè)度為：19貝葉斯網(wǎng)絡(luò)學(xué)習(xí)貪婪搜索:

令E表示所有可能添加到網(wǎng)絡(luò)中的候選邊集合，表示邊e加入到網(wǎng)絡(luò)中后評(píng)分函數(shù)的變化。步驟1.選擇一個(gè)網(wǎng)絡(luò)。步驟2.選擇集合E中的邊e，使得，如果找不到滿足條件的邊，則停止，否則繼續(xù)。步驟3.加入邊e到網(wǎng)絡(luò)中，并從集合E中刪除e，轉(zhuǎn)步驟2。MDL優(yōu)缺點(diǎn)：目標(biāo)是結(jié)構(gòu)簡(jiǎn)單、參數(shù)較少的稀疏網(wǎng)絡(luò)具有一致性沒有用到先驗(yàn)知識(shí)對(duì)兩個(gè)具有等價(jià)性的結(jié)構(gòu)，不能保證得到相同MDL測(cè)度值。20貝葉斯網(wǎng)絡(luò)學(xué)習(xí)BDe函數(shù)Heckerman等擴(kuò)展BD(BayesianDirichlet)度量，提出BDe函數(shù)。定義一個(gè)離散變量G表示未知的網(wǎng)絡(luò)結(jié)構(gòu)，其取值范圍是所有可能網(wǎng)絡(luò)結(jié)構(gòu)；估計(jì)G的先驗(yàn)概率P(G)；計(jì)算網(wǎng)絡(luò)結(jié)構(gòu)后驗(yàn)概率P(G|D)和參數(shù)后驗(yàn)概率P(θ|D,G)，并計(jì)算目標(biāo)期望值。BDe函數(shù)取做網(wǎng)絡(luò)結(jié)構(gòu)同數(shù)據(jù)集的聯(lián)合概率分布的對(duì)數(shù)形式：

（5.11）其中P(D|G)稱邊際似然函數(shù)。定義一個(gè)隨機(jī)變量Sh表示網(wǎng)絡(luò)結(jié)構(gòu)對(duì)應(yīng)的狀態(tài)，并賦予先驗(yàn)概率分布P(Sh)。對(duì)任意樣本D，計(jì)算后驗(yàn)概率分布有

其中P(D)是一個(gè)與結(jié)構(gòu)無關(guān)的正規(guī)化常數(shù)，P(D|Sh)是邊界似然。

21貝葉斯網(wǎng)絡(luò)學(xué)習(xí)度量公式如下：先驗(yàn)概率分布的計(jì)算依據(jù)先驗(yàn)知識(shí)。優(yōu)缺點(diǎn)：使用先驗(yàn)知識(shí)，其對(duì)訓(xùn)練數(shù)據(jù)集的依賴性比MDL測(cè)度要低沒有明確地包含結(jié)構(gòu)復(fù)雜性指標(biāo)，會(huì)傾向于選擇較復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。22貝葉斯網(wǎng)絡(luò)學(xué)習(xí)(二)搜索算法搜索算法在某個(gè)評(píng)分函數(shù)下搜索分值最高的網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)數(shù)據(jù)完備時(shí)，搜索算法借助評(píng)分函數(shù)的“可分解性”來提高搜索效率。所謂評(píng)分函數(shù)可分解是指：G的分值可以通過其各個(gè)家族的分值之和求得。家族即一個(gè)節(jié)點(diǎn)和其所有父節(jié)點(diǎn)所構(gòu)成的簡(jiǎn)單圖。搜索算法執(zhí)行過程：從一個(gè)初始的網(wǎng)絡(luò)結(jié)構(gòu)開始，對(duì)當(dāng)前結(jié)構(gòu)進(jìn)行某些的修改；計(jì)算修改后結(jié)構(gòu)的分值，根據(jù)分值決定是否更新結(jié)構(gòu)。定義5.9.

如果給定某一問題領(lǐng)域的各個(gè)變量，用一個(gè)結(jié)點(diǎn)表示其中的一個(gè)變量，由任意兩個(gè)結(jié)點(diǎn)間的無向邊連接構(gòu)成的圖模型，稱為完全潛在圖。定義5.10.

如果變量X、Y和變量集Z之間存在以下關(guān)系：

即在變量集Z已知的條件下，變量Y的狀態(tài)和概率不會(huì)造成對(duì)變量X的影響，稱為在給定變量集Z的前提下，X條件獨(dú)立于Y。23貝葉斯網(wǎng)絡(luò)學(xué)習(xí)定義5.11.設(shè)X、Y和Z為有向無環(huán)圖中3個(gè)互不相交的結(jié)點(diǎn)子集，當(dāng)且僅當(dāng)沒有一條從X中一個(gè)結(jié)點(diǎn)到Y(jié)中一個(gè)結(jié)點(diǎn)的所有路徑之間，存在結(jié)點(diǎn)W滿足下列條件之一：i.每個(gè)匯聚結(jié)點(diǎn)要么是Z中的結(jié)點(diǎn)，要么有子孫在Z中；ii.其它的每個(gè)結(jié)點(diǎn)都不在Z中。滿足以上兩個(gè)條件的路徑是活躍的；否則被稱為Z阻塞。稱在給定條件集Z的情況下，X與Y為d分割。記作d(X；Z；Y)。例：X={X2}和Y={X3}被Z={X1}分割。路徑X2←X1→X3被X3∈Z阻塞；路徑X2←X4→X3也被阻塞，因?yàn)閄4及它的所有子孫都不在Z中。因此，d(X2；X1；X3)。X和Y沒有被d分割，故，d(X2；{X1；X5}；X3)不成立。24貝葉斯網(wǎng)絡(luò)學(xué)習(xí)定理5.1對(duì)網(wǎng)絡(luò)結(jié)構(gòu)中的結(jié)點(diǎn)集X、Y和Z，當(dāng)且僅當(dāng)P(X|Y；Z)=P(X|Z)時(shí)，X與Y為d分割。定理5.2在依賴模型M中，設(shè)X、Y和Z為互不相交的子集，條件獨(dú)立性滿足對(duì)稱性、分解律和交換律等屬性。定理5.3滿足對(duì)稱性、分布律和交換律的依賴模型M，從完整圖中刪除任意條件獨(dú)立性成立的連接(X；Y)，則產(chǎn)生一個(gè)惟一的最小獨(dú)立圖。基于獨(dú)立性測(cè)試的網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法：1.初始化圖結(jié)構(gòu)B(V;A;Θ)；V={V1;V2;…;Vm}；E=Φ；S=Φ；R=Φ。2.對(duì)于每對(duì)結(jié)點(diǎn)Vi;Vj(Vi;Vj∈V)計(jì)算互信息I(Vi;Vj)。按互信息降序排序，將互信息大于某一閾值的結(jié)點(diǎn)對(duì)依次放入到集合S中。3.從集合S中取出第一對(duì)結(jié)點(diǎn)并將其從S中刪除，將相應(yīng)的弧加入到E中(弧的方向由現(xiàn)有的結(jié)點(diǎn)順序所決定)。設(shè)置成由根結(jié)點(diǎn)指向外，把無向圖轉(zhuǎn)換成有向圖。4.從集合S中取出剩余的第一對(duì)結(jié)點(diǎn)并將其從S中刪除，如果該對(duì)結(jié)點(diǎn)之間無開放通路，將對(duì)應(yīng)弧加入到E中，否則將該對(duì)結(jié)點(diǎn)加入到有序集合R中的末端。25貝葉斯網(wǎng)絡(luò)學(xué)習(xí)(三)基于約束的方法(Constraintbased)

通過條件獨(dú)立性測(cè)試來發(fā)現(xiàn)數(shù)據(jù)中暗含的條件獨(dú)立關(guān)系，尋找和這些條件獨(dú)立關(guān)系一致的網(wǎng)絡(luò)結(jié)構(gòu)。在基于約束的方法中，貝葉斯網(wǎng)絡(luò)被看作是編碼了變量間獨(dú)立性關(guān)系的圖結(jié)構(gòu)，是通過一些有效的測(cè)試手段找出數(shù)據(jù)D中各變量間的條件獨(dú)立關(guān)系，再尋找和這些條件獨(dú)立一致的網(wǎng)絡(luò)模型。算法采用互信息和條件互信息進(jìn)行變量之間定量條件獨(dú)立性檢驗(yàn)。對(duì)于給定的閥值ε一般取ε=0.01)，如果I(Xi，Xj|C)<ε，就認(rèn)為Xi和Xj條件獨(dú)立。階段I(畫草圖，Drafting)(1)初始化圖G=(V，E)，V={數(shù)據(jù)集中的所有節(jié)點(diǎn)}，邊集合E={}。列表L={}，R={}；(2)對(duì)每一節(jié)點(diǎn)對(duì)，計(jì)算它們的互信息，并將互信息大于某一閥值的節(jié)點(diǎn)對(duì)按互信息值的大小順序加入到L中；(3)從列表L中取出前兩組節(jié)點(diǎn)對(duì)，將對(duì)應(yīng)的邊加入到邊集E中(邊的方向由節(jié)點(diǎn)序來確定)。(4)從列表L中剩余的節(jié)點(diǎn)對(duì)中取出第一個(gè)點(diǎn)對(duì)，如果這兩個(gè)節(jié)點(diǎn)之間不存在開放路徑(不含碰撞節(jié)點(diǎn)的路徑)，則將其對(duì)應(yīng)的邊加入到E，并將該節(jié)點(diǎn)對(duì)從L中刪除，否則將節(jié)點(diǎn)加入到R中。(5)重復(fù)(4)，直至L為空。

26貝葉斯網(wǎng)絡(luò)學(xué)習(xí)階段II(增厚，Thickening)(6)從R中取出第一個(gè)點(diǎn)對(duì)。找出能夠d-分離該點(diǎn)對(duì)的某一切割集，在該切割集上做CI測(cè)試，如果兩個(gè)節(jié)點(diǎn)條件獨(dú)立，則轉(zhuǎn)下一步；否則用一條邊連接該節(jié)點(diǎn)對(duì)，將該邊加入到邊集E中。(7)重復(fù)(6)，直至R為空。階段III(削減圖，Thinning)(8)對(duì)于E中的每一條邊，如果除這條邊之外在這兩個(gè)節(jié)點(diǎn)之間仍存在開放路徑，則暫時(shí)移走這條邊，并在相應(yīng)的切割集上作CI測(cè)試，如果兩節(jié)點(diǎn)條件獨(dú)立，在E中永久刪除該邊，否則將該邊放回E中。確定切割集設(shè)Xi不是Xj的祖先結(jié)點(diǎn)(否則選擇Xi)，記Xi的父結(jié)點(diǎn)集為πXi，則πXi是Xi和Xj的切割集，按如下方法對(duì)πXi進(jìn)行簡(jiǎn)化：(l)把連接Xi不是Xj且經(jīng)過πXi中節(jié)點(diǎn)的所有開放路徑儲(chǔ)存到Sij中。(2)把D(Xi

,Xj)初始化為空。(3)在Sij中，把路徑上只含有一個(gè)結(jié)點(diǎn)的這個(gè)結(jié)點(diǎn)放入切割集D(Xi,Xj)中；(4)把經(jīng)過這些結(jié)點(diǎn)的路徑從Sij中刪除；(5)返回(1)步，直到?jīng)]有滿足條件的結(jié)點(diǎn)為止；(6)在Sij中，把能夠堵塞最多路徑的πXi中結(jié)點(diǎn)放入切割集D(Xi,Xj)中；(7)在Sij中刪除經(jīng)過這點(diǎn)的路徑；(8)返回(4)步，直到Sij空為止。27貝葉斯網(wǎng)絡(luò)學(xué)習(xí)(四)參數(shù)學(xué)習(xí)

貝葉斯網(wǎng)的條件概率學(xué)習(xí)問題可以歸結(jié)為統(tǒng)計(jì)學(xué)中的參數(shù)估計(jì)問題。實(shí)際應(yīng)用領(lǐng)域中，概率信息獲得方式：從統(tǒng)計(jì)數(shù)據(jù)中學(xué)習(xí)從文獻(xiàn)中查閱咨詢領(lǐng)域?qū)＜页Ｓ脜?shù)學(xué)習(xí)方法：極大似然性估計(jì)MLE(maximumlikelihoodestimation)方法Bayesian方法極大似然性估計(jì)MLE方法基本思想：一個(gè)隨機(jī)實(shí)驗(yàn)可能的結(jié)果有C1,C2,…,Cn，在一次實(shí)驗(yàn)中，結(jié)果Cｍ出現(xiàn)，即Cｍ出現(xiàn)的概率應(yīng)該最大，可將似然函數(shù)P(C|θ)取極大值時(shí)的參數(shù)值θ作為對(duì)參數(shù)的估計(jì)值。給定參數(shù)θ，數(shù)據(jù)D的條件概率P(D|θ)稱為是θ的似然度，記為L(zhǎng)(θ|D)=P(D|θ)。如果固定D而讓?duì)仍谄涠x域上變動(dòng)，那么L(θ|D)就是θ的一個(gè)函數(shù)，稱為θ的似然函數(shù)。28貝葉斯網(wǎng)絡(luò)學(xué)習(xí)參數(shù)θ的最大似然估計(jì)簡(jiǎn)稱MLE，是L(θ|D)達(dá)到最大的那個(gè)取值θ*，即（5.14）三個(gè)假設(shè)前提：1.樣本中的數(shù)據(jù)是完備的；產(chǎn)生事例的概率分布始終相同。2.D中各樣本在給定參數(shù)θ時(shí)相互獨(dú)立，即L(θ|D)=P(D|θ)=∏P(Di|θ)3.每個(gè)樣本Di的條件概率分布P(Di|θ)相同，即P(Di|θ)=P(Dj|θ)(i≠j)MLE方法具有以下性質(zhì)：一致性(consistent)

隨著事例的增多，算法逐漸收斂于最佳可能值。2.漸進(jìn)有效性(asympototicefficiency)

事例越多，接近的程度越好。3.表示靈活性(representationinvariant)

參數(shù)的不同表示形式不影響估計(jì)出的概率分布結(jié)果。29貝葉斯網(wǎng)絡(luò)分類器貝葉斯網(wǎng)絡(luò)用結(jié)點(diǎn)表示變量，有向邊表示變量間的依賴關(guān)系。如果把其中代表類別變量的結(jié)點(diǎn)作為根結(jié)點(diǎn)，其余所有變量都作為它的子結(jié)點(diǎn)時(shí)，貝葉斯網(wǎng)絡(luò)就變成了分類器。樸素貝葉斯分類(NaiveBayesianClassification)

將訓(xùn)練樣本I分解成特征向量X和決策類別變量C。假定一個(gè)特征向量的各分量相對(duì)于決策變量是獨(dú)立的(類條件獨(dú)立)。樸素貝葉斯分類的工作過程：1.用n維特征向量X={x1,x2,…,xn}表示每個(gè)數(shù)據(jù)樣本，用以描述對(duì)該樣本的n個(gè)屬性A1,A2,…,An的度量。2.假定數(shù)據(jù)樣本可以分為m個(gè)類C1,C2,…,Cm。給定一個(gè)未知類標(biāo)號(hào)的數(shù)據(jù)樣本X，樸素貝葉斯分類將其分類到類Ci

，當(dāng)且僅當(dāng)

P(Ci|X)>P(Cj|X)，1≤j≤m，j≠i

（5.17）P(Ci|X)最大的類Ci稱為最大后驗(yàn)假定。由貝葉斯公式可知30貝葉斯網(wǎng)絡(luò)分類器3.只需要P(X|Ci)P(Ci)最大即可。如果類的先驗(yàn)概率未知，可取P(C1)=P(C2)=…=P(Cm)。類的先驗(yàn)概率也可以用P(Ci)=si/s計(jì)算，其中si是類Ci中的訓(xùn)練樣本數(shù)，s是訓(xùn)練樣本總數(shù)。4.如果假定類條件獨(dú)立，可以降低計(jì)算P(X|Ci)的開銷。給定樣本的類標(biāo)號(hào)，若屬性值相互條件獨(dú)立，則有：5.樸素貝葉斯以后驗(yàn)概率作為分類指示

對(duì)每個(gè)類Ci

，計(jì)算P(X|Ci)P(Ci)。把樣本X指派到類Ci的充要條件是

P(X|Ci)P(Ci)>P(X|Cj)P(Cj)，1≤j≤m，j≠i

（5.21）X被分配到使P(X|Ci)P(Ci)最大的類Ci

。31貝葉斯網(wǎng)絡(luò)分類器例5.1使用樸素貝葉斯分類預(yù)測(cè)未知樣本的類標(biāo)號(hào)。給定Playtennis的訓(xùn)練樣本集見表5.3。使用樸素貝葉斯分類來預(yù)測(cè)在＜Outlook=Sunny,Temperature=Hot,Humidity=High,wind=Strong＞的情況下，是否打球。32貝葉斯網(wǎng)絡(luò)分類器解：要分類的未知樣本為：

X=＜Outlook=Sunny,Temperature=Hot,Humidity=High,wind=Strong＞每個(gè)類的先驗(yàn)概率P(Ci)可以根據(jù)訓(xùn)練樣本計(jì)算：P(Playtennis=“yes”)=9/14=0.643P(Playtennis=“no”)=5/14=0.357為計(jì)算P(X|Ci)，i=1,2，先計(jì)算下面的條件概率：P(Outlook=“Sunny”|Playtennis=“yes”)=2/9=0.222P(Outlook=“Sunny”|Playtennis=“no”)=3/5=0.600P(Temperature=“hot”|Playtennis=“yes”)=2/9=0.222P(Temperature=“hot”|Playtennis=“no”)=2/5=0.400P(Humidity=“high”|Playtennis=“yes”)=3/9=0.333P(Humidity=“high”|Playtennis=“no”)=4/5=0.800P(Windy=“Strong”|Playtennis=“yes”)=3/9=0.333P(Windy=“Strong”|Playtennis=“no”)=3/5=0.600利用以上概率，可以得到：P(X|Playtennis

=“yes”)=0.222×0.222×0.333×0.333=0.005P(X|Playtennis=“no”)=0.600×0.400×0.800×0.600=0.115P(X|

Playtennis=“yes”)P(Playtennis=“yes”)=0.005×0.643=0.003P(X|Playtennis=“no”)P(Playtennis=“no”)=0.115×0.357=0.041因此，將樣本X指派給類C2：Playtennis=“no”。即不去打球。33貝葉斯網(wǎng)絡(luò)分類器半樸素貝葉斯分類器(Semi-NaiveBayesianClassifier,SNBC)

依照一定的標(biāo)準(zhǔn)將關(guān)聯(lián)程度較大的特征屬性合并在一起組合成新屬性，各個(gè)組合屬性之間也是相對(duì)于類別屬性相互獨(dú)立的。這里合并并不是真正上的合并，只是在計(jì)算中體現(xiàn)出來，是概念層次上的一個(gè)抽象過程。

SNBC模型限制網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜度。計(jì)算推導(dǎo)過程與樸素貝葉斯相同。34貝葉斯網(wǎng)絡(luò)分類器選擇貝葉斯分類器(SelectiveNa?veBayesianClassifier)

使用屬性集的子集作為決策過程中的屬性結(jié)點(diǎn)，即選擇貝葉斯分類器選擇初始特征的子集作為屬性結(jié)點(diǎn)。它通過搜索特征空間，去掉特征間具有較強(qiáng)依賴關(guān)系的屬性。應(yīng)該著重考慮的問題：l.搜索方向的選擇向前搜索是從空集開始，逐漸添加新的屬性；向后搜索是從整個(gè)屬性集開始，逐漸移走相應(yīng)的屬性。2.搜索策略的選擇。算法考慮新增加的屬性對(duì)分類性能的影響，選取最好的屬性添加到當(dāng)前的屬性集中，然后繼續(xù)下一次選擇。貪婪搜索在最壞情況下的復(fù)雜度為O(m2)。3.各種屬性子集下算法性能的度量準(zhǔn)則采用Leave-one-out技術(shù)從訓(xùn)練集中估計(jì)算法的精度，是交叉驗(yàn)證法中最精確的一種估計(jì)方法。4.停止搜索的標(biāo)準(zhǔn)。當(dāng)對(duì)新添加的任何屬性都不能提高分類精度時(shí)，停止搜索；只要分類精度不減少，就繼續(xù)選擇其他的屬性加入到屬性集