雪花台湾

PRML學習筆記（八）第八章 圖模型

PRML 和 ESL 的學習基本上是學十得一。穩紮穩打再來一次

圖模型

概率分布的圖形表示被稱為概率圖模型，它提供了幾個有用的性質：

在概率圖模型中，每個節點表示一個隨機變數，鏈接表示這些變數之間的概率關係。這樣，圖描述了聯合概率分布在所有隨機變數上，能夠分解為一組因子乘積的方式，每個因子只依賴於隨機變數的一個子集。

概率圖分為又想吐和無向圖兩大類。有向圖模型也就是貝葉斯網路，圖之間的鏈接有一個特定的方向，使用箭頭表示。另一大類是馬爾科夫隨機場，也被稱為無向圖模型，這個模型中，鏈接沒有箭頭，沒有方向性質。有向圖對於表達隨機變數之間的因果關係很有用，而無向圖對於表示隨機變數之間的軟限制比較有用。為了求解推斷問題，通常比較方便的做法是把有向圖和無向圖都轉化為一個不同的表示形式，被稱為因子圖。

8.1 貝葉斯網路

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

讓我們來分析它，首先，每個節點對應於一個隨機變數a, b, c。每個帶箭頭的鏈接的起點表示條件概率中隨機變數對應的節點。對於沒有輸入鏈接的節點a,則表示為p(a)。因此上圖表示的概率為：

由此可見上圖表示了方程的右側。同時我們注意到方程的左側是對稱的，但右側不是，因此對弈一個聯合概率，我們可能會得到不同的分解方式。上面這個圖我們說它是全連接的，因為每對節點之間都存在一個鏈接。與之對應，也就存在鏈接缺失的情況，如：

更一般地，在圖的所有節點上定義的聯合概率分布由每個節點上的條件概率分布的乘積表示，每個條件概率分布的條件都是圖中節點的父節點所對應的變數。因此，對於一個有K個節點的圖，聯合概率為：

其中 表示 父節點的集合， 。上式表示有向圖的聯合概率分布的分解屬性。

我們考慮的有向圖要滿足一個重要的限制，即不能存在有向環，這種沒有有向環的圖被稱為有向無環圖，或者DAG。

8.1.1 例子：多項式回歸

對於多項式回歸，我們有多項式係數向量w，觀測數據t，輸入數據x，雜訊方差 以及w的高斯先驗精度 。當我們顯示地寫出模型的參數和隨機變數時，聯合概率分布可寫為：

對應的概率分布圖如下圖所示：

其中隨機變數由空心圓表示，確定性參數由小的實心圓表示，藍色框被稱為板，來表示變數的集合。

8.1.4 線性高斯模型

現在我們將說明多元高斯分布如何表示為一個對應於成分變數上的線性高斯模型的有向無環圖。

考慮D個變數上的任意的有向無環圖，其中節點i表示服從高斯分布的一元連續隨機變數 。這個分布的均值是節點i的父節點 的狀態的線性組合，即：

其中 和 是控制均值的參數， 是 的條件概率分布的方差。這樣，聯合概率分布的對數為圖中所有節點上的這些條件分布的乘積的對數，因此形式為：

可以看出聯合概率分布是一個多元高斯分布。我可以遞歸地計算它的均值和方差，首先計算 的均值和方差：

而後從序號最低的節點開始，沿著圖遞歸的計算，就可以求出 的各個元素和協方差的各個元素。

假設圖中不存在鏈接時，圖由D個孤立的節點組成，此時不存在參數 因此只有D個參數 和D個參數 。根據遞歸關係，我們看到p(x)的均值為 ，協方差矩陣是一個對角矩陣，形式為 。聯合概率分布總計由2D個參數，表示D個獨立的一元高斯分布的集合。

當圖為全連接時，其中每個節點的序號都低於其父節點的序號。 對應於下三角矩陣， 對應於一個一般的對稱協方差矩陣。

複雜度處於二者之間的對應於協方差矩陣取特定形式的聯合高斯分布。

8.2 條件獨立

