百面机器学习（9）——采样
目录
马尔可夫蒙特卡洛采样法（蒙特卡洛法，马尔可夫链，吉布斯采样）
采样的作用（采样，机器学习，概率统计）
1. 举例说明采样在机器学习中的应用（2）
采样本质上是对随机现象的模拟，根据给定的概率分布，来模拟产生一个对应的随机事件。采样可以让人们对随机事件及其产生的过程有更直观的认识。
另一方面，采样得到的样本集也可以看作是一种非参数模型，即用较少量的样本点（经验分布）来近似总体分布，并刻画总体分布中的不确定性。 从这个角度来说，采样其实也是一种信息降维，可以起到简化问题的作用。
对当前的数据集进行重采样，可以充分利用己有数据集，拮据更多信息，如自助法和刀切法（ Jack knife ），通过对样本多次重采样来估计统计量的偏差、方差等。另外，利用重采样技术，可以在保持特定的信息下（目标信息不丢失），有意识地改变样本的分布，以更适应后续的模型训练和学习，例如利用重采样来处理分类模型的训练、样本不均衡问题。
此外，很多模型由于结构复杂、含有隐变量等原因，导致对应的求解公式比较复杂，没有显式解析解，难以进行精确求解或推理。 在这种情况下，可以利用采样方法进行随机模拟，从而对这些复杂模型进行近似求解或推理。这－般会转化为某些函数在特定分布下的积分或期望，或者是求某些随机变量或参数在给定数据下的后验分布等。
比如，在隐狄利克雷模型和深度玻尔兹量机（ Deep Boltzmann Machines, DBM ）的求解过程中，由于含有隐变量， 直接计算比较困难，此时可以用吉布斯采样对隐变量的分布进行采样。 如果对于贝叶斯模型，还可以将隐变量和参数变量放在一起 ，对它们的联合分布进行采样。 注意，不同于－些确定性的近似求解方法（如变分贝叶斯方法、期望传播等），基于采样的随机模拟方法是数值型的近似求解方法。
均匀分布随机数（概率统计，线性同余）
均匀分布是指整个样本空间中的每一个样本点对应的概率（密度）都是相等的。根据样本空间是否连续，又分为离散均匀分布和连续均匀分布。
1. 如何编程实现均匀分布随机数的生成器（1）
计算机程序都是确定性的，因此并不能产生真正意义上的完全均匀分布随机数，只能产生伪随机数（伪随机数是指这些数字虽然是通过确定性的程序产生的，但是官们能通过近似的随机性测试）。
一般可采用线性同余法（ Linear Congruential Generator ）来生成离散均匀分布伪随机数，计算公式为
也就是根据当前生成的随机数 xt，来进行适当变换，进而产生下一次的随机数xt+1。初始值 x0 称为随机种子。式（ 8 .1 ）得到的是区间［0, m-1]上的随机整数，如果想要得到区间 ［0, 1］上的连续均匀分布随机数，用xt除以m 即可。可以看出，线性同余法得到的随机数并不是相互独立的（下一次的随机数根据当前随机数来产生）。
常见的采样方法（逆变换采样，拒绝采样，重要性采样）
对于一个随机变量，通常用概率密度函数来刻画该变量的概率分布特性。具体来说，给定随机变量的一个取值，可以限据概率密度函数来计算该值对应的概率（密度）。反过来，也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值，这就是采样。
1. 抛开那些针对特定分布而精心设计的采样方法，说一些你所知道的通用采样方法，说一些你所知道的通用采样方法或采样策略，简单描述它们的主要思想以及具体的操作步骤。（3）
逆变换采样法：根据分布函数进行采样，如果分布不好直接采样，可以考虑函数变换法，根据变换后的分布采样，然后根据转换关系进行原分布的采样。
拒绝采样：又叫接受/拒绝采样（Accept-Reject Sampling）。对于目标分布 p(x)，选取一个容易采样的参考分布q(x)，使得对于任意x都有p(x)≤M·q(x)，则可以按照如下过程进行采样。
1）从参考分布 q(x）中随机抽取一个样本xi。
2 ) 从均匀分布 U(0, 1 ）产生一个随机数ui。
3）如果ui<p(xi)/M·q(x)则接受样本 xi ；否则拒绝，重新进行步骤 1-3，直到新产生的样本均被接受。
重要性采样：很多时候，采样的最终目的并不是为了得到样本，而是为了进行一些后续任务，如预测变量取值，这通常表现为一个求函数期望的形式。重要性采样就是用于计算函数f（x）在目标分布p(x）上的积分（函数期望）,即
首先，找一个比较容易抽样的参考分布q(x)，并令w(x)=p(x)/q(x)，则有
这里 w(x）可以看成是样本 x 的重要性权重。 由此，可以先从参考分布 q(x）中抽取 N个样本｛xi｝，然后利用如下公式来估计 E[f]:
在实际应用中，如果是高维空间的随机向量， 拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受慨率小或重要性权重低），此时可以考虑马尔可夫蒙特卡洛采样法，常见的有Metropolis-Hastings 采样法和吉布斯采样法。
高斯分布的采样
高斯分布，又称正态分布，是一个在数学、物理及工程领域都非常重要的概率分布。
1. 如何对高斯分布进行采样？（3）
逆变换法和拒绝采样法
马尔可夫蒙特卡洛采样法（蒙特卡洛法，马尔可夫链，吉布斯采样）
1. 简述MCMC采样法的主要思想（1）
MCMC采样法主要包捂两个MC ， 即蒙特卡洛法（ Monte Carlo ）和马尔可夫链（ Markov Chain ） 。蒙特卡洛法是指基于采样的数值型近似求解方法，而马尔可夫链则用于进行采样。 MCMC 采样法基本思想是：针对待采样的目标分布，构造一个马尔可夫链，使得该马尔可夫链的平稳分布就是目标分布，然后，从任何一个初始状态出发，沿着马尔可夫链进行状态转移，最终得到的状态转移序列会收敛到目标分布，由此可以得到目标分布的一系列样本。
2. 简单介绍几种常见的MCMC采样法（2）
MCMC 采样法的核心点是构造合适的马尔可夫链，不同的马尔可夫链对应着不同的 MCMC 采样法，常见的有 Metropolis-Hastings 采样法和吉布斯采样法。
3. MCMC采样法如何得到相互独立的样本？（2）
与一般的蒙特卡洛算法不同， MCMC 采样法得到的样本序列中相邻的样本不是独立的，因为后一个样本是由前一个样本根据特定的转移概率得到，或者有一定概率就是前一个样本。如果仅仅是采样，并不需要样本之间相互独立。如果确实需要产生独立同分布的样本，可以同时运行多条马尔可夫链，这样不同链上的样本是独立的；或者在同一条马尔可夫链上每隔若干个样本才选取一个，这样选取出来的样本也是近似独立的。
贝叶斯网络的采样
概率图模型经常被用来描述多个随机变量的联合概率分布。贝叶斯网络，又称信念网络或有向无环图模型。 它是一种概率图模型，利用有向无环图来刻画一组随机变量之间的条件概率分布关系。如下图是贝叶斯网络的一个经典例子，用来刻画Cloudy、Sprinkler、Rain、WetGrass等变量之间的条件分布关系。
1. 如何对贝叶斯网络进行采样？如果只需要考虑一部分变量的边缘分布，如何采样？如果网络中含有观测变量，又该如何采样？（3）
对一个没有观测变量的贝叶斯网络进行采样，最简单的方法是祖先采样（Ancestral Sampling），它的核心思想是是根据有向图的顺序，先对祖先节点进行采样，只有当某个节点的所有父节点都已完成采样，才对该节点进行采样。
如果只需要对贝叶斯网络中－部分随机变量的边缘分布进行采样，可以用祖先采样先对全部随机变量进行采样，然后直接忽视那些不需要的变量的采样值即可。
接下来考虑含有观测变量的贝叶斯网络的采样，最直接的方法是逻辑采样，还是利用祖先采样得到所有变量的取值。如果这个样本在观测变量上的采样值与实际观测值相同，则接受，否则拒绝，重新采样。这种方法的缺点是采样效率可能会非常低，随着观测变量个数的增加、每个变量状态数目的上升，逻辑采样法的采样效率急剧下降，实际中基本不可用。
不均衡样本集的重采样
1. 对于二分类问题，当训练集中正负样本非常不均衡时，如何处理数据以更好地训练分类模型？（3）
为什么很多分类模型在训练数据不均衡时会出现问题？本质原因是模型在训练时优化的目标函数和人们在测试时使用的评价标准不一致。这种“不一致”可能是由于训练数据的样本分布与测试时期望的样本分布不一致，例如，在训练时优化的是整个训练集（正负样本比例可能是1 : 99 ）的正确率，而测试时可能想要模型在正样本和负样本上的平均正确率尽可能大（实际上是期望正负样本比例为 1 : 1 ）；也可能是由于训练阶段不同类别的权重（重要性）与测试阶段不一致，例如训练时认为所有样本的贡献是相等的，而测试时假阳性样本（ False Positive ) 和伪阴性样本（ False Negative ）有着不同的代价。根据上述分析，一般可以从两个角度来处理样本不均衡问题
1）基于数据的方法
对数据进行重采样，使原本不均衡的样本变得均衡。最简单的处理不均衡样本集的方法时随机采样，采样一般分为过采样(Over-sampling)和欠采样（Under-sampling）。
随机过采样是指从少数类样本集中随机重复抽取样本（有放回）以得到更多样本；
随机欠采样是指从多数类样本集中随机选取较少的样本（有放回或者无放回）。
这种随机采样会带来一些弊端，如过采样会增加模型训练的复杂度，同时也容易过拟合；欠采样会丢弃一些样本，可能会损失部分有用的信息，造成模型只学到了整体模式的一部分。为解决这些问题，可以采用一些方法生成新的样本，如添加噪声，K近邻拟合新样本等。
2）基于算法的方法
在样本不均衡时， 也可以通过改变模型训练时的目标函数（如代价敏感学习中不同类别有不同的权重）采矫正这种不平衡性；当样本数目及其不均衡时，也可以将问题转化为单类学习（ one-class learning ）、异常检测（ anomaly detection ）。