机器学习中的采样方法

布丰投针问题

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)})}$ 。

马尔科夫链蒙特卡洛方法

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,692评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,482评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,995评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,223评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,245评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,208评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,091评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,929评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,346评论 1赞 311
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,570评论 2赞 333
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,739评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,437评论 5赞 344
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,037评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,677评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,833评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,760评论 2赞 369
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,647评论 2赞 354