貝葉斯網(wǎng)絡(luò)簡介

1、貝葉斯網(wǎng)絡(luò)簡介Introduction to Bayesian Networks,基本框架,貝葉斯網(wǎng)絡(luò)：? 概率論 ? 圖論,基本思路,貝葉斯網(wǎng)絡(luò)是為了處理人工智能研究中的不確定性(uncertainty)問題而發(fā)展起來的.貝葉斯網(wǎng)絡(luò)是將概率統(tǒng)計應(yīng)用于復(fù)雜領(lǐng)域進(jìn)行不確定性推理和數(shù)據(jù)分析的工具。BN是一種系統(tǒng)地描述隨即變量之間關(guān)系的工具。建立BN的目的主要是進(jìn)行概率推理(probabilistic inference)。用概率

2、論處理不確定性的主要優(yōu)點(diǎn)是保證推理結(jié)果的正確性。,幾個重要原理,鏈規(guī)則(chain rule)貝葉斯定理(Bayes’ theorem)利用變量間條件獨(dú)立性,What are they?Bayesian nets are a network-based framework for representing and analyzing models involving uncertaintyWhat are they us

3、ed for?Intelligent decision aids, data fusion, feature recognition, intelligent diagnostic aids, automated free text understanding, data miningWhere did they come from?Cross fertilization of ideas between the artifici

4、al intelligence, decision analysis, and statistic communities,貝葉斯網(wǎng)絡(luò)的幾個主要問題,貝葉斯網(wǎng)絡(luò)概率推理(Probabilistic Inference)結(jié)構(gòu)學(xué)習(xí) (structure learning)參數(shù)學(xué)習(xí) (Parameter learning)分類 (classification)? 隱變量及隱結(jié)構(gòu)學(xué)習(xí) (Hidden variables and

5、hidden structure learning),一個簡單貝葉斯網(wǎng)絡(luò)例子,一個簡單貝葉斯網(wǎng)絡(luò)例子,計算過程：(1)P(y1|x1)=0.9P(z1|x1)=P(z1|y1,x1)P(y1|x1)+P(z1|y2,x1)P(y2|x1) =P(z1|y1)P(y1|x1)+P(z1|y2)P(y2|x1) =0.7*0.9+0.4*0.1=0.67P(w1|x1)=P(w1|z1,x1)P(z1

6、|x1)+P(w1|z2,x1)P(z2|x1) =P(w1|z1)P(z1|x1)+P(w1|z2)P(z2|x1) =0.5*0.67+0.6*0.33=0.533該計算利用向下概率傳播及鏈?zhǔn)揭?guī)則。,一個簡單貝葉斯網(wǎng)絡(luò)例子,計算過程：(2) P(y1)=P(y1|x1)P(x1)+P(y1|x2)P(x2)=0.9*0.4+0.8*0.6=0.84P(z1)=P(z1|y1)P(y1)+P(z

7、1|y2)P(y2)=0.7*0.84+0.4*0.16=0.652P(w1)=P(w1|z1)P(z1)+P(w1|z2)P(z2)=0.5*0.652+0.6*0.348=0.5348P(w1|y1)=P(w1|z1)P(z1|y1)+P(w1|z2)P(z2|y1)=0.5*0.7+0.6*0.3=0.53P(w1|y2)=P(w1|z1)P(z1|y2)+P(w1|z2)P(z2|y2) =0.5*0

8、.4+0.6*0.6=0.56P(w1|x1)=P(w1|y1)P(y1|x1)+P(w1|y2)P(y2|x1) =0.53*0.9+0.56*0.1=0.533 該計算利用向上概率傳播及貝葉斯定理。,為什么要用貝葉斯網(wǎng)絡(luò)進(jìn)行概率推理？,理論上，進(jìn)行概率推理所需要的只是一個聯(lián)合概率分布。但是聯(lián)合概率分布的復(fù)雜度相對于變量個數(shù)成指數(shù)增長，所以當(dāng)變量眾多時不可行。貝葉斯網(wǎng)絡(luò)的提出就是要解決這個問題。它把復(fù)雜的聯(lián)

