机器学习中的采样方法

布丰投针问题

1777年，法国科学家布丰提出一种计算圆周率 $\pi$ 的方法，即随机投针法。

1、在平面上画上间距为 $a$ 的平行线；

2、取一根长度为 $l$ （ $l<a$ ）的针，随机投掷于平面上，针与任一线相交的概率为： $p=\frac{2l}{\pi a}$ 。

$\pi$ 的值可计算为： $\pi=\frac{2l}{\pi a} \approx \frac{2l}{a} (\frac{N}{n} )$ ，

$N$ 为总的投针次数， $n$ 为与平行线相交的次数。

布丰投针问题被认为是蒙特卡洛方法的起源。

复杂函数定积分计算

上面的方法称为蒙特卡洛方法（Monte Cralo method），可以用于计算任一个函数的定积分。

如要求 $\int_{a}^{b} f(x)dx$ 积分，而 $f(x)$ 积分的解析形式又很难求，可通过数值方法求其近似值：

$\int_{a}^{b} f(x)dx=\int_{a}^{b} \frac{f(x)}{q(x)}q(x)dx\approx \frac{1}{N}\sum_{i=1}^N\frac{f(x_{i} )}{q(x_{i} )}$ ,

其中， $q(x)$ 是某种容易采样的分布， $x_{i}$ 是服从 $q(x)$ 分布的随机采样。

解释：上式可能看起来不太容易理解，可以将 $\int_{a}^{b} \frac{f(x)}{q(x)}q(x)dx$ 看作为函数 $h(x)=\frac{f(x)}{q(x)}$ 在分布 $q(x)$ 下的期望，从分布 $q(x)$ 中随机采样，得到 $N$ 个样本 $x_{1},x_{2},...,x_{N}$ ，用这些样本来估计 $E[h(x)]$ 可得 $E[h(x)]\approx \frac{1}{N}\sum_{i=1}^N\frac{f(x_{i} )}{q(x_{i} )}$ 。

基本采样法（Basic Sampling）

思想：从基本概率分布中产生新变量的分布

假设要从均匀分布： $p(z)=1$ ， $z\in (0,1)$ 中，产生非均匀分布： $p(y)$ ， $y=f(z)$ 。

又概率统计知识，可知 $p(y)=p(z) \vert \frac{dz}{dx} \vert$ ，则 $p(y)\vert dy \vert =p(z)\vert dz \vert$ ，两边同时积分得： $z=\int_{-\infty}^{y} p(y)dy$ 。

使用上式，在已知 $p(y)$ 的条件下，即可求解 $z$ 与 $y$ 之间的转化函数。

拒绝采样（Rejection Sampling）

对一个很复杂的分布 $p(z)$ 进行采样，但又无法给出其具体的解析形式，但是每个 $z$ 可以计算其概率，可以借助一个容易采样的分布 $q(z)$ 去逼近 $\tilde{p}(z)$ ， $q(z)$ 称为建议分布（proposal distribution），其中 $p(z)= \frac{1}{z_{p}} \tilde{p}(z)$ 。

找到一个常数 $k$ ，使得 $\tilde{p}(z) \leq kq(z)$ ，采样步骤如下：

1、从 $q(z)$ 中产生 $z_{0}$

2、从 $[0,kq(z_{0} )]$ 均匀分布中产生 $u_{0}$

3、如果 $u_{0} >\tilde{p}(z_{0} )$ ，则拒绝采样，否则接受采样

$p(accept)=\int \frac{\tilde{p}(z) }{kq(z)}q(z)dz=\frac{1}{k} \int \tilde{p}(z)dz$

拒绝采样又称为接受-拒绝采样。

自适应拒绝采样（Adaptive Rejection Sampling）

在实际应用中，往往很难找到合适的 $q(z)$ ，当 $p(z)$ 为log凸函数时，可以采用自适应拒绝采样（ARS）。

$q(z)=k_{i} \lambda_{i}exp\{-\lambda_{i}(z-z_{i-1})\}$ ， $z_{i-1}<z<z_{i}$

$\ln q(z)=C-\lambda (z-z_{i-1})$ ， $z_{i-1}<z<z_{i}$

在log域执行拒绝采样，如果满足，则接受，如果拒绝，则重新逼近。

重要性采样（Importance Sampling）

对于某个变量 $z$ ，其概率密度函数为 $p(z)$ ，现在要预测一个函数 $f(z)$ 关于 $z$ 的期望： $E[f]=\int f(z)p(z)dz$ ，

$p(z)$ 很复杂，但可以估算每个出现的 $z$ 的概率。

于拒绝采样类似，借助一个容易采样地分布 $q(z)$ ，计算方式如下：

$E[f]= \int f(z)p(z)dz=\frac{Z_{q} }{Z_{p}} \int f(z) \frac{\tilde{p}(z) }{\tilde{q}(z)}q(z)dz\approx \frac{Z_{q} }{Z_{p}} \frac{1}{L}\sum_{l=1}^L \tilde{r_{l}} f(z^{(l)})$

其中， $\tilde{r_{l}} = \frac{\tilde{p}(z^{(l)})}{\tilde{q}(z^{(l)})}$ ， $q(z)=\frac{1}{Z_{q}}\tilde{q}(z)$ ， $p(z)=\frac{1}{Z_{p}}\tilde{p}(z)$ 。

$\frac{Z_{p}}{Z_{q}}=\frac{1}{Z_{q}} \int \tilde{p}(z)dz=\int \frac{\tilde{p}(z)}{\tilde{q}(z)}q(z)dz\approx \frac{1}{L}\sum_{l=1}^L \tilde{r_l}$ ，则 $E[f]\approx \sum_{l=1}^L w_l f(z^{(l)})$ ，其中

$w_l=\frac{\tilde{r_l}}{\sum_m \tilde{r_m}}=\frac{\tilde{p}(z^{(l)})/q(z^{(l})}{\sum_m \tilde{p}(z^{(m)})/q(z^{(m)})}$ 。

马尔科夫链蒙特卡洛方法

马尔科夫链蒙特卡洛方法也是一种采样方法，这种方法内容有点多，有机会再写。