2009高級(jí)人工智能大綱日歷及教案4網(wǎng)絡(luò)

1、2022/8/61高級(jí)人工智能 第四章 貝葉斯網(wǎng)絡(luò) 4.1概述 4.2貝葉斯概率基礎(chǔ)4.3貝葉斯學(xué)習(xí)理論4.4簡(jiǎn)單貝葉斯學(xué)習(xí)模型4.5貝葉斯網(wǎng)絡(luò)的建造 4.6貝葉斯?jié)撛谡Z義模型 內(nèi)容提要2022/8/63貝葉斯網(wǎng)絡(luò)是什么貝葉斯網(wǎng)絡(luò)是用來表示變量間連接概率的圖形模式，它提供了一種自然的表示因果信息的方法，用來發(fā)現(xiàn)數(shù)據(jù)間的潛在關(guān)系。在這個(gè)網(wǎng)絡(luò)中，用節(jié)點(diǎn)表示變量，有向邊表示變量間的依賴關(guān)系。貝葉斯方法正在以其獨(dú)特的不確定性知識(shí)表達(dá)形式、豐富的概率表達(dá)能力、綜合先驗(yàn)知識(shí)的增量學(xué)習(xí)特性等成為當(dāng)前數(shù)據(jù)挖掘眾多方法中最為引人注目的焦點(diǎn)之一。2022/8/64貝葉斯網(wǎng)絡(luò)是什么貝葉斯（Reverend Thom

2、as Bayes 1702-1761）學(xué)派奠基性的工作是貝葉斯的論文“關(guān)于幾率性問題求解的評(píng)論”?；蛟S是他自己感覺到它的學(xué)說還有不完善的地方，這一論文在他生前并沒有發(fā)表，而是在他死后，由他的朋友發(fā)表的。著名的數(shù)學(xué)家拉普拉斯（Laplace P. S.）用貝葉斯的方法導(dǎo)出了重要的“相繼律”，貝葉斯的方法和理論逐漸被人理解和重視起來。但由于當(dāng)時(shí)貝葉斯方法在理論和實(shí)際應(yīng)用中還存在很多不完善的地方，因而在十九世紀(jì)并未被普遍接受。2022/8/65貝葉斯網(wǎng)絡(luò)是什么二十世紀(jì)初，意大利的菲納特（B. de Finetti）以及英國的杰弗萊（Jeffreys H.）都對(duì)貝葉斯學(xué)派的理論作出重要的貢獻(xiàn)。第二次世

3、界大戰(zhàn)后，瓦爾德（Wald A.）提出了統(tǒng)計(jì)的決策理論，在這一理論中，貝葉斯解占有重要的地位；信息論的發(fā)展也對(duì)貝葉斯學(xué)派做出了新的貢獻(xiàn)。1958年英國最悠久的統(tǒng)計(jì)雜志Biometrika全文重新刊登了貝葉斯的論文，20世紀(jì)50年代，以羅賓斯（Robbins H.）為代表，提出了經(jīng)驗(yàn)貝葉斯方法和經(jīng)典方法相結(jié)合，引起統(tǒng)計(jì)界的廣泛注意，這一方法很快就顯示出它的優(yōu)點(diǎn)，成為很活躍的一個(gè)方向。2022/8/66貝葉斯網(wǎng)絡(luò)是什么隨著人工智能的發(fā)展，尤其是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等興起，為貝葉斯理論的發(fā)展和應(yīng)用提供了更為廣闊的空間。貝葉斯理論的內(nèi)涵也比以前有了很大的變化。80年代貝葉斯網(wǎng)絡(luò)用于專家系統(tǒng)的知識(shí)表示，9

4、0年代進(jìn)一步研究可學(xué)習(xí)的貝葉斯網(wǎng)絡(luò)，用于數(shù)據(jù)采掘和機(jī)器學(xué)習(xí)。近年來，貝葉斯學(xué)習(xí)理論方面的文章更是層出不窮，內(nèi)容涵蓋了人工智能的大部分領(lǐng)域，包括因果推理、不確定性知識(shí)表達(dá)、模式識(shí)別和聚類分析等。并且出現(xiàn)了專門研究貝葉斯理論的組織和學(xué)術(shù)刊物ISBA2022/8/67貝葉斯網(wǎng)絡(luò)的應(yīng)用領(lǐng)域輔助智能決策數(shù)據(jù)融合模式識(shí)別醫(yī)療診斷文本理解數(shù)據(jù)挖掘2022/8/68統(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), 即 pP(A) 可見概率就是頻率的穩(wěn)定中心。任何事件A的概率為不大于1的非負(fù)實(shí)數(shù)，即

