aai04貝葉斯網(wǎng)絡(luò)高級人工智能史忠植

高級人工智能第四章貝葉斯網(wǎng)絡(luò)史忠植

中國科學(xué)院計(jì)算技術(shù)所2025/2/41史忠植高級人工智能4.1概述4.2貝葉斯概率基礎(chǔ)4.3貝葉斯學(xué)習(xí)理論4.4簡單貝葉斯學(xué)習(xí)模型4.5貝葉斯網(wǎng)絡(luò)的建造

4.6貝葉斯?jié)撛谡Z義模型

內(nèi)容提要2025/2/42史忠植高級人工智能貝葉斯網(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)之一。2025/2/43史忠植高級人工智能貝葉斯網(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ì)并未被普遍接受。2025/2/44史忠植高級人工智能貝葉斯網(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è)方向。2025/2/45史忠植高級人工智能貝葉斯網(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ù)刊物ISBA2025/2/46史忠植高級人工智能貝葉斯網(wǎng)絡(luò)的應(yīng)用領(lǐng)域輔助智能決策數(shù)據(jù)融合模式識別醫(yī)療診斷文本理解數(shù)據(jù)挖掘2025/2/47史忠植高級人工智能統(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)＜12025/2/48史忠植高級人工智能條件概率條件概率:我們把事件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ú)立的事件。2025/2/49史忠植高級人工智能加法定理

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

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

