AI-05-15-貝葉斯網(wǎng)絡(luò)-----人工智能課程--浙江大學(xué)研究生.ppt

1、徐從富,浙江大學(xué)人工智能研究所 2005年9月11日,貝葉斯網(wǎng)絡(luò) Bayesian Network,研究生人工智能補充課件,內(nèi)容提綱,什么是貝葉斯網(wǎng)絡(luò)？ 貝葉斯網(wǎng)絡(luò)的語義 條件分布的有效表達 貝葉斯網(wǎng)絡(luò)中的精確推理 貝葉斯網(wǎng)絡(luò)中的近似推理 課后習(xí)題、編程實現(xiàn)及研讀論文,1、什么是貝葉斯網(wǎng)絡(luò)？,貝葉斯網(wǎng)絡(luò)的由來 貝葉斯網(wǎng)絡(luò)的定義 貝葉斯網(wǎng)絡(luò)的別名 獨立和條件獨立 貝葉斯網(wǎng)絡(luò)示例,貝葉斯網(wǎng)絡(luò)的由來,全聯(lián)合概率計算復(fù)雜性十分巨大 樸素貝葉斯太過簡單 現(xiàn)實需要一種自然、有效的方式來捕捉和推理不確定性知識 變量之間的獨立性和條件獨立性可大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目,B. 貝葉斯網(wǎng)絡(luò)的定義

