概率圖模型之貝葉斯網路

上文我們講到，在圖的基礎上表示概率分布的模型我們稱之為概率圖模型；而且在圖中，我們用結點來表示隨機變數，結點之間的邊表示結點的概率依賴關係。本文我們介紹概率圖模型中一個最基礎的模型 ---- 貝葉斯網路。

貝葉斯網路(Bayesian network)，又稱信念網路(Belief Network)，或有向無環圖模型(directed acyclic graphical model)，是一種概率圖模型，於1985年由Judea Pearl首先提出。它是一種模擬人類推理過程中因果關係的不確定性處理模型，其網路拓樸結構是一個有向無環圖(DAG)。我們將有因果關係（或非條件獨立）的變數或命題用箭頭來連接（換言之，連接兩個節點的箭頭代表此兩個隨機變數是具有因果關係，或非條件獨立）。若兩個節點間以一個單箭頭連接在一起，表示其中一個節點是「因(parents)」，另一個是「果(children)」，兩節點就會產生一個條件概率值。 例如，假設節點E直接影響到節點H，即E→H，則用從E指向H的箭頭建立結點E到結點H的有向弧(E,H)，權值(即連接強度)用條件概率P(H|E)來表示，如下圖所示：

把某個研究系統中涉及的隨機變數，根據是否條件獨立繪製在一個有向圖中，就形成了貝葉斯網路。

貝葉斯網路的定義

令G = (I,E)表示一個有向無環圖(DAG)，其中I代表圖形中所有的節點的集合，而E代表有向連接線段的集合，且令X = (Xi)i ∈ I為其有向無環圖中的某一節點i所代表的隨機變數，若節點X的聯合概率可以表示成：

則稱X為相對於一有向無環圖G 的貝葉斯網路，其中，

表示節點i之「因」，或稱pa(i)是i的parents（父母）。

此外，對於任意的隨機變數，其聯合概率可由各自的局部條件概率分布相乘而得出：

如下圖所示，便是一個簡單的貝葉斯網路：

因為a導致b，a和b導致c，所以有

2.2 貝葉斯網路的實例

給定如下圖所示的貝葉斯網路：

其中，各個單詞、表達式表示的含義如下：

• smoking表示吸煙，其概率用P(S)表示，lung Cancer表示的肺癌，一個人在吸煙的情況下得肺癌的概率用P(C|S)表示，X-ray表示需要照醫學上的X光，肺癌可能會導致需要照X光，吸煙也有可能會導致需要照X光（所以smoking也是X-ray的一個因），所以，因吸煙且得肺癌而需要照X光的概率用P(X|C,S)表示。
• Bronchitis表示支氣管炎，一個人在吸煙的情況下得支氣管炎的概率用P(B|S)，dyspnoea表示呼吸困難，支氣管炎可能會導致呼吸困難，肺癌也有可能會導致呼吸困難（所以lung Cancer也是dyspnoea的一個因），因吸煙且得了支氣管炎導致呼吸困難的概率用P(D|C,B)表示。

lung Cancer簡記為C，Bronchitis簡記為B，dyspnoea簡記為D，且C = 0表示lung Cancer不發生的概率，C = 1表示lung Cancer發生的概率，B等於0（B不發生）或1（B發生）也類似於C，同樣的，D=1表示D發生的概率，D=0表示D不發生的概率，便可得到dyspnoea的一張概率表，如上圖的最右下角所示。

2.3 貝葉斯網路的3種結構形式

給定如下圖所示的一個貝葉斯網路，

從圖上可以比較直觀的看出：

• 1. x1,x2,…x7的聯合分布為

• 2. x1和x2獨立（對應head-to-head）；
• 3. x6和x7在x4給定的條件下獨立（對應tail-to-tail）。

根據上圖，第1點可能很容易理解，但第2、3點中所述的條件獨立是啥意思呢？其實第2、3點是貝葉斯網路中3種結構形式中的其中二種。為了說清楚這個問題，需要引入D-Separation（D-分離）這個概念。

D-Separation是一種用來判斷變數是否條件獨立的圖形化方法。換言之，對於一個DAG(有向無環圖)E，D-Separation方法可以快速的判斷出兩個節點之間是否是條件獨立的。

2.3.1 形式1：head-to-head

貝葉斯網路的第一種結構形式如下圖所示

所以有：P(a,b,c) = P(a)*P(b)*P(c|a,b)成立，化簡後可得：

即在c未知的條件下，a、b被阻斷(blocked)，是獨立的，稱之為head-to-head條件獨立，對應本節中最開始那張圖中的「x1、x2獨立」。

2.3.2 形式2：tail-to-tail

貝葉斯網路的第二種結構形式如下圖所示

有P(a,b,c)=P(c)*P(a|c)*P(b|c)，則：P(a,b|c)=P(a,b,c)/P(c)，然後將P(a,b,c)=P(c)*P(a|c)*P(b|c)帶入上式，得到：P(a,b|c)=P(a|c)*P(b|c)。

2.3.3 形式3：head-to-tail

貝葉斯網路的第三種結構形式如下圖所示：

有：P(a,b,c)=P(a)*P(c|a)*P(b|c)。

化簡後可得：

即：在c給定的條件下，a，b被阻斷(blocked)，是獨立的，稱之為head-to-tail條件獨立。

插一句：這個head-to-tail其實就是一個鏈式網路，如下圖所示：

在xi給定的條件下，xi+1的分布和x1,x2…xi-1條件獨立。即：xi+1的分布狀態只和xi有關，和其他變數條件獨立，這種順次演變的隨機過程，就叫做馬爾科夫鏈（Markov chain）。且有：

