貝葉斯網(wǎng)絡(luò)全解培訓(xùn)講學(xué)

1、貝葉斯網(wǎng)絡(luò)全解對(duì)偶問題o 給定M個(gè)整數(shù)和某定值s，要求從M個(gè)數(shù)中選擇若干個(gè)數(shù)（同一個(gè)整數(shù)不能多次選擇），使得被選中的數(shù)的和為s。輸出滿足條件的選擇數(shù)目。n 如：從1、2、3、4、5、6、7、8、9中選擇若干數(shù)，使得它們的和為40。對(duì)偶圖：Voronoi圖和Delaunay剖分Delaunay三角剖分K近鄰圖的遺留問題o K近鄰圖中，結(jié)點(diǎn)的度至少是Ko K互近鄰圖中，結(jié)點(diǎn)的度至多是K復(fù)習(xí)：相對(duì)熵o 相對(duì)熵，又稱互熵，交叉熵，鑒別信息，Kullback熵，Kullback-Leible散度等o 設(shè)p(x)、q(x)是X中取值的兩個(gè)概率分布，則p對(duì)q的相對(duì)熵是o 兩點(diǎn)說明：n在一定程度上，相對(duì)熵可以

2、度量兩個(gè)隨機(jī)變量的“距離”n一般的，D(p|q) D(q|p)xxpyqxpExqxPxpqpD)()(log)()(log)()|()(復(fù)習(xí)：互信息o 兩個(gè)隨機(jī)變量X，Y的互信息，定義為X，Y的聯(lián)合分布和獨(dú)立分布乘積的相對(duì)熵。o I(X,Y)=D(P(X,Y) | P(X)P(Y)yxypxpyxpyxpYXI,)()(),(log),(),(主要內(nèi)容和目標(biāo)o 掌握樸素貝葉斯分類的原理和具體步驟o 掌握概率圖模型PGM的思想o 理解貝葉斯網(wǎng)絡(luò)n鏈?zhǔn)骄W(wǎng)絡(luò)n樹形網(wǎng)絡(luò)n因子圖n非樹形網(wǎng)絡(luò)轉(zhuǎn)換成樹形網(wǎng)絡(luò)的思路nSummary-Product算法o 了解馬爾科夫鏈、隱馬爾科夫模型的網(wǎng)絡(luò)拓?fù)浜秃x一個(gè)實(shí)

3、例后驗(yàn)概率o c1、c2表示左右兩個(gè)信封。o P(R)，P(B)表示摸到紅球、黑球的概率。o P(R)=P(R|c1)*P(c1) + P(R|c2)*P(c2)：全概率公式o P(c1|R)=P(R|c1)*P(c1)/P(R)n P(R|c1)=2/4n P(R|c2)=1/3n P(c1)=P(c2)=1/2o 如果摸到一個(gè)紅球，那么，這個(gè)信封有1美元的概率是0.6o 如果摸到一個(gè)黑球，那么，這個(gè)信封有1美元的概率是3/7樸素貝葉斯的假設(shè)o 一個(gè)特征出現(xiàn)的概率，與其他特征(條件)獨(dú)立（特征獨(dú)立性）n 其實(shí)是：對(duì)于給定分類的條件下，特征獨(dú)立o 每個(gè)特征同等重要（特征均衡性）以文本分類為例o

4、 樣本：1000封郵件，每個(gè)郵件被標(biāo)記為垃圾郵件或者非垃圾郵件o 分類目標(biāo)：給定第1001封郵件，確定它是垃圾郵件還是非垃圾郵件o 方法：樸素貝葉斯分析o 類別c：垃圾郵件c1，非垃圾郵件c2o 詞匯表：統(tǒng)計(jì)1000封郵件中出現(xiàn)的所有單詞，記單詞數(shù)目為N，即形成詞匯表。o 將每個(gè)樣本si向量化：初始化N維向量xi，若詞wj在si中出現(xiàn)，則xij=1，否則，為0。從而得到1000個(gè)N維向量x。o 使用：P(c|x)=P(x|c)*P(c) / P(x)分解o P(c|x)=P(x|c)*P(c) / P(x)o P(x|c)=P(x1,x2xN|c)=P(x1|c)*P(x2|c)P(xN|c)

