MCMC采樣和M-H采樣

在MCMC之馬爾可夫

解決平穩分布π所對應的馬爾可夫鍊狀态轉移矩陣P之前，我們先看一下馬爾可夫鍊的細緻平穩條件。其定義為：如果非周期馬爾可夫鍊的狀态轉移矩陣P和機率分布π(x)對于所有的i,j滿足下列方程，則機率分布π(x)是狀态轉移矩陣P的平穩分布。

證明如下，由細緻平穩條件有

将上式用矩陣表示為

上式滿足馬爾可夫鍊的收斂性質，也就是說，隻要我們找到可以使機率分布π(x)滿足細緻平穩分布的矩陣P即可。不過僅僅從細緻平穩條件還是很難找到合适的矩陣P，比如我們的目标平穩分布使π(x)，随機找一個馬爾可夫鍊狀态轉移矩陣Q，他是很難滿足細緻平穩條件的，即

那麼有什麼辦法可以使這個等式相等呢？

由于一般情況下，目标平穩分布π(x)和某一馬爾可夫鍊狀态轉移矩陣Q不滿足細緻平穩條件，即

我們對上式進行一些變換，使細緻平穩條件成立。方法是引入一個α(i,j)，使得上式等式能夠成立，即

問題是什麼樣的α可以使上式成立？其實很簡單，隻要滿足

這樣，我們便找到使分布π(x)對應的馬爾可夫鍊狀态轉移矩陣P，滿足

從上面可以得到，目标矩陣P可以通過任意一個馬爾可夫鍊狀态轉移矩陣Q乘以α(i,j)得到。α(i,j)我們一般稱之為接受率，取值在[0,1]之間，可以了解為一個機率值。也就是說，目标矩陣P可以通過任意一個馬爾可夫鍊狀态轉移矩陣Q以一定的接受率得到。

其實很像我們在MCMC之蒙特卡羅方法中提到的接受-拒絕采樣，那裡是以常用分布通過一定的接受-拒絕機率得到一個非常見分布。這裡是通過常見的馬爾可夫鍊狀态轉移矩陣Q通過一定的接受-拒絕機率得到目标轉移矩陣P，兩者解決問題的思路是相同的。下面，我們來總結下MCMC的采樣過程

上述過程便是MCMC采樣理論，但很難在實際應用，為什麼呢? 因為α可能非常小，比如0.1，導緻大部分采樣值都被拒絕轉移，采樣效率很低。可能我們采樣可上百萬次，馬爾科夫鍊還沒有收斂。實際應用中，我們可以通過M-H采樣方法進行采樣。

M-H采樣解決了MCMC采樣接受率過低的問題，我們首先回到MCMC采樣的細緻平穩條件

采樣效率過低的原因是α(i,j)太小，比如0.1，α(j,i)為0.2，即

如果兩邊同時擴大5倍，細緻平穩條件仍然是滿足的，即

這樣我們可以對接受率做如下改進，即

通過上述的轉換，我們便可在實際應用中使用M-H算法進行采樣，M-H采樣算法過程如下所示

很多時候，我們選擇的馬爾科夫鍊狀态轉移矩陣Q如果是對稱的，即滿足Q(i,j)=Q(j,i)，這時我們的接受率可以進一步簡化為

M-H采樣解決了使用蒙特卡羅方法需要的任意機率分布樣本集的問題，是以在實際生産環境中得到廣泛應用。但在大資料情況下，M-H面臨如下問題

資料特征非常多：因為M-H采樣由于接受率的存在，在高維計算時需要很長的計算時間，算法效率很低。同時α(i,j)一般小于1，有時候辛苦計算出來的結果卻被拒絕，能不能做到不拒絕轉移呢？
特征次元比較大：很多時候我們很難求出目标的各特征次元聯合分布，但是可以友善求出各個特征之間的條件機率分布。這時能不能隻用各次元之間的條件機率分布去友善的采樣呢?

你看到的這篇文章來自于公衆号「謂之小一」，歡迎關注我閱讀更多文章