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算法执行多次之后，产生的样本服从真实样本的分布，即相当于直接从联合分布中采样。