MCMC採樣算法

完整的MCMC採樣算法已經有很多博主發佈了，這裏就不再重複了。主要想分享一下在看其他博主寫的MCMC採樣算法時，不太理解的地方。

MCMC採樣關鍵問題在於如何構建轉移矩陣，使得平穩分佈恰好是p(x)。主要使用細緻平穩條件。

細緻平穩條件

如果非週期馬氏鏈的轉移矩陣P和分佈π(x)滿足：
π(i)Pij=π(j)Pji for all i,j
則π(x)是馬爾可夫鏈的平穩分佈，上式稱爲細緻平穩條件。

馬氏鏈的一個例子：
社會學家經常把人按其經濟狀況分成3類：下層(lower-class)、中層(middle-class)、上層(upper-class)，我們用1,2,3 分別代表這三個階層。社會學家們發現決定一個人的收入階層的最重要的因素就是其父母的收入階層。如果一個人的收入屬於下層類別，那麼他的孩子屬於下層收入的概率是 0.65, 屬於中層收入的概率是 0.28, 屬於上層收入的概率是 0.07。事實上，從父代到子代，收入階層的變化的轉移概率如下

假設初始概率分佈爲π0=[0.21,0.68,0.11]，則我們可以計算前n代人的分佈狀況如下：

從第7代人開始，這個分佈開始穩定不變。

回到細緻平穩分佈，當達到馬氏鏈的平穩分佈的時候，π=(0.286，0.489，0.225)，由細緻平穩可知滿足π(i)Pij = π(j)Pji。
如： π(1)P12=π(2)P21—–>0.286*0.28 =0.08008
0.489*0.15 =0.07335 近似相等
所以當π(i)Pij=π(j)Pji時，π(x)是馬氏鏈的平穩分佈。

MCMC算法

假設我們已經有一個轉移矩陣Q(對應元素爲q(i,j)), 得到了如下的用於採樣概率分佈p(x)的算法。

讀Rickjin的LDA數學八卦的時候特別不理解，爲什麼α就是接受率。
先談論一個簡單的採樣，假設採樣擲一枚硬幣是正面還是反面，從均勻分佈中採樣u，當u>0.5時候接受採樣（正面），否則拒絕採樣。

下面說說我對MCMC算法的理解：
假設對一篇文章的4個主題分佈進行採樣：設置初始狀態X0=Topic1。
假設時刻t=1,從轉移矩陣Q中的q(x|T1)分佈採樣了T2。
對於隨機遊走，此時以概率p(T1)q(T2|T1)從Topic1轉移到Topic2，採樣T2，沒有接受率之說。
而此時我們需要採樣的是馬氏鏈細緻平穩分佈π(x)/p(x)的樣本，必須滿足π(i)Pij=π(j)Pji。爲了保證p(T1)q(T2|T1)=p(T2)q(T1|T2)，使得樣本來自p(x)概率分佈,只有當u小於p(T2)q(T1|T2)時，接受X1=Topic2。

MCMC理解（網上看到的另一種解釋）

Gibbs sampling

• 什麼是Gibbs Sampling Gibbs Sampling是MCMC算法中的一種，用來構造多變量概率分佈的隨機樣本，比如構造兩個或多個變量的聯合分佈，求積分，期望。 • 爲什麼需要Gibbs Sampling 積分、期望、聯合分佈計算，通常情況下當前面三個問題是NP問題時才需要Gibbs Sampling，否則直接計算就可以了。補充一句Gibbs Sampling只是（也只能）到近似解。 • 應用場景 a、積分，期望，樣本概率很難計算出來；b、條件概率很容易計算。具體例子：受限玻爾茲曼機（RBM）的訓練，貝葉斯網絡，LDA都用到Gibbs Sampling。 • 爲什麼Gibbs Sampling有效 當Gibbs Sapling算法執行多次之後，產生的樣本服從真實樣本的分佈，即相當於直接從聯合分佈中採樣。