數據流可能長得無法儲存,第一項到達時也可能不知道最終長度。水塘抽樣維持一個小型樣本,對目前已見的項目精確均勻。然後我們用樣本估計固定數據流的一項性質,明確說明隨機性及其限制。
數據流增長時保留樣本
固定整數容量 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 。