9、合概率分布分解成一系列相對簡單的模塊，從而大大降低知識獲取和概率推理的復(fù)雜度，使得可以把概率論應(yīng)用于大型問題。統(tǒng)計學(xué)、系統(tǒng)工程、信息論以及模式識別等學(xué)科中貝葉斯網(wǎng)絡(luò)特里的多元概率模型：樸素貝葉斯模型，隱類模型，混合模型，隱馬爾科夫模型，卡爾曼濾波器等。動態(tài)貝葉斯網(wǎng)絡(luò)主要用于對多維離散時間序列的監(jiān)控和預(yù)測。多層隱類模型，能夠揭示觀測變量背后的隱結(jié)構(gòu)。,概率論基礎(chǔ),貝葉斯網(wǎng)絡(luò)所依賴的一個核心概念是條件獨(dú)立: Condition

10、al Independence,基本概念,例子,P(C, S,R,W) = P(C)P(S|C)P(R|S,C)P(W|S,R,C) chain rule = P(C)P(S|C)P(R|C)P(W|S,R,C) since = P(C)P(S|C)P(R|C)P(W|S,R) since,貝葉斯網(wǎng)絡(luò)應(yīng)用,醫(yī)療診斷，工業(yè)，金融分

11、析，計算機(jī)（微軟Windows,Office），模式識別：分類，語義理解軍事（目標(biāo)識別，多目標(biāo)跟蹤，戰(zhàn)爭身份識別等），生態(tài)學(xué)，生物信息學(xué)（貝葉斯網(wǎng)絡(luò)在基因連鎖分析中應(yīng)用），編碼學(xué)，分類聚類，時序數(shù)據(jù)和動態(tài)模型,圖分割與變量獨(dú)立,圖分割，有向分割（d-separate,d-分割）變量X和Y通過第三個變量Z間接相連的三種情況：阻塞(block)設(shè)Z為一節(jié)點(diǎn)集合，X和Y是不在Z中的兩個節(jié)點(diǎn)?？紤]X和Y之間的一條通

12、路。如果滿足下面條件之一，則稱被Z所阻塞：1．有一個在Z中的順連節(jié)點(diǎn)；2．有一個在Z中的分連節(jié)點(diǎn)3． 有一個匯連節(jié)點(diǎn)W，它和它的后代節(jié)點(diǎn)均不在Z中。,圖分割與變量獨(dú)立,如果X和Y之間的所有通路都被Z阻塞，則說Z有向分割(directed separate)X和Y，簡稱d-separate,d-分割。那么X和Y在給定Z時條件獨(dú)立。定理（整體馬爾科夫性）設(shè)X和Y為貝葉斯網(wǎng)N中的兩個變量，Z為N中一個不包含X和Y的節(jié)點(diǎn)集合。如果Z

13、d-分割X和Y，那么X和Y在給定Z時條件獨(dú)立，即 d-分割是圖論的概念，而條件獨(dú)立是概率論的概念，所以定理揭示了貝葉斯網(wǎng)絡(luò)圖論側(cè)面和概率論側(cè)面之間的關(guān)系。,馬爾科夫邊界與端正圖,?馬爾科夫邊界：條件獨(dú)立性 在貝葉斯網(wǎng)絡(luò)中，一個節(jié)點(diǎn)X的馬爾科夫邊界(Markov boundary)包括其父節(jié)點(diǎn)、子節(jié)點(diǎn)、以及子節(jié)點(diǎn)的父節(jié)點(diǎn)。? 端正圖(Moral graph): 團(tuán)樹傳播算法-junction tree 設(shè)G為一

