如果假定我們可以得到我們需要采樣樣本的平穩分布所對應的馬爾科夫鏈狀態轉移矩陣，那么我們就可以用馬爾科夫鏈采樣得到我們需要的樣本集，進而進行蒙特卡羅模擬。但是一個重要的問題是，隨意給定一個平穩分布?π?,如何得到它所對應的馬爾科夫鏈狀態轉移矩陣?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算法流程

總結

以上是生活随笔為你收集整理的算法学习系列（MCMC）：MCMC采样的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。