重要性采样
参考
Why Sampling
采样是生活和机器学习算法中都会经常用到的技术，一般来说采样的目的是评估一个函数在某个分布上的期望值，也就是
这是用频率法估计概率，依据的是大数定律。计算机生成的伪随机数一般并不是完全均匀的。
不过还是可以用的。
Sampling Method
可以看到蒙特卡洛法其实就是按一定的概率分布中获取大量样本，用于计算函数在样本的概率分布上的期望。其中最关键的一个步骤就是如何按照指定的概率分布p进行样本采样，抛硬币这个case里伯努利分布是一个离散的概率分布，它的概率分布一般用概率质量函数（pmf）表示，相对来说比较简单，而对于连续概率分布我们需要考虑它的概率密度函数（pdf）：
比如上图示例分别是标准正态分布概率密度函数，它们的面积都是1（这是概率的定义），如果我们可以按照相应概率分布生成很多样本，那这些样本绘制出来的直方图应该跟概率密度函数是一致的。
而在实际的问题中，p的概率密度函数可能会比较复杂，我们由浅入深，看看如何采样方法如何获得服从指定概率分布的样本。
逆采样
目前的内容没有什么难度。
指数分布CDF在大于0部分是严格递增的，所以有反函数。
上面的公式中a是服从[0,1]之间均匀分布的。以上推导对于任意P
有些不严格递增的CDF就不行了。
这个图要把纵轴看为是a也就是横轴,然后就有了CDF的逆，绿色的线对应上去就是a经过F-1得到的值。由于原来是均匀分布，所以现每条绿线对应的点的概率相等，而每条红线又对应一条绿线，那么每条红线的概率也是相等的。现在要竖着切一刀，也就是F-1(a)x的这个x就是这一刀，然后把这一刀左边的红线的概率加起来，就是F(x)。由于每条红线概率相等，于是这一刀左边红线越多，自然表示F(X)越大，或者求个导，也就是红线越密集的地方，PDF越大。右边的采样直方图表示的是横轴对应点附近红线的个数，也就是密度，所以近似表示PDF。
这是一种由[0,1]的均匀分布产生其他分布序列的方法。这种方法需要用到CDF。
Rejective Sampling
对于无法求逆的CDF，我们怎么办？
我们在学习随机模拟的时候通常会讲到用采样的方法来计算π值，也就是在一个1×1的范围内随机采样一个点，如果它到原点的距离小于1,则说明它在1/4圆内，则接受它，最后通过接受的占比来计算1/4圆形的面积，从而根据公式反算出预估的π值，随着采样点的增多，最后的结果πˆ越精确。这种随机肯定是要求均匀分布的。这种方式就显示了几何概型的用处，不过其实求π还有蒲丰投针的模拟方法。
这个分母也不一定非得选择2，是可以自己选择的。
上例中的c=2。这种方法用到的是PDF。
另外参考
蒙特·卡罗方法(Monte Carlo method)也称统计模拟方法，通过重复随机采样模拟对象的概率与统计的问题，在物理、化学、经济学和信息技术领域均具有广泛应用。拒绝采样(reject sampling)就是针对复杂问题的一种随机采样方法。
为什么会出现无法得到PDF的情况呢？因为如果无法从理论分析推导出某个现象的一个分布，那么就得做大量实验，最后得到频数图，如果按照大数定律，频数图和PDF就差一个归一化。
拒绝采样其实分为两步，第一步是根据参考分布得到采样，然后利用接受概率来接受采样。
证明：
用到了贝叶斯定理：
所以最后接受的分布还是原来的分布。转来转去还是回到了原点嘛这不是。但是这是有意义的，因为首先p~(z)是我们在实际中大量试验得到的结果，而现在又想在计算机上进行模拟试验，就需要这样做。用逆采样其实也可以实现。
import numpy as np
import matplotlib.pyplot as plt
size = 1e+07
z = np.random.normal(loc = 1.4,scale = 1.2, size = size)
sigma = 1.2
qz = 1/(np.sqrt(2*np.pi)*sigma**2)*np.exp(-0.5*(z-1.4)**2/sigma**2)
k = 3
u = np.random.uniform(low = 0, high = k*qz, size = size)
pz =0.3*np.exp(-(z-0.3)**2) + 0.7* np.exp(-(z-2.)**2/0.3)
sample = z[pz = u]
plt.hist(sample,bins=150,normed = True)
不过我感觉上面的理解都不太对。可以看看机器之心的：
参考
在数学中，拒绝抽样是用来从分布产生观测值的基本技术。它也被称为接受拒绝方法或“接受 - 拒绝算法”，是一种蒙特卡罗方法。
接收-拒绝算法是利用符合某个分布的函数g去模拟目标概率密度函数f，且f/g是有界的。
假设我们相对PDF为p(x)的函数进行采集，但是由于种种原因（例如这个函数很复杂），对其进行采样时相对困难的。但是，另外一个PDF（概率密度函数）为q(x)的函数则相对容易采样，例如其就是一个均匀分布。
Importance Sampling
上面两种采样方法或多或少都有一些问题。
###Importance Sample 解决的问题
首先当然是我们本来没办法sample from p，这个是我们看到的，IS将之转化为了从q分布进行采样；同时IS有时候还可以改进原来的sample，比如说:
无法直接求得p(x)的情况
举一个例子：
蒙特卡洛积分
重要性采样是蒙特卡洛方法中的一个重要策略。该方法不改变统计量，只改变概率分布，可以用来降低方差。
重要性采样算法就是在有限的采样次数内，尽量让采样点覆盖对积分贡献很大的点。
重要性采样是蒙特卡洛积分的一种采样策略，所以在介绍重要性采样之前我们先来介绍一下蒙特卡洛积分的一些基本内容。
均匀性
这个感觉就是数值积分。
求积分的话这个π(x)就是1。
类似的还有
如何选取这个p也是比较主观的。
还有
对于重要性采样，我之前是有个疑问的，既然是采样，为何最后没有得到样本，反而去求均值去了？其他很多介绍重要性采样的文章都没有讲明白这一点，其实重要性采样与接受-拒绝采样有异曲同工之妙。接受拒绝采样时通过接受拒绝的方式对通过q(z)得到的样本进行筛选使得最后得到的样本服从分布p(z)，每个接受的样本没有高低贵贱之分，一视同仁。而重要性采样的思想是，对于通过q(z)得到的样本，我全部接受！全部接受的话会有一个问题，那就是最后样本点分布不能服从p(z)分布，为了矫正这个样本全部接受带来的偏差，我们给每个样本附一个重要性权重，比如，对于p(z0)/q(z0)=1的样本，给的权重大一点，p(z0)/q(z0)=0.1的样本，权重小一点。但是这个权重怎么算呢？哎，我们发现这个p(z0)/q(z0)不就是一个很好的权重标识吗？
重要性采样取得到的是带有重要性权重的服从q(z)分布的样本，这个权重乘以样本之后的结果其实就是服从p(z)分布的。对于这种比较特殊的样本，我们怎么用呢？我们一般用来求均值，所以，这一小节的标题是重要性采样求均值。如果只写重要性采样容易让人产生误解。
如果q是均匀分布，那么其实上一个式子就是均匀采样，就是最原始的数值积分方法。q分布选择的不一样，效果肯定会有不同。我们最后会试一试。
这个约等号其实按照离散期望的计算不难理解。
应当注意的是，图中p(z)与f(z)的关系，p(z)是一种分布，是相对于z轴的采样点而言的，比如在红色的两个驼峰处，z的取点比较多，在其他地方z的取点就比较少，这叫样本分布服从p(z)。对于f(z)是一种映射关系，将z值映射到其他维度。比如我们熟悉的y = f(x)，将x映射到y。我们所说的求均值就是求f(z)的均值。这一点一定要想明白。
说一点其实稍微懂点数学的都懂，不是说函数值大就要多采样，而是应该在函数变化快的地方多采样。
举一个简单的例子：
这个函数求积分，明显肯定得在斜坡那里密集取点才更精确，而不是在函数值大的地方多取点。
不过重要性采样的思想是
把f(z)看作均匀分布，代表取样间隔相同，另取一个q(z)比较容易产生样本的来作为中介，然后权值函数可以看作矩形的宽加倍系数，那么对p(z)求积分就可以看作是对q(z)进行不均匀采样的积分了，至于矩形的宽，和p(z)也就是函数值有关。
来看一个其它的应用场合。
importance Sampling在深度学习里面的应用
在深度学习特别是NLP的Language Model中，训练的时候最后一层往往会使用softmax函数并计算相应的梯度。
还有其他采样方式，不过这个等我学了随机过程再说。
MATLAB实现
求的是2自由度卡方分布的期望，也就是
中f(z)为z，p(z)为2自由度卡方分布PDF。
这个期望理论为2，分别采用离散法，也就是等距求矩形面积和法和把参考函数q(z)分别取均匀分布，正态分布和指数分布。
clear
m=10;
t=0:0.1:m;
d=5;
l=length(t);
f=t;
p=chi2pdf(t,d);
subplot(2,2,1)
plot(t,p)
r=f*p*0.1;
title([标准值为,num2str(d),积分离散化为,num2str(r)])
grid
for i=1:10
t1=rand(1,l).*m;
R1(i)=t1*chi2pdf(t1,d)*m/l;
end
r1=mean(R1);
subplot(2,2,2)
histogram(t1)
title([均匀分布,num2str(r1)])
for i=1:10
t2=randn(1,l)+m/2;
R2(i)=t2*(chi2pdf(t2,d)./normpdf(t2,m/2))/l;
end
r2=mean(R2);
subplot(2,2,3)
histogram(t2)
title([正态分布,num2str(r2)])
for i=1:10
t3=exprnd(10,1,l);
R3(i)=t3*(chi2pdf(t3,d)./exppdf(t3,10))/l;
end
r3=mean(R3);
subplot(2,2,4)
histogram(t3)
title([指数分布,num2str(r3)])
分别运行了十次取均值，来比较和理论值怎么样。
我们看到指数分布的结果比较好。正态分布我们把期望移到了5，不然的话，正态分布负的太多，而卡方负的是0。离散化和均匀分布有差距，因为均匀分布的结果并不均匀，样本数量不够大，而且计算机是伪随机。
如果加大范围：
反而是均匀分布的效果最好。
改变卡方自由度为2，就又是离散化效果最好了。
总结
逆采样：适用于可逆的CDF，可以用0-1均匀分布产生符合其他分布的序列。
拒绝采样：CDF不可逆也能用，用的是PDF，需要引入另一个可以由计算机产生的分布，它先产生序列，然后按照原分布的PDF来决定序列是否被接受，如果PDF太小，被接受的概率小。被接受与否可以用均匀分布模拟。
重要性采样：它和上面两种应用场景不同，它是求一个期望值，相当于求某个变量的函数的期望，它也引入一个计算机容易产生的分布，然后产序列，这些序列值全部接受，因为它并不是要产生序列，而是求期望，但是要根据原分布的PDF加上权重。
（重要性采样）宝，都看到这里了你确定不收藏一下？？
