高級人工智能 課件

高級人工智能第六章

概率推理

史忠植

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

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

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

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

P(A+B)＝P(A)＋P(B)－P(AB)2022/12/1010史忠植高級人工智能加法定理兩個(gè)不相容(互斥)事件之和的概率,等于兩個(gè)事件概乘法定理設(shè)A、B為兩個(gè)任意的非零事件，則其乘積的概率等于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/1011史忠植高級人工智能乘法定理設(shè)A、B為兩個(gè)任意的非零事件，則其乘積的概率等于貝葉斯網(wǎng)絡(luò)定義貝葉斯網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖，這里每個(gè)節(jié)點(diǎn)表示領(lǐng)域變量，每條邊表示變量間的概率依賴關(guān)系，同時(shí)對每個(gè)節(jié)點(diǎn)都對應(yīng)著一個(gè)條件概率分布表(CPT)，指明了該變量與父節(jié)點(diǎn)之間概率依賴的數(shù)量關(guān)系。2022/12/1012史忠植高級人工智能貝葉斯網(wǎng)絡(luò)定義貝葉斯網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖貝葉斯網(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)

條件獨(dú)立性假設(shè)有效的表示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)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖2022/12/1013史忠植高級人工智能貝葉斯網(wǎng)的表示方法 =P(A)P(S)P(T先驗(yàn)概率先驗(yàn)概率是指根據(jù)歷史的資料或主觀判斷所確定的各事件發(fā)生的概率，該類概率沒能經(jīng)過實(shí)驗(yàn)證實(shí)，屬于檢驗(yàn)前的概率，所以稱之為先驗(yàn)概率。先驗(yàn)概率一般分為兩類，一是客觀先驗(yàn)概率，是指利用過去的歷史資料計(jì)算得到的概率；二是主觀先驗(yàn)概率，是指在無歷史資料或歷史資料不全的時(shí)候，只能憑借人們的主觀經(jīng)驗(yàn)來判斷取得的概率。

2022/12/1014史忠植高級人工智能先驗(yàn)概率先驗(yàn)概率是指根據(jù)歷史的資料或主觀判斷所確定的后驗(yàn)概率后驗(yàn)概率一般是指利用貝葉斯公式，結(jié)合調(diào)查等方式獲取了新的附加信息，對先驗(yàn)概率進(jìn)行修正后得到的更符合實(shí)際的概率。2022/12/1015史忠植高級人工智能后驗(yàn)概率后驗(yàn)概率一般是指利用貝葉斯公式，結(jié)合調(diào)查等方式獲取了聯(lián)合概率聯(lián)合概率也叫乘法公式，是指兩個(gè)任意事件的乘積的概率，或稱之為交事件的概率。2022/12/1016史忠植高級人工智能聯(lián)合概率聯(lián)合概率也叫乘法公式，是指兩個(gè)任意事件的乘積的概率，

設(shè)A1,A2,…,An是兩兩互斥的事件，且P(Ai)>0，i=1,2,…,n,A1+A2+…,+An=Ω全概率公式A1A2A3AnB另有一事件B=BA1+BA2+…,+BAn稱滿足上述條件的A1,A2,…,An為完備事件組.2022/12/1017史忠植高級人工智能設(shè)A1,A2,…,An是兩兩互斥的事件，且P(Ai)全概率例:某汽車公司下屬有兩個(gè)汽車制造廠,全部產(chǎn)品的40%由甲廠生產(chǎn),60%由乙廠生產(chǎn).而甲乙二廠生產(chǎn)的汽車的不合格率分別為1%,2%.求從公司生產(chǎn)的汽車中隨機(jī)抽取一輛為不合品的概率.解:設(shè)A1,A2分別表示{甲廠汽車}{乙廠汽車},B表示{不合格品}

P(A1)=0.4,P(A2)=0.6

P(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/1018史忠植高級人工智能全概率例:某汽車公司下屬有兩個(gè)汽車制造廠,全部產(chǎn)品的40%由

由此可以形象地把全概率公式看成為“由原因推結(jié)果”，每個(gè)原因?qū)Y(jié)果的發(fā)生有一定的“作用”，即結(jié)果發(fā)生的可能性與各種原因的“作用”大小有關(guān).全概率公式表達(dá)了它們之間的關(guān)系.諸Ai是原因B是結(jié)果A1A2A3A4A5A6A7A8B全概率2022/12/1019史忠植高級人工智能由此可以形象地把全概率公式看成為諸Ai是原因A該公式于1763年由貝葉斯(Bayes)給出.它是在觀察到事件B已發(fā)生的條件下，尋找導(dǎo)致B發(fā)生的每個(gè)原因的概率.貝葉斯公式

設(shè)A1,A2,…,An是樣本空間中的完備事件組且P(Ai)>0，i=1,2,…,n,另有一事件B，則有2022/12/1020史忠植高級人工智能該公式于1763年由貝葉斯(Bayes)給出.貝葉斯規(guī)則基于條件概率的定義p(Ai|E)是在給定證據(jù)下的后驗(yàn)概率p(Ai)是先驗(yàn)概率P(E|Ai)是在給定Ai下的證據(jù)似然p(E)是證據(jù)的預(yù)定義后驗(yàn)概率?==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/1021史忠植高級人工智能貝葉斯規(guī)則基于條件概率的定義?==iiiiiiii))p(A貝葉斯網(wǎng)絡(luò)的概率解釋任何完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力。完全的枚舉需要指數(shù)級的規(guī)模（相對于領(lǐng)域變量個(gè)數(shù)）貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個(gè)局部分布的乘積：

從公式可以看出，需要的參數(shù)個(gè)數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)呈線性增長，而聯(lián)合分布的計(jì)算呈指數(shù)增長。網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。這種獨(dú)立性關(guān)系在通過人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。

2022/12/1022史忠植高級人工智能貝葉斯網(wǎng)絡(luò)的概率解釋任何完整的概率模型必須具有表示（直接或間簡單貝葉斯學(xué)習(xí)模型簡單貝葉斯學(xué)習(xí)模型（SimpleBayes或

