貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)和建造

貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)和建造

20世紀(jì)80年代，伯斯基網(wǎng)絡(luò)成功應(yīng)用于專家系統(tǒng)，成為一種流行的方法，用于表達(dá)不確定性知識和論證。近幾年研究者們進(jìn)一步研究直接從數(shù)據(jù)中學(xué)習(xí)并生成Bayesian網(wǎng)絡(luò)的方法,包括Bayesian方法、類Bayesian方法和非Bayesian方法,為Bayesian網(wǎng)絡(luò)用于數(shù)據(jù)采掘和知識發(fā)現(xiàn)開辟了道路。這些新的方法和技術(shù)還在發(fā)展之中,但是已經(jīng)在一些數(shù)據(jù)建模問題中顯示出令人矚目的效果。1局部概率分布Bayesian網(wǎng)絡(luò)是一個帶有概率注釋的有向無環(huán)圖。這個圖模型能表示大變量集合的聯(lián)合概率分布,可以分析大量變量之間的相互關(guān)系,利用Bayesian方法的學(xué)習(xí)和統(tǒng)計推斷功能,實現(xiàn)預(yù)測、分類、聚類、因果分析等數(shù)據(jù)采掘任務(wù)。關(guān)于一組變量X={X1,X2,…,Xn}的Bayesian網(wǎng)絡(luò)由以下兩部分組成:1)一個表示X中變量的條件獨立斷言的網(wǎng)絡(luò)結(jié)構(gòu)S;2)與每一個變量相聯(lián)系的局部概率分布集合P。S是一個有向無環(huán)圖,S中的節(jié)點一對一地對應(yīng)于X中的變量,節(jié)點之間缺省弧線表示條件獨立。S和P定義了X的聯(lián)合概率分布。為了建立Bayesian網(wǎng)絡(luò),第1步,必須確定為建立模型有關(guān)的變量及其解釋。第2步,建立一個表示條件獨立斷言的有向無環(huán)圖。根據(jù)概率乘法公式有p(x)=n∏i=1p(xi|x1,x2,?,xi-1).(1)p(x)=∏i=1np(xi|x1,x2,?,xi?1).(1)用Pai表示變量Xi的父節(jié)點集,則p(x)=n∏i=1p(xi|Ρai).(2)p(x)=∏i=1np(xi|Pai).(2)于是,為了決定Bayesian網(wǎng)絡(luò)的結(jié)構(gòu),需要:1)將變量X1,X2,…,Xn按某種次序排序;2)決定滿足式(2)的父節(jié)點集Pai(i=1,2,…,n)。從原理上說,如何從n個變量中找出適合條件獨立的順序,是一個組合爆炸問題。因為要比較n!種變量順序。不過,通?？梢栽诂F(xiàn)實問題中決定因果關(guān)系,而且因果關(guān)系一般都對應(yīng)于條件獨立的斷言。因此,可以從原因變量到結(jié)果變量劃一個帶箭頭的弧來直觀表示變量之間的因果關(guān)系。第3步,指派局部概率分布p(xi|Pai)。在離散的情形,需要為每一個變量Xi的父節(jié)點集的各個狀態(tài)指派一個分布。顯然,以上各步可能交叉進(jìn)行,而不是簡單的順序進(jìn)行可以完成的。2局部分布函數(shù)及參數(shù)假設(shè)變量組X=(X1,X2,…,Xn)的聯(lián)合概率分布可以編碼在某個網(wǎng)絡(luò)結(jié)構(gòu)S中,即p(x|θs?Sh)=n∏i=1p(xi|Ρai,θi?Sh)?(3)p(x|θs?Sh)=∏i=1np(xi|Pai,θi?Sh)?(3)其中:θi是分布p(xi|Pai,θi,Sh)的參數(shù)向量,θs是參數(shù)組(θ1,θ2,…,θn)的向量,而Sh表示物理聯(lián)合分布可以依照S被分解的假設(shè)。此外,假設(shè)從X的物理聯(lián)合概率分布得到一個隨機(jī)樣本D={x1,…,xN}。于是Bayesian網(wǎng)絡(luò)的概率學(xué)習(xí)問題可以簡單地表示成:給定隨機(jī)樣本D,計算后驗分布p(θs|D,Sh)。假定變量Xi∈X是離散的,有ri個可能的值x1i,x2i,…,xrii,一個分布對應(yīng)于Pai的一個狀態(tài)。也就是說,假定p(xki|Ρjai,θi?Sh)=θijk>0?i=1,2,?,n;j=1,2,?,qi;k=1,2,?,ri?(4)p(xki|Pjai,θi?Sh)=θijk>0?i=1,2,?,n;j=1,2,?,qi;k=1,2,?,ri?(4)其中:P1ai,P2ai,…,Pqiai表示Pai的qi個取值狀態(tài),qi=∏Xi∈Ρairi。θi=((θijk)rik=2)qij=1是參數(shù),θij1沒有列入,因為θij1=1-ri∑k=2θijk,可以通過計算得到。為方便起見,定義參數(shù)向量θij=(θij2?θij3???θijri)?i=1?2???n；j=1?2???qi.給定局部分布函數(shù),需要有以下兩個假設(shè),才能以封閉的形式計算后驗分布p(θs|D,Sh):1)在隨機(jī)樣本D中沒有缺失數(shù)據(jù),這時又稱D是完整的;2)參數(shù)向量θij是相互獨立的,即p(θs|Sh)=n∏i=1qi∏j=1p(θij|Sh)。這就是參數(shù)獨立假設(shè)。在以上兩個假設(shè)下,對于給定的隨機(jī)樣本D,參數(shù)仍然保持獨立,即p(θs|D,Sh)=n∏i=1qi∏j=1p(θij|D,Sh).(5)于是可以獨立地更新每一個參數(shù)向量θij。假設(shè)每一個參數(shù)向量θij有先驗Dirichlet分布Dir(θij|αij1,αij2,…,αijri),則后驗分布為p(θij|D,Sh)=Dir(θij|αij1+Νij1?αij2+Νij2???αijri+Νijri),(6)其中Nijk是D中Xi=xki且Pai=Pjai事例的數(shù)目?，F(xiàn)在可以計算D中第N+1個事例出現(xiàn)的概率p(xΝ+1|D,Sh)=Ep(θs|D,Sh)(ri∏i=1θijk)。利用參數(shù)對給定D保持獨立,可以計算數(shù)學(xué)期望:p(xΝ+1|D,Sh)=∫n∏i=1θijkp(θs|D,Sh)dθ=n∏i=1∫θijkp(θij|D,Sh)dθij.通過計算可得p(xΝ+1|D,Sh)=n∏i=1αijk+Νijkαij+Νij?(7)其中αij=ri∑k=1αijk且Νij=ri∑k=1Νijk.當(dāng)樣本數(shù)據(jù)不完全時,一般要借助于近似方法,如Monte-Carlo方法,Gaussian逼近,以及EM(期望-極大化)算法求ML(極大似然)或MAP(極大后驗)等。盡管有成熟的算法,其計算開銷是比較大的。3網(wǎng)絡(luò)結(jié)構(gòu)的確定當(dāng)不能確定Bayesian網(wǎng)絡(luò)的結(jié)構(gòu)時,可以用Bayesian方法從給定數(shù)據(jù)中學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)。由于數(shù)據(jù)采掘面對的是大量數(shù)據(jù),一時往往難以斷定變量之間的關(guān)系,因此這個問題更具有現(xiàn)實意義。首先定義一個隨機(jī)變量Sh,表示網(wǎng)絡(luò)結(jié)構(gòu)的不確定性,并賦予先驗概率分布p(Sh)。然后計算后驗概率分布p(Sh|D)。根據(jù)Bayesian定理有p(Sh|D)=p(Sh,D)/p(D)=p(Sh)p(D|Sh)/p(D)?(8)其中:p(D)是一個與結(jié)構(gòu)無關(guān)的正規(guī)化常數(shù),p(D|Sh)是邊界似然。于是確定網(wǎng)絡(luò)結(jié)構(gòu)的后驗分布只需要為每一個可能的結(jié)構(gòu)計算數(shù)據(jù)的邊界似然。在無約束多項分布、參數(shù)獨立、采用Dirichlet先驗和數(shù)據(jù)完整的前提下,數(shù)據(jù)的邊界似然正好等于每一個(i,j)對的邊界似然的乘積,即p(D|Sh)=n∏i=1qi∏j=1Γ(αij)Γ(αij+Νij)ri∏k=1Γ(αijk+Νijk)Γ(αijk).(9)該公式由Cooper和Herskovits于1992年首次給出。在一般情況下,n個變量的可能的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)目大于以n為指數(shù)的函數(shù)。逐一排除這些假設(shè)是很困難的。可以使用兩個方法來處理這個問題:“模型選擇”和“有選擇的模型平均”。前者是從所有可能的模型(結(jié)構(gòu)假設(shè))中選擇一個“好的”模型,并把它當(dāng)作正確的模型。后者是從所有可能的模型中選擇合理數(shù)目的“好”模型,并認(rèn)為這些模型代表了所有情況。若干研究者(Chickering,Heckerman)的工作表明,使用貪心搜索法選擇單個好的模型通常會得到準(zhǔn)確的預(yù)測。使用Monte-Carlo方法進(jìn)行模型平均也很有效,甚至可以得到更好的預(yù)測。4線上的多模型先驗下面是一個使用Bayesian網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)采掘和知識發(fā)現(xiàn)的應(yīng)用實例(Sewell和Shah)。數(shù)據(jù)來自華盛頓高級中學(xué)的10318名高年級學(xué)生。每個學(xué)生用下列變量及其相應(yīng)的狀態(tài)來描述:性別(SEX):男、女;社會經(jīng)濟(jì)狀態(tài)(SES):低、中下、中上、高;智商(IQ):低、中下、中上、高;家長的鼓勵(PE):低、高;升學(xué)計劃(CP):是、否;目標(biāo)是從數(shù)據(jù)中發(fā)現(xiàn)影響高中學(xué)生上大學(xué)意向的因素。數(shù)據(jù)已經(jīng)整理成表1所示的格式。表中每個數(shù)據(jù)表示對于5個變量的某種取值組合統(tǒng)計所得到的人數(shù)。例如,第一個數(shù)據(jù)表示對(SEX=男,SES=低,IQ=低,PE=低,CP=是)這種組合統(tǒng)計得到的人數(shù)為4。第二個數(shù)據(jù)則表示對(SEX=男,SES=低,IQ=低,PE=低,CP=否)這種組合統(tǒng)計得到的人數(shù)為349。其后的數(shù)據(jù)表示依次輪換每個變量可能的狀態(tài)統(tǒng)計得到的人數(shù)。變量依照從右到左的順序輪換,狀態(tài)則按照上面列出的各變量狀態(tài)順序輪換。先假定沒有隱藏變量,使用容量為5的等值樣本和p(x|Shc)服從均勻分布的先驗網(wǎng)絡(luò)。排除掉SEX和SES有父節(jié)點、CP有子節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)之后,假定其它所有網(wǎng)絡(luò)結(jié)構(gòu)都是等可能的。因為數(shù)據(jù)集是完整的,可以用式(8)和式(9)計算網(wǎng)絡(luò)結(jié)構(gòu)的后驗概率。通過對所有網(wǎng)絡(luò)結(jié)構(gòu)的窮舉搜索,發(fā)現(xiàn)兩個最可能的網(wǎng)絡(luò)結(jié)構(gòu)(如圖1)。右邊的網(wǎng)絡(luò)曾由Spirtes等用非Bayesian方法于1993年選出。最值得懷疑的結(jié)果是:社會經(jīng)濟(jì)狀況對智商有直接的影響。為了考證這個結(jié)果,考慮一個新的模型,即將圖1中原來模型的直接影響用一個指向SES和IQ的隱藏變量代替。此外還考慮這樣的模型,隱藏變量指向SES,IQ和PE,而且在SES—PE和PE—IQ兩個連接中分別去掉兩個、一個和0個,對每個結(jié)構(gòu)將隱藏變量的狀態(tài)數(shù)從2變到6。使用Laplace逼近的Cheeseman-Stutz變體計算這些模型的后驗概率。為了找最大后驗構(gòu)成?θs,使用EM算法,并在帶有不同的隨機(jī)初始化的θs的100次運(yùn)行中取最大的局部極大值。這些模型中帶有最大后驗概率的一個如圖2所示。這個模型的可能性比不含有隱藏變量的最好模型高2×1010倍。假定沒有忽略合理的模型,那么有強(qiáng)烈的證據(jù)表明:有一個隱藏變量在影響著SES(社會經(jīng)濟(jì)狀態(tài))和IQ(智商)。分析圖2可知,隱藏變量對應(yīng)于“家長的素質(zhì)”。5全樣本信息的使用使用Bayesian方法從先驗信息和樣本信息學(xué)習(xí)Bayesian網(wǎng)絡(luò)的結(jié)構(gòu)和概率分布,進(jìn)而建立Bayesian網(wǎng)絡(luò),為Bayesian網(wǎng)絡(luò)在數(shù)據(jù)采掘和知識發(fā)現(xiàn)中的應(yīng)用開辟了道路。與其它用于數(shù)據(jù)采掘的方法相比,Bayesian網(wǎng)絡(luò)有如下特點:1)可以綜合先驗信息和樣本信息,既可避免只使用先驗信息可能帶來的主觀偏見,也可避免只使用樣本信息帶來的噪音影響。并且,這在樣本難得或者代價高昂時特別有用;2)能夠處理不完整數(shù)據(jù)問題;3)可以發(fā)現(xiàn)數(shù)據(jù)間的因果關(guān)系;2)和3)在實際問題中經(jīng)常遇到,而且用其它模型難以處理。4)有成熟的近似算法。雖然任意Bayesian網(wǎng)絡(luò)的概率推斷是NP難題,但是很