对采样的理解
什么是采样
我们知道了一个变数的分布，要生成一批样本服从这个分布，这个过程就叫采样。听起来好像很简单，对一些简单的分布函数确实如此，比如，均匀分布、正太分布，但只要分布函数稍微复杂一点，采样这个事情就没那么简单了。
为什么要采样
在讲具体的采样方法之前，有必要弄清楚采样的目的。为什么要采样呢？有人可能会这样想，样本一般是用来估计分布参数的，现在我都知道分布函数了，还采样干嘛呢？其实采样不只是可以用来估计分布参数，还有其他用途，比如说用来估计分布的期望、高阶动量等。其实在机器学习中，采样的主要用途是用来估计某个函数在某个分布上的期望 ，比如在EM演算法中，计算E步的时候，已知隐变数的分布，用采样的方法估计对数似然的期望。
基本采样方法
首先，最基本的方法是变换法，大概思想是这样的，比如我们要对分布a采样，但是只有分布b的采样器，我们可以通过对b采样的结果进行一些变换，使变换后的结果服从分布a，举个例子，对0到1的均匀分布的结果进行tan函数变换得到的结果就服从柯西分布，大家可以试想下怎么变换能得到指数分布和高斯分布。
对于简单的标准分布，可以用变换法，对于复杂分布就搞不定了。这个时候就有了拒绝采样（Rejection Sampling）和自适应拒绝采样（Adaptive Rejection Sampling），大概过程如下图所示，假设我们要对分布p采样，分布p比较复杂，可以先找一个简单的分布q，然后对q乘上一个系数k，保证对于任意z都有 ，这样可以保证p分布围成的区域一定在kq的下面，然后就可以在kq围成的区域内采样(z, h)(分别是横坐标和纵坐标)，如果落在p围成的区域中就得到一个样本点z，否则丢弃这个样本。
这类方法的问题在于，如果建议分布q和实际分布p差别比较大的时候，拒绝率会比较高，导致采样效率低下，而且在高维的情况下这种问题还会被放大，因为维度越高，球的体积会越来越向球壳集中，所以即使建议分布和实际分布很接近，拒绝率还是会非常高。
为了解决拒绝率高的问题，就有了重要性采样（Importance Sampling），这种方法直接考虑求期望 ，在需要拒绝的时候，打一个折扣然后再算到期望里面，感觉很巧妙。。但这种方法实际是绕开了问题，如果不只是需要期望还需要样本呢？这个时候就有了（Sampling-importance-resampleing），也不知道怎么翻译好了。。其实和拒绝采样比较类似，只不过是拒绝采样是当场拒绝，这个是先留做备胎，最后按重要性权重再采样一次。。。
前面这些其实都是铺垫，接著该大招出场了，大招就是我们的MCMC及其变种Gibbs Sampling。
马尔科夫链蒙特卡洛采样（Markov Chain Monte Carlo）
要理解MCMC，有几个关键要点：
- 什么是随机过程
- 随机变数的变化过程就叫随机过程。。相当于给随机变数加了一个时间的维度。
- 什么是马氏链
- x1, x2, x3, ..., xn, ...是一个随机过程，如果第n时刻的变数分布只和n-1时刻的状态有关，那么这个随机过程就叫马尔科夫随机过程，简称马氏链。
- 什么是转移矩阵
- 描述状态的转移过程，
，如果马氏链的转移矩阵和时间无关，就叫齐次马氏链
- 什么是细致平稳条件
- 对于齐次马氏链，如果转移矩阵满足一定的条件，就可以保证每个时刻的状态服从相同的分布，并且最终可以收敛到平稳分布。细致平稳条件就是能保证收敛到平稳分布的一个充分条件
MCMC的基本思路是构造一个马氏链，并且凑出一个满足细致平稳条件的转移矩阵，从而保证最后能收敛到我们需要采样的分布。MCMC的巧妙之处就在于转移矩阵的构造 ，对于任意的
都可以满足细致平稳条件。
吉布斯采样（Gibbs Sampling）
吉布斯采样是MCMC的一个特例，吉布斯采样的牛逼之处在于只需要知道条件概率的分布，便可以通过采样得到联合概率分布的样本，LDA的求解可以说是吉布斯采样的一个绝妙应用例子，通过采样的方法就完成了整个模型的求解，确实很巧妙。另一个很好的例子是玻尔兹曼机的训练，哪天有时间把这两个例子展开讲讲。
参考资料
Bishop - Pattern Recognition And Machine Learning
推荐阅读：