Na?veBayes）將訓(xùn)練實(shí)例I分解成特征向量X和決策類別變量C。簡單貝葉斯模型假定特征向量的各分量間相對于決策變量是相對獨(dú)立的，也就是說各分量獨(dú)立地作用于決策變量。盡管這一假定一定程度上限制了簡單貝葉斯模型的適用范圍，然而在實(shí)際應(yīng)用中，不僅以指數(shù)級降低了貝葉斯網(wǎng)絡(luò)構(gòu)建的復(fù)雜性，而且在許多領(lǐng)域，在違背這種假定的條件下，簡單貝葉斯也表現(xiàn)出相當(dāng)?shù)慕研院透咝訹111]，它已經(jīng)成功地應(yīng)用到分類、聚類及模型選擇等數(shù)據(jù)挖掘的任務(wù)中。目前，許多研究人員正致力于改善特征變量間獨(dú)立性的限制[54]，以使它適用于更大的范圍。

2022/12/1023史忠植高級人工智能簡單貝葉斯學(xué)習(xí)模型簡單貝葉斯學(xué)習(xí)模型（SimpleBaye簡單貝葉斯

Na?veBayesian結(jié)構(gòu)簡單－只有兩層結(jié)構(gòu)推理復(fù)雜性與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)呈線性關(guān)系2022/12/1024史忠植高級人工智能簡單貝葉斯

Na?veBayesian結(jié)構(gòu)簡單－只有兩層結(jié)設(shè)樣本A表示成屬性向量，如果屬性對于給定的類別獨(dú)立，那么P(A|Ci)可以分解成幾個(gè)分量的積：

ai是樣本A的第i個(gè)屬性

簡單貝葉斯學(xué)習(xí)模型2022/12/1025史忠植高級人工智能設(shè)樣本A表示成屬性向量，如果屬性對于給定的類別獨(dú)立，那么P(簡單貝葉斯分類模型這個(gè)過程稱之為簡單貝葉斯分類(SBC:SimpleBayesianClassifier)。一般認(rèn)為，只有在獨(dú)立性假定成立的時(shí)候，SBC才能獲得精度最優(yōu)的分類效率；或者在屬性相關(guān)性較小的情況下，能獲得近似最優(yōu)的分類效果。

簡單貝葉斯學(xué)習(xí)模型2022/12/1026史忠植高級人工智能簡單貝葉斯分類模型這個(gè)過程稱之為簡單貝葉斯分類(SBC:基于Boosting簡單貝葉斯模型。

提升方法（Boosting）總的思想是學(xué)習(xí)一系列分類器，在這個(gè)序列中每一個(gè)分類器對它前一個(gè)分類器導(dǎo)致的錯(cuò)誤分類例子給與更大的重視。尤其是，在學(xué)習(xí)完分類器Hk之后，增加了由Hk導(dǎo)致分類錯(cuò)誤的訓(xùn)練例子的權(quán)值，并且通過重新對訓(xùn)練例子計(jì)算權(quán)值，再學(xué)習(xí)下一個(gè)分類器Hk+1。這個(gè)過程重復(fù)T次。最終的分類器從這一系列的分類器中綜合得出。

簡單貝葉斯模型的提升2022/12/1027史忠植高級人工智能基于Boosting簡單貝葉斯模型。提升方法（BoostiBoosting背景來源于:PAC-LearningModelValiant1984-11提出問題:強(qiáng)學(xué)習(xí)算法:準(zhǔn)確率很高的學(xué)習(xí)算法弱學(xué)習(xí)算法:準(zhǔn)確率不高,僅比隨機(jī)猜測略好是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法2022/12/1028史忠植高級人工智能Boosting背景來源于:PAC-LearningModBoosting背景最初的boosting算法

Schapire1989AdaBoost算法

FreundandSchapire19952022/12/1029史忠植高級人工智能Boosting背景最初的boosting算法2022/12Boosting—concepts(3)弱學(xué)習(xí)機(jī)（weaklearner):對一定分布的訓(xùn)練樣本給出假設(shè)（僅僅強(qiáng)于隨機(jī)猜測）

根據(jù)有云猜測可能會(huì)下雨強(qiáng)學(xué)習(xí)機(jī)（stronglearner):根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出假設(shè)（最大程度上符合實(shí)際情況：almostperfectexpert)

根據(jù)CNN,ABC,CBS以往的預(yù)測表現(xiàn)及實(shí)際天氣情況作出綜合準(zhǔn)確的天氣預(yù)測弱學(xué)習(xí)機(jī)強(qiáng)學(xué)習(xí)機(jī)Boosting2022/12/1030史忠植高級人工智能Boosting—concepts(3)弱學(xué)習(xí)機(jī)（weakBoosting流程(loop1)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集加權(quán)后的訓(xùn)練集加權(quán)后的假設(shè)X>1?1:-1弱假設(shè)2022/12/1031史忠植高級人工智能Boosting流程(loop1)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集Boosting流程(loop2)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集加權(quán)后的訓(xùn)練集加權(quán)后的假設(shè)Y>3?1:-1弱假設(shè)2022/12/1032史忠植高級人工智能Boosting流程(loop2)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集Boosting流程(loop3)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集加權(quán)后的訓(xùn)練集加權(quán)后的假設(shè)Z>7?1:-1弱假設(shè)2022/12/1033史忠植高級人工智能Boosting流程(loop3)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集Boosting過程:在一定的權(quán)重條件下訓(xùn)練數(shù)據(jù)，得出分類法Ct根據(jù)Ct的錯(cuò)誤率調(diào)整權(quán)重SetofweightedinstancesClassifierCt

trainclassifier

adjustweights2022/12/1034史忠植高級人工智能Boosting過程:SetofClassifierC流程描述Step1:原始訓(xùn)練集輸入，帶有原始分布Step2:給出訓(xùn)練集中各樣本的權(quán)重Step3:將改變分布后的訓(xùn)練集輸入已知的弱學(xué)習(xí)機(jī)，弱學(xué)習(xí)機(jī)對每個(gè)樣本給出假設(shè)Step4:對此次的弱學(xué)習(xí)機(jī)給出權(quán)重Step5:轉(zhuǎn)到Step2,直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6:將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī)2022/12/1035史忠植高級人工智能流程描述Step1:原始訓(xùn)練集輸入，帶有原始分布2022/核心思想樣本的權(quán)重沒有先驗(yàn)知識的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大，使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對這些錯(cuò)誤樣本進(jìn)行判斷。弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制：損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小。2022/12/1036史忠植高級人工智能核心思想樣本的權(quán)重2022/12/836史忠植高級人工智簡單問題演示（Boosting訓(xùn)練過程）2022/12/1037史忠植高級人工智能簡單問題演示（Boosting訓(xùn)練過程）2022/12/83算法—問題描述訓(xùn)練集{(x1,y1),(x2,y2),…,(xN,yN)}xiRm,yi{-1,+1}Dt

