最近學習了機器學習中的馬爾科夫鏈蒙特卡洛(Markov Chain Monte Carlo, 簡稱MCMC) 相關的知識。

主要內容包括：

【1】蒙特卡洛原則，及其應用于采樣的必要性(已經發(fā)布在頭條)

【2】用于求解最大似然、近似推斷、期望問題的經典采樣算法：Metropolis-Hastings，Rejection，Importan，Metropolis和Gibbs算法。(本文屬于此部分)

【3】馬爾可夫鏈各個性質在蒙特卡洛采樣問題中的應用，包括同質性，平移不變性

—————【2】—————

上一篇【2.2】中詳細討論了EM優(yōu)化算法的推導和性質，EM算法通過不斷提高下界來逼近最大似然，其中E步求Q(z)=p(z|x,θ)，此時的θ是上一個M步已經固定的，求得此θ對應的最大下界的Q(z)，更新Q(z)。M步固定Q(z)，求得此時使得下界最大的θ，更新θ，如此迭代，直到收斂到局部最優(yōu)，得到最終估計值。

圖中L(q,θ)為下界，

M步中對L最大化求新θ，等價于求使得Q(θ，θold)最大的θ值。因此，如果此后驗概率p(z|x,θ)不能用分析式直接求得，可以用采樣的方法近似之。Q(θ，θold)寫成積分形式為 integral(p(z|x,θold)ln(p(z,x|θ)))dz。

這里，p(z|x,θ)成為我們采樣的目標函數，分析式未知。

【蒙特卡洛期望最大化算法Monte Carlo EM algorithm】

MCEM算法可以解決此問題，該算法從當前p(z|x,θold)中取L個樣本，根據積分的定義，Q(θ，θold)可由下式的樣本逼近：

MCEM算法，采樣逼近Q

使用此算法計算Q，完成EM算法的運算。

以上就是EM算法和蒙特卡洛采樣的關系。在上上篇文章討論重要性采樣算法時提到，其局限性在于假設分布和目標分布的差異不能太大。而MCMC采樣可以克服此問題。

【馬爾科夫鏈蒙特卡洛采樣算法Markov Chain Monte Carlo】

MCMC是使用馬爾科夫鏈生成樣本的方法，這個鏈設計為在最重要的區(qū)域花費最多的時間，樣本x的生成模擬從目標分布p(x)中產生的過程。

對比MCMC和重要性采樣(見上上篇文章【2采樣算法】)，MCMC采用可變的假設分布，即使用q(x'|x)而不是q(x)，x'是新的要采樣的狀態(tài)，x是前一個樣本。每產生一個樣本，原假設分布都會更新為一個新的假設分布。

MCMC算法不是一個特定的算法，而是使用上述思想的一類算法。

從最簡單的一個成員開始：

【Metropolis-Hasting算法】

1、初始化x0

2、循環(huán)N-1次：對i=0，1，一直到N-1

從【0，1】均勻分布中隨機采樣小數u；

從假設分布q(x'|xi)中隨機采樣x'；

判斷：若u< min {1, p_(x')*q(xi|x')/(p_(xi)*q(x'|xi))},x(i+1)=x'接受x'為新樣本，

否則x(i+1)=x(i)

例如，令每一個假設分布為均值等于x的高斯分布，【1蒙特卡洛原則】中已經討論過p_(x)也易得，因此可以很方便對p(x)采樣。

Metropolis Hasting采樣算法

如圖所示，每次取一個樣本修正一次假設分布，避免了重要性采樣算法的誤差。馬爾科夫鏈性質體現在假設分布的設置。

【廢棄樣本Burn-In period】

在MCMC算法中，初次取樣本時，可能取在上圖中的長尾之中，導致經過很多次迭代才把假設分布逐漸逼近到目標分布去，因此可能需要在采樣完成后將前面這些廢棄樣本刪除，例如前1000個樣本可能都是無效的。

本文討論了EM算法中應用蒙特卡洛采樣，以及一種馬爾可夫鏈蒙特卡洛采樣算法-Metropolis hasting算法，之后將繼續(xù)討論其他MCMC算法。

總結

以上是生活随笔為你收集整理的蒙特卡洛分析_随机模拟：马尔科夫链蒙特卡洛采样MCMC与EM算法「2.3」的全部內容，希望文章能夠幫你解決所遇到的問題。

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