百面机器学习｜第八章采样知识点(一)

作者: 蓝白绛 | 来源:发表于2019-01-31 17:57 被阅读42次

前言

如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对《百面机器学习——算法工程师带你去面试》这本书。主要记录我认为重要的知识点，希望对大家有帮助。

第八章采样

引导语

采样，是从特定概率分布中抽取相应样本点的过程。它可以将复杂的分布简化为离散的样本点；可以用重采样对样本集进行调整以更好地适应后期的模型学习；可以用于随机模拟以进行复杂模型的近似求解或推理。另外，采样在数据可视化方面也有很多应用，可以帮助人们快速、直观地了解数据的结构和特性。

1、采样的作用

采样本质上是对随机现象的模拟，根据给定的概率分布，来模拟产生一个对应的随机事件。采样可以让人们对随机事件及其产生过程有更直观的认识。例如通过对二项分布的采样，可以模拟“抛硬币出现正面还是反面”这个随机事件，进而模拟产生一个多次抛硬币出现的结果序列，或者计算多次抛硬币后出现正面的频率。
另一方面，采样得到的样本集也可以看作是一种非参数模型，即用较少量的样本点(经验分布)来近似总体分布，并刻画总体分布中的不确定性。从这个角度来说，采样其实也是一种信息降维，可以起到简化问题的作用。例如在训练机器学习模型时，一般想要优化的是模型在总体分布上的期望损失(期望风险)，但训练时用上全部的数据集是不可能的，采集和存储样本的代价也非常大。因此一般采用总体分布的一个样本集来作为总体分布的近似，称为训练集。同理，评估模型是看模型在另外一个样本集(测试集)上的效果。这种信息降维的特性，使得采样在数据可视化方面也有很多应用，它可以帮助人们快速、直观地了解总体分布中数据的结构和特性。
重采样可以充分利用现有数据集，挖掘更多信息，如自助法和刀切法(Jack knife)，通过对样本多次重采样来估计统计量的偏差、方差等。
另外，利用重采样技术，可以在保持特定的信息下(目标信息不丢失)，有意识地改变样本的分布，以更适应后续的模型训练和学习，例如利用重采样来处理分类模型的训练样本不均衡问题。
很多模型由于结构复杂、含有隐变量等原因，导致求解公式比较复杂，没有显式解析解，难以进行精确求解或推理。这时候可以用采样方法进行随机模拟，从而对复杂模型进行近似求解或推理。这一般会转化为某些函数在特定分布下的积分或期望，或者是求某些随机变量或参数在给定数据下的后验分布等。
例如在隐狄利克雷模型和深度波尔兹曼机的求解过程中，由于含有隐变量，直接计算比较困难，可以用吉布斯采样对因变量的分布进行采样。如果对于贝叶斯模型，还可以将因变量和参数变量放在一起，对他们的联合分布进行采样。注意，不同于一些确定性的近似求解方法(如变分贝叶斯方法、期望传播等)，基于采样的随机模拟方法是数值型的近似求解方法。

2、均匀分布随机数

均匀分布是指整个样本空间中每个样本点对应的概率(密度)都是相等的。根据样本空间是否连续，分为离散均匀分布和连续均匀分布。
计算机程序都是确定性的，因此并不能产生真正意义上的完全均匀分布随机数，只能产生伪随机数(伪随机数是指这些数字虽然是通过确定性的程序产生的，但是它们能通过近似的随机性测试)。另外由于计算机的存储和计算单元只能处理离散状态值，因此也不能产生连续均匀分布随机数，只能通过离散分布来逼近连续分布(用很大的离散空间来提供足够的精度)。
一般可采用线性同余法(Linear Congruential Generator)来生成离散均匀分布伪随机数，计算公式为 $x_{t+1}=a\cdot x_t+c(\mod m)$ 也就是根据当前生成的随机数 $x_{t}$ 来进行适当变换，进而产生下一次随机数 $x_{t+1}$ 。初始值 $x_0$ 称为随机种子， $a$ 为乘法因子。
线性同余法得到的随机数并不是相互独立的(下一次的随机数根据当前随机数来产生)，且最多只能产生 $m$ 个不同的随机数，对于特定的种子，很多数无法取到，循环周期基本达不到 $m$ 。如果进行多次操作，得到的随机数序列会进入循环周期。因此，一个好的线性同余随机数生成器，要让其循环周期尽可能接近 $m$ ，需要精心选择合适的乘法因子 $a$ 和模数 $m$ 。

3、常见的采样方法

