貝葉斯網(wǎng)絡(luò)簡(jiǎn)介課件

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

2、建立BN的目的主要是進(jìn)行概率的目的主要是進(jìn)行概率推理推理(probabilistic inference)。 用概率論處理不確定性的主要優(yōu)點(diǎn)是保用概率論處理不確定性的主要優(yōu)點(diǎn)是保證推理結(jié)果的正確性。證推理結(jié)果的正確性。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介幾個(gè)重要原理幾個(gè)重要原理 鏈規(guī)則鏈規(guī)則(chain rule) 貝葉斯定理貝葉斯定理(Bayes theorem) 利用變量間條件獨(dú)立性利用變量間條件獨(dú)立性),.,|().|()(),.,(2112121nnnXXXXPXXPXPXXXP貝葉斯網(wǎng)絡(luò)簡(jiǎn)介 What are they? Bayesian nets are a network-based framewor

3、k for representing and analyzing models involving uncertainty What are they used for? Intelligent decision aids, data fusion, feature recognition, intelligent diagnostic aids, automated free text understanding, data mining Where did they come from? Cross fertilization of ideas between the artificial

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

5、網(wǎng)絡(luò)例子一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子貝葉斯網(wǎng)絡(luò)簡(jiǎn)介一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子 計(jì)算過(guò)程：計(jì)算過(guò)程： (1) P(y1|x1)=0.9 P(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.67 P(w1|x1)=P(w1|z1,x1)P(z1|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 該計(jì)算利用向下概率傳播及

6、鏈?zhǔn)揭?guī)則。該計(jì)算利用向下概率傳播及鏈?zhǔn)揭?guī)則。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子計(jì)算過(guò)程：計(jì)算過(guò)程：(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(z1|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

7、(w1|y2)=P(w1|z1)P(z1|y2)+P(w1|z2)P(z2|y2) =0.5*0.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 該計(jì)算利用向上概率傳播及貝葉斯定理。該計(jì)算利用向上概率傳播及貝葉斯定理。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介為什么要用貝葉斯網(wǎng)絡(luò)進(jìn)行概率推理？為什么要用貝葉斯網(wǎng)絡(luò)進(jìn)行概率推理？ 理論上，進(jìn)行概率推理所需要的只是一個(gè)聯(lián)合概率分理論上，進(jìn)行概率推理所需要的只是一個(gè)聯(lián)合概率分布。但是聯(lián)合概率分布的復(fù)雜度相對(duì)于變量個(gè)數(shù)成指布。但是聯(lián)合概率分布的復(fù)雜度相對(duì)于變量個(gè)數(shù)

8、成指數(shù)增長(zhǎng)，所以當(dāng)變量眾多時(shí)不可行。數(shù)增長(zhǎng)，所以當(dāng)變量眾多時(shí)不可行。 貝葉斯網(wǎng)絡(luò)的提出就是要解決這個(gè)問(wèn)題。貝葉斯網(wǎng)絡(luò)的提出就是要解決這個(gè)問(wèn)題。它把復(fù)雜的它把復(fù)雜的聯(lián)合概率分布分解成一系列相對(duì)簡(jiǎn)單的模塊，從而大聯(lián)合概率分布分解成一系列相對(duì)簡(jiǎn)單的模塊，從而大大降低知識(shí)獲取和概率推理的復(fù)雜度，使得可以把概大降低知識(shí)獲取和概率推理的復(fù)雜度，使得可以把概率論應(yīng)用于大型問(wèn)題。率論應(yīng)用于大型問(wèn)題。 統(tǒng)計(jì)學(xué)、系統(tǒng)工程、信息論以及模式識(shí)別等學(xué)科中貝統(tǒng)計(jì)學(xué)、系統(tǒng)工程、信息論以及模式識(shí)別等學(xué)科中貝葉斯網(wǎng)絡(luò)特里的多元概率模型：樸素貝葉斯模型，隱葉斯網(wǎng)絡(luò)特里的多元概率模型：樸素貝葉斯模型，隱類模型，混合模型，隱馬爾科夫

9、模型，卡爾曼濾波器類模型，混合模型，隱馬爾科夫模型，卡爾曼濾波器等。等。 動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)主要用于對(duì)多維離散時(shí)間序列的監(jiān)控動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)主要用于對(duì)多維離散時(shí)間序列的監(jiān)控和預(yù)測(cè)。和預(yù)測(cè)。 多層隱類模型，能夠揭示觀測(cè)變量背后的隱結(jié)構(gòu)。多層隱類模型，能夠揭示觀測(cè)變量背后的隱結(jié)構(gòu)。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介概率論基礎(chǔ)貝葉斯網(wǎng)絡(luò)所依賴的一個(gè)核心貝葉斯網(wǎng)絡(luò)所依賴的一個(gè)核心概念是條件獨(dú)立概念是條件獨(dú)立: Conditional Independence貝葉斯網(wǎng)絡(luò)簡(jiǎn)介基本概念基本概念貝葉斯網(wǎng)絡(luò)簡(jiǎn)介例子例子P(C, S,R,W) = P(C)P(S|C)P(R|S,C)P(W|S,R,C) chain rule = P(C)