為第t次循環(huán)時(shí)的訓(xùn)練樣本分布（每個(gè)樣本在訓(xùn)練集中所占的概率，Dt總和應(yīng)該為1）ht:X{-1,+1}為第t次循環(huán)時(shí)的Weaklearner，對每個(gè)樣本給出相應(yīng)的假設(shè)，應(yīng)該滿足強(qiáng)于隨機(jī)猜測：wt為ht的權(quán)重

為t次循環(huán)得到的Stronglearner2022/12/1038史忠植高級人工智能算法—問題描述訓(xùn)練集{(x1,y1),(x2,y2)算法—樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重反映了stronglearner對樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？

2022/12/1039史忠植高級人工智能算法—樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重2022/12/839算法—弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式？

和指數(shù)函數(shù)遙相呼應(yīng)：2022/12/1040史忠植高級人工智能算法—弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大2算法--Adaboost2022/12/1041史忠植高級人工智能算法--Adaboost2022/12/841史忠植高級AdaBoost.M1初始賦予每個(gè)樣本相等的權(quán)重1/N

；Fort=1,2,…,TDo學(xué)習(xí)得到分類法Ct；計(jì)算該分類法的錯(cuò)誤率EtEt=所有被錯(cuò)誤分類的樣本的權(quán)重和；βt=Et/（1-Et）根據(jù)錯(cuò)誤率更新樣本的權(quán)重；正確分類的樣本：Wnew=Wold*βt

錯(cuò)誤分類的樣本：Wnew=Wold調(diào)整使得權(quán)重和為1；每個(gè)分類法Ct的投票價(jià)值為log[1/βt]2022/12/1042史忠植高級人工智能AdaBoost.M1初始賦予每個(gè)樣本相等的權(quán)重1/N；2AdaBoostTrainingError將γt=1/2-Et;FreundandSchapire證明:

最大錯(cuò)誤率為:即訓(xùn)練錯(cuò)誤率隨γt的增大呈指數(shù)級的減小.

2022/12/1043史忠植高級人工智能AdaBoostTrainingError將γt=1/2AdaBoostGeneralizationError(1)最大總誤差:m:樣本個(gè)數(shù)d:VC維T:訓(xùn)練輪數(shù)Pr:對訓(xùn)練集的經(jīng)驗(yàn)概率如果T值太大,Boosting會(huì)導(dǎo)致過適應(yīng)（overfit）2022/12/1044史忠植高級人工智能AdaBoostGeneralizationError(AdaBoostGeneralizationError(2)許多的試驗(yàn)表明:Boosting不會(huì)導(dǎo)致overfit2022/12/1045史忠植高級人工智能AdaBoostGeneralizationError(AdaBoostGeneralizationError(3)解釋以上試驗(yàn)現(xiàn)象;樣本(X,Y)的margin:margin(x,y)=αt=1/2ln((1-Εt)/Εt)較大的正邊界表示可信度高的正確的預(yù)測較大的負(fù)邊界表示可信度高的錯(cuò)誤的預(yù)測2022/12/1046史忠植高級人工智能AdaBoostGeneralizationError(AdaBoostGeneralizationError(4)解釋:當(dāng)訓(xùn)練誤差降低后,Boosting繼續(xù)提高邊界,從而增大了最小邊界,使分類的可靠性增加,降低總誤差.總誤差的上界:該公式與T無關(guān)2022/12/1047史忠植高級人工智能AdaBoostGeneralizationError(Boosting其它應(yīng)用Boosting易受到噪音的影響;AdaBoost可以用來鑒別異常;

具有最高權(quán)重的樣本即為異常.2022/12/1048史忠植高級人工智能Boosting其它應(yīng)用Boosting易受到噪音的影響;2是表示變量間連結(jié)關(guān)系的有向無環(huán)圖貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)結(jié)構(gòu)學(xué)習(xí)參數(shù)學(xué)習(xí)基于評分函數(shù)的結(jié)構(gòu)學(xué)習(xí)基于條件獨(dú)立性檢驗(yàn)的結(jié)構(gòu)學(xué)習(xí)構(gòu)建貝葉斯網(wǎng)絡(luò)2022/12/1049史忠植高級人工智能是表示變量間連結(jié)關(guān)系的有向無環(huán)圖貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)結(jié)構(gòu)學(xué)習(xí)參數(shù)構(gòu)建貝葉斯網(wǎng)絡(luò)BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2022/12/1050史忠植高級人工智能構(gòu)建貝葉斯網(wǎng)絡(luò)BayesianBayesianBayesia貝葉斯概率(密度估計(jì))貝葉斯學(xué)習(xí)理論利用先驗(yàn)信息和樣本數(shù)據(jù)來獲得對未知樣本的估計(jì)，而概率（聯(lián)合概率和條件概率）是先驗(yàn)信息和樣本數(shù)據(jù)信息在貝葉斯學(xué)習(xí)理論中的表現(xiàn)形式。如何獲得這些概率（也稱之為密度估計(jì)）是貝葉斯學(xué)習(xí)理論爭議較多的地方。研究如何根據(jù)樣本的數(shù)據(jù)信息和人類專家的先驗(yàn)知識獲得對未知變量（向量）的分布及其參數(shù)的估計(jì)。它有兩個(gè)過程：一是確定未知變量的先驗(yàn)分布；二是獲得相應(yīng)分布的參數(shù)估計(jì)。如果以前對所有信息一無所知，稱這種分布為無信息先驗(yàn)分布；如果知道其分布求它的分布參數(shù)，稱之為有信息先驗(yàn)分布。2022/12/1051史忠植高級人工智能貝葉斯概率(密度估計(jì))貝葉斯學(xué)習(xí)理論利用先驗(yàn)信息和樣本數(shù)據(jù)來密度估計(jì)先驗(yàn)分布的選取原則共軛分布杰弗萊原則

最大熵原則2022/12/1052史忠植高級人工智能密度估計(jì)先驗(yàn)分布的選取原則2022/12/852史忠植高從數(shù)據(jù)中學(xué)習(xí)共軛分布族先驗(yàn)與后驗(yàn)屬于同一分布族預(yù)先給定一個(gè)似然分布形式對于變量定義在0-1之間的概率分布，存在一個(gè)離散的樣本空間Beta對應(yīng)著2個(gè)似然狀態(tài)多變量Dirichlet分布對應(yīng)2個(gè)以上的狀態(tài)2022/12/1053史忠植高級人工智能從數(shù)據(jù)中學(xué)習(xí)共軛分布族2022/12/853史忠植高級人共軛分布Raiffa和Schaifeer提出先驗(yàn)分布應(yīng)選取共軛分布，即要求后驗(yàn)分布與先驗(yàn)分布屬于同一分布類型。它的一般描述為:

設(shè)樣本X1,X2,…,Xn

對參數(shù)θ的條件分布為p（x1,x2,…,xn|θ），如果先驗(yàn)分布密度函數(shù)決定的后驗(yàn)密度同屬于一種類型，則稱與為p（x|θ）的共軛分布。2022/12/1054史忠植高級人工智能共軛分布Raiffa和Schaifeer提出先驗(yàn)分布應(yīng)選取共杰弗萊原則杰弗萊對于先驗(yàn)分布的選取做出了重大的貢獻(xiàn)，它提出一個(gè)不變原理，較好地解決了貝葉斯假設(shè)中的一個(gè)矛盾，并且給出了一個(gè)尋求先驗(yàn)密度的方法。杰弗萊原則由兩個(gè)部分組成：一是對先驗(yàn)分布有一合理要求；一是給出具體的方法求得適合于要求的先驗(yàn)分布。先驗(yàn)分布的選取原則2022/12/1055史忠植高級人工智能杰弗萊原則杰弗萊對于先驗(yàn)分布的選取做出了重大的貢獻(xiàn)，它提出一最大熵原則很明顯，（1）的不確定性要比（2）的不確定性小得多，而且從直覺上也可以看得出當(dāng)取的兩個(gè)值得概率相等時(shí)，不確定性達(dá)到最大。熵是信息論中描述事物不確定性的程度的一個(gè)概念。如果一個(gè)隨機(jī)變量只取與兩個(gè)不同的值，比較下面兩種情況：（1）（2）2022/12/1056史忠植高級人工智能最大熵原則很明顯，（1）的不確定性要比（2）的不確定性小得多最大熵原則對連續(xù)型隨機(jī)變量x，它的概率密度函數(shù)為p(x)，若積分設(shè)隨機(jī)變量x是離散的，它取至多可列個(gè)值，且則

稱為x的熵

有意義，稱它為連續(xù)型隨機(jī)變量的熵

2022/12/1057史忠植高級人工智能最大熵原則對連續(xù)型隨機(jī)變量x，它的概率密度函數(shù)為p(x)，若1)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta--=---GGG先驗(yàn)分布的選?。璪eta分布2022/12/1058史忠植高級人工智能1)n(nm/n)m(1variance+-=nmmean=先驗(yàn)分布的選?。囗?xiàng)Dirichlet分布1)m(m)m/m(1mstate

i

theof

variancemmstate

i

theofmean...xxx)(m)...(m)(m)m()m,...,m,m|(xpN1iiN1iiN1iiiithN1iiith1m1-m1mN21N1iiN21DirichletN21+-==GGGG=?????====--=2022/12/1059史忠植高級人工智能先驗(yàn)分布的選?。囗?xiàng)Dirichlet分布1)m(m)m/m不完全數(shù)據(jù)的密度估計(jì)期望最大化方法（ExpectationMaximizationEM）

