8. 采样

8.1 采样的作用 **

• 本质是对随机现象的 模拟

• 样本集可以看作 非参数模型，是 信息降维（经验风险 => 期望风险）

• 重采样，估计统计量的 bias / variance（bootstrap），或改变样本分布（imbalance）

• 复杂 / 因变量，随机模拟近似求解，e.g. LDA 和 深度玻尔兹曼机 DBM 的 Gibbs Sampling

  • MCMC 和 EM、变分推断（Variational Inference, VI） 的联系和区别？

8.2 均匀分布随机数 *

• 线性同余法 $x_{t+1}=a\cdot x_t+c(mod\ m)$，区间为 [0, m-1]，初始值 $x_0$ 称为随机种子

• 最多只能产生 m 个不同的随机数，很多数无法取到，循环周期达不到 m

8.3 常见的采样方法 ***

• 有限离散分布，轮盘赌算法

• 不好直接采样，函数变换法，抽样后反函数 $x=\phi^{-1}(u)$ 间接得到 x

  • 如果 $u=\phi(x)$，则 $p(u)|\phi'(x)|=p(x)$

  • 如果 $\phi(\cdot)$ 是 x 的累计分布函数，称为 逆变换采样

    • 抽取随机数 $u_i$；计算 $x_i=\Phi^{-1}(u_i)$

• 如果累计分布函数的逆函数无法求解，可以构造 参考分布，再 后处理

  • 接受-拒绝采样

    • 参考分布 $q(x)$ 抽取 $x_i$；抽取随机数 $u_i$；如果 $u_i<\frac{p(x_i)}{Mq(x_i)}$，则接受 $x_i$

    • $M\cdot q(x)$ 为 包络函数，延伸出 自适应拒绝采样

  • 重要性采样 $E[f]=\int f(x)p(x)dx$

    • 计算函数$f(x)$ 在目标分布 $p(x)$ 上的积分（函数期望）

    • 参考分布 $q(x)$，令 $w(x)=\frac{p(x)}{q(x)}$，则有 $E[f]=\int f(x)w(x)(q)$，$w(x)$ 可以看作重要性权重

    • 从 $q(x)$ 中抽取样本，然后 $E[f]\approx \hat{E}_N[f]=\sum_{i=1}^N f(x_i)w(x_i)$

    • 如果不需要计算函数积分，只想采样若干样本，可以按照 $w(x_i)$ 重要性重采样

  • MCMC 采样

    • 高维空间随机向量，难以寻找合适参考分布，采样效率低下

      • 接受概率小 / 重要性权重低

    • Metropolis-Hastings Sampling

    • Gibbs Ssampling

8.4 高斯分布的采样 ***

• 逆变换法

  • $z=\sqrt2 erf ^{-1}(2u-1)$，其中 erf 是高斯误差函数 $erf(x)=\frac{2}{\sqrt\pi}\int_0^x e^{-t^2}dt$

  • erf 不是初等函数，没有显式解，避免求逆

• Box-Muller：联合概率分布，圆盘概率

  • $\begin{cases}x=\sqrt{-2\ln(u_1)}\cos2\pi u_2 \\y=\sqrt{-2\ln(u_1)}\sin2\pi u_2\end{cases}$，$x,y\sim N(0,1)$，且相互独立

  • 三角函数，相对比较耗时

• Marsaglia polar method：单位圆盘采样，$\frac{x}{\sqrt s}$, $\frac{y}{\sqrt s}$ 替代 cos / sin

  • 令 $s^2=x^2+y^2$，则 $x\sqrt{\frac{-2\ln s}{s}}$， $y\sqrt{\frac{-2\ln s}{s}}$ 服从 $N(0,1)$

• 拒绝采样法：指数分布 为参考分布，

• Ziggurat 算法：拒绝采样，阶梯矩形逼近目标分布

8.5 马尔可夫蒙特卡洛采样法 MCMC **

• 基本思想

  • 针对目标分布，构造 Markov Chain，平稳分布是目标分布

  • 初始状态出发，状态转移，序列会收敛到目标分布，得到一系列样本

  • 核心是构造合适的 Markov Chain，即确定 状态转移概率

• 常见方法

  • Metropolis-Hastings Sampling

    • 对于目标分布 $p(x)$，选取参考条件分布 $q(x^*|x)$，并令 $A(x^*|x)=min\{1,\frac{p(x^*)q(x|x^*)}{p(x)q(x^*|x)}\}$

    • 随机初始样本 $x^{(0)}$，根据参考条件分布抽取 $x^*$，抽取随机数 u

    • 若 $u<A(x^{(t-1)},x^*)$，则接受 $x^*$，否则拒绝，保持不变

  • Gibbs Sampling：是 MH 算法的一个特例，每次只对 一个维度 进行采样和更新

  • 与拒绝采样的区别

    • 在拒绝采样中，如果拒绝，则不产生新样本，重新采样

    • MCMC 每一步都产生一个样本，只是有时候与之前的相同，此外需要 burn-in

• 如何得到相互独立的样本

  • MCMC 样本序列中，相邻的样本不是独立的

  • 采样不需要独立，如果确实需要，多条 Markov Chain 或间隔取出

8.6 贝叶斯网络的采样 ***

• 没有观测变量

  • 祖先采样（Ancestral Sampling），根据有向图顺序依次采样

  • 只需要对部分变量的边缘分布采样，祖先采样，对全部变量采样，再忽略不需要的

• 含有观测变量

  • 逻辑采样，即 祖先采样 得到所有变量的值，符合则接受，不符则拒绝（效率低）

  • 似然加权采样（重要性思想），只对非观测变量采样，但需要重要性权值 $w\propto \prod_{z_i\in E}p(z_i|pa(z_i))$

  • MCMC 采样

    • Metropolis-Hastings Sampling：Cloudy=T/F, Rain=T/F，4 种状态转移

    • Gibbs Sampling：每次只更新 Cloudy / Rain，交替进行

8.7 不均衡样本集的重采样 ***

• 很多模型 imbalance 时会出现问题，本质是 训练优化目标 和 测试评价标准 不一致

  • train 的样本分布（e.g. 1:99） 与 test 的期望分布（正确率=>1:1） 不一致

  • train 的类别权重（FP == FN） 与 test（FP != FN） 代价不一致

• 基于数据的方法

  • over-sampling：增加复杂度，过拟合

    • SMOTE：降低过拟合风险，但可能增大 类间重叠度，生成无效样本

      • Borderline-SMOTE 只给边界上的少数类合成样本

      • ADASYN 给不同的少数类合成不同个数的新样本

      • 清理方法，进一步降低 类间重叠

  • under-sampling：损失信息

    • Informed Undersampling：多次训练，级联结构 等思想

    • Hard Negative Mining：比较难的样本抽出来，用于迭代

• 基于算法的方法

  • 改变目标函数：代价敏感学习，AUC

  • 极度不均衡：单类学习（one-class learning）、异常检测（anomaly detection）