作為一種隨機(jī)采樣方法，馬爾科夫鏈蒙特卡羅（Markov Chain Monte Carlo，以下簡稱MCMC）在機(jī)器學(xué)習(xí),深度學(xué)習(xí)以及自然語言處理等領(lǐng)域都有廣泛的應(yīng)用逻恐，是很多復(fù)雜算法求解的基礎(chǔ)嫩实。比如我們前面講到的分解機(jī)(Factorization Machines)推薦算法，還有前面講到的受限玻爾茲曼機(jī)（RBM）原理總結(jié)玛追，都用到了MCMC來做一些復(fù)雜運(yùn)算的近似求解。下面我們就對MCMC的原理做一個(gè)總結(jié)闲延。
1. MCMC概述
從名字我們可以看出痊剖，MCMC由兩個(gè)MC組成，即蒙特卡羅方法（Monte Carlo Simulation垒玲，簡稱MC）和馬爾科夫鏈（Markov Chain 陆馁，也簡稱MC）。要弄懂MCMC的原理我們首先得搞清楚蒙特卡羅方法和馬爾科夫鏈的原理合愈。我們將用三篇來完整學(xué)習(xí)MCMC叮贩。在本篇，我們關(guān)注于蒙特卡羅方法佛析。
2. 蒙特卡羅方法引入
蒙特卡羅原來是一個(gè)賭場的名稱益老，用它作為名字大概是因?yàn)槊商乜_方法是一種隨機(jī)模擬的方法，這很像賭博場里面的扔骰子的過程寸莫。最早的蒙特卡羅方法都是為了求解一些不太好求解的求和或者積分問題捺萌。比如積分：
如果我們很難求解出f(x)的原函數(shù)，那么這個(gè)積分比較難求解膘茎。當(dāng)然我們可以通過蒙特卡羅方法來模擬求解近似值桃纯。如何模擬呢？假設(shè)我們函數(shù)圖像如下圖:
則一個(gè)簡單的近似求解方法是在[a,b]之間隨機(jī)的采樣一個(gè)點(diǎn)披坏。比如x0,然后用f(x0)代表在[a,b]區(qū)間上所有的f(x)的值态坦。那么上面的定積分的近似求解為:
當(dāng)然，用一個(gè)值代表[a,b]區(qū)間上所有的f(x)的值棒拂，這個(gè)假設(shè)太粗糙驮配。那么我們可以采樣[a,b]區(qū)間的n個(gè)值：x0,x1,...xn?1,用它們的均值來代表[a,b]區(qū)間上所有的f(x)的值。這樣我們上面的定積分的近似求解為:
雖然上面的方法可以一定程度上求解出近似的解着茸，但是它隱含了一個(gè)假定壮锻，即x在[a,b]之間是均勻分布的，而絕大部分情況涮阔，x在[a,b]之間不是均勻分布的猜绣。如果我們用上面的方法，則模擬求出的結(jié)果很可能和真實(shí)值相差甚遠(yuǎn)敬特。
怎么解決這個(gè)問題呢掰邢？ 如果我們可以得到x在[a,b]的概率分布函數(shù)p(x)牺陶，那么我們的定積分求和可以這樣進(jìn)行：
上式最右邊的這個(gè)形式就是蒙特卡羅方法的一般形式。當(dāng)然這里是連續(xù)函數(shù)形式的蒙特卡羅方法辣之，但是在離散時(shí)一樣成立掰伸。
可以看出，最上面我們假設(shè)x在[a,b]之間是均勻分布的時(shí)候怀估，p(xi)=1/(b?a)p(xi)=1/(b?a)狮鸭，帶入我們有概率分布的蒙特卡羅積分的上式，可以得到
也就是說多搀，我們最上面的均勻分布也可以作為一般概率分布函數(shù)p(x)在均勻分布時(shí)候的特例歧蕉。那么我們現(xiàn)在的問題轉(zhuǎn)到了如何求出x的分布p(x)的若干和樣本上來。
3. 概率分布采樣
上一節(jié)我們講到蒙特卡羅方法的關(guān)鍵是得到x的概率分布康铭。如果求出了x的概率分布惯退，我們可以基于概率分布去采樣基于這個(gè)概率分布的n個(gè)x的樣本集，帶入蒙特卡羅求和的式子即可求解从藤。但是還有一個(gè)關(guān)鍵的問題需要解決催跪，即如何基于概率分布去采樣基于這個(gè)概率分布的n個(gè)x的樣本集。
對于常見的均勻分布uniform(0,1)是非常容易采樣樣本的夷野，一般通過線性同余發(fā)生器可以很方便的生成(0,1)之間的偽隨機(jī)數(shù)樣本叠荠。而其他常見的概率分布，無論是離散的分布還是連續(xù)的分布扫责，它們的樣本都可以通過uniform(0,1)的樣本轉(zhuǎn)換而得。比如二維正態(tài)分布的樣本(Z1,Z2)可以通過通過獨(dú)立采樣得到的uniform(0,1)樣本對(X1,X2)通過如下的式子轉(zhuǎn)換而得：
其他一些常見的連續(xù)分布逃呼，比如t分布鳖孤，F(xiàn)分布，Beta分布抡笼，Gamma分布等苏揣，都可以通過類似的方式從uniform(0,1)得到的采樣樣本轉(zhuǎn)化得到。在python的numpy推姻，scikit-learn等類庫中平匈，都有生成這些常用分布樣本的函數(shù)可以使用。
不過很多時(shí)候藏古，我們的xx的概率分布不是常見的分布增炭，這意味著我們沒法方便的得到這些非常見的概率分布的樣本集。那這個(gè)問題怎么解決呢拧晕？
4. 接受-拒絕采樣
對于概率分布不是常見的分布隙姿，一個(gè)可行的辦法是采用接受-拒絕采樣來得到該分布的樣本。既然 p(x)太復(fù)雜在程序中沒法直接采樣厂捞，那么我設(shè)定一個(gè)程序可采樣的分布 q(x) 比如高斯分布输玷，然后按照一定的方法拒絕某些樣本队丝，以達(dá)到接近 p(x) 分布的目的，其中q(x)叫做 proposal distribution欲鹏。
具體采用過程如下机久，設(shè)定一個(gè)方便采樣的常用概率分布函數(shù) q(x)，以及一個(gè)常量 k赔嚎，使得 p(x) 總在 kq(x) 的下方膘盖。如上圖。
首先尽狠，采樣得到q(x) 的一個(gè)樣本z0衔憨，采樣方法如第三節(jié)。然后袄膏，從均勻分布（0,kq(z0)) 中采樣得到一個(gè)值uu践图。如果uu落在了上圖中的灰色區(qū)域，則拒絕這次抽樣沉馆，否則接受這個(gè)樣本z0码党。重復(fù)以上過程得到n個(gè)接受的樣本z0,z1,...zn?1,則最后的蒙特卡羅方法求解結(jié)果為：
整個(gè)過程中，我們通過一系列的接受拒絕決策來達(dá)到用q(x)模擬p(x)概率分布的目的斥黑。
5. 蒙特卡羅方法小結(jié)
使用接受-拒絕采樣揖盘，我們可以解決一些概率分布不是常見的分布的時(shí)候，得到其采樣集并用蒙特卡羅方法求和的目的锌奴。但是接受-拒絕采樣也只能部分滿足我們的需求兽狭，在很多時(shí)候我們還是很難得到我們的概率分布的樣本集。比如：
- 對于一些二維分布p(x,y)鹿蜀，有時(shí)候我們只能得到條件分布p(x|y)和p(y|x)和,卻很難得到二維分布p(x,y)一般形式箕慧，這時(shí)我們無法用接受-拒絕采樣得到其樣本集。
- 對于一些高維的復(fù)雜非常見分布p(x1,x2,...,xn)茴恰，我們要找到一個(gè)合適的q(x)和k非常困難颠焦。
從上面可以看出，要想將蒙特卡羅方法作為一個(gè)通用的采樣模擬求和的方法往枣，必須解決如何方便得到各種復(fù)雜概率分布的對應(yīng)的采樣樣本集的問題伐庭。而我們下一篇要講到的馬爾科夫鏈就是幫助找到這些復(fù)雜概率分布的對應(yīng)的采樣樣本集的白衣騎士。下一篇我們來總結(jié)馬爾科夫鏈的原理分冈。