2、,是一個有向無環(huán)圖(DAG) 隨機變量集組成網(wǎng)絡(luò)節(jié)點，變量可離散或連續(xù) 一個連接節(jié)點對的有向邊或箭頭集合 每節(jié)點Xi都有一個條件概率分布表：P(Xi|Parents(Xi)，量化其父節(jié)點對該節(jié)點的影響,C. 貝葉斯網(wǎng)絡(luò)的別名,信念網(wǎng)(Belief Network) 概率網(wǎng)絡(luò)(Probability Network) 因果網(wǎng)絡(luò)(Causal Network) 知識圖(Knowledge Map) 圖模型(Graphical Model)或概率圖模型 決策網(wǎng)絡(luò)(Decision Network) 影響圖(Influence Diagram),D. 獨立和條件獨立,Weather,Cavity,Ca

3、tch,Toothache,Weather和其它3個變量相互獨立 給定Cavity后，Toothache和Catch條件獨立,E. 貝葉斯網(wǎng)絡(luò)示例,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,貝葉斯網(wǎng)絡(luò)的語義,貝葉斯網(wǎng)絡(luò)的兩種含義 對聯(lián)合概率分布的表示 構(gòu)造網(wǎng)絡(luò) 對條件依賴性語句集合的編碼 設(shè)計推理過程 貝葉斯網(wǎng)絡(luò)的語義 P(x1,., xn) = P(x1|parent(x1). P(x1|parent(xn),貝葉斯網(wǎng)絡(luò)的語義公式計算示例：,試計算：報警器響了，但既沒有盜賊闖入，也沒有發(fā)生地震，同時John和Mary都給你打電話的概率。 解：

4、 P(j,m,a,b,e) = P(j|a)P(m|a)P(a|b,e)P(e) = 0.9x0.7x0.001x0.999x0.998 = 0.00062 = 0.062%,貝葉斯網(wǎng)絡(luò)的特性：,作為對域的一種完備而無冗余的表示，貝葉斯網(wǎng)絡(luò)比全聯(lián)合概率分布緊湊得多 BN的緊湊性是局部結(jié)構(gòu)化(Locally structured, 也稱稀疏, Sparse)系統(tǒng)一個非常普遍特性的實例 BN中每個節(jié)點只與數(shù)量有限的其它節(jié)點發(fā)生直接的相互作用 假設(shè)節(jié)點數(shù)n=30, 每節(jié)點有5個父節(jié)點，則BN需30 x25=960個數(shù)據(jù)，而全聯(lián)合概率分布需要230= 10億個。,貝葉斯網(wǎng)絡(luò)的構(gòu)造原則：,首先，添加“根

5、本原因”節(jié)點 然后，加入受它們直接影響的變量 依次類推，直到葉節(jié)點，即對其它變量沒有直接因果影響的節(jié)點 兩節(jié)點間的有向邊的取舍原則：更高精度概率的重要性與指定額外信息的代價的折衷 “因果模型”比“診斷模型”需要更少的數(shù)據(jù)，且這些數(shù)據(jù)也更容易得到,貝葉斯網(wǎng)絡(luò)中的條件獨立關(guān)系：,給定父節(jié)點，一個節(jié)點與它的非后代節(jié)點是條件獨立的 給定一個節(jié)點的父節(jié)點、子節(jié)點以及子節(jié)點的父節(jié)點馬爾可夫覆蓋(Markov blanket)，這個節(jié)點和網(wǎng)絡(luò)中的所有其它節(jié)點是條件獨立的,U1,Um,X,Z1j,Znj,Y1,Yn,【說明】： 給定節(jié)點X的父節(jié)點U1. Um，節(jié)點X與它的非后代節(jié)點（即Zij）是條件獨立的。,

6、U1,Um,X,Z1j,Znj,Y1,Yn,【說明】： 給定馬爾可夫覆蓋（兩圓圈之間的區(qū)域），節(jié)點X和網(wǎng)絡(luò)中所有其它節(jié)點都是條件獨立的。,3、條件概率分布的有效表達,已知：P(fever | cold, flu, malaria) = 0.6 P(fever | cold, flu, malaria) = 0.2 P(fever | cold, flu, malaria) = 0.1， 可利用“噪聲或”（Noisy-OR）關(guān)系得到下表：,包含連續(xù)變量的貝葉斯網(wǎng)絡(luò)Hybrid BN,Subsidy,Harvest,Buys,Cost,離散隨機變量：Subsidy, Buys; 連續(xù)隨機變量：Ha

7、rvest, Cost.,線性高斯分布：,P(c | h, subsidy) = N(ath + bt, t2)(c) = 1/ (t21/2) e 1/2c-(ath + bt)/t P(c | h, subsidy) = N(afh + bf, f2)(c) = 1/ (f21/2) e 1/2c-(afh + bf)/t S型函數(shù)(Sigmoid function) p(buys | Cost = c) = 1 / 1 + exp-2(-u+)/ ,4、貝葉斯網(wǎng)絡(luò)中的精確推理,變量分類： 證據(jù)變量集E 特定事件e， 查詢變量X 非證據(jù)變量集 Y隱變量（Hidden variable） 全

8、部變量的集合U = x E Y,（1）通過枚舉進行推理,Burglary,Earthquake,MaryCalls,JohnCalls,Alarm,已知，一個事件e = JohnCalls = true, and MaryCalls = true，試問出現(xiàn)盜賊的概率是多少？ 解：P(X|e) = P(X,e) = yP(X,e,y) 而P(X,e,y)可寫成條件概率乘積的形式。 因此，在貝葉斯網(wǎng)絡(luò)中可通過計算條件概率的乘積并求和來回答查詢。 P(Burgary | JohnCalls = true, MaryCalls = true)簡寫為： P(B | j, m) = P(B, j, m)

9、= eaP(B, e, a, j, m) = ea P(b)P(e)P(a|b,e)P(j|a)P(m|a) = P(b) e P(e) a P(a|b,e)P(j|a)P(m|a),+,+,+,P(b)0.01,P(e) 0.002,P(e) 0.998,P(a|b,e) 0.95,P(a|b,e) 0.05,P(a|b,e) 0.94,P(a|b,e) 0.06,P(m|a) 0.70,P(j|a) 0.90,P(j|a) 0.05,P(j|a) 0.90,P(j|a) 0.05,P(m|a) 0.70,P(m|a) 0.01,P(m|a) 0.01,P(b | j, m)的自頂向下的計算

10、過程,P(B | j, m) = P(B, j, m) = eaP(B, e, a, j, m) = ea P(b)P(e)P(a|b,e)P(j|a)P(m|a) = P(b) e P(e) a P(a|b,e)P(j|a)P(m|a) = 0.0010.002(0.950.90.7 + 0.050.05 0.01) + 0.998 (0.94 0.9 0.7+0.06 0.05 0.01) = 0.00059224,+,+,+,P(b)0.999,P(e) 0.002,P(e) 0.998,P(a|b,e) 0.29,P(a|b,e) 0.71,P(a|b,e) 0.001,P(a|b,e

11、) 0.999,P(m|a) 0.70,P(j|a) 0.90,P(j|a) 0.05,P(j|a) 0.90,P(j|a) 0.05,P(m|a) 0.70,P(m|a) 0.01,P(m|a) 0.01,P(b | j, m)的自頂向下的計算過程,P(B | j, m) = P(B, j, m) = eaP(B, e, a, j, m) = ea P(b)P(e)P(a|b,e)P(j|a)P(m|a) = P(b) e P(e) a P(a|b,e)P(j|a)P(m|a) = 0.9990.002(0.290.90.7 + 0.710.05 0.01) + 0.998 (0.001 0

12、.9 0.7+0.999 0.05 0.01) = 0.0014919 因此，P(B|j, m) = 即在John和Mary都打電話的條件下，出現(xiàn)盜賊的概率約為28%。,【課后習(xí)題1】,國家政策 （C）,學(xué)校政策 （U）,身體狀況 差（B）,過勞死 （D）,工作壓力 大（W）,已知：一個事件e = 學(xué)校政策U = true, and 工作壓力大 = true， 請根據(jù)上述枚舉法計算出現(xiàn)過勞死的概率。 （2）變量消元算法 消除重復(fù)計算，提高枚舉算法的效率 保存中間結(jié)果，以備多次使用 從右到左（在樹結(jié)構(gòu)中為自底向上）的次序計算BN的計算公式 算法過程：參見人工智能：一種現(xiàn)代方法中的第14章14.4

13、.2節(jié),（3）Clustering算法（Joint Tree算法） 單獨節(jié)點聯(lián)合起來形成Cluster節(jié)點，使得BN結(jié)構(gòu)成為一棵多樹（Polytree） 多樹單連通網(wǎng)絡(luò)，即任何兩節(jié)點間至多只有一條路徑相連 概率推理包含命題邏輯推理作為其特殊情況，故BN的推理是一個NP問題 在多連通的BN結(jié)構(gòu)中，及時每個節(jié)點的父節(jié)點個數(shù)有固定的界限，在最壞的情況下，變量消元算法仍可能具有指數(shù)級時間和空間復(fù)雜度,多連通網(wǎng)絡(luò)及其CPT：,Cloudy,Rain,Wet Grass,Sprinkler,等價的聯(lián)合樹及其CPT：,Cloudy,Spr+Rain,Wet Grass,5、貝葉斯網(wǎng)絡(luò)的近似推理,大規(guī)模多連通

14、BN的精確推理是不可操作的， 必須通過近似推理來解決。 后驗概率計算的主要采樣方法 直接采樣方法 馬爾可夫鏈蒙特卡羅（MCMC）方法 變分法(Variational method) 環(huán)傳播(Loopy propagation)方法,直接采樣方法： 直接采樣算法 拒絕采樣(Rejection sampling)算法 似然加權(quán)(Likelihood weighting)算法 上述方法的詳細(xì)步驟請參見： 人工智能：一種現(xiàn)代方法第14章14.5.1節(jié) Berkeley大學(xué)Russell等人制作的PPT /,馬爾可夫鏈蒙特卡羅（MCMC）算法思想： 對

15、前一個事件進行隨機改變而生成事件樣本 BN為每個變量指定了一個特定的當(dāng)前狀態(tài) 下一個狀態(tài)是通過對某個非證據(jù)變量Xi進行采樣來產(chǎn)生，取決于Xi的馬爾可夫覆蓋中的變量當(dāng)前值 MCMC方法可視為：在狀態(tài)空間中所有可能的完整賦值空間的隨機走動每次改變一個變量，但是證據(jù)變量的值固定不變。,MCMC算法執(zhí)行過程示例：,Cloudy,Rain,Wet Grass,Sprinkler,【要求】：查詢P(Rain | Sprinkler = true, WetGrass = true)的概率,MCMC算法執(zhí)行步驟： 證據(jù)變量Sprinkler, WetGrass固定為true 隱變量Cloudy和查詢變量Rai

16、n隨機初始化，例如， Cloudy = true, Rain = false，初始狀態(tài)為：C=true, S=true, R=false, W=true 反復(fù)執(zhí)行如下步驟： （1） 根據(jù)Cloudy的馬爾可夫覆蓋(MB)變量的當(dāng)前值，對Cloudy采樣，即根據(jù)P(Cloudy|Sprinkler= true, Rain=false)（即轉(zhuǎn)移概率）來采樣。即： P(C|S, R) = P(C,S,R) / P(S, R) = P(C)P(S|C)P(R|C) / P(C)P(S|C)P(R|C)+P(C)P(S|C)P(R|C) =() / +0.5 0.50

17、.8=0.04762,再由計算機生成一個隨機數(shù)q0,1（可參照概率統(tǒng)計中的隨機數(shù)生成方法）。比較轉(zhuǎn)移概率值與隨機數(shù)q的大小，以決定是繼續(xù)停留在原狀態(tài)，還是轉(zhuǎn)移到下一個新的狀態(tài)。判別方法如下： if q P(C|S, R) then 轉(zhuǎn)移到下一個新狀態(tài)； otherwise 停留在原狀態(tài). 對于本例子，假設(shè)生成的隨機數(shù)q=0.0489，可知， 轉(zhuǎn)移概率P(Cloudy|Sprinkler= true, Rain=false)= 0.04762 q=0.0489，所以，Cloudy由true狀態(tài)轉(zhuǎn)移到新狀態(tài)false，即采樣結(jié)果為：Cloudy = false。故新的當(dāng)前狀態(tài)為： C=false,

18、 S=true, R=false, W=true,（2） 根據(jù)Rain節(jié)點的馬爾可夫覆蓋(MB)變量的當(dāng)前值，對Rain采樣，即根據(jù)P(Rain | Cloudy = false, Sprinkler = true, WetGrass = true)來采樣。假設(shè)采樣結(jié)果為：Rain = true。故新的當(dāng)前狀態(tài)為： C=false, S=true, R=true, W=true 【注】： 上述過程中所訪問的每一個狀態(tài)都是一個樣本，能對查詢變量Rain的估計有貢獻。 （3）重復(fù)上述步驟，直到所要求的訪問次數(shù)N。 若為true, false的次數(shù)分別為n1, n2，則查詢解為： Normalize

19、() = 若上述過程訪問了20個Rain=true的狀態(tài)和60個Rain = false的狀態(tài)，則所求查詢的解為。,Cloudy,Rain,Sprinkler,Wet Grass,Rain,Cloudy,Cloudy,Rain,Cloudy,Rain,Sprinkler,Sprinkler,Sprinkler,Wet Grass,Wet Grass,Wet Grass,馬爾可夫鏈蒙特卡羅（MCMC）算法描述： function MCMC-Ask(X, e, bn, N) return P(X | e) local variables: NX, /關(guān)于查詢變量X的向量計數(shù)，初值0 Z，/bn中的

20、非證據(jù)變量集 x， / bn的當(dāng)前狀態(tài) 利用Z中變量的隨機值來初始化x； for j = 1 to N do N(x) N(x) + 1; /x是當(dāng)前狀態(tài)x中的查詢變量X的值 for each Zi in Z do 給出Zi的馬爾可夫覆蓋MB(Zi)，并根據(jù)P(Zi |mb(Zi) 來采樣的Zi值; return Normalize(NX) /對NX進行歸一化,關(guān)于MCMC算法的補充說明： MCMC方法的一種常用的簡單變體為： 吉布斯采樣器（Gibbs sampler） MCMC是概率模型計算中的一種強有力的方法，目前已發(fā)展出很多變形，包括： （1）模擬退火算法 （2）隨機可滿足性(Stochastic satisfiability)算法,【課后習(xí)題2】,國家政策 （C）,學(xué)校政策 （U）,身體狀況 差（B）,過勞死 （D）,工作壓力 大（W）,已知：事件e