5、 0P(A)1 2022/8/69條件概率 條件概率:我們把事件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(AB)或P(B)P(BA)時(shí)，則稱A與B是相互獨(dú)立的事件。 2022/8/610加法定理 兩個(gè)不相容(互斥)事件之和的概率,等于兩個(gè)事件概率之和,即 P(A+B) P(A)P(B) 若A、B為兩任意事件，則：P(A+B)P(A)P(B)P(AB)2022/8/611乘法定理 設(shè)A、B為兩個(gè)任意的非零事件，則其乘積的概率等于A(或B)的概

6、率與在A(或B)出現(xiàn)的條件下B(或A)出現(xiàn)的條件概率的乘積。 P(AB)P(A)P(B|A) 或 P(AB)P(B)P(A|B)2022/8/612貝葉斯網(wǎng)絡(luò)定義圖形描述概率描述ColdAllegoryCatSneezeScratch貝葉斯網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的有向無環(huán)圖，這里每個(gè)節(jié)點(diǎn)表示領(lǐng)域變量，每條邊表示變量間的概率依賴關(guān)系，同時(shí)對(duì)每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)著一個(gè)條件概率分布表(CPT) ，指明了該變量與父節(jié)點(diǎn)之間概率依賴的數(shù)量關(guān)系。2022/8/613幾點(diǎn)說明貝葉斯網(wǎng)絡(luò)的特點(diǎn)：雙向推理能力（預(yù)測(cè)和診斷）快速的調(diào)試和重構(gòu)能力具有較強(qiáng)的概率統(tǒng)計(jì)基礎(chǔ)用于人工智能和專家系統(tǒng)的不確定推理（優(yōu)于早期的基

7、于規(guī)則的模式）。這種網(wǎng)絡(luò)支持任何變量子集相對(duì)于另一子集的條件概率計(jì)算。貝葉斯網(wǎng)絡(luò)是領(lǐng)域中變量關(guān)系的直接表示，而不是推理過程。網(wǎng)絡(luò)中的方向表示變量間真正的因果關(guān)系而不是推理過程的信息流向。 因此在貝葉斯推理過程中，推理過程可以沿任何方向進(jìn)行（預(yù)測(cè)、診斷、解釋。從知識(shí)工程的角度講，貝葉斯網(wǎng)絡(luò)是用圖形結(jié)構(gòu)和數(shù)值參數(shù)來表示不確定性知識(shí)的知識(shí)系統(tǒng)，因而有時(shí)也稱為因果網(wǎng)、信任網(wǎng)絡(luò)和影響圖。2022/8/614貝葉斯規(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)

8、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/8/615貝葉斯網(wǎng)絡(luò)的概率解釋任何完整的概率模型必須具有表示（直接或間接）該領(lǐng)域變量聯(lián)合分布的能力。完全的枚舉需要指數(shù)級(jí)的規(guī)模（相對(duì)于領(lǐng)域變量個(gè)數(shù)）貝葉斯網(wǎng)絡(luò)提供了這種聯(lián)合概率分布的緊湊表示：分解聯(lián)合分布為幾個(gè)局部分布的乘積： 從公式可以看出，需要的參數(shù)個(gè)數(shù)隨網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)呈線性增長(zhǎng)，而聯(lián)合分布的計(jì)算呈指數(shù)增長(zhǎng)。網(wǎng)絡(luò)中變量間獨(dú)立性的指定是實(shí)現(xiàn)緊湊表示的關(guān)鍵。這種獨(dú)立性關(guān)系在通過人類專家構(gòu)造貝葉斯網(wǎng)中特別有效。 2022/8/616Industri

9、alProcessor Fault Diagnosis - by IntelAuxiliary Turbine Diagnosis - GEMS by GE Diagnosis of space shuttle propulsion systems - VISTA by NASA/RockwellSituation assessment for nuclear power plant - NRCMilitaryAuBmatic Target Recognition - MITREAuBnomous control of unmanned underwater vehicle - Lockhee

10、d MartinAssessment of IntentMedical DiagnosisInternal MedicinePathology diagnosis - Intellipath by Chapman & HallBreast Cancer Manager with IntellipathCommercialFinancial Market AnalysisInformation RetrievalSoftware troubleshooting and advice - Windows 95 & Office 97, and Software debugging - Americ

11、an Airlines SABRE online reservation system貝葉斯網(wǎng)絡(luò)的應(yīng)用2022/8/617貝葉斯網(wǎng)絡(luò)來自醫(yī)療診斷的例子Visit To AsiaTuberculosisTuberculosisor CancerXRay ResultDyspneaBronchitisLung CancerSmokingPatient InformationMedical DifficultiesDiagnostic TestsMedical DifficultiesTub or CanTrueTrueFalseFalseBronchitisPresentAbsentPresent

