貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)

Outlines貝葉斯網(wǎng)的引入圖表示的引入貝葉斯網(wǎng)作為框架對(duì)其他模型的分析圖論觀點(diǎn)和概率論觀點(diǎn)的對(duì)應(yīng)貝葉斯網(wǎng)上的推理被證明是NPC，變量消元法(Poole1996)貝葉斯網(wǎng)的學(xué)習(xí)分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)貝葉斯網(wǎng)的引入聯(lián)合概論分布隨著變量數(shù)量指數(shù)增長(zhǎng)利用問(wèn)題中的獨(dú)立性簡(jiǎn)化分布的表示對(duì)于任意的，如果存在，則得到了一個(gè)聯(lián)合概論分布的一個(gè)分解，使得原來(lái)的指數(shù)級(jí)變?yōu)?/p>

圖表示的引入每個(gè)變量表示為一個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)，從中向X引一條有向邊在語(yǔ)義上，使聯(lián)合概率分布的一種表示優(yōu)點(diǎn)：雖然沒(méi)有進(jìn)一步減少?gòu)?fù)雜度，但為概論推理提供了方便，有利于計(jì)算機(jī)處理，并且易于理解

貝葉斯網(wǎng)框架對(duì)其他模型的解釋Na?veBayesTAN圖論觀點(diǎn)和概率論觀點(diǎn)的對(duì)應(yīng)定理(局部馬爾可夫性):在一個(gè)貝葉斯網(wǎng)中，給定變量X的父節(jié)點(diǎn)，則X條件獨(dú)立于他的所有非后代節(jié)點(diǎn)：貝葉斯網(wǎng)上的推理推理是實(shí)際上是一個(gè)計(jì)算過(guò)程：在給出某些變量的取值的條件下，計(jì)算貝葉斯網(wǎng)絡(luò)中另外一些變量的后驗(yàn)概率分布如在Alarm網(wǎng)絡(luò)中，如已知MaryCall變量的值計(jì)算發(fā)生地震的概率，即計(jì)算的值。其中MaryCall被稱(chēng)為證據(jù)變量，Earthquake稱(chēng)為查詢(xún)變量。推理的分類(lèi)根據(jù)查詢(xún)變量和證據(jù)變量的位置不同，后驗(yàn)假設(shè)問(wèn)題又分為四種不同類(lèi)型:1，從結(jié)果到原因的診斷推理，如已知Mary打過(guò)電話(huà)，推斷發(fā)生地震的概率。2，從原因到結(jié)果的預(yù)測(cè)推斷，如已知發(fā)生盜竊（Burglary=True），推斷接到Mary電話(huà)的概率。3，在統(tǒng)一結(jié)果的不同原因之間的原因關(guān)聯(lián)推理，如已知鈴響（Alarm=true）和發(fā)生了地震（Earthquake=true），推斷同時(shí)發(fā)生盜竊的概率。4，包含多種上述類(lèi)型的混合推理，如接到John的電話(huà)（JohnCall=true）的同時(shí)知道發(fā)生了地震（Earthquake=true），推斷鈴響的概率。無(wú)論何種類(lèi)型的推理問(wèn)題，都可通過(guò)將全局聯(lián)合概率分布中的某些項(xiàng)相加獲得。X如果代表查詢(xún)變量，e為證據(jù)變量的取值，Y為其余變量集合。那么查詢(xún)變量概率分布可以通過(guò)

公式獲得。有了上式，我們可以得到一個(gè)解決推理問(wèn)題的算法。以一個(gè)鏈狀的貝葉斯網(wǎng)絡(luò)為例已知

P(A)P(B|A)P(C|B)P(D|C)計(jì)算P(D)ABCD根據(jù)公式我們有很自然，我們可以將上式變?yōu)橛?jì)算P(D)方法如下1，CPT是貝葉斯網(wǎng)絡(luò)的條件概率分布集合CPT={P(A)，P(B|A)，P(C|B)，P(D|C)}2，從CPT中刪去含有A的函數(shù)P(A)，P(B|A);加入一個(gè)新函數(shù)得到新的CPT={f(B)，P(C|B)，P(D|C)}3，從CPT中刪去含有B的函數(shù)f(B)，P(C|B);加入一個(gè)新函數(shù)得到新的CPT={f(C)，P(D|C)}4,從CPT中刪去含有B的函數(shù)f(B)，P(C|B);加入一個(gè)新函數(shù)得到新的CPT={f(D)}得到的f(D)就是所求的P(D)變量消元法將上述的算法一般化，就得到了一種常用的，有效的貝葉斯網(wǎng)絡(luò)上的推理算法：變量消元法算法復(fù)雜度空間復(fù)雜度O(n)時(shí)間復(fù)雜度 每一次消元代價(jià) 總的代價(jià)即為所有非查詢(xún)節(jié)點(diǎn)消元代價(jià)之和 易見(jiàn)是NPC貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)參數(shù)學(xué)習(xí)和結(jié)構(gòu)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)在結(jié)構(gòu)已知且數(shù)據(jù)完整的情況下，參數(shù)學(xué)習(xí)就是在數(shù)據(jù)上統(tǒng)計(jì)滿(mǎn)足條件的樣本數(shù)目，例在貝葉斯網(wǎng)絡(luò)Bn中學(xué)習(xí)一個(gè)父節(jié)點(diǎn)為Parent(x)的節(jié)點(diǎn)X的條件概率表，只要計(jì)算數(shù)據(jù)集中頻率f(X=k|parenti(X)=j)，方法為統(tǒng)計(jì)數(shù)據(jù)集中滿(mǎn)足X=k，Parent(X)=j的樣本數(shù)目，然后計(jì)算在所有k，j取值中所占比例，作為P(X|parent(X))中的一項(xiàng)填入條件概率表中。ExamplefortrainingBNBuycomputerageincomestudentCredit-ratingExamplefortrainingBN數(shù)據(jù)不完整的BN網(wǎng)絡(luò)參數(shù)學(xué)習(xí) 一般使用EM算法Loop1，使用學(xué)習(xí)好的參數(shù)將不完整數(shù)據(jù)補(bǔ)充完整2，利用補(bǔ)充好的數(shù)據(jù)學(xué)習(xí)參數(shù)3，ifcondition==false gotoloop

貝葉斯網(wǎng)的結(jié)構(gòu)學(xué)習(xí)基于評(píng)分-搜索結(jié)構(gòu)學(xué)習(xí)一般分為：模型選擇模型優(yōu)化模型選擇幾種模型選擇參數(shù)：Cooper-Herskovits評(píng)分(CH)貝葉斯信息準(zhǔn)則(BIC)Akaike信息準(zhǔn)則(AIC)模型優(yōu)化實(shí)際為搜索一個(gè)在某種評(píng)分標(biāo)準(zhǔn)下的最優(yōu)結(jié)構(gòu)窮舉法回溯分支界定啟發(fā)式搜索爬山法貪心策略的應(yīng)用需要用到隨機(jī)策略缺點(diǎn)：不能找到全局最優(yōu)解啟發(fā)式搜索K2輸入：