多變數概率分布的一個重要概念是條件獨立。如下圖所示，考慮三個變數a, b, c，並且假定給定b,c的條件下a的條件概率分布不依賴於b的值，即：

我們說，在給定c的條件下，a條件獨立於b。

採用條件獨立標記表示為：

在模式識別中，使用概率模型時，條件獨立性起著重要的作用。它簡化了模型的結構，降低了模型的訓練和推斷的計算量。根據圖模型，聯合概率分布的條件獨立性可以直接從圖中讀出來，不用進行任何計算。完成這件事的一般框架被稱為"d-劃分"，其中d表示有向。

8.2.2 d-劃分

考慮一個一般的有向圖，其中 A, B, C是任意無交集的節點集合(它們的並集可能比圖中節點的完整集合要小)。我們希望知道，一個有向無環圖是否暗示了一個特定的條件依賴表述 。

為此我們考慮從A中任意節點到B中任意節點的所有可能的路徑。我們說這樣的路徑被阻隔，如果它包含一個節點滿足下面兩個性質中的任何一個：

如果所有的路徑都被阻隔，那麼我們說C把A從B中d-劃分開，且圖中所有變數上的聯合概率分布都將會滿足 。

8.3 馬爾科夫隨機場

前面看到有向圖模型表示將一組變數上的聯合概率分布分解為局部條件概率分布的乘積的一種分解方式。有向圖也定義了一組條件獨立性質，根據圖進行分解的任何概率分布都必須滿足這些條件獨立性質。現在我們考慮無向圖模型，與之前一樣，它表示一種分解方式，也表示一組條件獨立關係。

一個馬爾科夫隨機場，也被稱為馬爾科夫網路或者無向圖模型，包含一組節點，每個節點都對應著一個變數或者一組變數。鏈接是無向的，即不含有箭頭。

8.3.1 條件獨立性質

假設在一個無向圖中，我們有三個節點集合，記做 A, B, C。考慮鏈接集合A的節點和集合B的節點所有可能的路徑。如果所有這些路徑都用過集合C中的一個或多個節點，那麼所有這樣的路徑都被阻隔，因此條件獨立性質成立。由此可見，無向圖的條件獨立檢測更加簡單。

8.3.2 分解性質

分解即將聯合概率分布p(x)表示為在圖的局部範圍內的變數集合上定義的函數的乘積。為此我們首先給局部性一個合適的定義。團塊定義為圖中節點的一個子集，使得在這個子集中的每對接點之間都存在鏈接，即全連接的。一個最大團塊即不可能將圖中任何一個其他的節點包含到這個團塊中而不破壞團塊的性質。

於是，我們可以將聯合概率分布分解的因子定義為團塊中變數的函數。讓我們將團塊記做C，將團塊中的變數的集合記做 。這樣，聯合概率分布可以寫成圖的最大團塊的勢函數 的乘積的形式：

其中 Z 有時被稱為劃分函數，是一個歸一化的常數，等於：

歸一化常數的存在是無向圖的一個主要的缺點，因為歸一化項涉及到 個狀態的求和。對於參數學習來說，劃分函數是必要的，因為劃分函數是控制勢函數 的任意參數的函數。

現在我們形式化地描述條件獨立性和無向圖的分解形式，我們將限制勢函數嚴格為正，即對於任意的 的選擇都永遠不等於零也不取負值的勢函數。這樣我們可以給出分解和條件獨立間的精確關係。

考慮下圖所示的濾波器模型：

它表示將變數x的集合上的所有可能的概率分布p(x)輸入到濾波器中，那麼通過濾波器的概率分布的子集被記做 ，表示有向分解。

對於無向圖模型，我們定義 為滿足下麵條件的概率分布的集合：從使用圖劃分的方法得到的圖中可以讀出條件獨立性質，這個概率分布應該與這些條件獨立性質相容。類似地，我們定義 為：可以表示為關於圖中最大團塊的分解的形式的概率分布。Hammersley-Clifford 定理表明，集合 和 是完全相同的。