P(A+B)＝P(A)＋P(B)－P(AB)2025/2/410史忠植高級人工智能乘法定理設(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)2025/2/411史忠植高級人工智能貝葉斯網(wǎng)絡(luò)定義圖形描述概率描述ColdAllegoryCatSneezeScratch貝葉斯網(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)系。2025/2/412史忠植高級人工智能幾點(diǎn)說明貝葉斯網(wǎng)絡(luò)的特點(diǎn)：雙向推理能力（預(yù)測和診斷）快速的調(diào)試和重構(gòu)能力具有較強(qiáng)的概率統(tǒng)計(jì)基礎(chǔ)用于人工智能和專家系統(tǒng)的不確定推理（優(yōu)于早期的基于規(guī)則的模式）。這種網(wǎng)絡(luò)支持任何變量子集相對于另一子集的條件概率計(jì)算。貝葉斯網(wǎng)絡(luò)是領(lǐng)域中變量關(guān)系的直接表示，而不是推理過程。網(wǎng)絡(luò)中的方向表示變量間真正的因果關(guān)系而不是推理過程的信息流向。－－因此在貝葉斯推理過程中，推理過程可以沿任何方向進(jìn)行（預(yù)測、診斷、解釋。從知識工程的角度講，貝葉斯網(wǎng)絡(luò)是用圖形結(jié)構(gòu)和數(shù)值參數(shù)來表示不確定性知識的知識系統(tǒng)，因而有時(shí)也稱為因果網(wǎng)、信任網(wǎng)絡(luò)和影響圖。2025/2/413史忠植高級人工智能貝葉斯規(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(AA1A2A3A4A5A6E2025/2/414史忠植高級人工智能貝葉斯網(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)中特別有效。

2025/2/415史忠植高級人工智能IndustrialProcessorFaultDiagnosis-byIntelAuxiliaryTurbineDiagnosis-GEMSbyGEDiagnosisofspaceshuttlepropulsionsystems-VISTAbyNASA/RockwellSituationassessmentfornuclearpowerplant-NRCMilitaryAuBmaticTargetRecognition-MITREAuBnomouscontrolofunmannedunderwatervehicle-LockheedMartinAssessmentofIntentMedicalDiagnosisInternalMedicinePathologydiagnosis-IntellipathbyChapman&HallBreastCancerManagerwithIntellipathCommercialFinancialMarketAnalysisInformationRetrievalSoftwaretroubleshootingandadvice-Windows95&Office97,andSoftwaredebugging-AmericanAirlines’SABREonlinereservationsystem貝葉斯網(wǎng)絡(luò)的應(yīng)用2025/2/416史忠植高級人工智能貝葉斯網(wǎng)絡(luò)－來自醫(yī)療診斷的例子VisitBAsiaTuberculosisTuberculosisorCancerXRayResultDyspneaBronchitisLungCancerSmokingPatientInformationMedicalDifficultiesDiagnosticTestsMedicalDifficultiesTuborCanTrueTrueFalseFalseBronchitisPresentAbsentPresentAbsentPresent0.900.700.800.10Absent0.l00.300.200.90Dyspnea2025/2/417史忠植高級人工智能構(gòu)建貝葉斯網(wǎng)BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2025/2/418史忠植高級人工智能從數(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)2025/2/419史忠植高級人工智能1)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta--=---GGG先驗(yàn)分布的選取－beta分布2025/2/420史忠植高級人工智能先驗(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=?????====--=2025/2/421史忠植高級人工智能貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)基于搜索評分的方法:初始化貝葉斯網(wǎng)絡(luò)為孤立節(jié)點(diǎn)使用啟發(fā)式方法為網(wǎng)絡(luò)加邊使用評分函數(shù)評測新的結(jié)構(gòu)是否為更好貝葉斯評分

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

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

建立完全的無向圖，圖中的頂點(diǎn)是變量，邊是變量之間的互信息建立最大權(quán)張成樹根據(jù)一定的節(jié)點(diǎn)序關(guān)系，設(shè)置邊的方向2025/2/423史忠植高級人工智能基于CI的貝葉斯網(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-可分的，那么移走這條邊。2025/2/424史忠植高級人工智能貝葉斯網(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(A2025/2/425史忠植高級人工智能推理方法概述精確推理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是推理復(fù)雜性的主要原因；當(dāng)前的一些精確算法是有效地，能夠解決現(xiàn)實(shí)中的大部分問題由于對知識的認(rèn)知程度，精確推理還存在一些問題近似推理證據(jù)的低似然性和函數(shù)關(guān)系是近似推理中復(fù)雜性的主要原因NPHard2025/2/426史忠植高級人工智能影響推理的因素網(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ù)的特征2025/2/427史忠植高級人工智能查詢的任務(wù)類型預(yù)測對給定的模型，將要發(fā)生什么給定證據(jù)下的后驗(yàn)計(jì)算所有的邊界后驗(yàn)指定的邊界后驗(yàn)指定的聯(lián)合條件查詢最可能的假設(shè)

一個(gè)最可能的

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

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

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

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

P(B)=ΣAP(AB)效率低AB2025/2/432史忠植高級人工智能精確推理－Na?veBayesian結(jié)構(gòu)簡單－只有兩層結(jié)構(gòu)推理復(fù)雜性與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)呈線性關(guān)系2025/2/433史忠植高級人工智能HowanaiveBayesclassifies?BayesDecisionrule:Findthecthatmaximizes(1)(1)Givenaninstancevector

Calculateforallclassc2025/2/434史忠植高級人工智能HowtotrainanaiveBayes?

(discretecase)SupposeXj

isadiscretevariablewhosevalueisxj

thenusuallywecanestimateWhere

is#ofthetrainingexamplesbelongingtoclassc

andis#oftrainingexamplesbelongingtoclassc

andhavingtheirXj=xj;

αj,α

are“priorparameters.”fromtrainingdata.(Dirichlet

priors;[Cooper,1999])2025/2/435史忠植高級人工智能HowtotrainanaiveBayes?

continuouscase

ParameterestimationAssumingisGaussian

(Duda&Hart1973)

DiscretizationEqualwidthintervalbinningBinlogl(Spector,1990)1-R(Holts,1994)Entropy-based(Fayyad&Irani,1993)2025/2/436史忠植高級人工智能圖約簡算法－一般原理基本觀點(diǎn) 任何概率查詢可以表示成網(wǎng)絡(luò)的子網(wǎng)，推理的目的是把網(wǎng)絡(luò)分解成幾個(gè)子網(wǎng)三個(gè)基本操作擬轉(zhuǎn)弧操作（ArcReversal）－貝葉斯公式孤寡點(diǎn)移出(Barrennoderemoval)－求和公式值節(jié)點(diǎn)歸并(MergewithValuenode)－期望最大化 2025/2/437史忠植高級人工智能約簡算法－擬轉(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)2025/2/438史忠植高級人工智能約簡算法－孤寡點(diǎn)移出孤寡點(diǎn)－沒有孩子的節(jié)點(diǎn)2025/2/439史忠植高級人工智能約簡算法－值節(jié)點(diǎn)歸并值節(jié)點(diǎn)－證據(jù)節(jié)點(diǎn)或賦值節(jié)點(diǎn)2025/2/440史忠植高級人工智能Polytree算法－介紹該算法由Pearl于1982年首次提出基本觀點(diǎn)計(jì)算邊界后驗(yàn)的消息傳遞機(jī)制

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

pi算子：消息向下傳向孩子2025/2/441史忠植高級人工智能Polytree算法－單連通網(wǎng)定義：在任何兩個(gè)節(jié)點(diǎn)之間存在且僅存在一條路徑（忽略方向）XMultipleparentsand/ormultiplechildren2025/2/442史忠植高級人工智能單連通網(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)化常量2025/2/443史忠植高級人工智能概率的雙向傳播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)2025/2/444史忠植高級人工智能傳播算法對每個(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|y2025/2/445史忠植高級人工智能實(shí)例－描述p(A1)=0.9p(A2)=0.1MB|A=MC|B=

A1A2B1B2C1C2C3ABC.8.2.1.9[].5.4.1.1.3.6[]ChDiA1A2C1C2C3B1B22025/2/446史忠植高級人工智能實(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.02025/2/447史忠植高級人工智能實(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.ABC2025/2/448史忠植高級人工智能[]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.ABC2025/2/449史忠植高級人工智能實(shí)例－第三次傳播

(A) Bel