Gibbs抽樣（GibbsSamplingGS）BoundandCollapse(BC)

2022/12/1060史忠植高級人工智能不完全數(shù)據(jù)的密度估計(jì)期望最大化方法（Expectation期望最大化方法分為以下幾個(gè)步驟：（1）含有不完全數(shù)據(jù)的樣本的缺項(xiàng)用該項(xiàng)的最大似然估計(jì)代替；（2）把第一步中的缺項(xiàng)值作為先驗(yàn)信息，計(jì)算每一缺項(xiàng)的最大后驗(yàn)概率，并根據(jù)最大后驗(yàn)概率計(jì)算它的理想值。（3）用理想值替換（1）中的缺項(xiàng)。（4）重復(fù)（1—3），直到兩次相繼估計(jì)的差在某一固定閥值內(nèi)。2022/12/1061史忠植高級人工智能期望最大化方法分為以下幾個(gè)步驟：2022/12/861史忠植Gibbs抽樣Gibbs抽樣（GibbsSamplingGS）

GS是最為流行的馬爾科夫、蒙特卡羅方法之一。GS把含有不完全數(shù)據(jù)樣本的每一缺項(xiàng)當(dāng)作待估參數(shù)，通過對未知參數(shù)后驗(yàn)分布的一系列隨機(jī)抽樣過程，計(jì)算參數(shù)的后驗(yàn)均值的經(jīng)驗(yàn)估計(jì)。

2022/12/1062史忠植高級人工智能Gibbs抽樣Gibbs抽樣（GibbsSampling貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)基于搜索評分的方法:初始化貝葉斯網(wǎng)絡(luò)為孤立節(jié)點(diǎn)使用啟發(fā)式方法為網(wǎng)絡(luò)加邊使用評分函數(shù)評測新的結(jié)構(gòu)是否為更好貝葉斯評分（BayesianScoreMetric）

基于墑的評分最小描述長度MDL(MinimalDescriptionLength)

重復(fù)這個(gè)過程，直到找不到更好的結(jié)構(gòu)基于依賴分析的方法:通過使用條件獨(dú)立性檢驗(yàn)conditionalindependence(CI)

找到網(wǎng)絡(luò)的依賴結(jié)構(gòu)2022/12/1063史忠植高級人工智能貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)基于搜索評分的方法:2022/12/8基于MDL的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí)計(jì)算每一點(diǎn)對之間的互信息：