5、o P(x)=P(x1,x2xN)=P(x1)*P(x2)P(xN)o 帶入公式： P(c|x)=P(x|c)*P(c) / P(x)o 等式右側(cè)各項(xiàng)的含義：nP(xi|cj)：在cj(此題目，cj要么為垃圾郵件1，要么為非垃圾郵件0)的前提下，第i個(gè)單詞xi出現(xiàn)的概率nP(xi)：在所有樣本中，單詞xi出現(xiàn)的概率nP(cj) ：(垃圾郵件)cj出現(xiàn)的概率關(guān)于樸素貝葉斯的若干探討o 遇到生詞怎么辦？n 拉普拉斯平滑o 編程的限制：小數(shù)乘積怎么辦？o 問題：一個(gè)詞在樣本中出現(xiàn)多次，和一個(gè)詞在樣本中出現(xiàn)一次，形成的詞向量相同n 由0/1改成計(jì)數(shù)o 如何判定該分類器的正確率n 樣本中：K個(gè)生成分類器

6、，1000-K個(gè)作為測(cè)試集n 交叉驗(yàn)證貝葉斯網(wǎng)絡(luò)o 把某個(gè)研究系統(tǒng)中涉及的隨機(jī)變量，根據(jù)是否條件獨(dú)立繪制在一個(gè)有向圖中，就形成了貝葉斯網(wǎng)絡(luò)。o 貝葉斯網(wǎng)絡(luò)(Bayesian Network)，又稱有向無環(huán)圖模型(directed acyclic graphical model)，是一種概率圖模型，借由有向無環(huán)圖(Directed Acyclic Graphs, DAG)中得知一組隨機(jī)變量X1,X2.Xn及其n組條件概率分布(Conditional Probability Distributions, CPD)的性質(zhì)。貝葉斯網(wǎng)絡(luò)o 一般而言，貝葉斯網(wǎng)絡(luò)的有向無環(huán)圖中的節(jié)點(diǎn)表示隨機(jī)變量，它們可以是

7、可觀察到的變量，或隱變量、未知參數(shù)等。連接兩個(gè)節(jié)點(diǎn)的箭頭代表此兩個(gè)隨機(jī)變量是具有因果關(guān)系（或非條件獨(dú)立）。若兩個(gè)節(jié)點(diǎn)間以一個(gè)單箭頭連接在一起，表示其中一個(gè)節(jié)點(diǎn)是“因(parents)”，另一個(gè)是“果(children)”，兩節(jié)點(diǎn)就會(huì)產(chǎn)生一個(gè)條件概率值。o 每個(gè)結(jié)點(diǎn)在給定其直接前驅(qū)時(shí)，條件獨(dú)立于其非后繼。n稍后詳細(xì)解釋此結(jié)論一個(gè)簡單的貝葉斯網(wǎng)絡(luò)全連接貝葉斯網(wǎng)絡(luò)o 每一對(duì)結(jié)點(diǎn)之間都有邊連接一個(gè)“正?！钡呢惾~斯網(wǎng)絡(luò)o 有些邊缺失o 直觀上：n x1和x2獨(dú)立n x6和x7在x4給定的條件下獨(dú)立o x1,x2,x7的聯(lián)合分布：對(duì)一個(gè)實(shí)際貝葉斯網(wǎng)絡(luò)的分析1+2+2+4+4=13 vs 25貝葉斯網(wǎng)絡(luò)：打

