1、2021/4/11貝葉斯網絡簡介貝葉斯網絡簡介Introduction to Bayesian Networks 2021/4/12基本框架基本框架 貝葉斯網絡：貝葉斯網絡： 概率論概率論 圖論圖論2021/4/13基本思路基本思路 貝葉斯網絡是為了處理人工智能研究中貝葉斯網絡是為了處理人工智能研究中的不確定性的不確定性(uncertainty)問題而發展起來問題而發展起來的的. 貝葉斯網絡是將概率統計應用于復雜領貝葉斯網絡是將概率統計應用于復雜領域進行不確定性推理和數據分析的工具域進行不確定性推理和數據分析的工具。 BN是一種系統地描述隨即變量之間關系是一種系統地描述隨即變量之間關系的工具。

2、建立的工具。建立BN的目的主要是進行概率的目的主要是進行概率推理推理(probabilistic inference)。 用概率論處理不確定性的主要優點是保用概率論處理不確定性的主要優點是保證推理結果的正確性。證推理結果的正確性。2021/4/14幾個重要原理幾個重要原理 鏈規則鏈規則(chain rule) 貝葉斯定理貝葉斯定理(Bayes theorem) 利用變量間條件獨立性利用變量間條件獨立性),.,|().|()(),.,(2112121nnnXXXXPXXPXPXXXP2021/4/15 What are they? Bayesian nets are a network-base

3、d framework 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

4、artificial intelligence, decision analysis, and statistic communities2021/4/16貝葉斯網絡的幾個主要問題貝葉斯網絡的幾個主要問題F貝葉斯網絡概率推理貝葉斯網絡概率推理(Probabilistic Inference)F結構學習結構學習 (structure learning)F參數學習參數學習 (Parameter learning)F分類分類 (classification)FF 隱變量及隱結構學習隱變量及隱結構學習 (Hidden variables and hidden structure learning)20

5、21/4/17一個簡單貝葉斯網絡例子一個簡單貝葉斯網絡例子2021/4/18一個簡單貝葉斯網絡例子一個簡單貝葉斯網絡例子 計算過程：計算過程： (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.

6、533 該計算利用向下概率傳播及鏈式規則。該計算利用向下概率傳播及鏈式規則。2021/4/19一個簡單貝葉斯網絡例子一個簡單貝葉斯網絡例子計算過程：計算過程：(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

7、*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.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 該計算利用向上概率傳播及貝葉斯定理。該計算利用向上概率傳播及貝葉斯定理。 2021/4/110為什么要用貝葉斯網絡進行概率推理？為什么要用貝葉斯網絡進行概率推理？ 理論上，進行概率推理所需要的只是一個聯合概率分理論上，進行概率推理所需要的只是一個聯合概率分布。但是聯合概率分布的復雜度相對于變量個數成指

8、布。但是聯合概率分布的復雜度相對于變量個數成指數增長，所以當變量眾多時不可行。數增長，所以當變量眾多時不可行。 貝葉斯網絡的提出就是要解決這個問題。貝葉斯網絡的提出就是要解決這個問題。它把復雜的它把復雜的聯合概率分布分解成一系列相對簡單的模塊，從而大聯合概率分布分解成一系列相對簡單的模塊，從而大大降低知識獲取和概率推理的復雜度，使得可以把概大降低知識獲取和概率推理的復雜度，使得可以把概率論應用于大型問題。率論應用于大型問題。 統計學、系統工程、信息論以及模式識別等學科中貝統計學、系統工程、信息論以及模式識別等學科中貝葉斯網絡特里的多元概率模型：樸素貝葉斯模型，隱葉斯網絡特里的多元概率模型：樸素

9、貝葉斯模型，隱類模型，混合模型，隱馬爾科夫模型，卡爾曼濾波器類模型，混合模型，隱馬爾科夫模型，卡爾曼濾波器等。等。 動態貝葉斯網絡主要用于對多維離散時間序列的監控動態貝葉斯網絡主要用于對多維離散時間序列的監控和預測。和預測。 多層隱類模型，能夠揭示觀測變量背后的隱結構。多層隱類模型，能夠揭示觀測變量背后的隱結構。2021/4/111概率論基礎貝葉斯網絡所依賴的一個核心貝葉斯網絡所依賴的一個核心概念是條件獨立概念是條件獨立: Conditional Independence2021/4/112基本概念基本概念2021/4/113例子例子P(C, S,R,W) = P(C)P(S|C)P(R|S,

10、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 2021/4/114貝葉斯網絡應用l 醫療診斷，醫療診斷，l 工業，工業，l 金融分析，金融分析，l 計算機（微軟計算機（微軟Windows,Office），），l 模式識別：分類，語義理解模式識別：分類，語義理解l 軍事（目標識別，多目標跟蹤，戰爭身份識別軍事（目標識別，多目標跟蹤，戰爭身份識別等），等），l 生態學，生態學，l 生物信息學（貝葉斯網絡在基因連鎖分析中應生物信息學（貝葉斯網絡在基因連鎖分析中應用

11、），用），l 編碼學，編碼學，l 分類聚類，分類聚類，l 時序數據和動態模型時序數據和動態模型2021/4/115圖分割與變量獨立圖分割與變量獨立圖分割，有向分割（圖分割，有向分割（d-separate,d-分割）分割）變量變量X和和Y通過第三個變量通過第三個變量Z間接相連的三種情況：間接相連的三種情況：阻塞阻塞(block)設設Z為一節點集合，為一節點集合，X和和Y是不在是不在Z中的兩個節點。考慮中的兩個節點。考慮X和和Y之間的一條通之間的一條通路。如果滿足下面條件之一，則稱被路。如果滿足下面條件之一，則稱被Z所阻塞：所阻塞：1有一個在有一個在Z中的順連節點；中的順連節點；2有一個在有一個在

12、Z中的分連節點中的分連節點3 有一個匯連節點有一個匯連節點W，它和它的后代節點均不在，它和它的后代節點均不在Z中。中。2021/4/116圖分割與變量獨立圖分割與變量獨立 如果如果X和和Y之間的所有通路都被之間的所有通路都被Z阻塞，則說阻塞，則說Z有向分有向分割割(directed separate)X和和Y，簡稱，簡稱d-separate,d-分割。分割。那么那么X和和Y在給定在給定Z時條件獨立。時條件獨立。 定理（整體馬爾科夫性）定理（整體馬爾科夫性）設設X和和Y為貝葉斯網為貝葉斯網N中的兩中的兩個變量，個變量，Z為為N中一個不包含中一個不包含X和和Y的節點集合。如果的節點集合。如果Z d

13、-分割分割X和和Y，那么，那么X和和Y在給定在給定Z時條件獨立，即時條件獨立，即 d-分割是圖論的概念，而條件獨立是概率論的概念，分割是圖論的概念，而條件獨立是概率論的概念，所以定理揭示了貝葉斯網絡圖論側面和概率論側面之所以定理揭示了貝葉斯網絡圖論側面和概率論側面之間的關系。間的關系。2021/4/117馬爾科夫邊界與端正圖馬爾科夫邊界與端正圖馬爾科夫邊界：條件獨立性馬爾科夫邊界：條件獨立性 在貝葉斯網絡中，一個節點在貝葉斯網絡中，一個節點X的馬爾科夫邊界的馬爾科夫邊界(Markov boundary)包括其父節點、子節點、以及子節點的父節包括其父節點、子節點、以及子節點的父節點。點。 端正圖

14、端正圖(Moral graph): 團樹傳播算法團樹傳播算法-junction tree 設設G為一有向無環圖，如果將為一有向無環圖，如果將G中每個節點的不同父節中每個節點的不同父節點結合，即在他們之間加一條邊，然后去掉所有邊的點結合，即在他們之間加一條邊，然后去掉所有邊的方向，所得到的無向圖成為方向，所得到的無向圖成為G的端正圖。的端正圖。2021/4/118貝葉斯網絡推理貝葉斯網絡推理(Inference)貝葉斯網絡可以利用變量間的條件獨立對聯合分貝葉斯網絡可以利用變量間的條件獨立對聯合分布進行分解，降低參數個數。布進行分解，降低參數個數。 推理推理(inference)是通過計算來回答查

15、詢的過程是通過計算來回答查詢的過程 計算后驗概率分布：計算后驗概率分布：P(Q|E=e)2021/4/119貝葉斯網絡推理貝葉斯網絡推理(Inference)1 變量消元算法變量消元算法(Variable elimination) 利用概率分解降低推理復雜度。利用概率分解降低推理復雜度。 使得運算局部化。消元過程實質上就是一個邊緣化的過程。使得運算局部化。消元過程實質上就是一個邊緣化的過程。 最優消元順序：最大勢搜索，最小缺邊搜索最優消元順序：最大勢搜索，最小缺邊搜索2021/4/120貝葉斯網絡推理貝葉斯網絡推理(Inference)2. 團樹傳播算法l利用步驟共享來加快推理的算法。l團樹（

16、clique tree）是一種無向樹，其中每一個節點代表一個變量集合，稱為團(clique)。團樹必須滿足變量連通性，即包含同一變量的所有團所導出的子圖必須是連通的。 2021/4/121 用團樹組織變量消元的算法。計算共享用團樹組織變量消元的算法。計算共享 團樹傳播算法基本步驟：團樹傳播算法基本步驟： 將貝葉斯網絡轉化為團樹將貝葉斯網絡轉化為團樹 團樹初始化團樹初始化 在團樹中選一個團作為樞紐在團樹中選一個團作為樞紐 全局概率傳播：全局概率傳播：CollectMessage; DistributeMessage 邊緣化，歸一化邊緣化，歸一化2021/4/122 團樹傳播算法示例團樹傳播算法示

17、例 （TLR是樞紐節點）是樞紐節點） FF變量消元和團樹傳播算法都是精確推理算法。變量消元和團樹傳播算法都是精確推理算法。2021/4/123貝葉斯網絡推理貝葉斯網絡推理(Inference)3 . 近似推理近似推理(1) 隨機抽樣算法：順序抽樣法，隨機抽樣算法：順序抽樣法，MCMC抽樣抽樣 是一類應用于數值積分和統計物理中的近似計是一類應用于數值積分和統計物理中的近似計算方法。基本思想是從某個概率分布隨機抽樣算方法。基本思想是從某個概率分布隨機抽樣，生成一組樣本，然后從樣本出發近似計算感，生成一組樣本，然后從樣本出發近似計算感興趣的量。興趣的量。 隨機抽樣算法理論基礎是隨機抽樣算法理論基礎是

18、大數定律大數定律。 2021/4/124MCMC算法算法吉布斯抽樣吉布斯抽樣(Gibbs sampling)。它首先隨機生。它首先隨機生成一個與證據成一個與證據E=e相一致的樣本相一致的樣本s1作為起始樣本。此后，作為起始樣本。此后，每個樣本每個樣本si的產生都依賴于前一個樣本的產生都依賴于前一個樣本si-1,且且si與與si-1最多最多只有一個非證據變量的取值不同，記改變量為只有一個非證據變量的取值不同，記改變量為X。 X的取值可以從非證據變量中隨機選取，也可以按某個固的取值可以從非證據變量中隨機選取，也可以按某個固定順序輪流決定。定順序輪流決定。 在在si中，中，X的值通過隨機抽樣決定，抽

19、樣分布是：的值通過隨機抽樣決定，抽樣分布是： 當樣本數當樣本數 時，馬氏鏈理論保證了算法返回的結果收時，馬氏鏈理論保證了算法返回的結果收斂于真正的后驗概率。吉布斯抽樣的缺點是收斂速度慢，斂于真正的后驗概率。吉布斯抽樣的缺點是收斂速度慢，因為馬氏鏈往往需要花很長時間才能真正達到平穩分布。因為馬氏鏈往往需要花很長時間才能真正達到平穩分布。 (2) 變分法。變分法。2021/4/125貝葉斯網絡學習貝葉斯網絡學習1. 結構學習：發現變量之間的圖關系結構學習：發現變量之間的圖關系 ，2 .參數學習：決定變量之間互相關聯的量化關系。參數學習：決定變量之間互相關聯的量化關系。 2021/4/126貝葉斯網

20、絡結構學習貝葉斯網絡結構學習l 選擇具有最大后驗概率的結構選擇具有最大后驗概率的結構 。l 基于評分函數基于評分函數(scoring function)：BIC, MDL, AIC等等 拉普拉斯近似拉普拉斯近似(Laplace approximation):對拉普拉斯近似簡化，得對拉普拉斯近似簡化，得BIC:BICBIC既不依賴于先驗也不依賴于參數坐標系統既不依賴于先驗也不依賴于參數坐標系統 第一項度量參數模型預測數據的優良程度，第二項用于懲罰模型復雜度第一項度量參數模型預測數據的優良程度，第二項用于懲罰模型復雜度 2021/4/127結構學習算法結構學習算法算法：算法：u K2: 通過為每個

21、結點尋找父結點集合來學習貝葉斯網絡結構。它不斷通過為每個結點尋找父結點集合來學習貝葉斯網絡結構。它不斷往父結點集中添加結點，并選擇能最大化數據和結構的聯合概率往父結點集中添加結點，并選擇能最大化數據和結構的聯合概率的結點集。的結點集。 u HillClimbing (operators: edge addition, edge deletion, edge reversion) 從一個無邊結構開始，在每一步，它添加能最大化從一個無邊結構開始，在每一步，它添加能最大化BIC的邊。算的邊。算法在通過添加邊不能再提高結構得分時停止。法在通過添加邊不能再提高結構得分時停止。u 缺值數據結構學習：缺值數

22、據結構學習：Structural EM SEM不是每次迭代都同時優化模型結構和參數，而是先固定模型不是每次迭代都同時優化模型結構和參數，而是先固定模型結構進行數次參數優化后，再進行一次結構加參數優化，如此交結構進行數次參數優化后，再進行一次結構加參數優化，如此交替進行。替進行。 目的：減小計算復雜度。目的：減小計算復雜度。 2021/4/1282021/4/1292021/4/130貝葉斯網絡參數學習貝葉斯網絡參數學習u最大似然估計最大似然估計 完全基于數據，不需要先驗概率：完全基于數據，不需要先驗概率： u貝葉斯估計貝葉斯估計 假定在考慮數據之前，網絡參數服從某個先驗分布。假定在考慮數據之前

23、，網絡參數服從某個先驗分布。先驗的主觀概率先驗的主觀概率,它的影響隨著數據量的增大而減小。它的影響隨著數據量的增大而減小。 2021/4/131貝葉斯網絡參數學習貝葉斯網絡參數學習u缺值數據最大似然估計：缺值數據最大似然估計：EM算法算法 （迭代算法）（迭代算法） 1 基于基于 對數據進行修補，使之完整對數據進行修補，使之完整 (E-step) 2 基于修補后的完整數據計算的最大似然估計基于修補后的完整數據計算的最大似然估計 (M-Step)EM算法是收斂的。算法是收斂的。2021/4/132隱結構模型學習隱結構模型學習l 隱變量是取值未被觀察到的變量。通過數據分析：隱變量是取值未被觀察到的變

24、量。通過數據分析： 1 隱變量的個數隱變量的個數 2 隱結構隱結構 3 隱變量的勢隱變量的勢 4 模型參數模型參數l 方法：基于評分函數的爬山法方法：基于評分函數的爬山法 G是一個隱變量模型，是一個隱變量模型，D是一組數據。是一組數據。 是是G的參數的某一個最大似然估計，的參數的某一個最大似然估計， 是是G的有效維數。的有效維數。 u隱變量勢學習爬山算法隱變量勢學習爬山算法u隱結構學習雙重爬山算法隱結構學習雙重爬山算法2021/4/133貝葉斯網絡用于分類和因果關系分析貝葉斯網絡用于分類和因果關系分析(1) Nave Bayesian networks(2) Tree augment Baye

25、sian networks, et al.(3) PC (Spirtes et al.,2000) , IC(Pearl,2000) algorithm2021/4/134動態貝葉斯網絡動態貝葉斯網絡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 models Hidden Markov models (HMMs)2021/4/135Software ToolsuMicrosofts MSBNXuBNT Kevin Murphy. BayesNet Toolbox for Matlab (BNT). http:/www.cs.ubc