建立完全的無向圖，圖中的頂點(diǎn)是變量，邊是變量之間的互信息建立最大權(quán)張成樹根據(jù)一定的節(jié)點(diǎn)序關(guān)系，設(shè)置邊的方向2022/12/1064史忠植高級人工智能基于MDL的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí)計(jì)算每一點(diǎn)對之間的互信息：202基于條件獨(dú)立性的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)假定：節(jié)點(diǎn)序已知第一階段(Drafting)計(jì)算每對節(jié)點(diǎn)間的互信息，建立完整的無向圖.第二階段(Thickening)如果接點(diǎn)對不可能d-可分的話，把這一點(diǎn)對加入到邊集中。第三階段(Thinning)檢查邊集中的每個(gè)點(diǎn)對，如果兩個(gè)節(jié)點(diǎn)是d-可分的，那么移走這條邊。2022/12/1065史忠植高級人工智能基于條件獨(dú)立性的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)假定：節(jié)點(diǎn)序已知2022/12基于條件獨(dú)立性檢驗(yàn)(CI)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)1）初始化圖結(jié)構(gòu)B=<N,A,>,A=,R=,S=;2）對每一節(jié)點(diǎn)對，計(jì)算它們的互信息，并將互信息大于某一域值的節(jié)點(diǎn)對按互信息值的大小順序加入到S中；3）從S中取出第一個(gè)點(diǎn)對，并從S中刪除這個(gè)元素，把該點(diǎn)對加入到邊集A中；4）從S中剩余的點(diǎn)對中，取出第一個(gè)點(diǎn)對，如果這兩各界點(diǎn)之間不存在開放路徑，再把該點(diǎn)對加入A到中，否則加入到R中；5）重復(fù)4),直到S為空；6）從R中取出第一個(gè)點(diǎn)對；7）找出該點(diǎn)對的某一塊集，在該子集上做獨(dú)立性檢驗(yàn)，如果該點(diǎn)對的兩個(gè)節(jié)點(diǎn)，仍然相互依賴，則加入到A中；8）重復(fù)6),直到R為空；9）對A中的每一條邊，如果除這條邊外，仍舊含有開放路徑，則從A中臨時(shí)移出，并在相應(yīng)的塊集上作獨(dú)立性測試，如果仍然相關(guān)，則將其返回到A中，否則從A中刪除這條邊。2022/12/1066史忠植高級人工智能基于條件獨(dú)立性檢驗(yàn)(CI)的1）初始化圖結(jié)構(gòu)B=<N,A,樹增廣的樸素貝葉斯網(wǎng)TAN的結(jié)構(gòu)學(xué)習(xí)2022/12/1067史忠植高級人工智能樹增廣的樸素貝葉斯網(wǎng)2022/12/867史忠植高級人工主動(dòng)貝葉斯網(wǎng)絡(luò)分類器

主動(dòng)學(xué)習(xí)：主動(dòng)在候選樣本集中選擇測試?yán)?，并將這些實(shí)例以一定的方式加入到訓(xùn)練集中。選擇策略抽樣選擇投票選擇隨機(jī)抽樣相關(guān)抽樣不確定性抽樣2022/12/1068史忠植高級人工智能主動(dòng)貝葉斯網(wǎng)絡(luò)分類器主動(dòng)學(xué)習(xí)：主動(dòng)在候選樣本集中選擇測試?yán)鲃?dòng)貝葉斯網(wǎng)絡(luò)分類器

學(xué)習(xí)過程輸入：帶有類別標(biāo)注的樣本集L，未帶類別標(biāo)注的候選樣本集UL,選擇停止標(biāo)準(zhǔn)e，每次從候選集中選擇的樣本個(gè)數(shù)M輸出：分類器C.過程：

Whilenote{ TrainClassifer(L,C)//從L中學(xué)習(xí)分類器C；

Foreachx計(jì)算ES；SelectExampleByES(S,UL,M,ES)//根據(jù)ES從UL中選擇M個(gè)例子的子集S.LabeledAndAdd(S,L);//用當(dāng)前的分類器C標(biāo)注S中的元素，并把它加入到L中。

Remove(S,UL);//從UL中移走S. CheckStop(&e);//根據(jù)當(dāng)前狀態(tài)設(shè)置退出條件

}ReturnC;2022/12/1069史忠植高級人工智能主動(dòng)貝葉斯網(wǎng)絡(luò)分類器學(xué)習(xí)過程輸入：帶有類別標(biāo)注的樣本集L，主動(dòng)貝葉斯網(wǎng)絡(luò)分類器

基于最大最小熵的主動(dòng)學(xué)習(xí)首先從測試樣本中選擇出類條件熵最大和最小的候選樣本（MinExample,MaxExample），然后將這兩個(gè)樣本同時(shí)加入到訓(xùn)練集中。類條件熵最大的樣本的加入，使得分類器能夠?qū)哂刑厥庑畔⒌臉颖镜募霸缰匾?；而類條件熵最小的樣本是分類器較為確定的樣本，對它的分類也更加準(zhǔn)確，從而部分地抑制了由于不確定性樣本的加入而產(chǎn)生的誤差傳播問題2022/12/1070史忠植高級人工智能主動(dòng)貝葉斯網(wǎng)絡(luò)分類器基于最大最小熵的主動(dòng)學(xué)習(xí)首先從測試樣本主動(dòng)貝葉斯網(wǎng)絡(luò)分類器

基于分類損失與不確定抽樣相結(jié)合的主動(dòng)學(xué)習(xí)分類損失：選擇過程：從測試樣本中選擇個(gè)熵較大的樣本，組成集合maxS，然后對此集合中每個(gè)元素計(jì)算相對于該集合的分類損失和，選擇分類損失和最小的樣本做標(biāo)注并加入到訓(xùn)練樣本集中。2022/12/1071史忠植高級人工智能主動(dòng)貝葉斯網(wǎng)絡(luò)分類器基于分類損失與不確定抽樣相結(jié)合的主動(dòng)學(xué)主動(dòng)貝葉斯網(wǎng)絡(luò)分類器

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初始標(biāo)注樣本數(shù)：96未標(biāo)注訓(xùn)練樣本數(shù)：500測試集樣本數(shù)：1193ALearnerByMaxMinEntropy測試結(jié)果

ALearnerByUSandCL測試結(jié)果

2022/12/1072史忠植高級人工智能主動(dòng)貝葉斯網(wǎng)絡(luò)分類器

ABCDEF精度評定(%)精度召回率貝葉斯?jié)撛谡Z義模型隨著互聯(lián)網(wǎng)的普及，網(wǎng)上信息正在呈指數(shù)級增長趨勢。合理地組織這些信息，以便從茫茫的數(shù)據(jù)世界中，檢索到期望的目標(biāo)；有效地分析這些信息，以便從浩如煙海的信息海洋中，挖掘出新穎的、潛在有用的模式，正在成為網(wǎng)上信息處理的研究熱點(diǎn)。網(wǎng)上信息的分類目錄組織是提高檢索效率和檢索精度的有效途徑，如在利用搜索引擎對網(wǎng)頁數(shù)據(jù)進(jìn)行檢索時(shí)，如能提供查詢的類別信息，必然會(huì)縮小與限制檢索范圍，從而提高查準(zhǔn)率，同時(shí)，分類可以提供信息的良好組織結(jié)構(gòu)，便于用戶進(jìn)行瀏覽和過濾信息。

