Hulu机器学习问题与解答系列 | 三十：常见的采样方法
今天所有上班or学习的姑娘们，都是真女神。节日快乐！
今天的内容是
【常见的采样方法】
场景描述
对于一个随机变量，我们通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，我们可以根据概率密度函数来计算该值对应的概率（密度）；反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。因此，从某种意义上来说，采样是概率密度函数的逆向应用。与根据概率密度函数计算样本点对应的概率值不同，采样过程（即根据概率分布来选取样本点）往往没有那么直接，通常需要依据待采样分布的具体特点来选择合适的采样策略 。 在“采样”章节的前两个小问题中，我们展示了采样的一个具体应用（不均衡样本集的处理），以及针对特定分布（高斯分布）而特别设计的采样方法；接下来，我们来关注一些通用的采样方法和采样策略。
问题描述
抛开那些针对特定分布而精心设计的采样方法外，说一些你所知道的通用采样方法或采样策略，简单描述它们的主要思想以及具体操作步骤。
背景知识：概率与统计、采样
解答与分析
在之前采样章节的推送中我们提到，几乎所有的采样方法都是以均匀分布的采样作为基本操作。均匀分布随机数一般用线性同余法来产生（伪随机数），这里不再赘述，我们假设已经可以生成 [0,1] 上的均匀分布随机数。
对于一些简单的分布，可以直接用基于均匀采样的方法来产生样本点（如有限离散分布可以用轮盘赌算法来采样）；然而，很多分布一般不好直接进行采样，此时可以考虑函数变换法。一般地，如果随机变量x和u存在变换关系u＝φ(x)，则它们的概率密度函数有如下关系：p(u)|φ'(x)|＝p(x)。因此，如果从目标分布p(x)中不好采样x，可以构造一个变换u＝φ(x)，使得从变换后的分布p(u)中采样u比较容易，这样可以通过先对u进行采样然后通过反函数x＝φ-1(u)来间接得到x。如果是高维空间的随机向量，则上述|φ'(x)|对应Jacobian行列式。
特别地，在上述函数变换法中，如果变换关系φ(·)是累积分布函数的话，则得到所谓的逆变换采样法 (Inverse Transform Sampling)：假设待采样的目标分布的概率密度函数为p(x)，它的累积分布函数为
按如下过程进行采样：
根据函数变换法，上述采样过程得到的xi服从p(x)分布。图1是逆变换采样法的示意图。
图1 逆变换采样法示意图
如果待采样的目标分布的累积分布函数的逆函数无法求解或者不容易计算，则不适用于逆变换采样法。此时可以构造一个容易采样的参考分布，先对参考分布进行采样，然后对得到的样本进行一定的后处理操作，使得最终的样本服从目标分布。常见的拒绝采样、重要性采样，就属于这类采样算法，下面分别简单介绍它们的具体采样过程。
拒绝采样 (Rejection sampling)，又叫接受/拒绝采样 (Accept-Reject Sampling)。对于目标分布p(x)，选取一个容易采样的参考分布q(x)，使得p(x)≤M·q(x)，则可以按如下过程进行采样：
通过简单的推导，可以知道最终得到的xi服从目标分布p(x)。如图2(A)所示，拒绝采样法的关键是为目标分布p(x)选取一个合适的包络函数M·q(x)：包络函数越紧，每次采样时样本被接受的概率越大，采样效率越高。在实际应用中，有时候寻找解析形式的q(x)比较困难，因此延伸出了自适应拒绝采样 (Adaptive Rejection Sampling)，在目标分布是对数凹函数时，用分段线性函数来覆盖目标分布的对数㏑p(x)，如图2(B)所示，这里不再细述。
图2 (A) 拒绝采样示意图；(B) 自适应拒绝采样法
重要性采样 (Importance Sampling)，其实是用于计算函数f(x)在目标分布p(x)上的积分，即
这里w(x)可以看成是样本x的重要性权重。由此，可以先从参考q(x)分布中抽取N个样本{xi}，然后利用如下公式来估计I[f]：
如果不需要计算函数积分，只想对目标分布p(x)进行采样，则可以用重要性重采样 (Sampling-Importance Re-sampling, SIR)，即在从参考分布q(x)抽取N个样本{xi}后，按照它们对应的重要性权重{w(xi)}对这些样本进行重新采样（这是一个简单的针对有限离散分布的采样），最终得到的样本服从目标分布p(x)。
图3 重要性采样示意图
在实际应用中，如果是高维空间的随机向量，拒绝采样/重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔科夫蒙特卡洛采样法 (Markov Chain Monte Carlo, MCMC) 。MCMC基本思想是：针对待采样的目标分布，构造一个马尔科夫链，使得该马尔科夫链是收敛的，并且最终的稳态分布就是我们要采样的目标分布。实际操作中，核心点是构造合适的马尔科夫链，不同的马尔科夫链对应着不同的MCMC算法，常见的有Metropolis-Hastings算法和Gibbs算法。在后续的微信推送中，我们会有专门针对MCMC的问答小节，这里只简单介绍Metropolis-Hastings算法和Gibbs算法的具体操作步骤。
Metropolis-Hastings (MH) 采样：对于目标分布p(x)，首先选择一个容易采样的参考条件分布q(x*|x)，并令
然后根据如下过程进行采样：
可以证明，上述过程得到的样本序列{…, x(t-1), x(t), …}最终会收敛到目标分布p(x)。
Gibbs采样：Gibbs采样的核心思想是每次只对样本的一个维度进行采样和更新。对于目标分布p(x)，其中x＝(x1, x2,…, xd)是高维向量，按如下过程进行采样：
同样可以证明，上述过程得到的样本序列{…, x(t-1), x(t), …}会收敛到目标分布p(x)。另外，步骤2中对样本每个维度的抽样和更新操作，不是必须按下标顺序进行的，可以是随机顺序 。
扩展与总结
上述解答中我们只是列举了几个最常用的采样算法，简单介绍了它们的具体操作。在实际面试时，可以让面试者选择其最熟悉的某个采样算法来回答，展开来问一下该算法的理论证明、优缺点，以及相关扩展等。
下一题预告
【最大熵马尔科夫模型和条件随机场】
场景描述
序列标注（sequence labeling）是对一个序列的每个元素给出标签的机器学习任务。我们前面已经介绍过隐马尔科夫模型等序列标注模型，隐马尔科夫模型对标注（label）进行了独立性假设，而实际上，在序列标注问题中，隐状态（标注）不仅和单个观测状态相关，还和观察序列的长度、上下文等相关。最大熵马尔科夫模型和条件随机场可以认为是马尔科夫模型的改进，去除了独立性假设，获得了更强的表达能力。
问题描述
最大熵马尔科夫模型（Maximum Entropy Markov Model，MEMM）用于序列标注（Sequence Labeling）任务，为什么会产生标注偏置问题（Label Bias Problem）？相比于最大熵马尔科夫模型，条件随机场（Conditional Random Field，CRF）为什么能更好地解决这个问题？
欢迎留言提问或探讨
关注“Hulu”微信公众号
点击菜单栏“机器学习”获得更多系列文章