為甚麼要區分抽樣機制
均勻蓄水池使每筆記錄出現的機會相同;但記錄也可能有已知的正權重,例如一筆記錄代表另一筆三倍的流量。我們希望權重較大時較容易入選,同時限制樣本容量,並讓不同工作節點合併結果。「加權不放回抽樣」有不止一種定義;以下先精確定義一種,再推導它的性質,而不是把每筆的入選概率直接當作與權重成正比。
定義 18.1.1
(容量為 的指數競賽樣本)
固定有限數據流中的互相區別的記錄 ,其確定權重為 。內容相同的兩筆仍算不同記錄。給定整數容量 ,令 。獨立抽取速率為 的指數時鐘 ,即
樣本由時鐘最小的 筆組成,按時鐘由小至大記為 。
理想連續抽樣下,時鐘相同的概率為零。此數學模型以固定數據及權重為條件,抽樣隨機性與之獨立;若後續輸入或停止時間取決於已觀察的隨機結果,固定數據流結論未必適用。此處不包括零權重,負權重亦不合法。
有序樣本的概率
定理 18.1.2
(指數競賽按剩餘權重選擇)
對固定有限數據流和正權重,將最小的 個獨立時鐘依次標記為 。對互異的 ,
時空乘積為一。因此每一步在尚未入選者中按其權重比例選擇。
證明
(首次到達,然後無記憶性)
設 。第一個時鐘屬於 ,表示 而所有其他時鐘大於 。利用獨立密度和尾概率積分:
指數分佈的無記憶性給出 。由獨立性,條件於 及首次到達時間 時,其餘時鐘的剩餘時間仍互相獨立,並分別服從原來速率的指數分佈。同樣積分便得到下一筆在剩餘權重中的比例;重複即證乘積公式。此處以確切連續時間為條件是相應條件密度的簡寫,而結果不依賴 。
證明透視
為甚麼每次到達後競賽會重新開始
證明用到一個計算和一個結構性事實。計算是首次到達的積分:獨立指數變量的最小值服從速率 的指數分佈,勝出者為 的概率是 。結構性事實是:在首次到達時刻,仍在運行的時鐘再次是原來速率的獨立指數變量。這裏同時需要獨立性與無記憶性:無記憶性消去已過的時間 ;獨立性保證得知哪個時鐘先響、何時響,並不透露其他時鐘的任何資訊。於是歸納在較小的記錄集合上以同一規則重新開始,這正是每個因子的分母為剩餘權重的原因。若時鐘不是指數分佈,例如 在 上均勻,比例規則一開始便失效:權重為 和 時,第二個時鐘先響的概率是 ,而非 。
定理描述的是有序樣本。凡是只問哪些記錄出現、不理次序的問題,都要把各個次序相加。
常見錯誤
(有序概率不是集合概率)
一個無序集合的概率,要把產生該集合的所有次序概率相加。定理並不表示大小為 的集合概率與其權重乘積成正比,也不表示入選概率是 。 時兩者沒有區別; 時通常有區別,見以下例子。
例題 18.1.3
(三筆不同權重的記錄)
權重為 ,容量為二。記錄 1 入選的互斥情況是它首先出現,或者在 2 或 3 之後第二個出現:
可是 ;因此把單次抽中概率乘以容量會出錯。無序集合 的概率為 。若所有權重相等,每個有序列表的概率均為 ,每個集合有 個次序,所以無序樣本均勻。
例題 18.1.4
(容量為二時的全部入選概率)
保留權重 及 。上例已得 。對記錄 2,把它首先出現的情況,以及它第二個出現的兩種情況相加:
同理 。驗算:,正是樣本大小。天真的 分別為 、 和 :權重大的記錄並非必然入選。在權重 、 的邊緣情況,重記錄的天真值是 ,不可能是概率;指數競賽給出 。
一次掃描與精確合併
每筆記錄到達時只產生一次時鐘。用最多 個 組成的大頂堆保留目前最小時鐘:未滿時插入;滿後只有新時鐘較堆頂小才替換堆頂。 時不儲存。當 ,一次堆更新需 ,樣本佔 個項目;權重、識別碼和時鐘表示方式都影響實際位元組數。這是理想實數運算的描述,並非有限精度隨機數保證。
歸納可知每讀完一筆,堆中都是目前前綴最小的 個時鐘:新時鐘若不比堆頂小,保留集合不變;否則恰好移除舊堆頂。在只插入的流程中,被捨棄的記錄不會重新入選,因為已有至少 個較小時鐘。
例題 18.1.5
(追蹤容量為二的堆)
設 ,時鐘依次為 。前兩個填滿堆:,堆頂 。 小於 ,所以 離開:。 不小於堆頂 ,堆不變;這是邊界情況:新記錄產生時鐘、比較一次便被捨棄。最後 取代 ,剩下 ,確是五個時鐘中最小的兩個。被捨棄的 、 和 在離開或被拒時,前面都已有兩個更小的時鐘。
定理 18.1.6
(各分區最小的 個優先值可精確合併)
把固定記錄集合分成互不重疊的分區。每筆產生一次符合其速率的獨立時鐘;各工作節點回傳本區最小的 個時鐘與記錄。從所有回傳結果中取最小的 個,在任何沒有平手的結果上,都與直接取全域最小時鐘完全相同。
證明
(本地落選者不可能全域入選)
一筆被其工作節點捨棄的記錄,在該分區已有至少 筆時鐘比它小,因此它不可能屬於全域最小的 筆。所有全域入選者都在回傳集合內,排序便可完全還原。這是逐次隨機結果均成立的結論;再由有序樣本定理得到抽樣分佈。空分區和 也適用。
這個逐結果的證明需要本地與全域比較的是同一組時鐘;下例說明不遵守這一點會怎樣。
反例模式
合併必須保留原始優先值
設 ,節點 A 有兩筆、B 有一筆,權重均為一。原始時鐘使三筆等概率勝出,故 A 勝出的概率為 。如果協調者丟棄時鐘,然後在兩個節點保留的記錄中均勻選一筆,A 勝出的概率卻是 。為本地勝出者重新抽時鐘也會改變分佈。必須保留原始優先值、互不重複的記錄識別碼,以及實際有限精度表示的統一平手規則。
理想獨立均勻變量 可產生 。實際偽隨機產生器只有有限狀態,端點、捨入、下溢、重複優先值、種子獨立性和溢出都需要具體實作政策。以識別碼決定平手可重現結果,但不會精確還原理想連續分佈。只要全體使用同一對偶值全序,上述合併證明仍逐結果成立,即使次序的分佈不同。重試時不要重新產生優先值:應按記錄去重並重用原值,否則同一記錄會得到額外機會。
概念視角算法
最小時鐘即最大冪次鍵
由於 嚴格遞減, 個最小時鐘就是 的 個最大值。取 時,這些值就是鍵 ,且當 時 。因此同一個樣本也就是 個最大的鍵 ,可用同一個堆、把比較方向反過來保存。在實數運算中兩種形式完全一致。在浮點運算中,大權重會把 推向 ,而比較 則保留了冪次形式失去的解析度。
估計需要入選概率
按比例抽樣本身並不是總量估計。令 為固定數值,。如果知道這些概率,Horvitz–Thompson 總量估計量
是無偏的:將它寫為 ,逐項取期望便得 。這個期望計算不需要各入選指示變量獨立,但方差通常需要聯合概率。 時 ,入選值貢獻 。 時,計算入選概率可能需要求和許多有序樣本的概率;使用 一般有誤,甚至可能大於一。若 而數據非空,便沒有這種正入選概率。若缺少所需權重和入選資訊,單靠樣本不能確定這個無偏總量估計。
練習與解答
快速檢查
(權重 且 ,求各入選概率。)
解答 · 答案
由首個時鐘的分佈,概率分別為 和 。
快速檢查
(權重 且 ,求無序集合 的概率。)
解答 · 答案
兩個次序的概率和為 。連同 的 及 的 ,三個集合的概率總和為 。
快速檢查
(容量二,節點一的時鐘為 ,節點二為 。怎樣傳送和合併?)
解答 · 答案
前者傳 ,後者傳 ;合併後為 。被捨棄的 在本區已有兩個更小值,不可能全域入選。
快速檢查
(抽一筆,權重 ,數值 。求兩種可能的無偏總量估計及其期望。)
解答 · 答案
入選概率為 和 ,估計值為 和 ;期望 ,正是總量 。
快速檢查
( 時,較大權重能保證入選嗎?)
解答 · 答案
不能。所有有限正權重下,任意 個互異記錄組成的有序列表都有正概率,包括不含指定記錄的列表。權重改變概率,並不保證入選。
這裏只處理固定正權重和有限的只插入數據流。不等概率刪除、權重變動、自適應輸入、有限位元的分佈誤差、有效計算入選概率及容錯分散式實作均須另行分析。