2022/12/1073史忠植高級人工智能貝葉斯?jié)撛谡Z義模型隨著互聯(lián)網(wǎng)的普及，網(wǎng)上信息正在呈指數(shù)級增長貝葉斯?jié)撛谡Z義模型聚類分析是文本挖掘的主要手段之一。它的主要作用是：1）通過對檢索結(jié)果的聚類，將檢索到的大量網(wǎng)頁以一定的類別提供給用戶，使用戶能快速定位期望的目標(biāo)；2）自動(dòng)生成分類目錄；3）通過相似網(wǎng)頁的歸并，便于分析這些網(wǎng)頁的共性。K-均值聚類是比較典型的聚類算法，另外自組織映射（SOM）神經(jīng)網(wǎng)絡(luò)聚類和基于概率分布的貝葉斯層次聚類（HBC）等新的聚類算法也正在不斷的研制與應(yīng)用中。然而這些聚類算法大部分是一種無監(jiān)督學(xué)習(xí)，它對解空間的搜索帶有一定的盲目性，因而聚類的結(jié)果一定程度上缺乏語義特征；同時(shí)，在高維情況下，選擇合適的距離度量標(biāo)準(zhǔn)變得相當(dāng)困難。而網(wǎng)頁分類是一種監(jiān)督學(xué)習(xí)，它通過一系列訓(xùn)練樣本的分析，來預(yù)測未知網(wǎng)頁的類別歸屬。目前已有很多有效的算法來實(shí)現(xiàn)網(wǎng)頁的分類，如NaiveBayesian、SVM等。遺憾的是獲得大量的、帶有類別標(biāo)注的樣本的代價(jià)是相當(dāng)昂貴的，而這些方法只有通過大規(guī)模的訓(xùn)練集才能獲得較高精度的分類效果。2022/12/1074史忠植高級人工智能貝葉斯?jié)撛谡Z義模型聚類分析是文本挖掘的主要手段之一。它的主要貝葉斯?jié)撛谡Z義模型KamalNigam等人提出從帶有類別標(biāo)注和不帶有類別標(biāo)注的混合文檔中分類Web網(wǎng)頁，它只需要部分帶有類別標(biāo)注的訓(xùn)練樣本，結(jié)合未標(biāo)注樣本含有的知識來學(xué)習(xí)貝葉斯分類器通過引入貝葉斯?jié)撛谡Z義模型，首先將含有潛在類別主題變量的文檔分配到相應(yīng)的類主題中。接著利用簡單貝葉斯模型，結(jié)合前一階段的知識，完成對未含類主題變量的文檔作標(biāo)注。針對這兩階段的特點(diǎn)，我們定義了兩種似然函數(shù)，并利用EM算法獲得最大似然估計(jì)的局部最優(yōu)解。這種處理方法一方面克服了非監(jiān)督學(xué)習(xí)中對求解空間搜索的盲目性；另一方面它不需要對大量訓(xùn)練樣本的類別標(biāo)注，只需提供相應(yīng)的類主題變量，把網(wǎng)站管理人員從繁瑣的訓(xùn)練樣本的標(biāo)注中解脫出來，提高了網(wǎng)頁分類的自動(dòng)性。為了與純粹的監(jiān)督與非監(jiān)督學(xué)習(xí)相區(qū)別，稱這種方法為半監(jiān)督學(xué)習(xí)算法。

2022/12/1075史忠植高級人工智能貝葉斯?jié)撛谡Z義模型KamalNigam等人提出從貝葉斯?jié)撛谡Z義模型潛在語義分析（LatentSemanticAnalysis:LSA）的基本觀點(diǎn)是：把高維的向量空間模型（VSM）表示中的文檔映射到低維的潛在語義空間中。這個(gè)映射是通過對項(xiàng)/文檔矩陣的奇異值分解（SVD）來實(shí)現(xiàn)的。具體地說，對任意矩陣，由線性代數(shù)的知識可知，它可分解為下面的形式：是正交陣潛在語義分析通過取k個(gè)最大的奇異值，而將剩余的值設(shè)為零來近似

是對角陣為N的奇異值2022/12/1076史忠植高級人工智能貝葉斯?jié)撛谡Z義模型潛在語義分析（LatentSemantiLSA的應(yīng)用：信息濾波、文檔索引、視頻檢索文檔的相似性特征的相似性貝葉斯?jié)撛谡Z義分析BLSA—LSA2022/12/1077史忠植高級人工智能LSA的應(yīng)用：信息濾波、文檔索引、視頻檢索文檔的相似性特征文檔產(chǎn)生模型以一定的概率選擇文檔d以一定的概率選擇一潛在變量z以一定的概率產(chǎn)生特征w產(chǎn)生如下的聯(lián)合概率模型貝葉斯?jié)撛谡Z義分析BLSA2022/12/1078史忠植高級人工智能文檔產(chǎn)生模型以一定的概率選擇文檔d以一定的概率選擇一潛在變d1d2d3dn...w1w2w3wm...z1z2zk...圖6.3貝葉斯?jié)撛谡Z義模型貝葉斯?jié)撛谡Z義分析BLSA2022/12/1079史忠植高級人工智能d1d2d3dn...w1w2w3wm...z1z2zk..最大化似然函數(shù)目的在于估計(jì)下面的分布參數(shù)

貝葉斯?jié)撛谡Z義分析BLSA2022/12/1080史忠植高級人工智能最大化似然函數(shù)目的在于估計(jì)下面的分布參數(shù)貝葉斯?jié)撛谡Z義分析E步M步似然函數(shù)值與迭代步驟的關(guān)系EM算法求得最大似然2022/12/1081史忠植高級人工智能E步M步似然函數(shù)值與迭代步驟的關(guān)系EM算法求得最大似然20算法描述:已知：求劃分:半監(jiān)督Web挖掘算法(1)2022/12/1082史忠植高級人工智能算法描述:已知：求劃分:半監(jiān)督Web挖掘算法(1)2022/解決策略：1.劃分D為兩個(gè)集和:3.使用NaiveBayesian標(biāo)注2.使用BLSA標(biāo)注半監(jiān)督Web挖掘算法(2)2022/12/1083史忠植高級人工智能解決策略：1.劃分D為兩個(gè)集和:3.使用NaiveBa1)使用BLSA估計(jì)分布參數(shù)2)使用最大后驗(yàn)概率標(biāo)注文檔1.使用BLSA標(biāo)注半監(jiān)督Web挖掘算法(3)2022/12/1084史忠植高級人工智能1)使用BLSA估計(jì)分布參數(shù)2)使用最大后驗(yàn)概率標(biāo)注文2.使用NaiveBayesian標(biāo)注M步:E步:似然函數(shù)半監(jiān)督web挖掘算法(3)2022/12/1085史忠植高級人工智能2.使用NaiveBayesian標(biāo)注M步:E步:似然半試驗(yàn)結(jié)果1000足球類文檔876特征詞