12、AbsentPresent0.900.700.800.10Absent0.l00.300.200.90Dyspnea2022/8/618構(gòu)建貝葉斯網(wǎng)BayesianNetworkBayesianNetworkBayesianNetworkProblemDomainProblemDomainProblemDomainExpertKnowledgeExpertKnowledgeTrainingDataTrainingDataProbabilityElicitorLearningAlgorithmLearningAlgorithm2022/8/619從數(shù)據(jù)中學(xué)習(xí)共軛分布族先驗(yàn)與后驗(yàn)屬于同一分布族預(yù)先

13、給定一個(gè)似然分布形式對(duì)于變量定義在0-1之間的概率分布，存在一個(gè)離散的樣本空間Beta 對(duì)應(yīng)著 2 個(gè)似然狀態(tài)多變量 Dirichlet 分布對(duì)應(yīng) 2個(gè)以上的狀態(tài)2022/8/6201)n(nm/n)m(1variance+-=nmmean=x)(1xm)(n(m)(n)n)m,|(xp1mn1mBeta-=-GGG先驗(yàn)分布的選取beta分布2022/8/621先驗(yàn)分布的選取多項(xiàng)Dirichlet分布1)m(m)m/m(1mstate i theof variancemmstate i theofmean .xxx)(m).(m)(m)m()m,.,m,m|(xpN1iiN1iiN1iiiit

14、hN1iiith1m1-m1mN21N1iiN21DirichletN21+-=GGGG=-=2022/8/622貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)基于搜索評(píng)分的方法: 初始化貝葉斯網(wǎng)絡(luò)為孤立節(jié)點(diǎn)使用啟發(fā)式方法為網(wǎng)絡(luò)加邊使用評(píng)分函數(shù)評(píng)測(cè)新的結(jié)構(gòu)是否為更好 貝葉斯評(píng)分 基于熵的評(píng)分 最小描述長(zhǎng)度（MDL）重復(fù)這個(gè)過程，直到找不到更好的結(jié)構(gòu) 基于依賴分析的方法:通過使用條件獨(dú)立性檢驗(yàn)conditional independence (CI) 找到網(wǎng)絡(luò)的依賴結(jié)構(gòu)2022/8/623基于MDL的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí)計(jì)算每一點(diǎn)對(duì)之間的互信息：建立完全的無向圖，圖中的頂點(diǎn)是變量，邊是變量之間的互信息建立最大權(quán)張成樹根據(jù)一定

