概率圖模型和馬爾可夫模型

概率圖模型和馬爾可夫隨機場

1.什么是概率圖模型

絕大多是機器學習的目的就是從給定的資料中學習到資料的特點，從給定的資料中找出資料與資料之間的關系，但是對于有一些資料而言，資料與資料之間的關系無法直接并且準確地從給定資料中觀察到，因為這樣的資料存在著一個或者多個隱變數，這些隱變數使得屬性之間的聯系變得更加的復雜，所以我們需要一個模型來清晰地表示變數與變數之間關系的概率模型，我們將變數作為一個節點，將變數之間的關系用線來表示，然后把所有有關聯的變數連接起來，就形成了我們所謂的概率圖模型，

概率圖模型根據資料點之間的相互關系，可以分成貝葉斯網(有向圖模型)和馬爾可夫網(無向圖模型)

1.1 有向圖模型

通常有向圖是用概率拼接起來的，因為有向圖中，變數與變數之間的依賴關系我們可以觀測或者預估，若變數之間的依賴關系已知，那么整個圖模型就可以使用所有的變數的聯合概率分布來表示，為了更容易理解，我們假設我們有一組觀測變數X={x1,x2,x3,x4}，這四個觀測變數的依賴關系如下圖所示:

這個圖的意思是，X1，X3是獨立的，他們的出現不依賴于集合中的任何變數，然而，X2的出現依賴于X1和X3兩個變數，X4的出現依賴于X2，
按照這樣的邏輯，我們可以很輕松的寫出這一個有向圖模型的運算式，用聯合概率分布表示為：

所以根據上面的式子，我們可以這樣來解釋有向圖：有向圖就是將一整個聯合概率分布分成了一個一個獨立于單個變數的條件概率分布，

A directed graphical model describes how a distribution factorizes into local conditional probability distributions.

1.2 什么是無向圖模型

無向圖模型資料與資料直接沒有可觀測或者可預估的依賴關系，且往往有著較大的資料量，比如圖片中的每一個像素點之間沒十分明確的依賴關系，所以這個時候我們無法直接用概率將無向圖進行拼接，但是我們也想要找到無向圖之間變數的依賴關系，于是，我們將一個無向圖分成一個一個小塊(這樣的小塊叫做團)，來研究每一個小塊中變數的依賴程度，團中的兩兩元素應該相互連接，如果一個團無法在容下另外的團，那么這樣的團我們稱之為最大團，那團中元素的依賴程度我們怎么來求解？這里要引入一個叫做勢函式的概念.勢函式的作用就是用來刻畫每一個團中的元素相關性的，假設我們使用C來表示一個無向圖的團的集合，那么這個無向圖我們可以表示成：

這里的Z叫做規范化因子，我們要注意的是，如果一個團不是最大團，那么他一定屬于某一個最大團，如果我們以所有的團來進行建模，會出現很多不必要的重復運算，所以，C應該是所有最大團的合集，

1.3 馬爾可夫模型

馬爾可夫模型就是一個非常經典的有向圖模型，既然是有向圖的一種，那么馬爾可夫模型，就一定包含有向圖的基本特征，那么如何來確定一個馬爾可夫模型呢？？

我們還是用拋硬幣的例子來解釋馬爾可夫模型，我們假設有兩枚硬幣，每一次隨機從兩枚硬幣中拿出一枚進行投擲，并記錄下結果(正面還是反面)，以上步驟重復5次，意思是，我們應該隨機從兩枚硬幣中拿5次并且記錄5次結果，
在以上的情景中，什么是隱變數？隱變數是我們每一次選擇的硬幣是A還是B，這些無法觀測，什么是觀測變數? 也就是我們每一次投擲的結果，這個是可以觀測到的，現在我們所能想到的變數就這些了，那我們將這些變數用上面提到的圖的方式，連接起來能得到什么呢？

從上圖中，藍色圈圈表示隱變數，也就是我們隨機拿的硬幣，這個在馬爾可夫模型中叫做狀態,假如我們拿了硬幣A來投，投出了正面，那么這個正面(圖中用綠色框框劃出來的)就是觀測變數(observations)，那投完了第一次硬幣之后，我們又要再一次從AB中拿一枚來投，這時候拿到的可能是硬幣B，也有可能還是硬幣A，再一次拿硬幣這個程序在馬爾可夫模型里也有專業的定義，我們可以叫它狀態轉移，

現在我們來定義馬爾可夫模型的三個重要引數：

• 初始狀態變數(Initial Probability)
  初始狀態變數通常指的是第一個狀態變數出現的概率，也就是第一次取硬幣是取到A還是B的概率，假設用 π \pi π來表示初始狀態概率，y表示當前狀態，初始狀態變數可以表示成：

• 輸出觀測概率/發射概率(Emission Probability)：
  發射概率闡述的是當前狀態下，輸出觀測變數為 x i x_i xi?的概率，
  結合硬幣的例子，當我現在拿到了硬幣A，出現正面或者反面的概率是多少，