几乎所有的采样方法都是以均匀分布随机数作为基本操作。假设已经可以生成 $[0,1]$ 上的均匀分布随机数，对于一些简单的分布，可以直接用均匀采样的一些扩展方法来产生样本点，比如有限离散分布可以用轮盘赌算法来采样。很多分布一般不好直接进行采样，可以考虑函数变换法。
一般地，如果随机变量 $x$ 和 $u$ 存在变量关系 $u=\varphi(x)$ ，则他们的概率密度函数有如下关系： $p(u)|\varphi'(x)|=p(x)$ 因此，如果从目标分布 $p(x)$ 中不好采样 $x$ ，可以构造一个变换 $u=\varphi(x)$ ，使得从变换后的分布 $p(u)$ 中采样 $u$ 比较容易，这样可以通过先对 $u$ 进行采样，然后通过反函数 $x=\varphi^{-1}(u)$ 来间接得到 $x$ 。如果是高维空间的随机向量，则 $\varphi'(x)$ 对应Jacobian行列式。
逆变换采样(Inverse Transform Sampling)：在函数变换法中，如果变换关系 $\varphi(\cdot)$ 是 $x$ 的累积分布函数的话，则得到所谓的逆变换采样。假设待采样的目标分布的概率密度函数为 $p(x)$ ，它的累积分布函数为 $u=\Phi(x)=\int_{-\infty}^{x}{p(t)}\,{\rm d}x$ 则逆变换采样法按如下过程进行采样：
(1) 从均匀分布 $U(0,1)$ 产生一个随机数 $u_i$ ；
(2) 计算 $x_i=\Phi^{-1}(u_i)$ ，其中 $\Phi^{-1}(\cdot)$ 是累积分布函数的逆函数。
上述采样过程得到的 $x_i$ 服从 $p(x)$ 分布，下图是逆变换采样法的示意图。
8-3 逆变换采样示意图
如果待采样的目标分布的累积分布函数的逆函数无法求解或者不容易计算，则不适用于逆变换采样法。可以构造一个容易采样的参考分布，先对参考分布进行采样，然后对得到的样本进行一定的后处理操作，使得最终的样本服从目标分布。例如拒绝采样(Rejection Sampling)、重要性采样(Importance Sampling)。
拒绝采样(Rejection Sampling)：又叫接受/拒绝采样(Accept-Reject Sampling)。对于目标分布 $p(x)$ ，选取一个容易采样的参考分布 $q(x)$ ，使得对于任意 $x$ 都有 $p(x)\leq M\cdot q(x)$ ，则可以按如下过程进行采样：
(1) 从参考分布 $q(x)$ 中随机抽取一个样本 $x_i$ ；
(2) 从均匀分布 $U(0,1)$ 产生一个随机数 $u_i$ ；
(3) 如果 $u_i<\frac{p(x_i)}{Mq(x_i)}$ ，则接受样本 $x_i$ ；否则拒绝，回到(1)继续产生样本，直到样本 $x_i$ 被接受。
最终得到的 $x_i$ 服从目标分布 $p(x)$ ，如下图(a)所示，拒绝采样的关键是为目标函数 $p(x)$ 选取一个合适的包络函数 $M\cdot q(x)$ ，包络函数越紧，每次采样时样本被接受的概率越大，采样效率越高。
在实际应用中，为了维持采样效率，有时很难寻找一个解析形式的 $q(x)$ ，因此延伸出了自适应拒绝采样(Adaptive Rejection Sampling)，在目标函数是对数凹函数时，用分段线性函数来覆盖目标函数的对数 $\ln p(x)$ ，如下图(b)所示。
8-3 拒绝采样示意图
重要性采样(Importance Sampling)：很多时候采样的最终目的不是为了得到样本，而是为了进行一些后续任务，如预测变量取值，通常表现为一个求函数期望的形式。重要性采样就是用于计算函数 $f(x)$ 在目标分布 $p(x)$ 上的积分(函数期望)，即 $E[f]=\int f(x)p(x)\,{\rm d}x.$ 首先找一个比较容易抽样的参考分布 $q(x)$ ，并令 $w(x)=\frac{p(x)}{q(x)}$ ，则有 $E[f]=\int f(x)w(x)q(x)\,{\rm d}x.$ 这里 $w(x)$ 可以看成是样本 $x$ 的重要性权重。由此可以从参考分布 $q(x)$ 中抽取 $N$ 个样本 $\{x_i\}$ ，然后利用如下公式来估计 $E[f]$ ： $E[f]\approx\hat{E}_N[f]=\sum_{i=1}^Nf(x_i)w(x_i).$ 下图是重要性采样的示意图。
8-3 重要性采样示意图.jpg
如果不需要计算函数积分，只想从目标分布 $p(x)$ 中采样出若干样本，则可以用重要性重采样(Sampling-Importance Re-sampling，SIR)，先在从参考分布 $q(x)$ 中抽取 $N$ 个样本 $\{x_i\}$ ，然后按照他们对应的重要性权重 $\{w(x_i)\}$ 对这些样本进行重新采样(这是一个简单的针对有限离散分布的采样)，最终得到样本服从目标分布 $p(x)$ 。
在实际应用中，如果是高维空间的随机向量，拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下(样本的接受概率小或重要性权重低)，可以考虑马尔可夫蒙特卡洛采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法。