14、有向無環(huán)圖，如果將G中每個節(jié)點(diǎn)的不同父節(jié)點(diǎn)結(jié)合，即在他們之間加一條邊，然后去掉所有邊的方向，所得到的無向圖成為G的端正圖。,貝葉斯網(wǎng)絡(luò)推理(Inference),貝葉斯網(wǎng)絡(luò)可以利用變量間的條件獨(dú)立對聯(lián)合分布進(jìn)行分解，降低參數(shù)個數(shù)。推理(inference)是通過計算來回答查詢的過程計算后驗概率分布：P(Q|E=e),貝葉斯網(wǎng)絡(luò)推理(Inference),1 變量消元算法(Variable elimination) 利用概率

15、分解降低推理復(fù)雜度。? 使得運(yùn)算局部化。消元過程實質(zhì)上就是一個邊緣化的過程。? 最優(yōu)消元順序：最大勢搜索，最小缺邊搜索,貝葉斯網(wǎng)絡(luò)推理(Inference),2. 團(tuán)樹傳播算法利用步驟共享來加快推理的算法。團(tuán)樹（clique tree）是一種無向樹，其中每一個節(jié)點(diǎn)代表一個變量集合，稱為團(tuán)(clique)。團(tuán)樹必須滿足變量連通性，即包含同一變量的所有團(tuán)所導(dǎo)出的子圖必須是連通的。,用團(tuán)樹組織變量消元的算法。計算共享

16、團(tuán)樹傳播算法基本步驟：將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹團(tuán)樹初始化在團(tuán)樹中選一個團(tuán)作為樞紐全局概率傳播：CollectMessage; DistributeMessage邊緣化，歸一化,團(tuán)樹傳播算法示例 （[TLR]是樞紐節(jié)點(diǎn)） ?變量消元和團(tuán)樹傳播算法都是精確推理算法。,,貝葉斯網(wǎng)絡(luò)推理(Inference),3 . 近似推理(1) 隨機(jī)抽樣算法：順序抽樣法，MCMC抽樣是一類應(yīng)用于數(shù)值積分和統(tǒng)

17、計物理中的近似計算方法。基本思想是從某個概率分布隨機(jī)抽樣，生成一組樣本，然后從樣本出發(fā)近似計算感興趣的量。隨機(jī)抽樣算法理論基礎(chǔ)是大數(shù)定律。,MCMC算法—吉布斯抽樣(Gibbs sampling)。它首先隨機(jī)生成一個與證據(jù)E=e相一致的樣本s1作為起始樣本。此后，每個樣本si的產(chǎn)生都依賴于前一個樣本si-1,且si與si-1最多只有一個非證據(jù)變量的取值不同，記改變量為X。X的取值可以從非證據(jù)變量中隨機(jī)選取，也可以按某個固定順序輪流決

18、定。在si中，X的值通過隨機(jī)抽樣決定，抽樣分布是：當(dāng)樣本數(shù) 時，馬氏鏈理論保證了算法返回的結(jié)果收斂于真正的后驗概率。吉布斯抽樣的缺點(diǎn)是收斂速度慢，因為馬氏鏈往往需要花很長時間才能真正達(dá)到平穩(wěn)分布。 (2) 變分法。,貝葉斯網(wǎng)絡(luò)學(xué)習(xí),1. 結(jié)構(gòu)學(xué)習(xí)：發(fā)現(xiàn)變量之間的圖關(guān)系 ，2 .參數(shù)學(xué)習(xí)：決定變量之間互相關(guān)聯(lián)的量化關(guān)系。,貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),選擇具有最大后驗概率的結(jié)構(gòu) ?；谠u分函數(shù)(scoring fu

19、nction)：BIC, MDL, AIC等 拉普拉斯近似(Laplace approximation):對拉普拉斯近似簡化，得BIC:①BIC既不依賴于先驗也不依賴于參數(shù)坐標(biāo)系統(tǒng) ②第一項度量參數(shù)模型預(yù)測數(shù)據(jù)的優(yōu)良程度，第二項用于懲罰模型復(fù)雜度,結(jié)構(gòu)學(xué)習(xí)算法,算法：K2: 通過為每個結(jié)點(diǎn)尋找父結(jié)點(diǎn)集合來學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。它不斷往父結(jié)點(diǎn)集中添加結(jié)點(diǎn)，并選擇能最大化數(shù)據(jù)和結(jié)構(gòu)的聯(lián)合概率的結(jié)點(diǎn)集。 Hi

