MCMC詳解1——蒙特卡洛方法

MCMC是一種随機采樣方法，用來處理一些複雜運算的近似求解。在HMM、LDA等模型中都有重要應用。

下一篇 MCMC詳解2——MCMC采樣、M-H采樣、Gibbs采樣

目錄

• 1，蒙特卡洛方法
• 2，拒絕-接受采樣

MCMC（ Markov Chain Monte Carlo）馬爾科夫蒙特卡洛方法，從名稱上包含蒙特卡洛方法與馬爾科夫鍊兩部分，本文先總結蒙特卡洛方法。

1，蒙特卡洛方法

最早的蒙特卡洛方法都是為了求解一些不太好求解的求和或者積分問題。

θ = ∫ a b f ( x ) d x \theta=\int_{a}^{b}f(x)dx θ=∫ab​f(x)dx

以上積分是不是很像是連續型資料的機率分布函數？我們這裡将他看做一個普通的積分就可以了，如果它真的是，此時 f ( x ) f(x) f(x)就是其機率密度函數，那麼 θ \theta θ應該為1，不過這裡我們将其視為一個用來求解的複雜函數即可。

如果我們很難求出f(x)的原函數，那麼這個積分就很難求得。但是我們可以用蒙特卡洛方法求近似值，公式如下:

θ = ∫ a b f ( x ) d x = ∫ a b f ( x ) p ( x ) p ( x ) d x ≈ 1 n ∑ i = 0 n − 1 f ( x i ) p ( x i ) \theta=\int_{a}^{b}f(x)dx=\int_{a}^{b}\frac{f(x)}{p(x)}p(x)dx\approx\frac{1}{n}\sum_{i=0}^{n-1}\frac{f(x_i)}{p(x_i)} θ=∫ab​f(x)dx=∫ab​p(x)f(x)​p(x)dx≈n1​i=0∑n−1​p(xi​)f(xi​)​

突然看這個公式會有點懵，我們一步步分析。

1）如果用 x 0 x_0 x0​表示 f ( x ) f(x) f(x)上的所有值，來近似表示，那麼積分結果為：

( b − a ) f ( x 0 ) (b-a)f(x_0) (b−a)f(x0​)

2）方法1）顯然過于粗糙，我們從區間[a,b]中選取n個樣本點 x i x_i xi​，用他們的均值來表示 f ( x ) f(x) f(x)的值，那麼積分結果為：

b − a n ∑ i = 0 n − 1 f ( x i ) \frac{b-a}{n}\sum_{i=0}^{n-1}f(x_i) nb−a​i=0∑n−1​f(xi​)

3）以上方法都有一個假設：x在區間[a,b]上是均勻分布，這顯然是不合理的。f(x)比較複雜，我們假設x在區間[a,b]上符合一個機率密度函數p(x),可以得到如下近似計算公式。

θ = ∫ a b f ( x ) d x = ∫ a b f ( x ) p ( x ) p ( x ) d x ≈ 1 n ∑ i = 0 n − 1 f ( x i ) p ( x i ) \theta=\int_{a}^{b}f(x)dx=\int_{a}^{b}\frac{f(x)}{p(x)}p(x)dx\approx\frac{1}{n}\sum_{i=0}^{n-1}\frac{f(x_i)}{p(x_i)} θ=∫ab​f(x)dx=∫ab​p(x)f(x)​p(x)dx≈n1​i=0∑n−1​p(xi​)f(xi​)​

注：

1）我們假設 p ( x ) p(x) p(x)的存在，完全就是為了得到近似積分。這裡是近似值，如果 p ( x ) p(x) p(x)是均勻分布，就變成了方法2），當然如何 f ( x ) f(x) f(x)真的是均勻分布的，結果仍然為1，等式成立。

2）我們沒法直接求 f ( x ) f(x) f(x)的積分，隻能通過假設x的機率密度函數符合 p ( x ) p(x) p(x)的情況來計算。這裡已經把近似機率分布 p ( x ) p(x) p(x)放到了分母的位置，考慮了機率密度分布p(x)的影響，那麼積分的式子就是 f ( x i ) p ( x i ) \frac{f(x_i)}{p(x_i)} p(xi​)f(xi​)​基于 p ( x ) p(x) p(x)的期望，那麼，我們可以用均值近似，然後轉化成采集多個符合 p ( x ) p(x) p(x)的樣本，求相應均值的方案。

是以，隻要我們知道了機率密度函數p(x)，那麼就能得到積分的近似結果（一般 p ( x ) p(x) p(x)是可以假設符合某種分布的）。

結論：蒙特卡洛方法将連續積分問題轉化為了基于機率密度函數多次采樣求期望的問題。

顯然這個時候，求解問題的關鍵就是獲得符合機率分布P的樣本集，那麼如何從機率密度函數 p ( x ) p(x) p(x)上進行采樣，得到n個樣本呢？

對于常見的均勻分布uniform(0,1)是非常容易采樣的，一般通過線性同餘發生器可以很友善的生成(0,1)之間的僞随機數樣本。其他常見的機率分布都可以通過均勻分布的樣本轉換得到。但是很多時候我們的機率分布并不是常見的分布，如何采樣呢？

2，拒絕-接受采樣

步驟：

1）首先設定一個可采樣的分布 q ( x ) q(x) q(x)（比如高斯分布），以及一個常量k，使得 p ( x ) p(x) p(x)總在 k q ( x ) kq(x) kq(x)的下方。

2）采樣得到 q ( x ) q(x) q(x)的一個樣本，然後從均勻分布 ( 0 , k q ( z 0 ) ) (0,kq(z0)) (0,kq(z0))中采樣，得到一個值u，如果u落在了灰色區域，則拒接這次抽樣，否則接受這個樣本 z 0 z_0 z0​，重複以上過程，得到n個樣本，然後利用蒙特卡洛方法求解.

注：

可能有些同學不太了解為什麼從均勻分布 ( 0 , k q ( z 0 ) ) (0,kq(z_0)) (0,kq(z0​))中采樣，落在灰色區間就拒絕，否則就接受呢？其實這是機率密度函數的概念問題，p和q都是機率密度函數，其下的面積是機率，一個區域的面積可以表示機率分布，從均勻分布 ( 0 , k q ( z 0 ) ) (0,kq(z_0)) (0,kq(z0​))中采樣，其實就是在一定程度上表示該樣本點 z 0 z_0 z0​存在p内的機率大小，雖然一個點對于連續型資料分布來講沒有意義，但是在這條線段上的機率大小是可以表示的。

通過拒接—接受采樣，可以解決 p ( x ) p(x) p(x)分布不是常見分布的時候，獲得樣本集，用蒙特卡洛方法求和的目的。但是很多時候該方法不能滿足我們的需求得到:

1）一些高維的資料分布，找一個合适的 q ( x ) q(x) q(x)和 k k k比較困難。

2）對于二維分布我們隻能得到其條件分布，卻很難得到二維分布的一般形式。比如 q ( x , y ) q(x,y) q(x,y)，拒絕-接受采樣隻能改變一個緯度得到條件機率，而馬爾科夫鍊可以有效的找到複雜機率分布的采樣樣本集。

（本文參考了劉建平老師的部落格，加入了一些自己的一些了解，有興趣的可以去拜讀原文）

下一篇 MCMC詳解2——MCMC采樣、M-H采樣、Gibbs采樣