由於我們將勢函數限制為嚴格大於0，因此將是函數表示為指數形式更方便，即：

其中 被稱為能量函數，指數表示被稱為玻爾茲曼分布。聯合概率分布被定義為勢函數的乘積，因此總的能量可以通過將每個最大團塊的能量相加的方法得到。

8.3.4 與有向圖的關係

將有向圖轉化為無向圖，我們首先在圖中每個節點的所有父節點之間添加額外的無向鏈接，然後去掉原始鏈接的箭頭，得到道德圖。之後，我們將道德圖的所有團塊勢函數初始化為1。接下來，我們拿出原始有向圖中所有的條件概率分布因子，將它乘到一個團塊勢函數中去。由於倫理步驟存在，總會存在至少一個最大的團塊，包含因子中所有的變數。注意，在所有情形下，劃分函數都等於1。

將有向圖轉化為無向圖的過程在精確推斷方法中起著重要作用，例如聯合樹演算法。從一個無向圖轉化到有向圖表示不太常用，通常表示歸一化限制中出現的問題。

8.4 圖模型中的推斷

現在考慮圖模型中的推斷問題，圖中的一些節點被限制為觀測值，我們想要計算其他節點中的一個或多個子集的後驗概率分布。本章我們集中精力與精確推斷，第十章考慮近似推斷。

8.4.1 鏈推斷

考慮下圖所示的節點鏈

對於圖b的聯合概率分布形式為：

現在考慮尋找邊緣概率分布 這一推斷問題，其中 是鏈上的一個具體的節點。如果我們對勢函數求和進行分組，就可以將需要求解的邊緣概率密度寫成：

根據上式，我們將邊緣概率分布 的表達式分解成了兩個因子的乘積乘以歸一化常數：

我們把 看成從節點 到節點 的沿著鏈向前傳遞的信息。類似地， 可以看做從節點 到節點 的沿著鏈向後傳遞的信息。注意，每條信息由K個值的集合構成，每個值對應於 的一種選擇，因此兩條信息的乘積可以被看做兩條信息的元素之間的點積，得到另外K個值的信息。

和 可以遞歸的計算，我們先計算：

如果圖中的某些節點被觀測到，那麼對應的變數簡單地被限制為觀測值即可，不需要求和。

現在假設我們想計算節點鏈中兩個相鄰節點的聯合概率分布 。這類似於計算單一結點的邊緣概率分布，區別於現在由兩個變數沒有被求和出來。因此：

一旦我們完成了計算邊緣概率分布所需的信息傳遞，我們就可以直接得到每個勢函數中的所有變數上的聯合概率分布。為了在並非所有的變數都被觀測到的情況下學習勢函數的參數，我們可以使用EM演算法。可以證明，以任意觀測數據為條件，團塊的局部聯合概率分布恰好是E步驟所需要的的。

8.4.3 因子圖

有向圖和無向圖都使得若干變數的一個全局函數能夠表示為這些變數的子集上的因子的乘積。因子圖顯式地表示出了這個分解。方法是：在表示變數的節點的基礎上，引入額外的節點表示因子本身。

在因子圖中，概率分布中的每個變數都有一個節點，這與有向圖和無向圖的情形相同。還存在其他的節點(用小正方形表示)，表示聯合高綠分布中的每個因子 。最後，在每個因子節點和因子所以來的變數之間，存在無向鏈接。由於因子圖由兩類不同的節點組成，且所有的鏈接都位於兩類不同的節點之間，因此因子圖被稱為二分的。一個因子圖的例子如下圖所示：

它對應於概率分布：

8.4.4 加和乘積演算法

關於有向無環圖的精確推斷，有一個被稱為置信傳播的演算法，它等價於加和-乘積演算法的一個具體情形。另外，對加和-乘積演算法稍作修改，使得概率最大的狀態被找到就引出了最大加和演算法。

假設原始的圖是一個無向樹或者有向樹或者多樹，從而對應的因子圖有一個樹結構。首先，我們將原始的圖轉化為因子圖，使得我們可以使用同樣的框架處理有向模型和無向模型。我們的目標是利用圖完成兩件事：1)得到一個高效的精確推斷演算法來尋找邊緣概率，2)在需要求解多個邊緣概率的情形，計算可以高效地共享。