8、印機(jī)故障診斷o17*1 + 1*2 + 2*22 + 3*23 + 3*24 = 99o226 = 67108864貝葉斯網(wǎng)絡(luò)：警報(bào)貝葉斯網(wǎng)絡(luò)：警報(bào)o 全部隨機(jī)變量的聯(lián)合分布貝葉斯網(wǎng)絡(luò)的形式化定義oBN(G, )nG:有向無環(huán)圖nG的結(jié)點(diǎn)：隨機(jī)變量nG的邊：結(jié)點(diǎn)間的有向依賴n：所有條件概率分布的參數(shù)集合n結(jié)點(diǎn)X的條件概率：P(X|parent(X)o思考：需要多少參數(shù)才能確定上述網(wǎng)絡(luò)呢？n每個(gè)結(jié)點(diǎn)所需參數(shù)的個(gè)數(shù)：結(jié)點(diǎn)的parent數(shù)目是M，結(jié)點(diǎn)和parent的可取值數(shù)目都是K：KM*(K-1)n為什么？n考察結(jié)點(diǎn)的parent對(duì)該結(jié)點(diǎn)形成了多少種情況（條件分布）特殊的貝葉斯網(wǎng)絡(luò)o M個(gè)離散結(jié)點(diǎn)

9、形成一條鏈，每一個(gè)結(jié)點(diǎn)有K個(gè)狀態(tài)，則需要K-1+(M-1)K(K-1)個(gè)參數(shù)。這是關(guān)于長度M的線性函數(shù)。n 別忘了，如果是全連接，需要KM-1個(gè)參數(shù)，是關(guān)于M的指數(shù)函數(shù)。通過貝葉斯網(wǎng)絡(luò)判定條件獨(dú)立1o P(a,b,c)=P(c)*P(a|c)*P(b|c)o 則：P(a,b|c)=P(a,b,c)/P(c)o 帶入，得到：o P(a,b|c)=P(a|c)*P(b|c)o 即：在c給定的條件下，a，b被阻斷(blocked)，是獨(dú)立的。n 條件獨(dú)立：tail-to-tail通過貝葉斯網(wǎng)絡(luò)判定條件獨(dú)立2o P(a,b,c)=P(a)*P(c|a)*P(b|c)o 即：在c給定的條件下，a，b被阻

10、斷(blocked)，是獨(dú)立的。n條件獨(dú)立：head-to-tail通過貝葉斯網(wǎng)絡(luò)判定條件獨(dú)立3o P(a,b,c) = P(a)*P(b)*P(c|a,b)o 在c未知的條件下，a，b被阻斷(blocked)，是獨(dú)立的： head-to-headP(b)*P(a),(b)a,|P(c*P(b)*P(a) = c)b,P(a,cbaPc舉例說明這三種情況將上述結(jié)點(diǎn)推廣到結(jié)點(diǎn)集o D-separation：有向分離o 對(duì)于任意的結(jié)點(diǎn)集A，B，C，考察所有通過A中任意結(jié)點(diǎn)到B中任意結(jié)點(diǎn)的路徑，若要求A，B條件獨(dú)立，則需要所有的路徑都被阻斷(blocked)，即滿足下列兩個(gè)前提之一：nA和B的“he

11、ad-to-tail型”和“tail-to-tail型”路徑都通過C；nA和B的“head-to-head型”路徑不通過C以及C的子孫；有向分離的舉例o Gas和Radio是獨(dú)立的嗎？給定Battery呢？Ignition呢？Starts呢？Moves呢？(答：IIIDD)再次分析鏈?zhǔn)骄W(wǎng)絡(luò)o 由D-separation可知，在xi給定的條件下，xi+1的分布和x1,x2xi-1條件獨(dú)立。即：xi+1的分布狀態(tài)只和xi有關(guān)，和其他變量條件獨(dú)立，這種順次演變的隨機(jī)過程，叫做馬爾科夫鏈。o 后面的課中，會(huì)再次專門講解馬爾科夫鏈。Markov Blanketo 一個(gè)結(jié)點(diǎn)的Markov Blanket是

12、一個(gè)集合，在這個(gè)集合中的結(jié)點(diǎn)都給定的條件下，該結(jié)點(diǎn)條件獨(dú)立于其他所有結(jié)點(diǎn)。o 即：一個(gè)結(jié)點(diǎn)的Markov Blanket是它的parents,children以及spouses(孩子的其他parent)Markov Blanket補(bǔ)充知識(shí)：Serum Calcium(血清鈣濃度)高于2.75mmo1/L即為高鈣血癥。許多惡性腫瘤可并發(fā)高鈣血癥。以乳腺癌、骨腫瘤、肺癌、胃癌、卵巢癌、多發(fā)性骨髓瘤、急性淋巴細(xì)胞白血病等較為多見，其中乳腺癌約1/3 可發(fā)生高鈣血癥。貝葉斯網(wǎng)絡(luò)的用途o 診斷：P(病因|癥狀)o 預(yù)測(cè)：P(癥狀|病因)o 分類：maxclassP(類別|數(shù)據(jù))o 通過給定的樣本數(shù)據(jù)，建

13、立貝葉斯網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和結(jié)點(diǎn)的條件概率分布參數(shù)。這往往需要借助先驗(yàn)知識(shí)和極大似然估計(jì)來完成。o 在貝葉斯網(wǎng)絡(luò)確定的結(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)和條件概率分布的前提下，可以使用該網(wǎng)絡(luò)，對(duì)未知數(shù)據(jù)計(jì)算條件概率或后驗(yàn)概率，從而達(dá)到診斷、預(yù)測(cè)或者分類的目的。應(yīng)用實(shí)例o 由AT&T貝爾實(shí)驗(yàn)室開發(fā)的APRI系統(tǒng)n從數(shù)據(jù)中學(xué)習(xí)和使用貝葉斯網(wǎng)絡(luò)，用來識(shí)別那些有賴賬傾向的客戶o NASA vista系統(tǒng)n預(yù)測(cè)推進(jìn)系統(tǒng)的失敗率n分析更精確的時(shí)間窗口，提供高可靠度的行動(dòng)n動(dòng)態(tài)決定顯示哪些信息應(yīng)用實(shí)例貝葉斯網(wǎng)絡(luò)的推斷計(jì)算過程推導(dǎo)貝葉斯推斷的通用公式o 由貝葉斯網(wǎng)絡(luò)得到因子圖(Factor Graph)o 通過在因子圖中消息傳遞的思想

14、，計(jì)算概率因子圖因子圖的構(gòu)造o 由貝葉斯網(wǎng)絡(luò)構(gòu)造因子圖的方法：n 一個(gè)因子對(duì)應(yīng)因子圖中的一個(gè)結(jié)點(diǎn)n 貝葉斯網(wǎng)絡(luò)中的每一個(gè)變量在因子圖上對(duì)應(yīng)邊或者半邊n 結(jié)點(diǎn)g和邊x相連當(dāng)且僅當(dāng)變量x出現(xiàn)在因子g中因子圖舉例o 馬爾科夫鏈因子圖舉例o 隱馬爾科夫模型邊緣分布o(jì) 由聯(lián)合概率分布求邊緣概率分布分配率o 如果有o 那么o 試想：na*b + a*c：2次乘法，1次加法na*(b + c)：1次乘法，1次加法舉例說明該算法提取公因子：即“分配率”使用“消息傳遞”的觀點(diǎn)box內(nèi)部的消息傳遞Sum-Product算法Sum-Product算法o 從計(jì)算來看， Sum-Product算法是將計(jì)算需要的中間過程

15、進(jìn)行了保存。如果計(jì)算多個(gè)概率分布，往往更有效。o Sum-Product算法有點(diǎn)類似動(dòng)態(tài)規(guī)劃的思想：將一個(gè)概率分布寫成兩個(gè)因子的乘積，而這兩個(gè)因子可以繼續(xù)分解或者通過已知得到。試給出該貝葉斯網(wǎng)絡(luò)的因子圖上述貝葉斯網(wǎng)絡(luò)的因子圖無向環(huán)o 可以發(fā)現(xiàn)，若貝葉斯網(wǎng)絡(luò)中存在“環(huán)”（無向），則因此構(gòu)造的因子圖會(huì)得到環(huán)。而使用消息傳遞的思想，這個(gè)消息將無限傳輸下去，不利于概率計(jì)算。o 解決方法：n 刪除貝葉斯網(wǎng)絡(luò)中的若干條邊，使得它不含有無向環(huán)n 重新構(gòu)造沒有環(huán)的貝葉斯網(wǎng)絡(luò)原貝葉斯網(wǎng)絡(luò)的近似樹結(jié)構(gòu)將兩圖的相對(duì)熵轉(zhuǎn)換成變量的互信息最大權(quán)生成樹MSWT的建立過程o1. 對(duì)于給定的分布P(x)，對(duì)于所有的ij，計(jì)算

16、聯(lián)合分布P(xi|xj)；o2.使用第1步得到的概率分布，計(jì)算任意兩個(gè)結(jié)點(diǎn)的互信息I(Xi,Yj)，并把I(Xi,Yj)作為這兩個(gè)結(jié)點(diǎn)連接邊的權(quán)值；o3.計(jì)算最大權(quán)生成樹(Maximum-weight spanning tree)na. 初始狀態(tài)：n個(gè)變量(結(jié)點(diǎn))，0條邊nb. 插入最大權(quán)重的邊nc. 找到下一個(gè)最大的邊，并且加入到樹中；要求加入后，沒有環(huán)生成。否則，查找次大的邊；nd. 重復(fù)上述過程c過程直到插入了n-1條邊（樹建立完成）o4. 選擇任意結(jié)點(diǎn)作為根，從根到葉子標(biāo)識(shí)邊的方向；o5. 可以保證，這課樹的近似聯(lián)合概率P(x)和原貝葉斯網(wǎng)絡(luò)的聯(lián)合概率P(x)的相對(duì)熵最小。參考文獻(xiàn)oP

17、attern Recognition and Machine Learning Chapter 8, M. Jordan, J. Kleinberg, ect, 2006oAn Introduction to Factor Graphs,Hans-Andrea Loeliger,MLSB 2008oFactor graph and sum-product algorithm, Frank R. Kschischang, Brendan J.Frey, ect, 1998oA Tutorial on Inference and Learning in Bayesian Networks, Irina RishoA Tutorial on Learni