算法學習系列（MCMC）：MCMC採樣

如果假定我們可以得到我們需要採樣樣本的平穩分佈所對應的馬爾科夫鏈狀態轉移矩陣，那麼我們就可以用馬爾科夫鏈採樣得到我們需要的樣本集，進而進行蒙特卡羅模擬。但是一個重要的問題是，隨意給定一個平穩分佈 π ,如何得到它所對應的馬爾科夫鏈狀態轉移矩陣 P 呢？這是個大問題。我們繞了一圈似乎還是沒有解決任意概率分佈採樣樣本集的問題。

概率圖模型中最常用的採樣技術就是馬爾可夫鏈蒙特卡洛方法（MCMC）。

MCMC 一般算法

算法基本思想

先設法構造一條馬爾可夫鏈，使其收斂至平穩分佈恰好爲 ，然後通過這條馬爾可夫鏈然後產生符合 分佈的樣本。最後通過這些樣本來進行估計。

MCMC採樣算法

由於一般情況下，目標平穩分佈π(x)π(x)和某一個馬爾科夫鏈狀態轉移矩陣QQ不滿足細緻平穩條件，即

我們可以對上式做一個改造，使細緻平穩條件成立。方法是引入一個 α( i , j ) ，使上式可以取等號，即：

什麼樣的 α( i , j ) 可以使等式成立呢？其實很簡單，只要滿足下兩式即可：

這樣，我們就得到了我們的分佈 π(x) 對應的馬爾科夫鏈狀態轉移矩陣 P，滿足：

α( i , j ) 我們有一般稱之爲接受率。(取值在[0,1]之間，可以理解爲一個概率值。)

也就是說，我們的目標矩陣 P 可以通過任意一個馬爾科夫鏈狀態轉移矩陣 Q 乘以 α( i , j ) 得到。α( i , j )我們一般稱之爲接受率。即目標矩陣 P 可以通過任意一個馬爾科夫鏈狀態轉移矩陣 Q 以一定的接受率獲得。

這個很像我們在之前講到的接受-拒絕採樣，那裏是以一個常用分佈通過一定的接受-拒絕概率得到一個非常見分佈，這裏是以一個常見的馬爾科夫鏈狀態轉移矩陣 Q 通過一定的接受-拒絕概率得到目標轉移矩陣 P ,兩者的解決問題思路是類似的。

現在我們來總結下MCMC的採樣過程：

上面這個過程基本上就是MCMC採樣的完整採樣理論了，這個算法存在一些問題，後面會提及

在介紹Metropolis- Hastings算法之前首先介紹以下Metropolis採樣算法。

Metropolis採樣算法

Metropolis算法的原理

從一個已知的形式較爲簡單的分佈中採樣，並以一定的概率接受這個樣本作爲目標分佈的近似樣本。

假設需要從目標概率密度函數 p(θ) 中進行採樣，同時，θ滿足 −∞<θ<∞ 。Metropolis採樣算法根據馬爾可夫鏈去生成一個序列：

                                                    

其中，表示的是馬爾可夫鏈在第 t代時的狀態。

在Metropolis採樣算法的過程中，首先初始化狀態值  ，然後利用一個已知的分佈 生成一個新的候選狀態 ，隨後根據一定的概率 a 選擇接受這個新值，或者拒絕這個新值，在Metropolis採樣算法中，概率爲：

                                 
這樣的過程一直持續到採樣過程的收斂，當收斂以後，樣本即爲目標分佈 p(θ) 中的樣本。

Metropolis算法的流程

基於以上的分析，可以總結出如下的Metropolis採樣算法的流程：

Metropolis算法的解釋

要證明Metropolis採樣算法的正確性，最重要的是要證明構造的馬爾可夫過程滿足如上的細緻平穩條件，即：

                                                               

對於上面所述的過程，分佈爲，從狀態 i 轉移到狀態 j 的轉移概率爲：

                                                             

對於選擇該已知的分佈，在Metropolis採樣算法中，要求該已知的分佈必須是對稱的，即 ，即

 

                                                  

常用的符合對稱的分佈主要有：正態分佈，柯西分佈以及均勻分佈等。

接下來，需要證明在Metropolis採樣算法中構造的馬爾可夫鏈滿足細緻平穩條件：

                                             

因此，通過以上的方法構造出來的馬爾可夫鏈是滿足細緻平穩條件的。

Metropolis算法要求已知的條件分佈必須是對稱的，而一般的MCMC採樣算法問題存在於上面第三步的 c 步驟。由於   可能非常的小，比如0.1，導致我們大部分的採樣值都被拒絕轉移，採樣效率很低。使得馬氏鏈遍歷所有的狀態空間要花費太長的時間，收斂到平穩分佈 p(x) 的速度太慢這時，就輪到我們的M-H採樣出場了。

Metropolis - Hastings算法

因此我們的接受率可以做如下改進，即：

 

很容易驗證：

MH算法流程

                                

Gibbs採樣

MH算法不僅適用於一維的情況，也適用於高維的情況，但是對於高維的情況存在問題，一是接受率的存在，計算量大。並且由於接受率的原因導致算法收斂時間變長。二是有些高維數據，特徵的條件概率分佈好求，但是特徵的聯合分佈不好求。

細緻平穩條件（Gibbs採樣原理）

 

在M-H採樣中我們通過引入接受率使細緻平穩條件滿足。現在我們換一個思路。

Gibbs算法流程