如何理解 重要性采样

如何理解 重要性采样
如何理解 重要性采样

如何理解 重要性采样
重要性采样是非常有意思的一个方法.我们首先需要明确,这个方法是基于采样的,也就是基于所谓的蒙特卡洛法(Monte Carlo).蒙特卡洛法,本身是一个利用随机采样对一个目标函数做近似.例如求一个稀奇古怪的形状的面积,如果我们没有一个解析的表达方法,那么怎么做呢?蒙特卡洛法告诉我们,你只要均匀的在一个包裹了这个形状的范围内随机撒点,并统计点在图形内的个数,那么当你撒的点很多的时候,面积可以近似为=(在图形内的点的个数/总的点个数),当你撒的点足够多的时候,这个值就是面积. 这里假设我们总有办法（至少要比找解析的面积公式简单）求出一个点是否在图形内.另一个例子,如果你要求一个稀奇古怪的积分,没有解析办法怎么办?蒙特卡洛法告诉你,同样,随机撒点,你一定可以知道f(xi)的值,那么这个积分的解可以表示为=(b-a)/点的个数*sigma[f(xi)],其中b,a为积分的上下限.
好了,知道了蒙特卡洛法,下面来说重要性采样的前提一些内容.
很多问题里,我们需要知道一个随机变量的期望E(X),更多时候,我们甚至需要知道关于X的某一个函数f(X)的期望E[f(X)].问题来了,如果这个X的概率分布超级特么的复杂,你准备怎么做呢?积分么?逐点求和么?听上去挺不现实的.这时蒙特卡洛法跑出来告诉你,来来来,咱只要按照你这个概率分布,随机的取一些样本点,再sigma(p(xi)*f(xi))不就可以近似这个期望了么.但问题又来了,你怎么”按照这个概率分布“去撒点呢?
经典蒙特卡洛法是这么做的,首先把这个概率分布写成累计概率分布的形式,就是从pdf写成cdf,然后在[0,1]上均匀取随机数(因为计算机只能取均匀随机数),假如我们取到了0.3,那么在cdf上cdf(x0)=0.3的点x0就是我们依据上述概率分布取得的随机点.
举个具体例子吧,例如我想按照标准正态分布N(0,1)取10个随机数,那么我首先在[0,1]上按照均匀分布取10个点
0.4505 0.0838 0.2290 0.9133 0.1524 0.8258 0.5383 0.9961 0.0782 0.4427
然后,我去找这些值在cdf上对应的x0,如下
-0.1243 -1.3798 -0.7422 1.3616 -1.0263 0.9378 0.0963 2.6636 -1.4175 -0.1442
那么上述这些点,就是我按照正态分布取得的10个随机数.
OK,你按照上述方法去找cdf吧.
我如果这么说,你肯定会疯掉.因为,如果概率分布都超级特么的复杂,累计概率分布岂不是会更特么不知道怎么求了!

然后,我们开始了重要性采样的介绍.
让我们回顾一下期望的求法E(f(x))=sum( p(x) * f(x) ) dx.那么,现在我们引入另一个概率分布s(x),相比于p(x),s(x)是非常简单能找到cdf的.那么我们变形一下E(f(x)) = sum( p(x) * f(x) / s(x) * s(x) ) dx ,再仔细看看,这个求f(x)的期望变成了,求在s(x)分布下,p(x)*f(x)/s(x)的期望.
重要性采样的关键就在这里,把对f(x)不好求的期望,变成了一个在另一个分布下相对好求的期望.
这样,s(x)能找到cdf,那么就用上面提到的那个方法去采样,然后对应的,求出h(x0)=p(x0)*f(x0)/s(x0)的值,最后再sigma(s(xi)*h(xi))就可以近似E(f(x))了.
举个例子：就上面那个求积分的问题,用重要性采样解释还可以有很好玩儿的内容.上面求积分时,我们是用的均匀采样的方法,注意这个时候自变量X已经被我们弄成了随机变量,f(X)就是这个随机变量的函数.但是,大家可能会注意到这个问题：如果这个f(x)长的比较特别,例如是个高斯函数N(a,b^2),只不过它的方差b特别的小,但是自变量范围特别大.这时的均匀采样,大多数点都会落在了概率很低的地方,落在a附近的点很少.这样,均匀随机采样法得到的期望很有可能会和真实值差得非常远.（唉,这个问题想不明白的画图,还想不明白的做实验）.那么,此时,如果我们换一个概率,不用均匀采样法,用,例如说N(a,b^2)分布,用上述方法重要性采样一下.那么落在a附近的点会超级的多,这样,得到的期望会很好的近似真实值.
当然,上面那个分布是我随口说的,大家都希望那个重要性采样的概率函数可以无限的逼近真实分布.但既然能表示真实分布,我们就知道cdf了,谁还需要重要性采样呢?所以这只是理论情况.实际上,一般大家用的方法都会根据具体的情况选择.我所见到的,大多都是利用某一种距离/相似度度量函数,然后把这些距离利用某种方法变换成概率分布.这么说还是太抽象,举例吧：
我有一个特定人的模板,我希望在一个给定的区域内寻找这个人.那么粒子的状态就是位置坐标(x, y)和大小(w,h),每个粒子的权重：
首先,求这个粒子的直方图,再和模板求一个距离,巴式距离啦,EMD啦,随你选.假设这个值为x.
然后,计算K*exp^(-alpha*x).这个方法被称为likelihood map,就是说分数越小则概率越高,分数越大概率越低.反正K和alpha积分从0到正无穷的和是1就可以了.这样每个点都有了一个概率值.
且慢,现在还不是概率值.所有粒子的和不是1,所以只能叫权重值.然后再归一化一下,就成为了概率值.
最后这个值就是我们要找的s(x).p(x),f(x),s(x)都有了,这样我们就可以比较轻易的利用s(x)的分布撒点,求期望了.

当然,在很多文章里这些概率都是带着条件概率的,有的利用马尔科夫性,只和前一帧的状态以及观测相关,有的则写成和以前全部状态相关.但是原理基本是一致的.s(x)的选取也各不相同,具体问题具体分析了.