2010年10月14日星期四

基本的蒙特卡洛方法(三)​

基本的蒙特卡洛方法(三)​

根据蒙特卡洛方法得到的样本总是无偏的,即样本期望等于总体期望。实践中,期望相同还不够,还要求方差尽量小。因此方差减小技术是蒙特卡洛方法极重要的一部分。

分层采样(Stratified sampling)

充分利用积分的可加性。

仍然考虑计算广告学中的例子,考察样本空间E=<V, C>,其中V是视频集合,C是城市集合。一个点e=(v, c)表示一个来自视频v且来自城市c的广告请求。

给定E的子集E1,求E1中的广告请求个数。

如何广告请求顺序写在了一个文件里,那我们只好随机采。

如果来自不同城市的请求分别写在不同的文件里,那我们可以每个城市随机采,从而有望减小方差。

方差减小的充要条件可以模糊地形容为:同一个城市的用户看视频的偏好相近。

不证明了,举个小规模的例子:

两个城市,100个视频,每个城市每个视频恰好有一个广告请求,共200个。考虑E1={城市1的视频1到90,城市2的视频1到10}。我们一眼就看出来E1中广告请求有90+10=100个。让我们采两个样本,来估计之。

在全空间上随机采:从200中等概率、有重复地采2个,X个属于E1,则100X是无偏估计。经计算,X的方差是0.5。

分层采:从每个城市各采1个,城市1中采中属于E1的个数是X1,城市2中采中属于E1的个数是X2,则100X=100(X1+X2)是无偏估计。经计算,X的方差是0.18。

控制变量法

也叫借鸡下蛋法,呵呵。

这部分的分析很简洁漂亮,情不自禁地说两句。

假设我们关心随机变量X的期望EX。已知另一个随机变量C的期望EC,而且X和C比较相关。用待定系数法,令随机变量X(b)=X-b(C-EC)。(原书中写成了+b有误!)

显然EX(b)=EX,因此,无论系数b如何取,求EX(b)即可。关键在于,适当选取b使得X(b)的方差尽量小。

varX(b)=varX-2bcov(X,C)+b2varC

中学生都会,这是关于b的抛物线,当b=cov(X,C)/varC时最小,最小值为


神了,这看上去就是白给。其实有很多代价:首先要知道EC,其次还要能算b,这太浪漫了。

举个浪漫的例子吧。考虑100个视频请求,一个广告C要投放在1~60,另一个广告X要投放在1~50。假设C的情况我们了解了,X是新来的,要通过采样估计它的访问量。

先按公式算出来b=5/6。从100个请求中随机采1个,属于广告X投放范围的有X个,属于广告C投放范围的有C个,则X(b)=X-5/6*C+0.5。

X

C

X(b)

概率

0

0

0.5

0.4

0

1

-1/3

0.1

1

0

1.5

0

1
1
2/3
0.5


varX(b)=1/3*0.4+1/9*0.1+1/2*4/9=1/12

varX=1/4






没有评论: