高級人工智能2

高級人工智能第六章

概率推理

史忠植

中國科學院計算技術研究所2023/1/171內(nèi)容提要6.1概述6.2貝葉斯概率基礎6.3貝葉斯學習理論6.4簡單貝葉斯學習模型6.5貝葉斯網(wǎng)絡的建造6.6主動貝葉斯網(wǎng)絡6.7貝葉斯?jié)撛谡Z義模型6.8貝葉斯網(wǎng)絡的證據(jù)推理2023/1/172貝葉斯網(wǎng)絡是什么貝葉斯網(wǎng)絡是用來表示變量間連接概率的圖形模式，它提供了一種自然的表示因果信息的方法，用來發(fā)現(xiàn)數(shù)據(jù)間的潛在關系。在這個網(wǎng)絡中，用節(jié)點表示變量，有向邊表示變量間的依賴關系。貝葉斯方法正在以其獨特的不確定性知識表達形式、豐富的概率表達能力、綜合先驗知識的增量學習特性等成為當前數(shù)據(jù)挖掘眾多方法中最為引人注目的焦點之一。2023/1/173貝葉斯網(wǎng)絡是什么貝葉斯（ReverendThomasBayes1702-1761）學派奠基性的工作是貝葉斯的論文“關于幾率性問題求解的評論”?；蛟S是他自己感覺到它的學說還有不完善的地方，這一論文在他生前并沒有發(fā)表，而是在他死后，由他的朋友發(fā)表的。著名的數(shù)學家拉普拉斯（LaplaceP.S.）用貝葉斯的方法導出了重要的“相繼律”，貝葉斯的方法和理論逐漸被人理解和重視起來。但由于當時貝葉斯方法在理論和實際應用中還存在很多不完善的地方，因而在十九世紀并未被普遍接受。2023/1/174貝葉斯網(wǎng)絡是什么二十世紀初，意大利的菲納特（B.deFinetti）以及英國的杰弗萊（JeffreysH.）都對貝葉斯學派的理論作出重要的貢獻。第二次世界大戰(zhàn)后，瓦爾德（WaldA.）提出了統(tǒng)計的決策理論，在這一理論中，貝葉斯解占有重要的地位；信息論的發(fā)展也對貝葉斯學派做出了新的貢獻。1958年英國最悠久的統(tǒng)計雜志Biometrika全文重新刊登了貝葉斯的論文，20世紀50年代，以羅賓斯（RobbinsH.）為代表，提出了經(jīng)驗貝葉斯方法和經(jīng)典方法相結合，引起統(tǒng)計界的廣泛注意，這一方法很快就顯示出它的優(yōu)點，成為很活躍的一個方向。2023/1/175貝葉斯網(wǎng)絡是什么隨著人工智能的發(fā)展，尤其是機器學習、數(shù)據(jù)挖掘等興起，為貝葉斯理論的發(fā)展和應用提供了更為廣闊的空間。貝葉斯理論的內(nèi)涵也比以前有了很大的變化。80年代貝葉斯網(wǎng)絡用于專家系統(tǒng)的知識表示，90年代進一步研究可學習的貝葉斯網(wǎng)絡，用于數(shù)據(jù)采掘和機器學習。近年來，貝葉斯學習理論方面的文章更是層出不窮，內(nèi)容涵蓋了人工智能的大部分領域，包括因果推理、不確定性知識表達、模式識別和聚類分析等。并且出現(xiàn)了專門研究貝葉斯理論的組織和學術刊物ISBA2023/1/176貝葉斯網(wǎng)絡的應用領域輔助智能決策數(shù)據(jù)融合模式識別醫(yī)療診斷文本理解數(shù)據(jù)挖掘2023/1/177統(tǒng)計概率

統(tǒng)計概率:若在大量重復試驗中，事件A發(fā)生的頻率穩(wěn)定地接近于一個固定的常數(shù)p，它表明事件A出現(xiàn)的可能性大小，則稱此常數(shù)p為事件A發(fā)生的概率，記為P(A),即p＝P(A)可見概率就是頻率的穩(wěn)定中心。任何事件A的概率為不大于1的非負實數(shù)，即0＜P(A)＜12023/1/178條件概率條件概率:我們把事件B已經(jīng)出現(xiàn)的條件下，事件A發(fā)生的概率記做為P(A|B)。并稱之為在B出現(xiàn)的條件下A出現(xiàn)的條件概率，而稱P(A)為無條件概率。若事件A與B中的任一個出現(xiàn)，并不影響另一事件出現(xiàn)的概率，即當P(A)＝P(A·B)或P(B)＝P(B·A)時，則稱A與B是相互獨立的事件。2023/1/179加法定理

兩個不相容(互斥)事件之和的概率,等于兩個事件概率之和,即

P(A+B)＝P(A)＋P(B)若A、B為兩任意事件，則：

P(A+B)＝P(A)＋P(B)－P(AB)2023/1/1710乘法定理設A、B為兩個任意意的非零事事件，則其其乘積的概概率等于A(或B)的概率與在在A(或B)出現(xiàn)的條件件下B(或A)出現(xiàn)的條件件概率的乘乘積。P(A·B)＝P(A)·P(B|A)或P(A·B)＝P(B)·P(A|B)2022/12/3111貝葉葉斯斯網(wǎng)網(wǎng)絡絡定定義義貝葉葉斯斯網(wǎng)網(wǎng)絡絡是是表表示示變變量量間間概概率率依依賴賴關關系系的的有有向向無無環(huán)環(huán)圖圖，，這這里里每每個個節(jié)節(jié)點點表表示示領領域域變變量量，，每每條條邊邊表表示示變變量量間間的的概概率率依依賴賴關關系系，，同同時時對對每每個個節(jié)節(jié)點點都都對對應應著著一一個個條條件件概概率率分分布布表表(CPT)，，指明明了了該該變變量量與與父父節(jié)節(jié)點點之之間間概概率率依依賴賴的的數(shù)數(shù)量量關關系系。。2022/12/3112貝葉葉斯斯網(wǎng)網(wǎng)的的表表示示方方法法=P(A)P(S)P(T|A)P(L|S)P(B|S)P(C|T,L)P(D|T,L,B)P(A,S,T,L,B,C,D)

條件獨立性假設有效的表示CPT:

TLBD=0D=10000.10.90010.70.30100.80.20110.90.1...LungCancerSmokingChestX-rayBronchitisDyspnoeaTuberculosisVisittoAsiaP(D|T,L,B)P(B|S)P(S)P(C|T,L)P(L|S)P(A)P(T|A)貝葉葉斯斯網(wǎng)網(wǎng)絡絡是是表表示示變變量量間間概概率率依依賴賴關關系系的的有有向向無無環(huán)環(huán)圖圖2022/12/3113先驗驗概概率率先驗驗概概率率是是指指根根據(jù)據(jù)歷歷史史的的資資料料或或主主觀觀判判斷斷所所確確定定的的各各事事件件發(fā)發(fā)生生的的概概率率，，該該類類概概率率沒沒能能經(jīng)經(jīng)過過實實驗驗證證實實，，屬屬于于檢檢驗驗前前的的概概率率，，所所以以稱稱之之為為先先驗驗概概率率。。先先驗驗概概率率一一般般分分為為兩兩類類，，一一是是客客觀觀先先驗驗概概率率，，是是指指利利用用過過去去的的歷歷史史資資料料計計算算得得到到的的概概率率；；二二是是主主觀觀先先驗驗概概率率，，是是指指在在無無歷歷史史資資料料或或歷歷史史資資料料不不全全的的時時候候，，只只能能憑憑借借人人們們的的主主觀觀經(jīng)經(jīng)驗驗來來判判斷斷取取得得的的概概率率。。2022/12/3114后驗驗概概率率后驗驗概概率率一一般般是是指指利利用用貝貝葉葉斯斯公公式式，，結結合合調(diào)調(diào)查查等等方方式式獲獲取取了了新新的的附附加加信信息息，，對對先先驗驗概概率率進進行行修修正正后后得得到到的的更更符符合合實實際際的的概概率率。。2022/12/3115聯(lián)合概率聯(lián)合概率也叫叫乘法公式，，是指兩個任任意事件的乘乘積的概率，，或稱之為交交事件的概率率。2022/12/3116設A1,A2,…,An是兩兩兩互斥斥的事事件，，且P(Ai)>0，i=1,2,……,n,A1+A2+…,+An=Ω全概率率公式式A1A2A3AnB另有一一事件件B=BA1+BA2+…,+BAn稱滿足足上述述條件件的A1,A2,…,An為完備事事件組組.2022/12/3117全概率率例:某某汽車車公司司下屬屬有兩兩個汽汽車制制造廠廠,全全部產(chǎn)產(chǎn)品的的40%由由甲廠廠生產(chǎn)產(chǎn),60%由乙乙廠生生產(chǎn).而甲甲乙二二廠生生產(chǎn)的的汽車車的不不合格格率分分別為為1%,2%.求從從公司司生產(chǎn)產(chǎn)的汽汽車中中隨機機抽取取一輛輛為不不合品品的概概率.解:設設A1,A2分別別表表示示{甲甲廠廠汽汽車車}{乙乙廠廠汽汽車車},B表示{不不合格品品}P(A1)=0.4,P(A2)=0.6P(B/A1)=0.01,P(B/A2)=0.02∵A1A2=φP(B)=P(A1B+A2B)=P(A1B)+P(A2B)=P(A1)P(B/A1)+P(A2)P(B/A2)=0.4×0.01+0.6×0.02=0.016甲乙BA1A22022/12/3118由此可以形象象地把全概率率公式看成為為“由原因推結果果”，每個原因因?qū)Y果的發(fā)發(fā)生有一定的的“作用”，，即結果發(fā)生生的可能性與與各種原因的的“作用”大大小有關.全全概率公式式表達了它們們之間的關系系.諸Ai是原因B是結果A1A2A3A4A5A6A7A8B全概率2022/12/3119該公式于1763年由貝貝葉斯(Bayes)給出.它它是在觀察到到事件B已發(fā)生的條件件下，尋找導導致B發(fā)生的每個原原因的概率.貝葉斯公式設A1,A2,…,An是樣本空間中中的完備事件件組且P(Ai)>0，i=1,2,……,n,另有一事件B，則有2022/12/3120貝葉斯規(guī)則基于條件概率率的定義p(Ai|E)是在給定證據(jù)據(jù)下的后驗概概率p(Ai)是先驗概率P(E|Ai)是在給定Ai下的證據(jù)似然然p(E)是證據(jù)的預定定義后驗概率率?==iiiiiiii))p(AA|p(E))p(AA|p(Ep(E)))p(AA|p(EE)|p(A==p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(AA1A2A3A4A5A6E2022/12/3121貝葉斯網(wǎng)絡的的概率解釋任何完整的概概率模型必須須具有表示（（直接或間接接）該領域變變量聯(lián)合分布布的能力。完完全的枚舉需需要指數(shù)級的的規(guī)模（相對對于領域變量量個數(shù)）貝葉斯網(wǎng)絡提提供了這種聯(lián)聯(lián)合概率分布布的緊湊表示示：分解聯(lián)合合分布為幾個個局部分布的的乘積：從公式可以看看出，需要的的參數(shù)個數(shù)隨隨網(wǎng)絡中節(jié)點點個數(shù)呈線性性增長，而聯(lián)聯(lián)合分布的計計算呈指數(shù)增增長。網(wǎng)絡中變量間間獨立性的指指定是實現(xiàn)緊緊湊表示的關關鍵。這種獨獨立性關系在在通過人類專專家構造貝葉葉斯網(wǎng)中特別別有效。2022/12/3122簡單貝葉斯學學習模型簡單貝葉斯學學習模型（SimpleBayes或Na?veBayes）將訓練實例I分解成特征向向量X和決策類別變變量C。簡單貝葉斯模模型假定特征征向量的各分分量間相對于于決策變量是是相對獨立的的，也就是說說各分量獨立立地作用于決決策變量。盡盡管這一假定定一定程度上上限制了簡單單貝葉斯模型型的適用范圍圍，然而在實實際應用中，，不僅以指數(shù)級降低了貝葉斯斯網(wǎng)絡構建的的復雜性，而且在許多領領域，在違背背這種假定的的條件下，簡單貝葉斯斯也表現(xiàn)出相相當?shù)慕研孕院透咝訹111]，它已經(jīng)成功功地應用到分分類、聚類及及模型選擇等等數(shù)據(jù)挖掘的的任務中。目目前，許多研研究人員正致致力于改善特特征變量間獨獨立性的限制制[54]，以使它適用用于更大的范范圍。2022/12/3123簡單貝葉斯斯Na?veBayesian結構簡單－－只有兩層層結構推理復雜性性與網(wǎng)絡節(jié)節(jié)點個數(shù)呈呈線性關系系2022/12/3124設樣本A表示成屬性性向量，如如果屬性對對于給定的的類別獨立立，那么P(A|Ci)可以分解成成幾個分量量的積：ai是樣本A的第i個屬性簡單貝葉斯斯學習模型型2022/12/3125簡單貝葉斯斯分類模型型這個過程稱稱之為簡單單貝葉斯分分類(SBC:SimpleBayesianClassifier)。一般認為，，只有在獨獨立性假定定成立的時時候，SBC才能獲得精精度最優(yōu)的的分類效率率；或者在在屬性相關關性較小的的情況下，，能獲得近近似最優(yōu)的的分類效果果。簡單貝葉斯斯學習模型型2022/12/3126基于Boosting簡單貝葉斯斯模型。提升方法（（Boosting）總的思想是是學習一系系列分類器器，在這個個序列中每每一個分類類器對它前前一個分類類器導致的的錯誤分類類例子給與與更大的重重視。尤其其是，在學學習完分類類器Hk之后，增加加了由Hk導致分類錯錯誤的訓練練例子的權權值，并且且通過重新新對訓練例例子計算權權值，再學學習下一個個分類器Hk+1。這個過程重重復T次。最終的的分類器從從這一系列列的分類器器中綜合得得出。簡單貝葉葉斯模型型的提升升2022/12/3127Boosting背景來源于:PAC-LearningModelValiant1984-11提出問題題:強學習算算法:準確率很很高的學學習算法法弱學習算算法:準確率不不高,僅比隨機機猜測略略好是否可以以將弱學學習算法法提升為為強學習習算法2022/12/3128Boosting背景最初的boosting算法Schapire1989AdaBoost算法FreundandSchapire19952022/12/3129Boosting—concepts(3)弱學習機機（weaklearner):對一定分分布的訓訓練樣本本給出假假設（僅僅僅強于于隨機猜猜測）根據(jù)有云云猜測可可能會下下雨強學習機機（stronglearner):根據(jù)得到到的弱學學習機和和相應的的權重給給出假設設（最大大程度上上符合實實際情況況：almostperfectexpert)根據(jù)CNN,ABC,CBS以往的的預測測表現(xiàn)現(xiàn)及實實際天天氣情情況作作出綜綜合準準確的的天氣氣預測測弱學習習機強強學學習機機Boosting2022/12/3130Boosting流程(loop1)強學習機弱學習機原始訓練集集加權后的訓訓練集加權后的假假設X>1?1:-1弱假設2022/12/3131Boosting流程(loop2)強學習機弱學習機原始訓練集集加權后的訓訓練集加權后的假假設Y>3?1:-1弱假設2022/12/3132Boosting流程(loop3)強學習機弱學習機原始訓練集集加權后的訓訓練集加權后的假假設Z>7?1:-1弱假設2022/12/3133Boosting過程:在一定的權權重條件下下訓練數(shù)據(jù)據(jù)，得出分分類法Ct根據(jù)Ct的錯誤率調(diào)調(diào)整權重SetofweightedinstancesClassifierCttrainclassifieradjustweights2022/12/3134流程描述Step1:原始訓練集集輸入，帶帶有原始分分布Step2:給出訓練集集中各樣本本的權重Step3:將改變分布布后的訓練練集輸入已已知的弱學學習機，弱弱學習機對對每個樣本本給出假設設Step4:對此次的弱弱學習機給給出權重Step5:轉到Step2,直到循環(huán)到到達一定次次數(shù)或者某某度量標準準符合要求求Step6:將弱學習機機按其相應應的權重加加權組合形形成強學習習機2022/12/3135核心思想想樣本的權權重沒有先驗驗知識的的情況下下，初始始的分布布應為等等概分布布，也就就是訓練練集如果果有N個樣本，，每個樣樣本的分分布概率率為1/N每次循環(huán)環(huán)一后提提高錯誤誤樣本的的分布概概率，分分錯樣本本在訓練練集中所所占權重重增大，，使得得下一次次循環(huán)的的弱學習習機能夠夠集中力力量對這這些錯誤誤樣本進進行判斷斷。弱學習機機的權重重準確率越越高的弱弱學習機機權重越越高循環(huán)控制制：損失失函數(shù)達達到最小小在強學習習機的組組合中增增加一個個加權的的弱學習習機，使使準確率率提高，，損失函函數(shù)值減減小。2022/12/3136簡單問題題演示（（Boosting訓練過程程）2022/12/3137算法—問題描述述訓練集{(x1,y1),(x2,y2),…,(xN,yN)}xiRm,yi{-1,+1}Dt為第t次循環(huán)時時的訓練練樣本分分布（每每個樣本本在訓練練集中所所占的概概率，Dt總和應該該為1）ht:X{-1,+1}為第t次循環(huán)時時的Weaklearner，對每個個樣本給給出相應應的假設設，應該該滿足強強于隨機機猜測：：wt為ht的權重為t次循環(huán)得得到的Stronglearner2022/12/3138算法—樣本權重重思想：提提高分錯錯樣本的的權重反映了stronglearner對樣本的的假設是是否正確確采用什么么樣的函函數(shù)形式式？2022/12/3139算法—弱學習機機權重思想：錯錯誤率越越低，該該學習機機的權重重應該越越大為學習機機的錯誤誤概率采用什么么樣的函函數(shù)形式式？和指指數(shù)數(shù)函函數(shù)數(shù)遙遙相相呼呼應應：：2022/12/3140算法法--Adaboost2022/12/3141AdaBoost.M1初始始賦賦予予每每個個樣樣本本相相等等的的權權重重1/N；Fort=1,2,……,TDo學習習得得到到分分類類法法Ct；計算算該該分分類類法法的的錯錯誤誤率率EtEt=所有有被被錯錯誤誤分分類類的的樣樣本本的的權權重重和和；；βt=Et/（1-Et）根據(jù)據(jù)錯錯誤誤率率更更新新樣樣本本的的權權重重；；正確確分分類類的的樣樣本本：：Wnew=Wold*ββt錯誤誤分分類類的的樣樣本本：：Wnew=Wold調(diào)整整使使得得權權重重和和為為1；每個個分分類類法法Ct的投投票票價價值值為為log[1/ββt]2022/12/3142AdaBoostTrainingError將γt=1/2-Et;FreundandSchapire證明明:最大大錯錯誤誤率率為為:即訓訓練練錯錯誤誤率率隨隨γt的增增大大呈呈指指數(shù)數(shù)級級的的減減小小.2022/12/3143AdaBoostGeneralizationError(1)最大總總誤差差:m:樣本個個數(shù)d:VC維T:訓練輪輪數(shù)Pr:對訓練練集的的經(jīng)驗驗概率率如果T值太大大,Boosting會導致致過適適應（（overfit）2022/12/3144AdaBoostGeneralizationError(2)許多的的試驗驗表明明:Boosting不會導導致overfit2022/12/3145AdaBoostGeneralizationError(3)解釋以以上試試驗現(xiàn)現(xiàn)象;樣本(X,Y)的margin:margin(x,y)=αt=1/2ln((1-ΕΕt)/ΕΕt)較大的的正邊邊界表表示可可信度度高的的正確確的預預測較大的負邊邊界表示可可信度高的的錯誤的預預測2022/12/3146AdaBoostGeneralizationError(4)解釋:當訓練誤差差降低后,Boosting繼續(xù)提高邊邊界,從而增大了了最小邊界界,使分類的可可靠性增加加,降低總誤差差.總誤差的上上界:該公式與T無關2022/12/3147Boosting其它應用用Boosting易受到噪噪音的影影響;AdaBoost可以用來來鑒別異異常;具有最高高權重的的樣本即即為異常常.2022/12/3148是表示變變量間連連結關系系的有向向無環(huán)圖圖貝葉斯網(wǎng)網(wǎng)絡的學學習結構學習習參數(shù)學習習基于評分函數(shù)的結構學習基于條件獨立性檢驗的結構學習構建貝葉葉斯網(wǎng)絡絡2022/12/3149構建貝葉葉斯網(wǎng)絡絡BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2022/12/3150貝葉斯概概率(密密度估計計)貝葉斯學學習理論論利用先先驗信息息和樣本本數(shù)據(jù)來來獲得對對未知樣樣本的估估計，而而概率（（聯(lián)合概概率和條條件概率率）是先先驗信息息和樣本本數(shù)據(jù)信信息在貝貝葉斯學學習理論論中的表表現(xiàn)形式式。如何何獲得這這些概率率（也稱稱之為密密度估計計）是貝貝葉斯學學習理論論爭議較較多的地地方。研研究如何何根據(jù)樣樣本的數(shù)數(shù)據(jù)信息息和人類類專家的的先驗知知識獲得得對未知知變量（（向量））的分布布及其參參數(shù)的估估計。它它有兩個個過程：：一是確確定未知知變量的的先驗分分布；二二是獲得得相應分分布的參參數(shù)估計計。如果果以前對對所有信信息一無無所知，，稱這種種分布為為無信息息先驗分分布；如如果知道道其分布布求它的的分布參參數(shù)，稱稱之為有有信息先先驗分布布。2022/12/3151密度估計計先驗分布布的選取取原則共軛分布布杰弗萊原原則最大熵原原則2022/12/3152從數(shù)據(jù)中中學習共軛分布族先驗與后驗屬屬于同一分布布族預先給定一個個似然分布形形式對于變量定定義在0-1之間的的概率分布布，存在一一個離散的的樣本空間間Beta對應著2個似然然狀態(tài)多變量Dirichlet分布對應2個以上上的狀態(tài)2022/12/3153共軛分布Raiffa和Schaifeer提出先驗分分布應選取取共軛分布布，即要求求后驗分布布與先驗分分布屬于同同一分布類類型。它的的一般描述述為:設樣本X1,X2,…,Xn對參數(shù)θ的條件分布布為p（x1,x2,…,xn|θ），如果先驗分分布密度函函數(shù)決定的后驗驗密度同屬于一種種類型，則則稱與為p（x|θ）的共軛分布布。2022/12/3154杰弗弗萊萊原原則則杰弗弗萊萊對對于于先先驗驗分分布布的的選選取取做做出出了了重重大大的的貢貢獻獻，，它它提提出出一一個個不不變變原原理理，，較較好好地地解解決決了了貝貝葉葉斯斯假假設設中中的的一一個個矛矛盾盾，，并并且且給給出出了了一一個個尋尋求求先先驗驗密密度度的的方方法法。。杰杰弗弗萊萊原原則則由由兩兩個個部部分分組組成成：：一一是是對對先先驗驗分分布布有有一一合合理理要要求求；；一一是是給給出出具具體體的的方方法法求求得得適適合合于于要要求求的的先先驗驗分分布布。。先驗驗分分布布的的選選取取原原則則2022/12/3155最大熵原原則很明顯，，（1））的不確確定性要要比（2）的不不確定性性小得多多，而且且從直覺覺上也可可以看得得出當取取的兩個個值得概概率相等等時，不不確定性性達到最最大。熵是信息息論中描描述事物物不確定定性的程程度的一一個概念念。如果一個個隨機變變量只取取與兩個個不同的的值，比比較下面面兩種情情況：（1）（2）2022/12/3156最大熵原原則對連續(xù)型型隨機變變量x，它的概率率密度函函數(shù)為p(x)，若積分設隨機變變量x是離散的的，它取取至多可列列個值，，且則稱為x的熵有意義，稱它為為連續(xù)型型隨機變變量的熵熵2022/12/31571)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta--=---GGG先驗分布布的選取?。璪eta分布2022/12/3158先驗分布布的選取?。囗楉桪irichlet分布1)m(m)m/m(1mstateitheofvariancemmstateitheofmean...xxx)(m)...(m)(m)m()m,...,m,m|(xpN1iiN1iiN1iiiithN1iiith1m1-m1mN21N1iiN21DirichletN21+-==GGGG=?????====--=2022/12/3159不完全全數(shù)據(jù)據(jù)的密密度估估計期望最最大化化方法法（ExpectationMaximizationEM）Gibbs抽樣（（GibbsSamplingGS）BoundandCollapse(BC)2022/12/3160期望最最大化化方法法分為以以下幾幾個步步驟：：（1））含有有不完完全數(shù)數(shù)據(jù)的的樣本本的缺缺項用用該項項的最最大似似然估估計代代替；；（2））把第第一步步中的的缺項項值作作為先先驗信信息，，計算算每一一缺項項的最最大后后驗概概率，，并根根據(jù)最最大后后驗概概率計計算它它的理理想值值。（3））用理理想值值替換換（1）中中的缺缺項。。（4））重復復（1—3），，直到到兩次次相繼繼估計計的差差在某某一固固定閥閥值內(nèi)內(nèi)。2022/12/3161Gibbs抽樣Gibbs抽樣（（GibbsSamplingGS）GS是最為為流行行的馬馬爾科科夫、、蒙特特卡羅羅方法法之一一。GS把含有不完全全數(shù)據(jù)樣本的的每一缺項當當作待估參數(shù)數(shù)，通過對未未知參數(shù)后驗驗分布的一系系列隨機抽樣樣過程，計算算參數(shù)的后驗驗均值的經(jīng)驗驗估計。2022/12/3162貝葉斯網(wǎng)絡的的結構學習基于搜索評分分的方法:初始化貝葉斯斯網(wǎng)絡為孤立立節(jié)點使用啟發(fā)式方方法為網(wǎng)絡加加邊使用評分函數(shù)數(shù)評測新的結結構是否為更更好貝葉斯評分（（BayesianScoreMetric）基于墑的評分分最小描述長度度MDL(MinimalDescriptionLength)重復這個過程程，直到找不不到更好的結結構基于依賴分析析的方法:通過使用條件件獨立性檢驗驗conditionalindependence(CI)找到網(wǎng)絡的依依賴結構2022/12/3163基于MDL的貝葉斯網(wǎng)結結構學習計算每一點對對之間的互信信息：建立完全的無無向圖，圖中中的頂點是變變量，邊是變變量之間的互互信息建立最大權張張成樹根據(jù)一定的節(jié)節(jié)點序關系，，設置邊的方方向2022/12/3164基于條條件獨獨立性性的貝貝葉斯斯網(wǎng)絡絡學習習假定：：節(jié)點點序已已知第一階階段(Drafting)計算每每對節(jié)節(jié)點間間的互互信息息，建建立完完整的的無向向圖.第二階階段(Thickening)如果接接點對對不可可能d-可分的的話，，把這這一點點對加加入到到邊集集中。。第三階階段(Thinning)檢查邊邊集中中的每每個點點對，，如果果兩個個節(jié)點點是d-可分的的，那那么移移走這這條邊邊。2022/12/3165基于條條件獨獨立性性檢驗驗(CI)的貝葉斯斯網(wǎng)絡絡結構構學習習1）初始始化圖圖結構構B=<N,A,>,A=,R=,S=;2）對對每每一一節(jié)節(jié)點點對對，，計計算算它它們們的的互互信信息息，，并并將將互互信信息息大大于于某某一一域域值值的的節(jié)節(jié)點點對對按按互互信信息息值值的的大大小小順順序序加加入入到到S中；；3）從從S中取取出出第第一一個個點點對對，，并并從從S中刪刪除除這這個個元元素素，，把把該該點點對對加加入入到到邊邊集集A中；；4）從從S中剩余的的點對中中，取出出第一個個點對，，如果這這兩各界界點之間間不存在在開放路路徑，再再把該點點對加入入A到中，否否則加入入到R中；5）重復4),直到S為空；6）從R中取出第第一個點點對；7）找出該該點對的的某一塊塊集，在在該子集集上做獨獨立性檢檢驗，如如果該點點對的兩兩個節(jié)點點，仍然然相互依依賴，則則加入到到A中；8）重復復6),直到R為空；9）對A中的每一一條邊，，如果除除這條邊邊外，仍仍舊含有有開放路路徑，則則從A中臨時移移出，并并在相應應的塊集集上作獨獨立性測測試，如如果仍然然相關，，則將其其返回到到A中，否則則從A中刪除這這條邊。。2022/12/3166樹增廣的樸樸素貝葉斯斯網(wǎng)TAN的結構學習習2022/12/3167主動貝葉斯斯網(wǎng)絡分類類器主動學習：：主動在候選選樣本集中中選擇測試試例子，并并將這些實實例以一定定的方式加加入到訓練練集中。選擇策略抽樣選擇投票選擇隨機抽樣相關抽樣不確定性抽抽樣2022/12/3168主動貝葉斯斯網(wǎng)絡分類類器學習過程輸入：帶有有類別標注注的樣本集集L，未帶類別別標注的候候選樣本集集UL,選擇停止標標準e，每次從候候選集中選選擇的樣本本個數(shù)M輸出：分類類器C.過程：Whilenote{TrainClassifer(L,C)//從L中學習分類類器C；Foreachx計算ES；SelectExampleByES(S,UL,M,ES)//根據(jù)ES從UL中選擇M個例子的子子集S.LabeledAndAdd(S,L);//用當前的分分類器C標注S中的元素，，并把它加加入到L中。Remove(S,UL);//從UL中移走S.CheckStop(&e);//根據(jù)當前狀狀態(tài)設置退退出條件}ReturnC;2022/12/3169主動貝葉斯斯網(wǎng)絡分類類器基于最大最最小熵的主主動學習首先從測試試樣本中選選擇出類條條件熵最大大和最小的的候選樣本本（MinExample,MaxExample），然后將將這兩個樣樣本同時加加入到訓練練集中。類類條件熵最最大的樣本本的加入，，使得分類類器能夠?qū)哂刑厥馐庑畔⒌臉訕颖镜募霸缭缰匾?；而而類條件熵熵最小的樣樣本是分類類器較為確確定的樣本本，對它的的分類也更更加準確，，從而部分分地抑制了了由于不確確定性樣本本的加入而而產(chǎn)生的誤誤差傳播問問題2022/12/3170主動貝葉斯斯網(wǎng)絡分類類器基于分類損損失與不確確定抽樣相相結合的主主動學習分類損失：：選擇過程：：從測試樣本本中選擇個個熵較大的的樣本，組組成集合maxS，然后對此此集合中每每個元素計計算相對于于該集合的的分類損失失和，選擇擇分類損失失和最小的的樣本做標標注并加入入到訓練樣樣本集中。。2022/12/3171主動貝葉斯網(wǎng)網(wǎng)絡分類器

ABCDEF精度評定(%)精度召回率A645650000.76700.983294290.4853C252500000.84750.6494D50233100.91670.8049E90035100.96230.8095F170201641.00000.7619

ABCDEF精度評定(%)精度召回率A6411140000.84120.9771B8119100000.85650.7022C82148

000.85710.6234D60232100.91430.7273E90035100.96230.8095F170201641.00000.7619初始標注樣本數(shù)：96未標注訓練樣本數(shù)：500測試集樣本數(shù)：1193ALearnerByMaxMinEntropy測試結果ALearnerByUSandCL測試結果2022/12/3172貝葉斯?jié)撛谡Z語義模型隨著互聯(lián)網(wǎng)的的普及，網(wǎng)上上信息正在呈呈指數(shù)級增長長趨勢。合理理地組織這些些信息，以便便從茫茫的數(shù)數(shù)據(jù)世界中，，檢索到期望望的目標；有有效地分析這這些信息，以以便從浩如煙煙海的信息海海洋中，挖掘掘出新穎的、、潛在有用的的模式，正在在成為網(wǎng)上信信息處理的研研究熱點。網(wǎng)網(wǎng)上信息的分分類目錄組織織是提高檢索索效率和檢索索精度的有效效途徑，如在在利用搜索引引擎對網(wǎng)頁數(shù)數(shù)據(jù)進行檢索索時，如能提提供查詢的類類別信息，必必然會縮小與與限制檢索范范圍，從而提提高查準率，，同時，分類類可以提供信信息的良好組組織結構，便便于用戶進行行瀏覽和過濾濾信息。2022/12/3173貝葉斯斯?jié)撛谠谡Z義義模型型聚類分分析是是文本本挖掘掘的主主要手手段之之一。。它的的主要要作用用是：：1））通過過對檢檢索結結果的的聚類類，將將檢索索到的的大量量網(wǎng)頁頁以一一定的的類別別提供供給用用戶，，使用用戶能能快速速定位位期望望的目目標；；2））自動動生成成分類類目錄錄；3）通通過相相似網(wǎng)網(wǎng)頁的的歸并并，便便于分分析這這些網(wǎng)網(wǎng)頁的的共性性。K-均值值聚聚類類是是比比較較典典型型的的聚聚類類算算法法，，另另外外自自組組織織映映射射（（SOM））神經(jīng)經(jīng)網(wǎng)網(wǎng)絡絡聚聚類類和和基基于于概概率率分分布布的的貝貝葉葉斯斯層層次次聚聚類類（（HBC））等新新的的聚聚類類算算法法也也正正在在不不斷斷的的研研制制與與應應用用中中。。然然而而這這些些聚聚類類算算法法大大部部分分是是一一種種無無監(jiān)監(jiān)督督學學習習，，它它對對解解空空間間的的搜搜索索帶帶有有一一定定的的盲盲目目性性，，因因而而聚聚類類的的結結果果一一定定程程度度上上缺缺乏乏語語義義特特征征；；同同時時，，在在高高維維情情況況下下，，選選擇擇合合適適的的距距離離度度量量標標準準變變得得相相當當困困難難。。而而網(wǎng)網(wǎng)頁頁分分類類是是一一種種監(jiān)監(jiān)督督學學習習，，它它通通過過一一系系列列訓訓練練樣樣本本的的分分析析，，來來預預測測未未知知網(wǎng)網(wǎng)頁頁的的類類別別歸歸屬屬。。目目前前已已有有很很多多有有效效的的算算法法來來實實現(xiàn)現(xiàn)網(wǎng)網(wǎng)頁頁的的分分類類，，如如NaiveBayesian、SVM等。遺憾憾的是獲獲得大量量的、帶帶有類別別標注的的樣本的的代價是是相當昂昂貴的，，而這些些方法只只有通過過大規(guī)模模的訓練練集才能能獲得較較高精度度的分類類效果。。2022/12/3174貝葉斯?jié)摑撛谡Z義義模型KamalNigam等人提出出從帶有有類別標標注和不不帶有類類別標注注的混合合文檔中中分類Web網(wǎng)頁，它它只需要要部分帶帶有類別別標注的的訓練樣樣本，結結合未標標注樣本本含有的的知識來來學習貝貝葉斯分分類器通過引入入貝葉斯斯?jié)撛谡Z語義模型型，首先先將含有有潛在類類別主題題變量的的文檔分分配到相相應的類類主題中中。接著著利用簡簡單貝葉葉斯模型型，結合合前一階階段的知知識，完完成對未未含類主主題變量量的文檔檔作標注注。針對對這兩階階段的特特點，我我們定義義了兩種種似然函函數(shù)，并并利用EM算法獲獲得最最大似似然估估計的的局部部最優(yōu)優(yōu)解。。這種種處理理方法法一方方面克克服了了非監(jiān)監(jiān)督學學習中中對求求解空空間搜搜索的的盲目目性；；另一一方面面它不不需要要對大大量訓訓練樣樣本的的類別別標注注，只只需提提供相相應的的類主主題變變量，，把網(wǎng)網(wǎng)站管管理人人員從從繁瑣瑣的訓訓練樣樣本的的標注注中解解脫出出來，，提高高了網(wǎng)網(wǎng)頁分分類的的自動動性。。為了了與純純粹的的監(jiān)督督與非非監(jiān)督督學習習相區(qū)區(qū)別，，稱這這種方方法為為半監(jiān)監(jiān)督學學習算算法。。2022/12/3175貝葉斯斯?jié)撛谠谡Z義義模型型潛在語語義分分析（（LatentSemanticAnalysis:LSA）的基基本觀觀點是是：把把高維維的向向量空空間模模型（（VSM）表示示中的的文檔檔映射射到低低維的的潛在在語義義空間間中。。這個個映射射是通通過對對項/文檔矩矩陣的的奇奇異值值分解解（SVD）來實實現(xiàn)的的。具具體地地說，，對任任意矩矩陣，，由由線性性代數(shù)數(shù)的知知識可可知，，它可可分解解為下下面的的形式式：是正交交陣潛在語語義分分析通通過取取k個最大大的奇奇異值值，而而將剩剩余的的值設設為零零來近近似是對角角陣為N的奇異異值2022/12/3176LSA的應用：信息濾波、、文檔索引引、視頻檢檢索文檔的相似似性特征的相似似性貝葉斯?jié)撛谠谡Z義分析析BLSA——LSA2022/12/3177文檔檔產(chǎn)產(chǎn)生生模模型型以一定的概率選擇文檔d以一定的概率選擇一潛在變量z以一定的概率產(chǎn)生特征w產(chǎn)生生如如下下的的聯(lián)聯(lián)合合概概率率模模型型貝葉葉斯斯?jié)摑撛谠谡Z語義義分分析析BLSA2022/12/3178d1d2d3dn...w1w2w3wm...z1z2zk...圖6.3貝葉斯?jié)撛谡Z義模型貝葉葉斯斯?jié)摑撛谠谡Z語義義分分析析BLSA2022/12/3179最大大化化似似然然函函數(shù)數(shù)目的的在在于于估估計計下下面面的的分分布布參參數(shù)數(shù)貝葉葉斯斯?jié)摑撛谠谡Z語義義分分析析BLSA2022/12/3180E步M步似然函數(shù)值與迭代步驟的關系EM算法求得最大大似然2022/12/3181算法描述:已知：求劃分:半監(jiān)督Web挖掘算法(1)2022/12/3182解決策略：1.劃分D為兩個集和:3.使用NaiveBayesian標注2.使用BLSA標注半監(jiān)督督Web挖掘算算法(2)2022/12/31831)使用BLSA估計分布參參數(shù)2)使用最大后后驗概率標標注文檔1.使用BLSA標注半監(jiān)督Web挖掘算法(3)2022/12/31842.使用NaiveBayesian標注M步:E步:似然函數(shù)半監(jiān)督web挖掘算法(3)2022/12/3185試驗結果1000足球類文檔檔876特征詞半監(jiān)督web挖掘算法(4)2022/12/3186貝葉斯網(wǎng)網(wǎng)中的證證據(jù)推理理目的：通通過聯(lián)合合概率分分布公式式，在給給定的網(wǎng)網(wǎng)絡結構構和已知證證據(jù)下，，計算某某一事件件的發(fā)生生的概率率。E網(wǎng)絡證據(jù)查詢推理貝葉斯推推理可以以在反復復使用貝貝葉斯規(guī)規(guī)則而獲獲得==p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(A2022/12/3187推理方法法概述精確推理理網(wǎng)絡的拓拓撲結構構是推理理復雜性性的主要要原因；；當前的一一些精確確算法是是有效地地，能夠夠解決現(xiàn)現(xiàn)實中的的大部分分問題由于對知知識的認認知程度度，精確確推理還還存在一一些問題題近似推理理證據(jù)的低低似然性性和函數(shù)數(shù)關系是是近近似推理理中復雜雜性的主主要原因因NPHard2022/12/3188影響推理的因因素網(wǎng)絡結構的特特征網(wǎng)絡的拓撲結結構網(wǎng)絡的大小網(wǎng)絡中變量的的類型（離散散、連續(xù)）變量的分布墑墑相關查詢的特特征任務查詢類型（（批處理、異異步執(zhí)行）可用的計算資資源（嵌入式式系統(tǒng)、并行行處理）相關證據(jù)的特特征證據(jù)的特征2022/12/3189查詢的任務類類型預測對給定的模型型，將要發(fā)生生什么給定證據(jù)下的的后驗計算所有的邊界后后驗指定的邊界后后驗指定的聯(lián)合條條件查詢最可能的假設設一個最可能的的n個最可能的決策策略2022/12/3190醫(yī)療診斷例子子貝葉斯推理中中非條件分布布和邊界分布布是常見的查查詢模式一個節(jié)點的邊邊界分布也稱稱為該節(jié)點的的信任函數(shù)2022/12/3191推理過程中的的信任傳播2022/12/3192推理算法精確推理聯(lián)合概率計算算Na?veBayesian圖約簡算法Polytree算法近似推理前向模擬推理理隨機模擬推理理Thealgorithm’spurposeis“…fusingandpropagatingtheimpactofnewevidenceandbeliefsthroughBayesiannetworkssothateachpropositioneventuallywillbeassignedacertaintymeasureconsistentwiththeaxiomsofprobabilitytheory.”(Pearl,1988,p143)2022/12/3193精確確推推理理－－計計算算聯(lián)聯(lián)合合概概率率任何何查查詢詢都都可可以以通通過過聯(lián)聯(lián)合合概概率率回回答答步驟驟：：計算算聯(lián)聯(lián)合合概概率率P(AB)=P(A)*P(B|A)邊界界化化不不在在查查詢詢中中的的變變量量P(B)=ΣΣAP(AB)效率率低低AB2022/12/3194圖約約簡簡算算法法－－一一般般原原理理基本本觀觀點點任何何概概率率查查詢詢可可以以表表示示成成網(wǎng)網(wǎng)絡絡的的子子網(wǎng)網(wǎng)，，推推理理的的目目的的是是把把網(wǎng)網(wǎng)絡絡分分解解成成幾幾個個子子網(wǎng)網(wǎng)三個個基基本本操操作作擬轉轉弧弧操操作作（（ArcReversal））－－貝葉葉斯斯公公式式孤寡寡點點移移出出(Barrennoderemoval)－－求和和公公式式值節(jié)節(jié)點點歸歸并并(MergewithValuenode)－－期望望最最大大化化2022/12/3195約簡算算法－－擬轉轉弧操操作X1X3X2X1X3X2X1X3X2X1X3X2p(x1,x2,x3)=p(x3|x1)p(x2|x1)p(x1)p(x1,x2,x3)=p(x3|x2,x1)p(x2)p(x1)p(x1,x2,x3)=p(x3|x1)p(x2,x1)=p(x3|x1)p(x1|x2)p(x2)p(x1,x2,x3)=p(x3,x2|x1)p(x1)=p(x2|x3,x1)p(x3|x1)p(x1)2022/12/3196約簡算算法－－孤寡寡點移移出孤寡點點－沒沒有孩孩子的的節(jié)點點2022/12/3197約簡算法法－值節(jié)節(jié)點歸并并值節(jié)點－－證據(jù)節(jié)節(jié)點或賦賦值節(jié)點點2022/12/3198Polytree算法－介介紹該算法由由Pearl于1982年首首次提出出基本觀點點計算邊界界后驗的的消息傳傳遞機制制Lambda算子：消消息向上上傳向父父親pi算子：消消息向下下傳向孩孩子2022/12/3199Polytree算法－單單連通網(wǎng)網(wǎng)定義：在任何兩兩個節(jié)點點之間存存在且僅僅存在一一條路徑徑（忽略略方向））XMulti