《蒙特卡洛方差减小技巧》由会员分享,可在线阅读,更多相关《蒙特卡洛方差减小技巧(8页珍藏版)》请在金锄头文库上搜索。
1、2. 4 蒙特卡洛计算中减少方差的技巧 蒙特卡洛求积分的方差为 nfV=2. 其中V为被积函数的方差。 ff公式反映出增加随机点数时,蒙特卡洛计算的精度可以得到改善,但是精度提高非常缓慢。因此用增加蒙特卡洛计算的随机投点数来提高精度总是耗费大量的机时。 n另一个减少计算结果误差的途径是减少的方差V。 f f重要的减少方差V的技巧。 f一、 分层抽样(stratified sampling) 数学上,分层抽样是基于黎曼积分的特性: , 0+=1001)()()(aadxxfdxxfdxxfI 1 a 将积分区域划分成小区域是在数值积分中常用的技巧。 蒙特卡洛的分层抽样技巧的抽样步骤: (1) 将
2、积分区间(或空间)划分为不相交的子区间(或子空间);然后在第个子区间(或子空间)内抽取个随机点。 iin(2) 如果将子区间长度(或子空间体积)记为i,我们将子区间(或子空间)内所有点上的函数值乘上权重因子ini之后迭加起来,就得到该积分在这个子区间的积分估计值; (3) 将所有子区间的积分值迭加起来,就得到在整个区间的积分估计值。这样得到积分的估计值的方差为: 1 ()2212jj jniijj jnjxfVnjIj=V如果适当选择子区间i的大小和随机点数,就可以使计算结果的方差得以减小。这里选择ini和的关键是要了解被积函数在子区间内的特性。如果inf i的划分和的选择都不适当,也可能造成
3、更大的误差。 in如果我们不管被积函数的特性,而简单地将积分区域划分成相等的子区间,并在各子区间内抽取相同数量的随机点数。这种处理方法称为均匀分层抽样法。 iin求一维定积分的问题,比较一下用分层抽样法和用原始蒙特卡洛方法计算得到的方差。 设所求积分为: . =10)( dxxfI数学上可以写成 I. =10110)()()( dxxfxgdxxf在0,1区间插入J 个点,其中1010=Jxxx。令 11111() ,()/ , ,()0,() () ,( 1,2, , )jjjjxjxjj jjxjjxpfxdxf xpx xxfxIgxfxdxj= = 其它J在上面的公式中,显然有关系式
4、. =JjjjIpI1如果用分层抽样蒙特卡洛方法计算的积分值, 在第j个子区间上2以)(xfj分布密度函数抽取个简单子样jn),2,1( Jjxij=,则积分的无偏估计值为 jp112jjjxxjI222jjj1nij=)xi)(=dx dxxf12)(IJ+fIIIjj)()2+j)2jI(=JjJjniijjjjJjxgnIpI1)(1. 令第j区间积分的方差为,根据方差的定义我们有关系式 =jijjdxxfxgxgV122)()()( . 则得到分层抽样计算结果的方差 JIV为: 1212)(1JjijjJjjJnpxgVnpI=V. 如果用通常的原始蒙特卡洛方法计算,以分布密度函数抽取
5、N 个简单子样,则积分的无偏估计值为: )(1xf=NiixgNI1(1它的方差为: NgVNIgNi2121=V其中又可以表示为 2g =JjxxgjjIxgxfIxg1121021)()()(dxxfIIxgpjJjxxJjjj)()(121= dxxxgIIIxgpjJjxxjjjj)()()(2)(11=+=. =+=JjjJjjjIpp1212)设分层抽样法的总抽样数为N ,我们有 JnnnN +=21. 3比较这两种方法计算出的结果的方差,我们有 212122)(1jJj jjJjjjjjJnpIIppNIVI =+=V2121)(11IIpNnpNpjJjjjJj jjj+=.
6、公式的右边第二项显然是大于零的量。第一项的正负则是取决于分层抽样时子区间的划分和子区间内的抽样点数。 jn如果上式的值大于零,则分层抽样计算积分的方差小于采用原始蒙特卡洛方法的方差。若取Nnpjj1=,即njjNp=,此时公式(2.4.14)中第一项为零,公式(2.4.14)总是大于零。这就意味着按比例的分层抽样的方差比原始蒙特卡洛方法小。这样的分层抽样方法具有实用意义。 如果采用均匀分层抽样方法,将0,1区间分成J 个相等的子区间,每个子区间内抽取的点数JNj=n,并且这些点是均匀分布的,即Jpxfj1,1)(1=,这时公式(2.4.14)中的第一项也为零,因而(2.4.14)式的值总是正的
7、。 由此我们也可以看出:均匀分层抽样法是一个减小方差的保险方法。 二、 重要抽样法(importance sampling) 重要抽样法的原理起源于数学上的变量代换方法的思想,即 . =101010)()()()()()()( xdGxgxfdxxgxgxfdxxf4此时随机点的选择不再是均匀的,而是以分布函数G分布的。新的被积函数为乘以权重1。公式(2.4.15)中)(x)(xf )(/ xgdxxdG )() =xg(。这里称为偏倚分布密度函数。该方法使原本对的抽样,变成由另一个分布密度函数)(xg )( xf)(*xf()xgxf中产生简单子样,并附带一个权重。这种方法也称为偏倚抽样法。
8、 )(xg公式右边积分中被积函数的方差为 gf /fV。如果选择恰当,并使它在积分域内的函数曲线形状与接近,则该方差可以变得很小。 )(xg函数应当满足如下条件: )(xg(1)应当是个分布密度函数。 )(xg(2)不应在积分域内起伏太大,使之尽量等于常数,以保证方差V比V小。 )(/)( xgxfgf / f(3)分布密度函数所对应的分布函数)(xg( )Gx能够比较方便地解析求出。 (4) 能方便地产生在积分域内满足分布函数( )Gx分布的随机点。 如能按上述条件找到函数,我们就可以依下列步骤求积分: )(xg(1) 根据分布密度函数产生随机点x . 例如采用反函数法。 )(xg(2) 求
9、出各抽样点x 的函数值,并将所有点上的该函数值迭加起来,再除以抽样点数就得到积分结果。 )(/)( xgxfn也可以采用作为分布密度函数,利用舍选法来舍去)(/)( xgxfw 5或接受个随机点的x 的值。用此方法时,应至少可以事先判断出的最大值。当然最好能从的函数中,推导出。 w )(/)( xgxfmaxwxN,2f)(xg)(xggf / g/上述讨论可以很容易地推广到更高维的积分中。但是要注意如下两个方面的问题: null 在产生随机向量的所有分量后,再用舍选法往往更快,效率更高。 xGnull 在计算)(/)( xgxfGG值之前,做随机变量Nxx ,21到的变换有时是很有用的。这时
10、需要将雅可比行列式yyy ,21),(1 NNyxxx ,(/)21yy 包括在权重因子内。 重要抽样法无疑是蒙特卡洛计算中最基本和常用的技巧之一。它无论在提高计算速度和增加数值结果的稳定性方面都有很大的潜力。 局限性: (1) 能寻找出某分布密度函数,并能解析求出其对应的分布函数G的情况并不多。当然我们也可以用数值计算方法求出,但通常这样处理不灵活,运算速度也慢,而且结果也不准确。 )(x)(xG(2) 当所选择的在某点函数值为零或很快趋于零时(如高斯分布),这时在该点的数值计算是十分危险的。其方差V可能趋于无穷大。即使是在某点上函数不为零,但其值很小时,方差V也可能很大。这一问题采用通常的
11、从样本点估计方差的方法却不一定能检查出来。这种情况会使计算结果不稳定。 )(xg6 三、 控制变量法(相关抽样法)(control variates) 控制变量法利用数学上积分运算的线性特性: += dxxgdxxgxfdxxf )()()()(选择函数时要考虑到:g在整个积分区间都是容易精确算出, 并且在上式右边第一项的运算中对()(xg )(x)gf 积分的方差应当要比第二项对积分的方差小。 f在应用这种方法时,在重要抽样法中所遇到的,当趋于零时,被积函数趋于无穷大的困难就不再存在,因而计算出的结果稳定性比较好。 该方法也不需要从分布密度函数, 解析求出分布函数G。 由此我们可以看出选择所
12、受到的限制比重要抽样法要小些。 )(xg)(xg)( gf )(x )(xg四、对偶变量法(antithetic variates) 通常在蒙特卡洛计算中采用互相独立的随机点来进行计算。 对偶变量法中却使用相关联的点来进行计算。它利用相关点间的关系可以是正关联的,也可以是负关联的这个特点。 两个函数值和之和的方差为 1f2f ( ) ( ) 2 fEffEfEfVfVffV22112121+=+ . 如果我们选择一些点,它们使和是负关联的。这样就可以使上式所示的方差减小。当然这需要对具体的函数和有充分的了解。 1f2f1f2f7 例 已知是一个单调递增的函数,现求积分 )(xf. =10)(
13、dxxfI解 首先,按通常的方法在积分域0,1区间上产生均匀分布的随机点集。计算对应每个点的函数ixix 2/)1()(iixfxf +的值,再将所有点上的函数值迭加起来,除以总的随机点数,则得到(2.4.18)式的积分值。即 =+NiiixfxfNI12/)1()(1. 这种做法与通常的蒙特卡洛计算中将的值迭加起来不相同。由于的单调递增性,)(ixf)(xf 2/)1()(iixfxf +的值应当比单个点的函数值更接近于常数。因而方差也小些。 )(xfi这实际上是采用了和)(xf )1( xf 的积分期望值的平均值作为结果。由于采用相同的随机数列 ix1( xf,使得和两个函数高度负关联,因而方差比和)(xf )1( xf )(xf )两者各自积分的方差之和要小。 8