概率加权的随机抽样 (Weighted Random Sampling) – A-Res 蓄水池算法

2017-11-20 18:51:10 旧日重来

最近,Aulddays 遇到一个随机抽样任务。有一个对象集合,由于整个集合非常大,希望考虑每个对象的热门程度抽样出一部分对象来进行分析。把这个任务抽象出来,其实就对应了一个带概率加权的随机抽样 (Weighted Random Sampling) 问题。对应到不同的应用场景,可以对应解决搜索query抽样、商品抽样、网页抽样等任务。对于不加权的普通随机抽样,其实并不难解决,在样本集合非常大的情况下,还可以使用经典的蓄水池算法 (Reservoir Sampling) 来高效实现的抽样。但对于带概率加权的情况,就不太容易了,特别的,在 Aulddays 的任务中,结果集合中每个对象只有1次,对应了无放回的情况,则更困难一些。在内存足够的情况下,似乎还能想到接近于 O(mlogn) 的思路,但大数据上就没什么好的思路了。Survey 了一番之后,发现这个问题其实已经被研究了很久,但直到 2006 年才得到较好的解决:Pavlos S. Efraimidis and Paul G. Spirakis, 2006, Weighted random sampling with a reservoir。这里介绍一下他们提出的 A-Res 算法

问题定义

(简单)随机抽样

给定 n 个样本(样本集合),从中随机抽出 m 个样本(抽样集合),样本集合中每个样本出现在抽样集合的概率相等(=m/n)。

加权随机抽样

样本集合中每个样本附加一个权重 wi >0,每个样本被抽中的概率由 wi 确定。wi 有两种指定方法:

  1. 概率值,即所有样本的权重 wi 加和为 1
  2. 相对权重,wi 只表明样本之间被抽中概率的相对关系,但事先并不知道每个样本具体的概率是多少。在大数据的场景下,这个是更常见的情况

显然,概率值是相对权重的一个特例,解决了相对权重的情况,拿概率值作为输入也是直接可运行的。

有放回/无放回 (with/without replacement)

顾名思义,无放回就是被抽中之后就不会被再次加入候选,也就是一个样本在最终的抽样结果中最多只出现1次。有放回则可能在结果中出现多次。更一般的,还可以定义 k-1-放回,即一个样本最多被抽中 k 次(被放回 k-1 次)。不难看出,无放回对应 k=1,而有放回对应 k=m (m是抽样集合的大小)
这里首先重点研究无放回的情况。对于有放回的情况,可以在无放回算法的基础上做简单扩展来解决。

A-Res 算法

A-Res 算法也利用了蓄水池 (reservoir) 的思想来解决大数据的问题,也就是说,事先不用知道样本集合的大小 n 和样本权重的情况(i.e. 权重之和),只需要依次遍历一次样本集合即可以得到结果,空间复杂度是 O(m),正比于结果集合的大小。
出人意料的,A-Res 算法相当简洁,只需要计算和记录一个参数即可。具体算法如下:

Algorithm: A-Res
Input: 样本序列 V,长度未知,第 i 个样本 vi 的权重为 wi
Output: 长度为 m 的结果集合 R
 
foreach vi in V (i = 1, 2, ...):
   ki = rand(0, 1) ^ (1 / wi)
   if i <= m:
      (vi, ki) 加入 R
   else:
      (vt, kt) = min k ∈ R // Aulddays: 选出 R 中 k 最小的那个样本
      if ki > kt:
         (vi, ki) 替换 (vt, kt)
提示:当 wi 值为一般权重而非概率值时,可能会是一个很大的数值,从而使得 ki 的指数操作可能会丢失精度。这种情况下可以对 ki 取 log() 而变成 ki = log(rand(0, 1)) / wi,因为后续在各个 ki 之间只涉及比较相对大小而不是绝对值,所以可以保证精度的同时不影响结果。

循环中的每一轮需要查找/更新蓄水池中 ki 特征值的最小值,显然这里用一个最小堆来维护是一个较优化的选择。于是整个算法的时间复杂度就是 O(m*log(n))

显然,整个算法的核心在于 ki = (rand(0, 1)) ^ (1 / wi) 这个特征值,这里做一个简单证明

  • U1, U2 为两个相互独立的随机变量且均服从 [0, 1] 区间上的均匀分布
  • k1 = (U1)1/w1, k2 = (U2)1/w2, 其中 w1, w2 > 0 (在算法中 w1, w2 就是对应目标样本的权重)
  • 可以推出概率关系:P(k1≤k2) = w2/(w1+w2)
  • 因此比较 ki 特征值确实实现了按 wi 的概率加权随机抽样

扩展(分布式、有放回)

因为所有数据只需过一轮,A-Res 可以比较容易的扩展到并行或分布式的情况。

对于有放回的情况,只需要这样进行修改:创建 m 个大小为 1 的蓄水池,对于每个样本 vi,分别在每个蓄水池上独立的运行 A-Res 算法。

查看:原文地址;来源:live.aulddays.com


注意:本站所有文章除特别说明外均为原创,版权所有,转载请务必以超链接方式注明作者出处,并禁止用作商业用途