OK，今天在總結貝葉斯網路中的上述3種結構時，發現跟河流關係比較相像，比如：

• ①兩條小河流入一條大河，叫head-to-head，由P(a,b,c)=P(c|a,b)P(b)P(a)，可得：P(a,b) = P(a)*P(b)，即c未知的條件下，a、b被阻斷(blocked)，是獨立的。同時，也謂之匯連，且匯連是條件依賴的（C依賴於A、B的聯合分布），匯連這種情況也稱為一個v-結構；

• ②一條大河到某處分叉成兩條支流，稱之為tail-to-tail，由P(a,b,c)=P(b|c)P(a|c)P(c) ，可得：P(a,b|c)=P(a|c)*P(b|c)，即在c給定的條件下，a，b被阻斷(blocked)，是獨立的。同時，也謂之分連；

• ③一條大河流到底，中間不分叉不匯入其它河流，但可能其中的某段叫什麼江，另一段叫什麼江，稱之為head-to-tail，由P(a,b,c)=P(b|c)P(c|a)P(a) ，化簡可得：P(a,b,c)=P(a)*P(c|a)*P(b|c)，即在c給定的條件下，a，b被阻斷(blocked)，是獨立的。同時，也謂之順連；

不知道讀者對這個河流的比喻怎麼看？^_^

接著，將上述結點推廣到結點集，則是：對於任意的結點集A，B，C，考察所有通過A中任意結點到B中任意結點的路徑，若要求A，B條件獨立，則需要所有的路徑都被阻斷(blocked)，即滿足下列兩個前提之一：

1. A和B的「head-to-tail型」和「tail-to-tail型」路徑都通過C；
2. A和B的「head-to-head型」路徑不通過C以及C的子孫；

最後，舉例說明上述D-Separation的3種情況，則是如下圖所示：

上圖中左邊部分是head-to-tail，右邊部分的右上角是tail-to-tail，右邊部分的右下角是head-to-head。

2.4 因子圖

回到2.2節中那個實例上，如下圖所示：

對於上圖，在一個人已經呼吸困難的情況下，其抽樣的概率是多少呢？即：

咱們來一步步計算推導下：

註：解釋下上述式子的第二行到最後一行第三行的推導過程。最開始，所有變數都在sigma(d=1,b,x,c)的後面（sigma表示對「求和」的稱謂），但由於P(s)和「d=1,b,x,c」都沒關係，所以，可以提到式子的最前面。而且P(b|s)和x、c沒關係，所以，也可以把它提出來，放到sigma(b)的後面，從而式子的右邊剩下sigma(x)和sigma(c)。

此外，Variable elimination表示的是變數消除的意思。為了更好的解決此類問題，咱們得引入因子圖的概念。

2.4.1 因子圖的定義

wikipedia上是這樣定義因子圖的：將一個具有多變數的全局函數因子分解，得到幾個局部函數的乘積，以此為基礎得到的一個雙向圖叫做因子圖（Factor Graph）。

比如，假定對於函數

，有下述式子成立：

其中

，其對應的因子圖

包括：

1. 變數節點

1. 因子（函數）節點

1. 邊

，邊通過下列因式分解結果得到：在因子（函數）節點

和變數節點

之間存在邊的充要條件是

存在。

官方正式的定義果然晦澀！我相信你沒看懂。通俗來講，所謂因子圖就是對函數進行因子分解得到的一種概率圖。一般內含兩種節點，變數節點和函數節點。我們知道，一個全局函數通過因式分解能夠分解為多個局部函數的乘積，這些局部函數和對應的變數關係就體現在因子圖上。舉個例子，現在有一個全局函數，其因式分解方程為：

其中fA,fB,fC,fD,fE為各函數，表示變數之間的關係，可以是條件概率也可以是其他關係(如馬爾可夫隨機場Markov Random Fields中的勢函數)。

為了方便表示，可以寫成：

其對應的因子圖為：

且上述因子圖等價於：

所以，在因子圖中，所有頂點不是變數節點就是函數節點，邊線表示它們之間的函數關係。

但搞了半天，雖然知道了什麼是因子圖，但因子圖到底是幹嘛的呢？為何要引入因子圖，其用途和意義何在？事實上，因子圖跟貝葉斯網路和馬爾可夫隨機場（Markov Random Fields）一樣，也是是概率圖的一種。從上文中，我們可以看到，在概率圖中，求某個變數的邊緣分布是常見的問題。這問題有很多求解方法，其中之一就是可以把貝葉斯網路或馬爾科夫隨機場轉換成因子圖，然後用sum-product演算法求解。換言之，基於因子圖可以用sum-product 演算法高效的求各個變數的邊緣分布。

先舉個例子說明如何把貝葉斯網路（和馬爾科夫隨機場）轉換成因子圖。給定下圖所示的貝葉斯網路或馬爾科夫隨機場：

根據各個變數對應的關係，可得：

其對應的因子圖為（以下兩種因子圖的表示方式皆可）：

由上述例子總結出由貝葉斯網路構造因子圖的方法：

• 貝葉斯網路中的一個因子對應因子圖中的一個結點
• 貝葉斯網路中的每一個變數在因子圖上對應邊或者半邊
• 結點g和邊x相連當且僅當變數x出現在因子g中

舉幾個例子。比如，對於如下的一個因子圖：

有：

而對於下圖所示的馬爾科夫鏈：

有：

另對於如下圖所示的隱馬爾科夫模型：

有：

本文轉自這篇博博客，我覺得寫的很詳細了，比我看的《數學之美》和《統計自然語言》裡面寫的還詳細。

推薦閱讀：