貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)及其應(yīng)用研究

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

1、DOI:10.13203/j.whugis2004.04.008第29卷第4期武漢大學(xué)學(xué)報·信息科學(xué)版Vol.29No.42004年4月GeomaticsandInformationScienceofWuhanUniversityApr.2004文章編號:1671-8860(2004)04-0315-04文獻(xiàn)標(biāo)識碼:A貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)及其應(yīng)用研究111黃解軍萬幼川潘和平(1武漢大學(xué)遙感信息工程學(xué)院,武漢市珞喻路129號,430079)摘要:闡述了貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的內(nèi)容與方法,提出一種基于條件獨立性(CI)測試的啟發(fā)式算法。從完

2、全潛在圖出發(fā),融入專家知識和先驗常識,有效地減少網(wǎng)絡(luò)結(jié)構(gòu)的搜索空間,通過變量之間的CI測試,將全連接無向圖修剪成最優(yōu)的潛在圖,近似于有向無環(huán)圖的無向版。通過汽車故障診斷實例,驗證了該算法的可行性與有效性。關(guān)鍵詞:貝葉斯網(wǎng)絡(luò);結(jié)構(gòu)學(xué)習(xí);條件獨立性;概率推理;圖論中圖法分類號:TP18;TP311貝葉斯網(wǎng)絡(luò)學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)的重要研究內(nèi)述,在具體問題領(lǐng)域,內(nèi)部的變量關(guān)系形成相對穩(wěn)容,也是貝葉斯網(wǎng)絡(luò)構(gòu)建中的關(guān)鍵環(huán)節(jié),大體分為定的結(jié)構(gòu)和狀態(tài)。這種結(jié)構(gòu)的固有屬性確保了結(jié)結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)兩個部分。由于網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)學(xué)習(xí)的可行性,也為結(jié)構(gòu)學(xué)習(xí)提供

3、了基本思路。空間分布隨著變量的數(shù)目和每個變量的狀態(tài)數(shù)量貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是一個網(wǎng)絡(luò)優(yōu)化的過程,其呈指數(shù)級增長,因此,結(jié)構(gòu)學(xué)習(xí)是一個NP難題。目標(biāo)是尋找一種最簡約的網(wǎng)絡(luò)結(jié)構(gòu)來表達(dá)數(shù)據(jù)集為了克服在構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)中計算和搜索的復(fù)雜中變量之間的關(guān)系。對于一個給定問題,學(xué)習(xí)貝[1～5]性,許多學(xué)者進(jìn)行了大量的探索性工作。至葉斯網(wǎng)絡(luò)結(jié)構(gòu)首先要定義變量及其構(gòu)成,確定變今雖然出現(xiàn)了許多成熟的學(xué)習(xí)算法,但由于網(wǎng)絡(luò)量所有可能存在的狀態(tài)或權(quán)植。同時,要考慮先結(jié)構(gòu)空間的不連續(xù)性、結(jié)構(gòu)搜索和參數(shù)學(xué)習(xí)的復(fù)驗知識的融合、評估函數(shù)的選擇和不完備數(shù)據(jù)的雜性、數(shù)據(jù)的不

4、完備性等特點,每種算法都存在一影響等因素。定的局限性。本文提出了一種新算法,不僅可以1.2貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的方法有效地減少網(wǎng)絡(luò)結(jié)構(gòu)的搜索空間,提高結(jié)構(gòu)學(xué)習(xí)近10年來,貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)理論和應(yīng)用取的效率,而且可避免收斂到次優(yōu)網(wǎng)絡(luò)模型的問題。得了較大的進(jìn)展。目前,貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的方法通常分為兩大類:①基于搜索與評分的方1貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的基本理論法,運用評分函數(shù)對網(wǎng)絡(luò)模型進(jìn)行評價。通常是給定一個初始結(jié)構(gòu)(或空結(jié)構(gòu)),逐步增加或刪減1.1貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的內(nèi)容連接邊,改進(jìn)網(wǎng)絡(luò)模型,從而搜索和選擇出一個與貝葉斯網(wǎng)絡(luò)又稱為信念網(wǎng)絡(luò)

5、、概率網(wǎng)絡(luò)或因樣本數(shù)據(jù)擬合得最好的結(jié)構(gòu)。根據(jù)不同的評分準(zhǔn)[6][3,7]果網(wǎng)絡(luò)。它主要由兩部分構(gòu)成:①有向無環(huán)圖則,學(xué)習(xí)算法可分為基于貝葉斯方法的算法、[8](directedacyclicgraph,DAG),即網(wǎng)絡(luò)結(jié)構(gòu),包括基于最大熵的算法和基于最小描述長度的算[1,2]節(jié)點集和節(jié)點之間的有向邊,每個節(jié)點代表一個法。②基于依賴關(guān)系分析的方法,節(jié)點之間變量,有向邊代表變量之間的依賴關(guān)系;②反映依賴關(guān)系的判斷通過條件獨立性(CI)測試來實變量之間關(guān)聯(lián)性的局部概率分布集,即概率參數(shù),現(xiàn),文獻(xiàn)[9,10]描述的算法屬于該類算法。前者通

6、常稱為條件概率表(conditionalprobability在DAG復(fù)雜的情況下,學(xué)習(xí)效率更高,但不能得table,CPT),概率值表示變量之間的關(guān)聯(lián)強度或到一個最優(yōu)的模型;后者在數(shù)據(jù)集的概率分布與[11]置信度。貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是對變量之間的關(guān)系描DAG同構(gòu)的條件下,通常獲得近似最優(yōu)的模型,收稿日期:2004-01-23。項目來源:國家自然科學(xué)基金資助項目(60175022)。316武漢大學(xué)學(xué)報·信息科學(xué)版2004年但運用該方法要求樣本數(shù)據(jù)集具有一定的規(guī)模。同樣,條件互信息I(X,YZ)定義為:I(X,Y

7、Z)=∑p(X,Y,Z

8、)·2貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的啟發(fā)式算X,Y,Zp(X,Y

9、Z)法lg(2)p(X

10、Z)p(Y

11、Z)先假設(shè)所有的節(jié)點之間存在連接,節(jié)點X和Y2.1算法的原理之間連接的潛在性運用條件互信息來計算。在通常貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是通過對給定數(shù)據(jù)集的情況下,設(shè)定一個較小正實數(shù)的閾值ε,當(dāng)學(xué)習(xí)和訓(xùn)練,尋找一種最佳的網(wǎng)絡(luò)來表達(dá)變量之I(X,YZ)≤ε時,稱X與Y被條件集Z進(jìn)行d-間的依賴關(guān)系,即確定變量之間的因果連接集合。分割,即在給定Z的條件下,X條件獨立于Y,從而本文提出一種貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的啟發(fā)式算刪除X與Y之間的連接。經(jīng)過n(n-1)/2次

12、CI法,其基本思路是基于給定數(shù)據(jù)集,通過CI測試,測試,最后由完全潛在圖修剪成稀疏的理想潛在圖。有效地修剪完全潛在圖,得到一個最優(yōu)的無向結(jié)2.2算法實現(xiàn)構(gòu)或最小潛在圖。在給定其他變量子集的情況1)初始化完全潛在圖。下,任何兩個變量X和Y之間的條件獨