• 狀態轉移概率：
  狀態轉移概率闡述了，模型之間每個狀態之間相互轉移的概率，
  同樣的結合硬幣例子來理解，就是第一次取到了硬幣A來投擲了，那么下一次我取到硬幣A或者硬幣B的概率，

這里有一個有趣的現象， 每次一投硬幣的結果只和當前選取的硬幣有關，去其他的變數無關，每一次隨機抽取的硬幣是A還是B，只和上一次投擲的硬幣有關，換句話說在任意時刻，觀測變數只和狀態變數有關，而且當前時刻的狀態僅和上一時刻的狀態有關，去其他時刻無關，這樣的現象(約束)被稱為‘馬爾可夫鏈’ ，

當我們可以從資料中找出上述的三種引數，并且資料的依賴規則滿足‘馬爾可夫鏈’的約束，那么我們就可以用馬爾可夫模型對這樣的資料進行建模，

1.4 D-separation

在進入馬爾可夫模型常見問題之前，有必要先了解什么叫做D-separation，它闡述了每個變數之間的相互依賴關系，也就是說，在給定的一個圖G中，可以通過D-separation來判斷屬于圖G中的兩個子合集A和B是不是相互獨立，

它有三條重要的規則：
1.A與B是 D-connected,如果AB之間沒有碰撞點(collider)，換句話說，如果他們之間有碰撞點，那么他們就是相互獨立的，
什么是碰撞點？舉個例子，如下如所示，這里的箭頭并不是代表的方向，因為我們在這里不討論方向，箭頭可以理解成變數間相互依賴關系，在下圖中，碰撞點是a4，簡單地理解，當箭頭出現‘頭對頭’的情況(head to head)，那么箭頭中間的那一個點就可以叫做‘碰撞點’，

我們可以發現，在這種情況下，只要經過碰撞點，箭頭的方向就發生了變化，我們理解成變數之間的依賴關系發生了變化，所以在下圖中，a1與a2是相互依賴的，同理a2，a3也是，但是a1與b1是相互獨立的，因為無論如何都無法避免依賴關系發生改變，也就是無法在a1和b1之間找到一條箭頭方向不改變的"路徑"，注意，這里的討論前提條件是無條件,意思是只討論兩個集合的情況，

2.有條件的約束，
因為第一種約束存在著局限性，在有些情境下可能無法使用，比如沒有碰撞點存在的時候，如何使得兩個變數條件獨立呢？我們引入一個條件合集Z，如果Z中的元素出現在了
"路徑"中間，那么這條路徑就可以說是被Z阻斷了，可以理解成，變數之間的依賴關系被新加入的元素打斷，我們可以設想如圖所示的情況，

上圖中，X1,X2依舊是相互依賴的，因為他們之間沒有元素加入，也沒有碰撞點，但是X2和X3就是相互獨立的，因為依賴關系被Z1阻斷，這個條件的使用也有一個前提，那就是如果存在這個碰撞點，碰撞點不可以在Z這個集合中

3.當碰撞點在條件集中
如果碰撞點出現在了條件集合中，又或者說，碰撞點的子代(descendant)在條件集合中，那么這個時候碰撞點將不會阻斷任何“路徑”，這里很抽象，什么意思？意味著當上述情況出現之后，原本獨立的兩個或多個變數變得相互依賴，如下圖所示

本來應該被碰撞點a3截斷的路徑，因為碰撞點的子代在條件集合Z中，導致從a1到b2都相互依賴，

詳細D-separation的解釋可以參考D-separation without tears

1.5 馬爾可夫模型的常見問題和解決方法

根據上面的描述，我們可以大致的推斷出馬爾可夫模型的幾種常見問題，

• Inference problem(推斷問題)
  我們只知道觀測變數和引數，需要預測狀態序列的時候，比如在硬幣問題中，我們知道三個關鍵引數和每一次投擲的結果，來推斷投擲的是A還是B，
  這種問題有兩種常見的方法，一種brute-force(暴力法)和Viterbi演算法，

  暴力法，顯而易見，就是嘗試每一個可能的狀態組合取出使得聯合概率最高的狀態，但是通常這樣的做法都是不可取的，特別是遇到資料量巨大的情況，因為如果是一個二選一的問題，那么我們就有 2 2 = 4 2^2=4 22=4個可能的狀態序列，如果有N個可能的狀態，那么就有 2 N 2^N 2N個可能的序列，計算壓力極大，時間復雜度極高，
  所以我們會使用Viterbi演算法來高效的推斷出最佳的狀態序列，

  Viterbi演算法本身是動態規劃演算法，動態規劃的核心就是將一個大問題分成多個小問題，秉持著所有sub-problems的最優解之和就是全域最優解的思想，我們也可以將inference 問題 分成多個小塊來求解，我們每一次只計算一個狀態，并保證每一次取到的狀態都能使當前時刻與觀測變數的聯合分布最大，如果每一步取到的狀態變數都能使當前的聯合分布最大的話，那么最后找出的狀態變數序列也一定可以讓聯合分布最大化，

  具體怎么做：
  我們首先創建一個變數 σ i \sigma_i σi?來表示從第1個時刻開始到當前時刻，所選狀態和觀測變數的聯合概率分布，我們在整個程序中都應該保持 σ i \sigma_i σi? 最大化， σ \sigma σ可以定義成：

  

  為了可視化整個程序，下面用一個表格來表示：

  

  圖中的橫軸Z1-Z5表示的是5個時刻的狀態，縱軸上的1-5表示的是每一個時刻可能取到的狀態，因為我們知道初始狀態概率，所以我們可以求出Z1時刻下能使聯合概率分布最大的狀態變數，在Z2時刻時，每一次計算應該是基于Z1時刻的結果，具體可以表示成：

  