加和-乘積演算法總結如下：

1) 將變數節點x看成因子圖的根節點，使用下面的公式初始化圖的葉節點的信息。

2) 遞歸地應用信息傳遞步驟進行信息傳播，知道信息被沿著每一個鏈接傳遞完畢，並且根節點收到了所有相鄰接點的信息。

其中 表示因子節點 的相鄰變數節點的集合，但移除了節點x。 3) 一旦節點收到了所有其他相鄰節點的信息，那麼它就可以向根節點發送信息。一旦根節點收到了所有相鄰節點的信息，需要求解的邊緣概率分布就可以使用下式進行計算：

現在假設我們項尋找圖中每個變數節點的邊緣概率分布，其過程如下。任意選擇一個節點(變數或因子節點)，然後將其指定為跟幾點。像之前一樣，我們從葉節點向根節點傳遞信息。現在根節點會接收來自所有相鄰節點的信息。因此，它可以向所有的相鄰節點發送信息。反過來，這些節點之後會收到來自所有相鄰節點的信息，因此可以沿著遠離根節點的鏈接發送信息。以此類推，通過這種方式，信息可以從根節點向外傳遞到葉節點。現在信息已經在兩個方向上沿著圖中所有的鏈接傳遞完畢，並且每個節點都已經接收到了來自所有相鄰節點的信息。因為每個變數節點會收到來自所有相鄰節點的信息，所以我們可以計算圖中每個變數的邊緣概率分布。

8.4.5 最大加和演算法

我們想在想找到變數的具有最大概率的一個設置，以及找到這個概率的值。它可以通過最大加和演算法完成，它可以被看做動態規劃在圖模型中的一個應用。

為了求得最大化聯合概率分布p(x)的x的值，我們首先將因子圖表達式 帶入下式：

然後交換乘積與最大化的計算順序。這種計算的結構與加和-乘積演算法完全相同，因此我們能夠簡單地將那些結果轉化到當前的問題中。特別地，假設令圖中的一個特定的變數節點為根節點。之後，我們計算起始的一組信息，然後從樹的葉節點向內部傳遞到根節點。對於每個節點，一旦它接收到來自其他相鄰節點的輸入信息，那麼它就向根節點發送信息。最後對所有到達根節點的信息的乘積進行最大化，得出p(x)的最大值。這可以被稱為最大化乘積演算法，與加和-乘積演算法完全相同，唯一的區別是求和被替換為了求最大值。

在實際應用中，許多小概率的乘積可以產生數值下溢的問題，因此更方便的做法是對聯合概率的對數進行操作。取對數後唯一的效果是把最大化乘積演算法中的乘積替換成了加和，因此我們得到了最大化加和演算法。結果為：

最開始的由葉節點發送的信息可以由類比得到：

在根節點處的最大概率可以類比得到：

對於求解聯合概率達到最大值的變數的配置，我們可採用如下方法： 如果一條信息從因子節點f出發送到變數節點x，那麼最大化針對的是因子節點的全部其他變數節點 ，使用公式：

當我們進行最大化時，我們記錄了給出最大值的變數 的值。這樣找到了 之後，我們在反向跟蹤步驟中可以使用這些存儲的值，為相容的最大狀態 的值。只要因子圖是樹，最大加和演算法以及反向跟蹤方法就可以給出變數的精確最大化配置。這種方法的一個重要應用就是尋找隱馬爾科夫模型中隱含狀態的最可能序列，這種情況下被稱為Viterbi演算法。

8.4.6 一般圖的精確推斷

信息傳遞框架可以被推廣到任意的圖拓撲結構，從而得到一個精確的推斷步驟，被稱為聯合樹演算法。這裡給出各個階段的大致思想。

聯合樹演算法對於任意的圖都是精確地、高效的。對於一個給定的圖，通常不存在計算代價更低的演算法。


推薦閱讀：
相关文章