基本任务：给定一个概率分布，然后根据概率分布来生成对应的样本
1. 马氏链和平稳分布
马氏链：下一个状态只与当前状态有关
马氏链定理：如果一个非周期的马氏链具有转移矩阵P，并且它的任何两个状态是联通的，那么�状态的稳态是存在的。
2. 接受-拒绝抽样
使用一个比较常见的简单分布来近似比较复杂的分布，下图所示：
样本采样过程如下：
1.首先设定一个方便抽样的简单分布q(x)，以及一个常量k，使得要得到的分布p(x)总在k*q(x)的上方
1. x轴方向，从比较简单的分布q(x)中抽样得到a
2. y轴方向，从均匀分布(0，k*q(x))抽样得到u
3. 根据抽样得到的结果是否在灰色区域，决定是否接受这次抽样
2. MCMC(Markov Chain Monte Carlo)
这个方法是考虑了以上两点基础知识，马尔可夫稳态以及接受拒绝抽样的思想得到的。
首先，由马尔可夫稳态的性质，我们可以考虑，让马尔链的平稳分布pai恰好为我们的目标抽样函数p(x)。这样我们从任何一个初始状态出发沿着马氏链转移，当收敛的时候就能够从此得到目标函数的分布了。
在这个方法中的难点就在于，如何构造转移矩阵P，使得平稳分布正好是我们的目标函数。由于对于一般的转移矩阵：
因此，我们可以给这个不等式两边加上系数，使之满足细致平稳条件：
其中的alpha就是我们引入的接受率的概念：
一般的MCMC采样算法步骤如下：
1. 初始化马氏链的初始状态
2. 开始进行循环采样：根据上一个状态，根据设定好的转移矩阵，计算下一个拟状态；从均匀分布进行采样，得到u，然后比较u和alpha的大小，决定是否接受这次采样。
这个是比较一般的MCMC采样，然而根据这个接受率比较低，导致采样效率比较低，于是我们可以对alpha进行等比放大(提高接受率的同时有不会破坏细致平稳条件)：
这个就是常说的Metropolis-Hastings采样了。
3. Gibbs sampling
即使我们对alpha的进行了等比放大，在高维数据的情况下，上述算法的效率还是不够高，因此Gibbs sampling出现了，在这里，我们得到在数据的每个维度上，其实都满足细致平稳条件，因此，我们可以对每个维度进行Metropolis-Hastings抽样。
参考文献：
1. LDA数学八卦
2.http://www.cnblogs.com/xbinworld/p/4266146.html
网友评论