10、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ò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)應(yīng)用l 醫(yī)療診斷，醫(yī)療診斷，l 工業(yè)，工業(yè)，l 金融分析，金融分析，l 計(jì)算機(jī)（微軟計(jì)算機(jī)（微軟Windows,Office），），l 模式識(shí)別：分類，語(yǔ)義理解模式識(shí)別：分類，語(yǔ)義理解l 軍事（目標(biāo)識(shí)別，多目標(biāo)跟蹤，戰(zhàn)爭(zhēng)身份識(shí)別軍事（目標(biāo)識(shí)別，多目標(biāo)跟蹤，戰(zhàn)爭(zhēng)身份識(shí)別等），等），l 生態(tài)學(xué)，生態(tài)學(xué)，l 生物信息學(xué)（貝葉斯網(wǎng)絡(luò)在基因連鎖分析中應(yīng)生物信息學(xué)（貝葉斯網(wǎng)絡(luò)在基因連鎖分析中應(yīng)用），用），l 編碼學(xué)，編碼學(xué)，l 分類聚類，分類聚類，l 時(shí)序數(shù)據(jù)

11、和動(dòng)態(tài)模型時(shí)序數(shù)據(jù)和動(dòng)態(tài)模型貝葉斯網(wǎng)絡(luò)簡(jiǎn)介圖分割與變量獨(dú)立圖分割與變量獨(dú)立圖分割，有向分割（圖分割，有向分割（d-separate,d-分割）分割）變量變量X和和Y通過(guò)第三個(gè)變量通過(guò)第三個(gè)變量Z間接相連的三種情況：間接相連的三種情況：阻塞阻塞(block)設(shè)設(shè)Z為一節(jié)點(diǎn)集合，為一節(jié)點(diǎn)集合，X和和Y是不在是不在Z中的兩個(gè)節(jié)點(diǎn)?？紤]中的兩個(gè)節(jié)點(diǎn)。考慮X和和Y之間的一條通之間的一條通路。如果滿足下面條件之一，則稱被路。如果滿足下面條件之一，則稱被Z所阻塞：所阻塞：1有一個(gè)在有一個(gè)在Z中的順連節(jié)點(diǎn)；中的順連節(jié)點(diǎn)；2有一個(gè)在有一個(gè)在Z中的分連節(jié)點(diǎn)中的分連節(jié)點(diǎn)3 有一個(gè)匯連節(jié)點(diǎn)有一個(gè)匯連節(jié)點(diǎn)W，它和它的后

