数据流可能长得无法存储,第一项到达时也可能不知道最终长度。水塘抽样维持一个小型样本,对目前已见的项目精确均匀。然后我们用样本估计固定数据流的一项性质,明确说明随机性及其限制。
数据流增长时保留样本
固定整数容量 k ≥ 1 k\ge1 k ≥ 1 。把数据流中的出现位置编号为 1 , 2 , … 1,2,\ldots 1 , 2 , … ;不同位置即使数值相同,仍是不同的出现项。把前 k k k 项存入 k k k 个槽位。对第 t > k t>k t > k 项,独立于此前抽样,从 { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } 均匀选取 J J J 。若 J ≤ k J\le k J ≤ k ,用第 t t t 项替换槽位 J J J ;否则水塘不变。若到达项目不足 k k k 个,全部保留。不需要事先知道最终长度。
对固定数据流以容量 k k k 运行水塘算法。对每个 t ≥ k t\ge k t ≥ k ,处理 t t t 个项后,水塘中出现位置的集合在 { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } 的 ( t k ) \binom tk ( k t ) 个 k k k 元子集上均匀分布。
对固定数据流及每个 t ≥ k t\ge k t ≥ k ,水塘中出现位置的集合在大小为 k k k 的 ( t k ) \binom tk ( k t ) 个子集上均匀分布。t = k t=k t = k 时只有一个这样的子集。假设结论在 t − 1 t-1 t − 1 成立,固定大小为 k k k 的目标集 S S S 。
若 t ∉ S t\notin S t ∈ / S ,此前水塘必须为 S S S ,而且不能发生替换。第一个事件的概率由归纳假设为 1 / ( t − 1 k ) 1/\binom{t-1}k 1/ ( k t − 1 ) ,不替换的概率为 ( t − k ) / t (t-k)/t ( t − k ) / t ,两者独立,乘积是
1 ( t − 1 k ) t − k t = 1 ( t k ) . \frac1{\binom{t-1}k}\frac{t-k}{t}=\frac1{\binom tk}. ( k t − 1 ) 1 t t − k = ( k t ) 1 . 由于 ( t k ) = ( t − 1 k ) t / ( t − k ) \binom tk=\binom{t-1}k\,t/(t-k) ( k t ) = ( k t − 1 ) t / ( t − k ) ,这恰好等于 1 / ( t k ) 1/\binom tk 1/ ( k t ) 。
若 t ∈ S t\in S t ∈ S ,此前水塘必须包含 S ∖ { t } S\setminus\{t\} S ∖ { t } ,以及 S S S 以外 t − k t-k t − k 个较早位置中的一个。对每个可能的此前集合(概率为 1 / ( t − 1 k ) 1/\binom{t-1}k 1/ ( k t − 1 ) ),不论该额外项在哪个槽位,选中它替换的概率都是 1 / t 1/t 1/ t 。因此总概率仍是 ( t − k ) / ( t ( t − 1 k ) ) = 1 / ( t k ) (t-k)/(t\binom{t-1}k)=1/\binom tk ( t − k ) / ( t ( k t − 1 ) ) = 1/ ( k t ) 。两种情况完备,归纳完成。
证明透视
为什么两种情况得出同一个数 这个证明只有一个关键动作:按目标集 S S S 是否包含最新位置 t t t 分类,使归纳假设可以用在此前的水塘上。归纳假设用了两次,每次都只用到“{ 1 , … , t − 1 } \{1,\ldots,t-1\} { 1 , … , t − 1 } 的每个 k k k 元子集概率相同,都是 1 / ( t − 1 k ) 1/\binom{t-1}k 1/ ( k t − 1 ) ”这一点。
两种情况是不同的事件,却由同一个算术闭合。若 t ∉ S t\notin S t ∈ / S ,只有一个此前集合可行,它以概率 ( t − k ) / t (t-k)/t ( t − k ) / t 保持不变。若 t ∈ S t\in S t ∈ S ,有 t − k t-k t − k 个此前集合,每个以概率 1 / t 1/t 1/ t 到达 S S S ,因为新项必须落入某个指定槽位,而 J J J 有 t t t 个等可能的取值。两个乘积都等于 ( t − k ) / ( t ( t − 1 k ) ) (t-k)/(t\binom{t-1}k) ( t − k ) / ( t ( k t − 1 ) ) ,即 1 / ( t k ) 1/\binom tk 1/ ( k t ) 。t − k t-k t − k 正是 S S S 以外较早位置的个数,所以两种情况的计数吻合。
替换概率 k / t k/t k / t 是必要的。若新项以另一个固定概率 q q q 替换槽位,则 t ∉ S t\notin S t ∈ / S 的情况给出 ( 1 − q ) / ( t − 1 k ) (1-q)/\binom{t-1}k ( 1 − q ) / ( k t − 1 ) ,只有 q = k / t q=k/t q = k / t 时才等于 1 / ( t k ) 1/\binom tk 1/ ( k t ) 。J J J 的新鲜性也被用到:它独立于过去,因此转移概率可以相乘。相等的值不能当作同一项,因为结论是针对出现位置的。
估计比例
固定一个长度 t ≥ k t\ge k t ≥ k 的数据流,且它独立于抽样随机性。为每个出现项指定固定指示值 z i ∈ { 0 , 1 } z_i\in\{0,1\} z i ∈ { 0 , 1 } ,记 p = 1 t ∑ i = 1 t z i p=\frac1t\sum\limits_{i=1}^t z_i p = t 1 i = 1 ∑ t z i 。令 p ^ \widehat p p 为 k k k 个存储指示值的平均。均匀不放回抽样给出 E [ p ^ ] = p \mathbb E[\widehat p]=p E [ p ] = p 。当 t > 1 t>1 t > 1 ,
Var ( p ^ ) = p ( 1 − p ) k t − k t − 1 . \operatorname{Var}(\widehat p)=\frac{p(1-p)}{k}\frac{t-k}{t-1}. Var ( p ) = k p ( 1 − p ) t − 1 t − k .
推导如下:令 X j X_j X j 为总体一个均匀随机排列中第 j j j 个位置的指示值,每个的方差都是 p ( 1 − p ) p(1-p) p ( 1 − p ) 。对不同位置,E [ X i X j ] = M ( M − 1 ) / ( t ( t − 1 ) ) \mathbb E[X_iX_j]=M(M-1)/(t(t-1)) E [ X i X j ] = M ( M − 1 ) / ( t ( t − 1 )) ,其中 M = t p M=tp M = tp 是 1 的数目,所以协方差是 − p ( 1 − p ) / ( t − 1 ) -p(1-p)/(t-1) − p ( 1 − p ) / ( t − 1 ) 。前 k k k 个位置的平均便有上述方差。若 t = k = 1 t=k=1 t = k = 1 ,水塘含唯一一项,方差为零;此时所示公式分母为零,不能使用。
对 ε > 0 \varepsilon>0 ε > 0 及 t > 1 t>1 t > 1 ,Chebyshev 不等式给出
P ( ∣ p ^ − p ∣ ≥ ε ) ≤ p ( 1 − p ) ( t − k ) k ( t − 1 ) ε 2 ≤ 1 4 k ε 2 . P(|\widehat p-p|\ge\varepsilon)
\le \frac{p(1-p)(t-k)}{k(t-1)\varepsilon^2}
\le\frac1{4k\varepsilon^2}. P ( ∣ p − p ∣ ≥ ε ) ≤ k ( t − 1 ) ε 2 p ( 1 − p ) ( t − k ) ≤ 4 k ε 2 1 .
此上界可能大于一,此时没有信息。当 t = k t=k t = k ,样本就是整个数据流,估计精确。固定数据流假设很重要:若后续项目或停止规则会响应已公开的水塘内容,那是不同的自适应模型,不在此证明涵盖范围内。
四个出现项
取 t = 4 t=4 t = 4 、k = 2 k=2 k = 2 ,指示值为 ( 1 , 1 , 0 , 0 ) (1,1,0,0) ( 1 , 1 , 0 , 0 ) 。六个双位置子集等可能:一个给 p ^ = 1 \widehat p=1 p = 1 ,四个给 p ^ = 1 / 2 \widehat p=1/2 p = 1/2 ,一个给 p ^ = 0 \widehat p=0 p = 0 。总体比例为 p = 1 / 2 p=1/2 p = 1/2 ,而 Var ( p ^ ) = 1 / 12 \operatorname{Var}(\widehat p)=1/12 Var ( p ) = 1/12 。取 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 ,误差至少 1 / 2 1/2 1/2 的概率为 2 / 6 = 1 / 3 2/6=1/3 2/6 = 1/3 ,恰等于此例中精确方差给出的界。
反例模式
个别纳入均匀不等于独立 一个自然但错误的说法:若每个出现项都以概率 k / t k/t k / t 被保留,则这 t t t 个纳入指示变量就像偏差相同的独立硬币。以 t = 4 t=4 t = 4 、k = 2 k=2 k = 2 检验。六个二元子集各有概率 1 / 6 1/6 1/6 ,所以每个出现项被纳入的概率为 3 / 6 = 1 / 2 3/6=1/2 3/6 = 1/2 。若独立,第 1、2 项同时纳入的概率应为 1 / 4 1/4 1/4 ,真实值却是 1 / 6 1/6 1/6 (只有子集 { 1 , 2 } \{1,2\} { 1 , 2 } )。这两个指示变量的协方差为 1 / 6 − 1 / 4 = − 1 / 12 ≠ 0 1/6-1/4=-1/12\ne0 1/6 − 1/4 = − 1/12 = 0 。四个指示变量之和恒为 2 2 2 ,方差为 0 0 0 ;若四个偏差为 1 / 2 1/2 1/2 的指示变量独立,方差会是 1 1 1 。对数据流 ( 1 , 1 , 0 , 0 ) (1,1,0,0) ( 1 , 1 , 0 , 0 ) ,把 k = 2 k=2 k = 2 次抽取当作独立,会得到 Var ( p ^ ) = p ( 1 − p ) / k = 1 / 8 \operatorname{Var}(\widehat p)=p(1-p)/k=1/8 Var ( p ) = p ( 1 − p ) / k = 1/8 ,真实值却是 1 / 12 = 1 8 ⋅ t − k t − 1 = 1 8 ⋅ 2 3 1/12=\tfrac18\cdot\tfrac{t-k}{t-1}=\tfrac18\cdot\tfrac23 1/12 = 8 1 ⋅ t − 1 t − k = 8 1 ⋅ 3 2 。修正方法是使用不放回抽样的精确方差,并保留有限总体因子 ( t − k ) / ( t − 1 ) (t-k)/(t-1) ( t − k ) / ( t − 1 ) 。
此算法最多存储 k k k 个项目及一个数据流位置计数器。在理想均匀整数抽取模型下,前 k k k 项之后每项需一次抽取;位成本及存储项目值所需空间取决于表示及抽样实现。它估计固定有限数据流的比例;不能自动估计未来数据分布,也不能自动处理对手自适应。
常见错误
(对任何容量都以概率 1 / t 1/t 1/ t 纳入新项)
k = 1 k=1 k = 1 时新项以概率 1 / t 1/t 1/ t 进入水塘,于是很容易把这条规则沿用到较大的 k k k ,再均匀选一个槽位覆写。取 k = 2 k=2 k = 2 、t = 3 t=3 t = 3 :第 3 3 3 项进入的概率是 1 / 3 1/3 1/3 ,而第 1 1 1 、2 2 2 项各自留下的概率是 1 − 1 3 ⋅ 1 2 = 5 / 6 1-\tfrac13\cdot\tfrac12=5/6 1 − 3 1 ⋅ 2 1 = 5/6 。{ 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } 的均匀二元子集包含每个位置的概率都是 2 / 3 2/3 2/3 ,所以这条规则偏向较早的项目。上面的算法从 { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } 均匀抽取 J J J ,只在 J ≤ k J\le k J ≤ k 时替换,因此第 t t t 项以概率 k / t k/t k / t 进入,并以概率 1 / t 1/t 1/ t 落在每个槽位。
习题
快速检查
(若 t = k t=k t = k ,p ^ \widehat p p 是什么?)
解答 · 答案 精确等于 p p p :水塘保存了每个出现项,所以样本均值就是数据流均值。
快速检查
(在四项例子中,某个指定出现项被存储的概率是多少?)
解答 · 答案 k / t = 1 / 2 k/t=1/2 k / t = 1/2 :六个等可能的双位置子集中,有三个包含该出现项。
快速检查
(当 t = 1 t=1 t = 1 、k = 1 k=1 k = 1 ,p ^ \widehat p p 的方差是多少?)
解答 · 答案 零,因为水塘总是保存唯一的项目;不要代入分母为 t − 1 t-1 t − 1 的公式。
快速检查
(均匀大小为 k k k 的样本是否要求各纳入指示变量独立?)
解答 · 答案 不要求;固定样本大小通常使它们相依。在四项例子中,两个指定出现项同时被存储的概率是 1 / 6 1/6 1/6 ,而不是 ( 1 / 2 ) 2 = 1 / 4 (1/2)^2=1/4 ( 1/2 ) 2 = 1/4 。