基本任務：給定一個概率分布，然后根據概率分布來生成對應的樣本

1. 馬氏鏈和平穩(wěn)分布

馬氏鏈：下一個狀態(tài)只與當前狀態(tài)有關

馬氏鏈定理：如果一個非周期的馬氏鏈具有轉移矩陣P，并且它的任何兩個狀態(tài)是聯(lián)通的，那么?狀態(tài)的穩(wěn)態(tài)是存在的。

2. 接受-拒絕抽樣

使用一個比較常見的簡單分布來近似比較復雜的分布，下圖所示：

樣本采樣過程如下：

1.首先設定一個方便抽樣的簡單分布q(x)，以及一個常量k，使得要得到的分布p(x)總在k*q(x)的上方

1. x軸方向，從比較簡單的分布q(x)中抽樣得到a

2. y軸方向，從均勻分布(0，k*q(x))抽樣得到u

3. 根據抽樣得到的結果是否在灰色區(qū)域，決定是否接受這次抽樣

2. MCMC(Markov Chain Monte Carlo)

這個方法是考慮了以上兩點基礎知識，馬爾可夫穩(wěn)態(tài)以及接受拒絕抽樣的思想得到的。

首先，由馬爾可夫穩(wěn)態(tài)的性質，我們可以考慮，讓馬爾鏈的平穩(wěn)分布pai恰好為我們的目標抽樣函數p(x)。這樣我們從任何一個初始狀態(tài)出發(fā)沿著馬氏鏈轉移，當收斂的時候就能夠從此得到目標函數的分布了。

在這個方法中的難點就在于，如何構造轉移矩陣P，使得平穩(wěn)分布正好是我們的目標函數。由于對于一般的轉移矩陣：

因此，我們可以給這個不等式兩邊加上系數，使之滿足細致平穩(wěn)條件：

其中的alpha就是我們引入的接受率的概念：

一般的MCMC采樣算法步驟如下：

1. 初始化馬氏鏈的初始狀態(tài)

2. 開始進行循環(huán)采樣：根據上一個狀態(tài)，根據設定好的轉移矩陣，計算下一個擬狀態(tài)；從均勻分布進行采樣，得到u，然后比較u和alpha的大小，決定是否接受這次采樣。

這個是比較一般的MCMC采樣，然而根據這個接受率比較低，導致采樣效率比較低，于是我們可以對alpha進行等比放大(提高接受率的同時有不會破壞細致平穩(wěn)條件)：

這個就是常說的Metropolis-Hastings采樣了。

3. Gibbs sampling

即使我們對alpha的進行了等比放大，在高維數據的情況下，上述算法的效率還是不夠高，因此Gibbs sampling出現了，在這里，我們得到在數據的每個維度上，其實都滿足細致平穩(wěn)條件，因此，我們可以對每個維度進行Metropolis-Hastings抽樣。

參考文獻：

1. LDA數學八卦

2.http://www.cnblogs.com/xbinworld/p/4266146.html