12、代節(jié)點(diǎn)均不在，它和它的后代節(jié)點(diǎn)均不在Z中。中。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介圖分割與變量獨(dú)立圖分割與變量獨(dú)立 如果如果X和和Y之間的所有通路都被之間的所有通路都被Z阻塞，則說(shuō)阻塞，則說(shuō)Z有向分有向分割割(directed separate)X和和Y，簡(jiǎn)稱，簡(jiǎn)稱d-separate,d-分割。分割。那么那么X和和Y在給定在給定Z時(shí)條件獨(dú)立。時(shí)條件獨(dú)立。 定理（整體馬爾科夫性）定理（整體馬爾科夫性）設(shè)設(shè)X和和Y為貝葉斯網(wǎng)為貝葉斯網(wǎng)N中的兩中的兩個(gè)變量，個(gè)變量，Z為為N中一個(gè)不包含中一個(gè)不包含X和和Y的節(jié)點(diǎn)集合。如果的節(jié)點(diǎn)集合。如果Z d-分割分割X和和Y，那么，那么X和和Y在給定在給定Z時(shí)條件獨(dú)立，即時(shí)條件獨(dú)立，

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

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

15、葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)推理貝葉斯網(wǎng)絡(luò)推理(Inference)1 變量消元算法變量消元算法(Variable elimination) 利用概率分解降低推理復(fù)雜度。利用概率分解降低推理復(fù)雜度。 使得運(yùn)算局部化。消元過(guò)程實(shí)質(zhì)上就是一個(gè)邊緣化的過(guò)程。使得運(yùn)算局部化。消元過(guò)程實(shí)質(zhì)上就是一個(gè)邊緣化的過(guò)程。 最優(yōu)消元順序：最大勢(shì)搜索，最小缺邊搜索最優(yōu)消元順序：最大勢(shì)搜索，最小缺邊搜索貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)推理貝葉斯網(wǎng)絡(luò)推理(Inference)2. 團(tuán)樹(shù)傳播算法l利用步驟共享來(lái)加快推理的算法。l團(tuán)樹(shù)（clique tree）是一種無(wú)向樹(shù)，其中每一個(gè)節(jié)點(diǎn)代表一個(gè)變量集合，稱為團(tuán)(clique)。團(tuán)樹(shù)必須

16、滿足變量連通性，即包含同一變量的所有團(tuán)所導(dǎo)出的子圖必須是連通的。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介 用團(tuán)樹(shù)組織變量消元的算法。計(jì)算共享用團(tuán)樹(shù)組織變量消元的算法。計(jì)算共享 團(tuán)樹(shù)傳播算法基本步驟：團(tuán)樹(shù)傳播算法基本步驟： 將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹(shù)將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹(shù) 團(tuán)樹(shù)初始化團(tuán)樹(shù)初始化 在團(tuán)樹(shù)中選一個(gè)團(tuán)作為樞紐在團(tuán)樹(shù)中選一個(gè)團(tuán)作為樞紐 全局概率傳播：全局概率傳播：CollectMessage; DistributeMessage 邊緣化，歸一化邊緣化，歸一化貝葉斯網(wǎng)絡(luò)簡(jiǎn)介 團(tuán)樹(shù)傳播算法示例團(tuán)樹(shù)傳播算法示例 （TLR是樞紐節(jié)點(diǎn)）是樞紐節(jié)點(diǎn)） FF變量消元和團(tuán)樹(shù)傳播算法都是精確推理算法。變量消元和團(tuán)樹(shù)傳播算法都是精確推

17、理算法。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)推理貝葉斯網(wǎng)絡(luò)推理(Inference)3 . 近似推理近似推理(1) 隨機(jī)抽樣算法：順序抽樣法，隨機(jī)抽樣算法：順序抽樣法，MCMC抽樣抽樣 是一類應(yīng)用于數(shù)值積分和統(tǒng)計(jì)物理中的近似計(jì)是一類應(yīng)用于數(shù)值積分和統(tǒng)計(jì)物理中的近似計(jì)算方法?；舅枷胧菑哪硞€(gè)概率分布隨機(jī)抽樣算方法。基本思想是從某個(gè)概率分布隨機(jī)抽樣，生成一組樣本，然后從樣本出發(fā)近似計(jì)算感，生成一組樣本，然后從樣本出發(fā)近似計(jì)算感興趣的量。興趣的量。 隨機(jī)抽樣算法理論基礎(chǔ)是隨機(jī)抽樣算法理論基礎(chǔ)是大數(shù)定律大數(shù)定律。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介MCMC算法算法吉布斯抽樣吉布斯抽樣(Gibbs sampling)。它首先隨機(jī)生。它