計算從 Z 1 Z_1 Z1?轉移至 Z 2 Z_{2} Z2?的狀態轉移矩陣，再加上 Z 1 Z_1 Z1?時刻的 σ \sigma σ值，我們取出其中最大的結果作為 Z 2 Z_2 Z2?的值，

然后重復上述步驟，計算每一個節時刻的狀態值，使得最后聯合概率分布最大的序列就是最佳的狀態序列，如下圖所示表示的最佳狀態序列就是23154，

• 引數估計問題
  引數估計的目標一定是估計發射概率，轉移概率以及初始概率這三個引數，那么引數估計本身有兩種情況，complete case 和 incomplete case，所謂的complete case 就是觀測變數和狀態變數全部已知,那么引數估計就可以寫成’ p ( x ∣ z ) p(x|z) p(x∣z)’，而 incomplete case 就是沒有只有觀測變數已知，但是狀態變數未知的情況’ p ( x ∣ ? ) p(x|?) p(x∣?)’，

  對于第一種情況，往往我們只需要做一些簡單的統計就可以找出合適的引數了，相對比較容易處理，比如說，我們想要知道初始狀態概率，只需要將每一種狀態變數作為第一個狀態的次數除以總共的樣本數即可，發射概率和轉移概率也是用類似的簡單統計思想，

  通常我們需要討論第二種情況，在狀態變數未知的情況下，是無法對三個關鍵引數進行預估的，所以這時我們可以用到EM演算法的思想來對狀態變數進行預估，從而預估引數，(如果對EM演算法不太熟悉，可以參考EM演算法的理解和證明這篇博客，

  現在思考狀態變數在馬爾可夫模型中能決定什么？？他可以決定當前狀態下的輸出觀測變數和下一時刻的狀態變數，所以我們可以用這一個關系，來求出當觀測變數給定時，所有狀態出現的概率：

  
  相當于我們可以通過上述的方式來求出狀態變數的expectation，將一個incomplete case 轉換成了一個complete case，之后我們就可以推算三個關鍵引數的值，然后再使用估算出的引數的值去更新狀態變數的expectation，

  我們現將在這個公式用貝葉斯公式展開：
  

  上述公式中，我將已知的觀測變數合集z,拆分成了兩個，一個包含了從第一個觀測變數到第K個，第二包含了從第K+1個觀測變數到最后一個，這么做的原因是，可以使后面的數學證明更加清晰，

  前面有講到，有向圖是將一個大的聯合概率分布拆分一個一個的基于單個變數的條件概率分布， 對于上述式子而言，我們還可以將其表達成：

  
  根據D-separation的第二條性質，我們可以斷定， x 1 : k x_{1:k} x1:k?和 x k + 1 : n x_{k+1:n} xk+1:n?是相互依賴的，所以 x 1 : k x_{1:k} x1:k?對當前分布不造成影響，所以：

  
  上述的運算式，其實是一種新演算法叫做前向-后向演算法(forward-backward algorithm)， 這個演算法其實是前向和反向演算法的總稱，在上述式子上 p ( z k , x 1 : k ) p(z_k,x_{1:k}) p(zk?,x1:k?)就是前向演算法， p ( x k + 1 : n ∣ z k ) p(x_{k+1:n}|z_k) p(xk+1:n?∣zk?)就是反向演算法，

1.6 總結

有向圖和無向圖之間最明顯的區別就是有向圖中每個變數的相互依賴關系是已知或者可觀測的，所以有向圖模型可以使用所有變數的聯合概率分布來表示，也就是可以使用概率拼接，但是無向圖中因為無法使用概率來進行拼接，我們將一個無向圖分成多個最大團，來研究團中元素的依賴程度，

馬爾可夫模型是一個典型的有向圖模型，定義它的三個引數是，初始概率，發射概率，和狀態轉移概率，它收到馬爾可夫鏈的約束，對于馬爾可夫模型問題的求解方式，可以發現很不管是推斷問題還是引數估計問題，都用到了動態規劃演算法的思想，forward演算法本身也用到了動態規劃演算法的思想，