2010年9月28日星期二

基本的蒙特卡洛技术(二)

将计算广告学中的一个问题形式化:

假设你开办了一个类似Hulu的网站,有n个视频,上周视频k的访问量是x[k],x[k]>0,通过某种时间序列模型,你预测下周视频k的访问量是y[k],y[k]>=0。

记x=sum{x[k],k=1..n}​, y=sum{y[k],k=1..n}

假设你现在有上周的全部x个视频请求,从中采样m个,第i个代表w[i]个,使得它们代表了下周的视频请求,即E(sum{w[i]h(i,k), i=1..m})=y[k]对任意k=1..n成立,其中

示性函数h(i,k)=1当且仅当样本i请求视频k。​

1. 加权采样

算法:

有放回、等概率地从上周x个视频请求中随机选取m个,如果选中的视频请求i来自视频k,则令w[i]=c*y[k]/x[k],其中c是归一化系数,等于x/m。

无偏性:

注意到E(w[i]h(i,k))=w[i]P(h(i,k)=1)=x/m*y[k]/x[k]*x[k]/x=y[k]/m

停时:

T显然概率一地为m

2. 拒绝方法

算法:

重复下列步骤直到接受m个请求为止,有放回、等概率地从上周x个视频请求中随机选取1个,假设它来自视频k,则以概率r[k]接受之,其中r[k]=c*y[k]/x[k],其中c=1/max{y[k]/x[k], k=1..n},接受的请求的权重w都是y/m

无偏性:

只需证明P(h(i,k)=1)=y[k]/y

令事件S(i,k)表示从历史采中的请求i来自视频k,S表示sample,事件A(i)表示接受采中的请求i,A表示Accept。我们已知P(S(i,k))=x[k]/x, P(A(i)|S(i,k))=r[k]

注意到h(i,k)=1是说,在接受的请求i的条件下,i来自视频k,因此转化成计算条件概率

P(h(i,k)=1)=P(S(i,k)|A(i))=P(A(i)|S(i,k))*P(S(i,k))/sum{P(A(i)|S(i,k))*P(S(i,k)), k=1..n}

注:​P(h(i,k)=1)=y[k]/y表明,拒绝方法可以达到按照目标分布采样的目的

停时:

即接受m个请求,需要尝试T次采样。E(T)=m/P(A(i))。接受概率P(A(i))=y/x/max{y[k]/x[k], k=1..n},也就是说,要想接受概率不太低,那么历史分布和目标分布必须一致接近。

3. 拒绝方法的拉斯维加斯版本

算法:

重复下列步骤直到视频k上的请求采够y[k]/w个,w=y/m。有放回、等概率地从上周x个视频请求中随机选取1个,假设它来自视频k,接受它当且仅当视频k上的请求还没采够y[k]/w个。接受的请求权重都是w。

注:拉斯维加斯版本的好处是不用计算接受概率,即不需要知道x[k]的情况,这一点在“历史分布”难以计算的情况下尤其有用。

正确性:

显然算法停止时,P(sum{w[i]h(i,k), i=1..m}=y[k])=1。

停时:

同前

4. 混合加权拒绝方法

加权方法完全靠样本权重将历史分布拉到目标分布,以牺牲权重相近为代价,换得最有停时性能。

拒绝方法完全靠接受拒绝控制了分布,以牺牲停时为代价,换得相近的权重。

有些场合,例如利用样本做某种预算控制的模拟,要求权重差异不能太大。这种混合方法目的是在停时和权重差异之间寻求平衡。

算法:

条件接受概率r[k]=min{1, c*y[k]/x[k]},c>1/max{y[k]/x[k], k=1..n}。

权重可以反算出来,当h(i,k)=1时,w[i]=y[k]/m*q/q[k],其中q=sum{q[k]},q[k]=r[k]*x[k]/x,这里q其实就是接受概率。

停时

注意到c越大,接受概率越大,停时越小,直到退化为纯加权方法。

5. 停时有界的混合加权拒绝方法

实际应用,由于SLA等原因,我们要求算法概率1地保证停时有界,即存在M,使得P(T<=M)=1。

这时我们松弛掉“恰好采纳m个样本”的要求。这个方法可以看做方法4的拉斯维加斯版本。

算法:

按照历史分布采M个,M>m,权重都是y/m,采够了的视频,拒绝更多样本,最后没采够的视频,通过调整其上每个样本权重,使之满足y[k]。

注:

这个算法不仅概率1保证停时有界,而且概率1保证满足等式约束sum{w[i]h(i,k), i=1..m}=y[k],代价是无法预知采纳的样本的个数。

1 条评论:

xlvector 说...

靠,我现在就在hulu