18、首先隨機(jī)生成一個(gè)與證據(jù)成一個(gè)與證據(jù)E=e相一致的樣本相一致的樣本s1作為起始樣本。此后，作為起始樣本。此后，每個(gè)樣本每個(gè)樣本si的產(chǎn)生都依賴于前一個(gè)樣本的產(chǎn)生都依賴于前一個(gè)樣本si-1,且且si與與si-1最多最多只有一個(gè)非證據(jù)變量的取值不同，記改變量為只有一個(gè)非證據(jù)變量的取值不同，記改變量為X。 X的取值可以從非證據(jù)變量中隨機(jī)選取，也可以按某個(gè)固的取值可以從非證據(jù)變量中隨機(jī)選取，也可以按某個(gè)固定順序輪流決定。定順序輪流決定。 在在si中，中，X的值通過(guò)隨機(jī)抽樣決定，抽樣分布是：的值通過(guò)隨機(jī)抽樣決定，抽樣分布是： 當(dāng)樣本數(shù)當(dāng)樣本數(shù) 時(shí)，馬氏鏈理論保證了算法返回的結(jié)果收時(shí)，馬氏鏈理論保證了算法返

19、回的結(jié)果收斂于真正的后驗(yàn)概率。吉布斯抽樣的缺點(diǎn)是收斂速度慢，斂于真正的后驗(yàn)概率。吉布斯抽樣的缺點(diǎn)是收斂速度慢，因?yàn)轳R氏鏈往往需要花很長(zhǎng)時(shí)間才能真正達(dá)到平穩(wěn)分布。因?yàn)轳R氏鏈往往需要花很長(zhǎng)時(shí)間才能真正達(dá)到平穩(wěn)分布。 (2) 變分法。變分法。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)學(xué)習(xí)1. 結(jié)構(gòu)學(xué)習(xí)：發(fā)現(xiàn)變量之間的圖關(guān)系結(jié)構(gòu)學(xué)習(xí)：發(fā)現(xiàn)變量之間的圖關(guān)系 ，2 .參數(shù)學(xué)習(xí)：決定變量之間互相關(guān)聯(lián)的量化關(guān)系。參數(shù)學(xué)習(xí)：決定變量之間互相關(guān)聯(lián)的量化關(guān)系。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)l 選擇具有最大后驗(yàn)概率的結(jié)構(gòu)選擇具有最大后驗(yàn)概率的結(jié)構(gòu) 。l 基于評(píng)分函數(shù)基于評(píng)分函數(shù)(scoring fu

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

21、結(jié)構(gòu)的聯(lián)合概率往父結(jié)點(diǎn)集中添加結(jié)點(diǎn)，并選擇能最大化數(shù)據(jù)和結(jié)構(gòu)的聯(lián)合概率的結(jié)點(diǎn)集。的結(jié)點(diǎn)集。 u HillClimbing (operators: edge addition, edge deletion, edge reversion) 從一個(gè)無(wú)邊結(jié)構(gòu)開(kāi)始，在每一步，它添加能最大化從一個(gè)無(wú)邊結(jié)構(gòu)開(kāi)始，在每一步，它添加能最大化BIC的邊。算的邊。算法在通過(guò)添加邊不能再提高結(jié)構(gòu)得分時(shí)停止。法在通過(guò)添加邊不能再提高結(jié)構(gòu)得分時(shí)停止。u 缺值數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)：缺值數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)：Structural EM SEM不是每次迭代都同時(shí)優(yōu)化模型結(jié)構(gòu)和參數(shù)，而是先固定模型不是每次迭代都同時(shí)優(yōu)化模型結(jié)構(gòu)和參數(shù)，而是先固