20、llClimbing (operators: edge addition, edge deletion, edge reversion) 從一個無邊結(jié)構(gòu)開始，在每一步，它添加能最大化BIC的邊。算法在通過添加邊不能再提高結(jié)構(gòu)得分時停止。缺值數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)：Structural EM SEM不是每次迭代都同時優(yōu)化模型結(jié)構(gòu)和參數(shù)，而是先固定模型結(jié)構(gòu)進(jìn)行數(shù)次參數(shù)優(yōu)化后，再進(jìn)行一次結(jié)構(gòu)加參數(shù)優(yōu)化，如此交替進(jìn)行。

21、 目的：減小計算復(fù)雜度。,貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí),最大似然估計 完全基于數(shù)據(jù)，不需要先驗概率： 貝葉斯估計 假定在考慮數(shù)據(jù)之前，網(wǎng)絡(luò)參數(shù)服從某個先驗分布。先驗的主觀概率,它的影響隨著數(shù)據(jù)量的增大而減小。,貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí),缺值數(shù)據(jù)最大似然估計：EM算法 （迭代算法） 1 基于 對數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整 (E-step) 2 基于修補(bǔ)后的完整數(shù)據(jù)計算的最大似然估計 (M-Step)

22、EM算法是收斂的。,隱結(jié)構(gòu)模型學(xué)習(xí),隱變量是取值未被觀察到的變量。通過數(shù)據(jù)分析： 1 隱變量的個數(shù) 2 隱結(jié)構(gòu) 3 隱變量的勢 4 模型參數(shù)方法：基于評分函數(shù)的爬山法 G是一個隱變量模型，D是一組數(shù)據(jù)。 是G的參數(shù)的某一個最大似然估計， 是G的有效維數(shù)。 隱變量勢學(xué)習(xí)爬山算法隱結(jié)構(gòu)學(xué)習(xí)雙重爬山算法,貝葉斯網(wǎng)絡(luò)用于分類和因

23、果關(guān)系分析,(1) Naïve Bayesian networks(2) Tree augment Bayesian networks, et al.(3) PC (Spirtes et al.,2000) , IC(Pearl,2000) algorithm,動態(tài)貝葉斯網(wǎng)絡(luò),DBN: Dynamic Bayesian networksDealing with timeIn many systems, data

24、arrives sequentiallyDynamic Bayes nets (DBNs) can be used to model such time-series (sequence) dataSpecial cases of DBNs includeState-space modelsHidden Markov models (HMMs),Software Tools,Microsoft’s MSBNXBNT

25、 Kevin Murphy. BayesNet Toolbox for Matlab (BNT). http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html, 2001.,參考文獻(xiàn),(美)拉塞爾，(美)諾文 著. 姜哲 等譯. 人工智能—一種現(xiàn)代 方法(第二版)，北京：人民郵電出版社，2004.6. (Chapter 13,14,15,20). Kevin Patrick Murphy.

26、 Dynamic Bayesian Networks: Representation, Inference and learning. PhD dissertation, University of California, Berkeley, 2002. David Heckerman. A Tutorial on Learning with Bayesian Networks. Microsoft Technical Report

27、.No.MSR-TR-95-06.Microsoft Research, March 1995 (revised November 1996) Richard E. Neapolitan. Learning Bayesian Networks. Prentice Hall Series in Artificial Intelligence, Pearson Education, Inc., Pearson Prentice Hall