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

《貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)總結(jié)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、貝葉斯網(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)就是對給定的數(shù)據(jù)集，找到一個與數(shù)據(jù)集擬合最好的網(wǎng)絡(luò)。首先定義一個隨機變量，表示網(wǎng)絡(luò)結(jié)構(gòu)的不確定性，并賦予先驗概率分布。然后計算后驗概率分布。根據(jù)Bayesian定理有其中是一個與結(jié)構(gòu)無關(guān)的正規(guī)化常數(shù)，是邊界似然。于是確定網(wǎng)絡(luò)結(jié)構(gòu)的后驗分布只需要為每一個可能的結(jié)構(gòu)計算數(shù)據(jù)的邊界似然。在無約束多項分布、參數(shù)獨立、采用Dirichlet先驗和數(shù)據(jù)完整的前提下，數(shù)據(jù)的邊界似然正好等于每一個（i，j）對的邊界似然的乘積，即二、貝葉斯網(wǎng)絡(luò)完整數(shù)據(jù)集下結(jié)構(gòu)學(xué)習(xí)方法貝葉斯網(wǎng)絡(luò)建模一般有三種方法：1）依靠專家建模；2）從數(shù)

2、據(jù)中學(xué)習(xí)；3）從知識庫中創(chuàng)建。在實際建模過程中常常綜合運用這些方法，以專家知識為主導(dǎo)，以數(shù)據(jù)庫和知識庫為輔助手段，揚長避短，發(fā)揮各自優(yōu)勢，來保證建模的效率和準(zhǔn)確性。但是，在不具備專家知識或知識庫的前提下，從數(shù)據(jù)中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)模型結(jié)構(gòu)的研究顯得尤為重要。常用的結(jié)構(gòu)學(xué)習(xí)方法主要有兩類，分別是基于依賴性測試的學(xué)習(xí)和基于搜索評分的學(xué)習(xí)。第一類方法是基于依賴性測試的方法，它是在給定數(shù)據(jù)集D中評估變量之間的條件獨立性關(guān)系，構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)。基于條件獨立測試方法學(xué)習(xí)效率最好，典型的算法包括三階段分析算法（TPDA）。基于依賴性測試的方法比較直觀，貼近貝葉斯網(wǎng)絡(luò)的語義，把條件獨立性測試和網(wǎng)絡(luò)結(jié)構(gòu)的

3、搜索分離開，不足之處是對條件獨立性測試產(chǎn)生的誤差非常敏感。且在某些情況下條件獨立性測試的次數(shù)相對于變量的數(shù)目成指數(shù)級增長。第二類方法是基于評分搜索的方法，其原理是在所有節(jié)點的結(jié)構(gòu)空間內(nèi)按照一定的搜索策略及評分準(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算法等。基于搜索評分的方法是一種統(tǒng)計驅(qū)動的方法，試圖在準(zhǔn)確性、稀疏性、魯棒性等多個因素之間找個平衡點。但由于搜索方法的先天弱點，導(dǎo)致用搜索評分的方法不一定能找到最好的結(jié)構(gòu)，但

4、是應(yīng)用范圍很廣。當(dāng)觀察到的數(shù)據(jù)足夠充分且計算次數(shù)足夠多時，基于搜索評分的方法和基于依賴性測試的方法都可以學(xué)到“正確”的網(wǎng)絡(luò)結(jié)構(gòu)。此外，有人結(jié)合上述兩種方法，提出了一些混合算法，這類算法首先利用獨立性測試降低搜索空間的復(fù)雜度，然后執(zhí)行評分搜索找到最佳網(wǎng)絡(luò)，如稀疏候選算法（sparsecandidate）及MMHC（max-minhill-climbing）算法等。1.基于依賴性測試結(jié)構(gòu)學(xué)習(xí)方法基于依賴性測試的結(jié)構(gòu)學(xué)習(xí)算法將貝葉斯網(wǎng)絡(luò)看作是編碼了變量間獨立性關(guān)系的圖結(jié)構(gòu)。它的核心思想是：通過樣本集D驗證條件獨立性I（Xi，Xj

5、C）是否成立，若成立，則在網(wǎng)絡(luò)S中節(jié)點Xi和Xj被C有向

6、分割，節(jié)點Xi和Xj之間不存在邊，若不成立，變量Xi和Xj是依賴的，網(wǎng)絡(luò)中節(jié)點Xi和Xj之間存在邊。然后，利用節(jié)點集之間的條件獨立性，建造一個有向無環(huán)圖，以盡可能多地覆蓋這些條件獨立性。常用的獨立性檢驗的方法有檢驗和基于互信息的檢驗方法?；谝蕾囆詼y試的學(xué)習(xí)方法學(xué)習(xí)效率較高，而且能夠獲得全局最優(yōu)解；但存在以下問題：1.判斷兩個節(jié)點是否獨立或條件獨立是困難的，變量間條件獨立性檢驗的次數(shù)是隨著變量的個數(shù)的增加指數(shù)級增長的；2.高階的條件獨立性檢驗的結(jié)果不夠可靠。1993年Sprites等提出的SGS算法是典型的以條件獨立性測試確定拓?fù)浣Y(jié)構(gòu)的算法。該算法從無向完全圖出發(fā)，如果相節(jié)點間存

7、在無向分割集，則刪除它們間的邊；然后通過統(tǒng)計測試來確定剩余邊的方向。2002年，Cheng將信息論與統(tǒng)計測試相結(jié)合，使用相互信息代替了條件獨立性測試。經(jīng)過Drafting、Thickening、Thinning三個步驟，通過計算相互信息量來確定節(jié)點間的條件獨立性。從而構(gòu)造出多連接有向圖模型。2.基于評分搜索的結(jié)構(gòu)學(xué)習(xí)方法：貝葉斯網(wǎng)絡(luò)基于評分搜索的結(jié)構(gòu)學(xué)習(xí)方法主要包括兩步:模型選擇和模型優(yōu)化。模型選擇部分要制定模型選擇準(zhǔn)則，即評分函數(shù),目前較常用的幾個評分函數(shù)如下：最優(yōu)參數(shù)對數(shù)似然函數(shù)，CH評分，BIC評分等，還有MDL（minimumdescriptionlength）,AIC(

8、Akaikeinformationcriterion)評分函數(shù)，HVL（holdoutvalidationlikelihood）評分（驗證數(shù)據(jù)似然度）。CVL（crossvalidationlikelihood）評分（交叉驗證）。模型優(yōu)化就是要根據(jù)模型選擇準(zhǔn)則，即評分函數(shù)，選擇出評分最高的網(wǎng)絡(luò)結(jié)構(gòu)，也就是搜索策略問題。從所有可能的網(wǎng)絡(luò)結(jié)構(gòu)空間搜索最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)被證明為NP-hard問題，所以一般使用啟發(fā)式搜索算法，主要有K2，hill-climbing算法；隨機重復(fù)爬山法（