15、的節(jié)點(diǎn)序關(guān)系，設(shè)置邊的方向2022/8/624基于CI的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)假定：節(jié)點(diǎn)序已知第一階段 (Drafting)計(jì)算每對(duì)節(jié)點(diǎn)間的互信息，建立完整的無向圖. 第二階段 (Thickening)如果節(jié)點(diǎn)對(duì)不可能d-可分的話，把這一點(diǎn)對(duì)加入到邊集中。第三階段 (Thinning)檢查邊集中的每個(gè)點(diǎn)對(duì)，如果兩個(gè)節(jié)點(diǎn)是d-可分的，那么移走這條邊。2022/8/625貝葉斯網(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/8

16、/626推理方法概述精確推理 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是推理復(fù)雜性的主要原因； 當(dāng)前的一些精確算法是有效地，能夠解決現(xiàn)實(shí)中的大部分問題 由于對(duì)知識(shí)的認(rèn)知程度，精確推理還存在一些問題近似推理 證據(jù)的低似然性和函數(shù)關(guān)系 是近似推理中復(fù)雜性的主要原因NP Hard2022/8/627影響推理的因素網(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/8/628查詢的任務(wù)類型預(yù)測(cè) 對(duì)給定的模型，將要發(fā)生什么給定證據(jù)下的后驗(yàn)計(jì)算所有的邊界后驗(yàn)指定的邊界后驗(yàn)指定的

17、聯(lián)合條件查詢最可能的假設(shè) 一個(gè)最可能的 n 個(gè)最可能的決策策略2022/8/629繼續(xù)前面的醫(yī)療診斷例子貝葉斯推理中非條件分布和邊界分布是常見的查詢模式一個(gè)節(jié)點(diǎn)的邊界分布也稱為該節(jié)點(diǎn)的信任函數(shù)2022/8/630推理過程中的信任傳播2022/8/631推理算法精確推理聯(lián)合概率計(jì)算Nave Bayesian圖約簡(jiǎn)算法Polytree算法 近似推理前向模擬推理隨機(jī)模擬推理 The algorithms purpose is “ fusing and propagating the impactof new evidence and beliefs through Bayesian networks

18、 so that each proposition eventually will be assigned a certainty measure consistent with the axioms of probability theory.” (Pearl, 1988, p 143)2022/8/632精確推理計(jì)算聯(lián)合概率任何查詢都可以通過聯(lián)合概率回答步驟：計(jì)算聯(lián)合概率 P(AB)=P(A)*P(B|A)邊界化不在查詢中的變量 P(B)=AP(AB)效率低AB2022/8/633精確推理Nave Bayesian結(jié)構(gòu)簡(jiǎn)單只有兩層結(jié)構(gòu)推理復(fù)雜性與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)呈線性關(guān)系2022/8/634H

19、ow a naive Bayes classifies?Bayes Decision rule : Find the c that maximizes (1)(1)Given an instance vector Calculate for all class c2022/8/635How to train a naive Bayes?(discrete case)Suppose Xj is a discrete variable whose value is xj then usually we can estimateWhere is # of the training examples

20、belonging to class c and is # of training examples belonging to class c and having their Xj=xj; j , are “prior parameters.”from training data. (Dirichlet priors;Cooper,1999)2022/8/636How to train a naive Bayes?continuous case Parameter estimationAssuming is Gaussian (Duda & Hart 1973) Discretization

21、Equal width interval binningBin log l (Spector, 1990)1-R (Holts, 1994)Entropy-based (Fayyad & Irani, 1993)2022/8/637圖約簡(jiǎn)算法一般原理基本觀點(diǎn)任何概率查詢可以表示成網(wǎng)絡(luò)的子網(wǎng)，推理的目的是把網(wǎng)絡(luò)分解成幾個(gè)子網(wǎng)三個(gè)基本操作擬轉(zhuǎn)弧操作（Arc Reversal）貝葉斯公式孤寡點(diǎn)移出(Barren node removal)求和公式值節(jié)點(diǎn)歸并(Merge with Value node)期望最大化2022/8/638約簡(jiǎn)算法擬轉(zhuǎn)弧操作X1X3X2X1X3X2X1X3X2X1X3X2p(

22、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/8/639約簡(jiǎn)算法孤寡點(diǎn)移出孤寡點(diǎn)沒有孩子的節(jié)點(diǎn)2022/8/640約簡(jiǎn)算法值節(jié)點(diǎn)歸并值節(jié)點(diǎn)證據(jù)節(jié)點(diǎn)或賦值節(jié)點(diǎn)2022/8/641Polyt

23、ree算法介紹該算法由Pearl 于1982年首次提出基本觀點(diǎn) 計(jì)算邊界后驗(yàn)的消息傳遞機(jī)制 Lambda 算子：消息向上傳向父親 pi 算子：消息向下傳向孩子2022/8/642Polytree算法單連通網(wǎng)定義： 在任何兩個(gè)節(jié)點(diǎn)之間存在且僅存在一條路徑（忽略方向）XMultiple parents and/ormultiple children2022/8/643單連通網(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)

24、 . . . 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/8/644概率的雙向傳播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) = x p(y|x,

25、e+) p(x| e+) = x p(y|x) (x) = (x) My|x(y) = z p(e-|y, z) p(z| y) = z p(e-|z) p(z| y) = z (z) p(z| y) = Mz|y (z)2022/8/645傳播算法對(duì)每個(gè)節(jié)點(diǎn)引入證據(jù)時(shí)，產(chǎn)生:沿著弧的方向傳播一組 “p” 消息逆著弧的方向傳播一組 “l(fā)” 消息對(duì)接收 “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

26、)p(t) l(t)ZBEL(t)p(t) l(t)Mu|tMx|uMy|xMz|y2022/8/646實(shí)例描述p(A1) = 0.9p(A2) = 0.1M B|A = M C|B = A1A2B1B2C1C2C3ABC.8 .2.1 .9.5 .4 .1.1 .3 .6ChDiA1A2C1C2C3B1B22022/8/647實(shí)例算子設(shè)定ABC(1) 初始化 lambda 算子為單位向量; Bel(A) = (A) (A)(A) Bel(A) (A)A1 0.9 0.9 1.0A2 0.1 0.1 1.0(2) (B) = (A) MB|A; Bel(B) = (B) (B)(B) Bel(

27、B) (B)B1 0.73 0.73 1.0B2 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.0C2 0.35 0.36 1.0C3 0.24 0.24 1.02022/8/648實(shí)例第一次傳播tTRT=05l(). 1 .6 t=0(lR)=.8 .2pt = 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