22、定模型結(jié)構(gòu)進(jìn)行數(shù)次參數(shù)優(yōu)化后，再進(jìn)行一次結(jié)構(gòu)加參數(shù)優(yōu)化，如此交結(jié)構(gòu)進(jìn)行數(shù)次參數(shù)優(yōu)化后，再進(jìn)行一次結(jié)構(gòu)加參數(shù)優(yōu)化，如此交替進(jìn)行。替進(jìn)行。 目的：減小計(jì)算復(fù)雜度。目的：減小計(jì)算復(fù)雜度。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)u最大似然估計(jì)最大似然估計(jì) 完全基于數(shù)據(jù)，不需要先驗(yàn)概率：完全基于數(shù)據(jù)，不需要先驗(yàn)概率： u貝葉斯估計(jì)貝葉斯估計(jì) 假定在考慮數(shù)據(jù)之前，網(wǎng)絡(luò)參數(shù)服從某個(gè)先驗(yàn)分布。假定在考慮數(shù)據(jù)之前，網(wǎng)絡(luò)參數(shù)服從某個(gè)先驗(yàn)分布。先驗(yàn)的主觀概率先驗(yàn)的主觀概率,它的影響隨著數(shù)據(jù)量的增大而減小。它的影響隨著數(shù)據(jù)量的增大而減小。 貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)貝葉斯

23、網(wǎng)絡(luò)參數(shù)學(xué)習(xí)u缺值數(shù)據(jù)最大似然估計(jì)：缺值數(shù)據(jù)最大似然估計(jì)：EM算法算法 （迭代算法）（迭代算法） 1 基于基于 對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整 (E-step) 2 基于修補(bǔ)后的完整數(shù)據(jù)計(jì)算的最大似然估計(jì)基于修補(bǔ)后的完整數(shù)據(jù)計(jì)算的最大似然估計(jì) (M-Step)EM算法是收斂的。算法是收斂的。貝葉斯網(wǎng)絡(luò)簡(jiǎn)介隱結(jié)構(gòu)模型學(xué)習(xí)隱結(jié)構(gòu)模型學(xué)習(xí)l 隱變量是取值未被觀察到的變量。通過(guò)數(shù)據(jù)分析：隱變量是取值未被觀察到的變量。通過(guò)數(shù)據(jù)分析： 1 隱變量的個(gè)數(shù)隱變量的個(gè)數(shù) 2 隱結(jié)構(gòu)隱結(jié)構(gòu) 3 隱變量的勢(shì)隱變量的勢(shì) 4 模型參數(shù)模型參數(shù)l 方法：基于評(píng)分函數(shù)的爬山法方法：基于評(píng)分函數(shù)的爬山法 G

24、是一個(gè)隱變量模型，是一個(gè)隱變量模型，D是一組數(shù)據(jù)。是一組數(shù)據(jù)。 是是G的參數(shù)的某一個(gè)最大似然估計(jì)，的參數(shù)的某一個(gè)最大似然估計(jì)， 是是G的有效維數(shù)。的有效維數(shù)。 u隱變量勢(shì)學(xué)習(xí)爬山算法隱變量勢(shì)學(xué)習(xí)爬山算法u隱結(jié)構(gòu)學(xué)習(xí)雙重爬山算法隱結(jié)構(gòu)學(xué)習(xí)雙重爬山算法貝葉斯網(wǎng)絡(luò)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)用于分類和因果關(guān)系分析貝葉斯網(wǎng)絡(luò)用于分類和因果關(guān)系分析(1) Nave Bayesian networks(2) Tree augment Bayesian networks, et al.(3) PC (Spirtes et al.,2000) , IC(Pearl,2000) algorithm貝葉斯網(wǎng)絡(luò)簡(jiǎn)介動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)DBN: Dynamic Bayesian networks Dealing with time In many systems, data arrives sequentially Dynamic Bayes nets (DBNs) can be used to model such time-series (sequence) data Special cases of DBNs include State-space mod