半監(jiān)督web挖掘算法(4)2022/12/1086史忠植高級人工智能試驗(yàn)結(jié)果1000足球類文檔半監(jiān)督web挖掘算法(4)20貝葉斯網(wǎng)中的證據(jù)推理目的：通過聯(lián)合概率分布公式，在給定的網(wǎng)絡(luò)結(jié)構(gòu)和已知證據(jù)下，計(jì)算某一事件的發(fā)生的概率。E網(wǎng)絡(luò)證據(jù)查詢推理貝葉斯推理可以在反復(fù)使用貝葉斯規(guī)則而獲得==p(B)A)p(A)|p(Bp(B)B)p(A,B)|p(A2022/12/1087史忠植高級人工智能貝葉斯網(wǎng)中的證據(jù)推理目的：通過聯(lián)合概率分布公式，在給定的網(wǎng)絡(luò)推理方法概述精確推理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是推理復(fù)雜性的主要原因；當(dāng)前的一些精確算法是有效地，能夠解決現(xiàn)實(shí)中的大部分問題由于對知識的認(rèn)知程度，精確推理還存在一些問題近似推理證據(jù)的低似然性和函數(shù)關(guān)系是近似推理中復(fù)雜性的主要原因NPHard2022/12/1088史忠植高級人工智能推理方法概述精確推理NPHard2022/12/888史忠影響推理的因素網(wǎng)絡(luò)結(jié)構(gòu)的特征

網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)的大小網(wǎng)絡(luò)中變量的類型（離散、連續(xù)）變量的分布墑相關(guān)查詢的特征任務(wù)查詢類型（批處理、異步執(zhí)行）可用的計(jì)算資源（嵌入式系統(tǒng)、并行處理）相關(guān)證據(jù)的特征證據(jù)的特征2022/12/1089史忠植高級人工智能影響推理的因素網(wǎng)絡(luò)結(jié)構(gòu)的特征2022/12/889史忠植查詢的任務(wù)類型預(yù)測對給定的模型，將要發(fā)生什么給定證據(jù)下的后驗(yàn)計(jì)算所有的邊界后驗(yàn)指定的邊界后驗(yàn)指定的聯(lián)合條件查詢最可能的假設(shè)

一個(gè)最可能的

n個(gè)最可能的決策策略2022/12/1090史忠植高級人工智能查詢的任務(wù)類型預(yù)測2022/12/890史忠植高級人工智醫(yī)療診斷例子貝葉斯推理中非條件分布和邊界分布是常見的查詢模式一個(gè)節(jié)點(diǎn)的邊界分布也稱為該節(jié)點(diǎn)的信任函數(shù)2022/12/1091史忠植高級人工智能醫(yī)療診斷例子貝葉斯推理中非條件分布和邊界分布是常見的查詢模式推理過程中的信任傳播2022/12/1092史忠植高級人工智能推理過程中的信任傳播2022/12/892史忠植高級人工推理算法精確推理聯(lián)合概率計(jì)算Na?veBayesian圖約簡算法Polytree算法

近似推理前向模擬推理隨機(jī)模擬推理

Thealgorithm’spurposeis“…fusingandpropagatingtheimpactofnewevidenceandbeliefsthroughBayesiannetworkssothateachpropositioneventuallywillbeassignedacertaintymeasureconsistentwiththeaxiomsofprobabilitytheory.”(Pearl,1988,p143)2022/12/1093史忠植高級人工智能推理算法精確推理近似推理Thealgorithm’spu精確推理－計(jì)算聯(lián)合概率任何查詢都可以通過聯(lián)合概率回答步驟：計(jì)算聯(lián)合概率

P(AB)=P(A)*P(B|A)邊界化不在查詢中的變量

P(B)=ΣAP(AB)效率低AB2022/12/1094史忠植高級人工智能精確推理－計(jì)算聯(lián)合概率任何查詢都可以通過聯(lián)合概率回答步驟：A圖約簡算法－一般原理基本觀點(diǎn) 任何概率查詢可以表示成網(wǎng)絡(luò)的子網(wǎng)，推理的目的是把網(wǎng)絡(luò)分解成幾個(gè)子網(wǎng)三個(gè)基本操作擬轉(zhuǎn)弧操作（ArcReversal）－貝葉斯公式孤寡點(diǎn)移出(Barrennoderemoval)－求和公式值節(jié)點(diǎn)歸并(MergewithValuenode)－期望最大化 2022/12/1095史忠植高級人工智能圖約簡算法－一般原理基本觀點(diǎn)2022/12/895史忠植約簡算法－擬轉(zhuǎn)弧操作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/1096史忠植高級人工智能約簡算法－擬轉(zhuǎn)弧操作X1X3X2X1X3X2X1X3X2X1約簡算法－孤寡點(diǎn)移出孤寡點(diǎn)－沒有孩子的節(jié)點(diǎn)2022/12/1097史忠植高級人工智能約簡算法－孤寡點(diǎn)移出孤寡點(diǎn)－沒有孩子的節(jié)點(diǎn)2022/12/8約簡算法－值節(jié)點(diǎn)歸并值節(jié)點(diǎn)－證據(jù)節(jié)點(diǎn)或賦值節(jié)點(diǎn)2022/12/1098史忠植高級人工智能約簡算法－值節(jié)點(diǎn)歸并值節(jié)點(diǎn)－證據(jù)節(jié)點(diǎn)或賦值節(jié)點(diǎn)2022/12Polytree算法－介紹該算法由Pearl于1982年首次提出基本觀點(diǎn)計(jì)算邊界后驗(yàn)的消息傳遞機(jī)制

Lambda算子：消息向上傳向父親

pi算子：消息向下傳向孩子2022/12/1099史忠植高級人工智能Polytree算法－介紹該算法由Pearl于1982年首Polytree算法－單連通網(wǎng)定義：在任何兩個(gè)節(jié)點(diǎn)之間存在且僅存在一條路徑（忽略方向）XMultipleparentsand/ormultiplechildren2022/12/10100史忠植高級人工智能Polytree算法－單連通網(wǎng)定義：在任何兩個(gè)節(jié)點(diǎn)之間存在單連通網(wǎng)的表示X

表示m維隨機(jī)向量;x

表示隨機(jī)向量可能的取值e

表示m維向量的一個(gè)取值My|x

是條件概率p(y|x)的似然矩陣p(y1|x1)p(y2|x1)...p(yn|x1)p(y1|x2)p(y2|x2)...p(yn|x2)... ...... p(y1|xm)p(y2|xm)...p(yn|xm)y=xBel(x)=p(x|e)表示隨機(jī)向量的后驗(yàn)；f(x)×g(x)表示向量的叉積f(x)g(x)表示向量的點(diǎn)積

是標(biāo)準(zhǔn)化常量2022/12/10101史忠植高級人工智能單連通網(wǎng)的表示X表示m維隨機(jī)向量;x表示隨機(jī)向量可概率的雙向傳播e+e-XYZ(e+)(x)(y)(y)(z)(e-)每個(gè)節(jié)點(diǎn)向兒子節(jié)點(diǎn)發(fā)送pi消息向父節(jié)點(diǎn)發(fā)送lambda消息

Bel(Y)=p(y|e+,e-)=(y)T

×

(y)其中(y)=p(y|e+),先驗(yàn)證據(jù)(y)=p(e-|y),似然證據(jù)(y)=xp(y|x,e+)×p(x|e+)=xp(y|x)×

(x)=(x)My|x(y)=zp(e-|y,z)×p(z|y)=zp(e-|z)×p(z|y)=z(z)×p(z|y)=Mz|y

(z)2022/12/10102史忠植高級人工智能概率的雙向傳播e+e-XYZ(e+)(x)(y)(y)(z)傳播算法對每個(gè)節(jié)點(diǎn)引入證據(jù)時(shí)，產(chǎn)生:沿著弧的方向傳播一組“p”消息逆著弧的方向傳播一組“l(fā)”消息對接收“p”or“l(fā)”消息的每個(gè)節(jié)點(diǎn):節(jié)點(diǎn)修正它的“p”或“l(fā)”，并發(fā)送到網(wǎng)絡(luò)中使用修正的“p”或“l(fā)”，更改結(jié)點(diǎn)的信任函數(shù)BELTBEL(t)p(t)l(t)UBEL(t)p(t)l(t)XBEL(t)p(t)l(t)YBEL(t)p(t)l(t)ZBEL(t)p(t)l(t)Mu|tMx|uMy|xMz|y2022/12/10103史忠植高級人工智能傳播算法對每個(gè)節(jié)點(diǎn)引入證據(jù)時(shí)，產(chǎn)生:TUXYZMu|tMx|實(shí)例－描述p(A1)=0.9p(A2)=0.1MB|A=MC|B=

A1A2B1B2C1C2C3ABC.8.2.1.9[].5.4.1.1.3.6[]ChDiA1A2C1C2C3B1B22022/12/10104史忠植高級人工智能實(shí)例－描述p(A1)=0.9A1B1C1ABC.8實(shí)例－算子設(shè)定ABC(1)初始化lambda算子為單位向量;Bel(A)=(A)×

(A)

(A) Bel(A) (A) A1 0.9 0.9 1.0 A2 0.1 0.1 1.0(2)(B)=(A)MB|A;Bel(B)=(B)×

(B)

(B) Bel(B) (B) B1 0.73 0.73 1.0 B2 0.27 0.27 1.0(3)(C)=(B)MC|B;Bel(C)=(C)×

(C) (C) Bel(C) (C) C1 0.39 0.40 1.0 C2 0.35 0.36 1.0 C3 0.24 0.24 1.02022/12/10105史忠植高級人工智能實(shí)例－算子設(shè)定ABC(1)初始化lambda算子為單位實(shí)例－第一次傳播[]tTRT==05l().1.6[]

t=0(lR)=.8.2p

t=1 (A)=(IR) (A) Bel(A) (A) A1 0.8 0.8 1.0A2 0.2 0.2 1.0

(B) Bel(B) (B) B1 0.73 0.73 1.0B2 0.27 0.27 1.0 (C) Bel(C) (C) C1 0.39 0.3 0.5C2 0.35 0.5 1.0C3 0.24 0.2 0.6 t=1

(C)=(TR)Intel.Rpt.TroopRpt.ABC2022/12/10106史忠植高級人工智能實(shí)例－第一次傳播[]tTRT==05l().1.[]tTRT==05l().1.6

t=0[](lR)=.8.2p (A) Bel(A) (A) Paris 0.8 0.8 1.0Med. 0.2 0.2 1.0

t=2 (B)=(A)MB|A (B) Bel(B) (B) B1 0.66 0.66 0.71B2 0.34 0.34 0.71 t=2

(B)=MC|B(A) (C) Bel(C) (C) C1 0.39 0.3 0.5C2 0.35 0.5 1.0C3 0.24 0.2 0.6

實(shí)例－第二次傳播Intel.Rpt.TroopRpt.ABC2022/12/10107史忠植高級人工智能[]tTRT==05l().1.6t實(shí)例－第三次傳播

(A) Bel(A) (A) A1 0.8 0.8 0.71A2 0.2 0.2 0.71

t=3 (A)=MB|A(B) (B) Bel(B) (B) B1 0.66 0.66 0.71B2 0.34 0.34 0.71 t=3

(C)=(B)MC|B (C) Bel(C) (C) C1 0.36 0.25 0.5C2 0.37 0.52 1.0C3 0.27 0.23 0.6

Intel.Rpt.TroopRpt.ABC2022/12/10108史忠植高級人工智能實(shí)例－第三次傳播 Intel.TroopABC2022/12結(jié)束語貝葉斯網(wǎng)絡(luò)是表示不確定性知識的一種有效方法貝葉斯網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)與結(jié)構(gòu)學(xué)習(xí)是比較活躍的研究領(lǐng)域貝葉斯網(wǎng)絡(luò)的推理能夠計(jì)算出任何給定事件在給定條件下發(fā)生的可能性貝葉斯網(wǎng)絡(luò)具有廣闊的應(yīng)用前景。2022/12/10109史忠植高級人工智能結(jié)束語貝葉斯網(wǎng)絡(luò)是表示不確定性知識的一種有效方法2022/1相關(guān)網(wǎng)址2022/12/10110史忠植高級人工智能相關(guān)網(wǎng)址2022/12/8110史忠植高級人工智能謝謝!2022/12/10111史忠植高級人工智能謝謝!2022/12/8111史忠植高級人工智能高級人工智能第六章

概率推理

史忠植

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

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