小型隨機樣本為何需要精確約定
日誌檔可能大得無法全部保留,而且第一筆記錄到達時,我們未必知道最終共有多少筆。保留最初一千筆記錄雖然便宜,卻完全剝奪了後來記錄入選的機會。若每筆記錄各自以千分之一的概率保留,所有記錄都有機會,但保留數量又未必能限制在一千筆。我們要的是另一種約定:讀完任何有限前綴後,在固定容量內保留一個均勻抽出的子集。
抽樣對象是每次出現的記錄,以其位置或不可變的唯一識別碼區分。兩筆數值相同的記錄仍是兩個不同的對象。不放回抽樣禁止同一次出現被選兩次,並不禁止樣本含有相同數值。以下先把輸入串流固定,再討論抽樣的概率律。若數據本身是隨機的,而抽樣亂數與數據獨立,則在給定數據後仍有相同結論。若對手會查看蓄水池,再改變後續輸入或決定何時停止,就需要另外分析。
方法只保留有界數量的記錄、精確整數計數,以及明確指定的隨機來源。實作一節會區分數學模型與可以實際執行的偽隨機示範。
蓄水池不變量與單次掃描更新
定義 11.1.1
(容量為 的均勻蓄水池)
固定整數容量 。讀入 次出現後,記 及 。正確的蓄水池 是 的隨機無序子集,並滿足
公式最後一項表示:每個大小為 的目標子集都具有同一概率。當 ,唯一子集是空集。當 ,所有記錄都保留,所以分佈集中在 。容量為零時,蓄水池始終為空。儲存陣列的先後位置只供算法使用;不變量並沒有宣稱陣列順序也是均勻排列。
先填滿最初 個陣列位置。其後每次收到 ,都重新抽取一個在 上均勻的整數 。若 ,以 取代第 個位置的記錄;否則不變。因此新記錄以 的概率入選,而每個特定已佔用位置以 的概率被取代。抽取範圍必須反映目前計數,不能一直使用固定上限。
定理 11.1.2
(每個有限前綴都有均勻子集)
假設給定全部先前抽樣歷史後,每個更新整數仍條件均勻,並與固定輸入獨立。對每個確定的有限 和每個容量 ,算法都滿足上述不變量,而且毋須預先知道最終串流長度。
證明
(對前綴長度歸納)
當 或 ,結果是確定的,已滿足不變量。對 ,由 開始歸納。設 ,並假設讀完 筆時不變量成立。固定 的一個 元子集 。
若 ,先前蓄水池必須恰為 ,且本次不能取代任何位置。因此
若 ,令 。先前蓄水池必須是某個 ,其中 。這樣的選擇共有 個。對每一種先前蓄水池,恰有一個位置儲存 ,而本次選中該位置的條件概率是 。各種先前狀態互不相交,故
兩種情況涵蓋所有 元子集。條件均勻性讓我們把先前狀態概率乘以相應的更新概率,無論 在陣列的哪個位置都成立。歸納完成。
證明透視
每項假設在歸納中的位置
歸納假設用在 的整個 元子集上: 的情況要對 個先前蓄水池 求和,每一項都需要確切值 ,而不只是某筆記錄的存活概率。給定全部歷史後 的條件均勻性用了兩次:不取代時乘以 ,選中儲存 的唯一位置時乘以 ;因為每個位置的條件概率相同, 在陣列的哪個位置並不重要。兩種情況都化為恆等式 ,歸納因此閉合。若各更新整數共用亂數,即使每個 的邊際分佈均勻,這些乘積也不再成立;下文共用抽取的練習題會算出由此產生的偏差。
常見錯誤
(相同入選概率不等於不變量)
很容易只驗證每筆記錄以 的概率被保留。考慮四筆記錄、容量二:各以一半概率選 或 ,每筆記錄的入選概率的確都是一半,但六種可能配對中有四種永不出現。不變量是關於每個目標子集的陳述,所以證明追蹤的是子集。
對無限到來的串流,每個固定有限前綴都有正確蓄水池,但不存在可數無限串流的最終均勻固定大小樣本。若每個正整數的入選概率都相同且為正,樣本的期望大小便是無限;若它們都為零,可數個零概率事件的聯集仍為零,所以樣本幾乎必然為空。當 ,兩者都不可能描述大小為 的樣本。
有限前綴定理亦容許與抽樣過程獨立的隨機停止計數:先給定該計數,再使用固定計數的結論即可。
常見錯誤
(因蓄水池「看來有趣」而停止)
查看蓄水池的停止規則與抽樣亂數並不獨立。例如 時,若第二筆入選便在計數二停止,否則到計數三才停止。條件於「在二停止」,第二筆的入選概率是一,而不是二分之一。定理只適用於每個固定計數,或與抽樣決策獨立選取的計數。
分區摘要必須保留甚麼
定義 11.1.3
(分區摘要)
在容量 下,含 次出現的分區的摘要是一對 :精確計數 ,以及該分區大小為 的均勻蓄水池 。
設互不重疊的分區 分別有 次出現,各工作節點以彼此獨立的亂數建立並回傳摘要。計數描述原始分區,不是保留陣列的長度。空分區的計數為零,其蓄水池也為空。
令 及 。聯集的均勻 元子集,會含有一個隨機數量 的 區記錄。直接計算子集數量,得到超幾何分配律
合併時,先使用與兩份摘要獨立的亂數,按此概率律抽取 。再以獨立的新決策,從 的保留陣列中均勻不放回選 筆,從 的保留陣列中選 筆,回傳聯集及計數 。所有可行分配都放得進原有蓄水池,因為 ,且 。
為甚麼還不知道最終分配,工作節點就能先丟棄數據?關鍵是:均勻蓄水池的均勻子抽樣,仍是原始分區的均勻子集。
引理 11.1.4
(均勻子抽樣可以組合)
設 是某個 元集合的均勻 元子集,其中 。給定 後,從 中均勻選一個 元子集 。那麼 是原始集合的均勻 元子集。
證明
(計算包含目標的蓄水池)
固定目標 元子集 ,恰有 個可能蓄水池包含它。給定其中任何一個,選出 的概率都是 。所以
這裏用到恆等式 。採用 的慣例後,這個階乘恆等式也涵蓋 和 。
定理 11.1.5
(加權合併保留完整子集概率律)
對固定且互不重疊的分區,若容量 的局部蓄水池獨立且均勻,分配及子抽樣亂數亦獨立,則上述合併輸出是 的均勻 元子集,並回傳正確計數 。
證明
(以分配為條件)
固定一個目標 元子集 ,記 。只有 時,合併才可能回傳 。給定此分配,子抽樣引理給出的兩個目標部分概率分別是 與 。原始蓄水池獨立,後續選擇又使用新亂數,因此兩事件獨立。相乘得到
同一慣例亦涵蓋 、 及 :對應的全集或空集都是唯一可能子集。計數可相加,是因為分區互不重疊。
證明透視
一個分配、兩次引理、一次約去
唯一的關鍵一步是以 為條件:滿足 的目標 只能來自分配 ,所以毋須對多種情況求和。然後在兩邊分別使用子抽樣引理:一邊取 、,另一邊取 、;這正是工作節點可在分配確定前丟棄記錄的理由。兩個節點及合併新決策的獨立性只用了一次,就是把兩邊概率相乘。證明能夠閉合,是因為超幾何分子恰好約去兩個引理分母,所以其他分配律都不行。結論是對節點抽樣取平均的:給定某份已實現摘要後,被丟棄的記錄不能重新出現;兩個節點重用同一種子,即使分區不重疊,也會破壞這次相乘。
合併樹可逐層歸納使用定理。只要來源亂數獨立,互不重疊子樹的摘要便維持獨立,所以任何固定合併樹都回傳正確均勻律。不同的樹卻未必回傳同一個實現樣本。正如先前的分散式歸約一節,分區必須不重疊且恰好處理一次;重複或遺漏分區會改變抽樣母體。只檢查摘要長度,不能證明這些外部識別條件。
例題 11.1.6
(五筆記錄的精確合併)
取 、 及 。 的分配概率依次為
配對 的概率是 。當中的 同時涵蓋第一個節點的三選二蓄水池,以及其後的二選一。配對 的概率是 ;配對 的概率也是 。三者代表三種分配類型;全部十種配對的概率都為十分之一。
例題 11.1.7
(低於容量的合併使分配確定)
取 、 及 。由於 、,每個局部蓄水池就是整個分區。此時 、,可行範圍是 。唯一分配是 ,概率為 。兩次子抽樣都取走全部記錄,合併回傳三筆記錄及計數 ,正是聯集唯一的 元子集。若改為 ,範圍同樣迫使 ,空摘要不貢獻任何記錄。
反例模式
摘要大小相同,不代表母體權重相同
令 , 只有一筆 ,而 有九筆各不相同的記錄。兩節點各回傳一筆。若從兩份摘要均勻選一份,保留 的概率是 ,每筆特定 區記錄的概率則是 。可是每筆原始記錄的目標概率應為 。正確分配是以 選 摘要、以 選 摘要。容量更大時需要超幾何分配;固定按比例配額,會排除均勻子集本應容許的某些分配。
使用有限隨機字的完整實作
假設理想來源每次回傳一個獨立均勻的 位元字,且與所有輸入及先前調用獨立。此處 。對任意正整數上限 ,串接足夠多個(記為 個)字,取得在 上均勻的整數 ,其中 。設 ;若 就拒絕重抽,否則回傳 。每個餘數恰有 個獲接受的代表值。因此重複獨立嘗試後,每個餘數的回傳概率都是 。接受概率 ,故程序幾乎必然終止,平均少於兩次嘗試;嘗試次數卻沒有固定上限。
使用新的獨立來源字,即使上限依賴過去決策,各次調用仍然條件均勻。特別是,串流計數增加時,不必把精確整數決策改成浮點概率比較。
分配時,可想像罐中有 個 標籤和 個 標籤。以整數決策不放回抽 個標籤,卻不實際儲存它們。含有 個 標籤的某個特定類型序列,概率是 ,其中 ,且 。這樣的類型序列共有 個。相乘化簡,正好得到上述超幾何公式。程式只須儲存剩餘計數。
以下完整 Python 程式以帶種子的產生器實作可執行的隨機字介面。其確定輸出並不能證明理想獨立性假設。示範中每次出現都有不同整數標籤;摘要驗證只檢查計數與長度一致,而分區不重疊及使用新亂數仍由調用者確保。
import random
class FiniteWords:
def __init__(self, seed):
self.rng = random.Random(seed)
def below(self, bound):
if not isinstance(bound, int) or bound < 1:
raise ValueError("positive integer bound required")
if bound == 1:
return 0
words = ((bound - 1).bit_length() + 15) // 16
size = 1 << (16 * words)
limit = size - size % bound
while True:
candidate = 0
for _ in range(words):
candidate = (candidate << 16) | self.rng.getrandbits(16)
if candidate < limit:
return candidate % bound
def reservoir(items, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
count, kept = 0, []
for item in items:
count += 1
if len(kept) < capacity:
kept.append(item)
elif capacity:
slot = source.below(count)
if slot < capacity:
kept[slot] = item
return count, kept
def subsample(items, take, source):
if not 0 <= take <= len(items):
raise ValueError("invalid subsample size")
pool = list(items)
for i in range(take):
j = i + source.below(len(pool) - i)
pool[i], pool[j] = pool[j], pool[i]
return pool[:take]
def merge(left, right, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
for count, kept in (left, right):
if (not isinstance(count, int) or count < 0
or len(kept) != min(capacity, count)):
raise ValueError("summary count/length mismatch")
na, ra = left
nb, rb = right
total = na + nb
take = min(capacity, total)
remaining_a, remaining_total, allocated_a = na, total, 0
for _ in range(take):
if source.below(remaining_total) < remaining_a:
allocated_a += 1
remaining_a -= 1
remaining_total -= 1
kept = (subsample(ra, allocated_a, source)
+ subsample(rb, take - allocated_a, source))
return total, kept
left = reservoir(iter(range(3)), 2, FiniteWords(101))
right = reservoir(iter(range(3, 5)), 2, FiniteWords(202))
count, sample = merge(left, right, 2, FiniteWords(303))
assert count == 5 and len(sample) == 2 and len(set(sample)) == 2
assert set(sample) <= set(range(5))
assert reservoir(iter(range(2)), 5, FiniteWords(404)) == (2, [0, 1])
assert reservoir(iter(range(5)), 0, FiniteWords(505)) == (5, [])
assert merge((0, []), (0, []), 2, FiniteWords(606)) == (0, [])
print("merged", count, sorted(sample))
函數 subsample 的部分交換,使每個由不同條目組成的有序序列都具有 的概率;忽略順序後,就是均勻 元子集。它只複製蓄水池,不會複製整個分區。分配迴圈最多執行 次,兩個子抽樣迴圈合計最多執行 次。
單次掃描最多保留 筆記錄及一個計數,亦即 個記錄位置,再加上計數及暫存隨機整數所需的 位元。對任意長度串流,這不是固定位元的記憶體上限:精確計數隨串流增長,就需要更多儲存空間。每個有限前綴仍只用有限記憶體,而且沒有建立輸入清單。此計算也假設保留記錄的大小有界,或使用有界大小的參照;任意大記錄內容需要另外的位元組預算。
在精確整數抽取成本為常數的理想模型下,掃描有 次更新,合併兩份摘要需要 工作及 個額外記錄位置。使用此處的字來源時,在 以下抽取一個整數,平均需 個來源字;整數運算及複製大型記錄另有成本。示範的不同種子標記可重現的不同串流,但種子不同並不構成數學獨立性的證明。
均勻子集對估計有甚麼作用
命題 11.1.8
(蓄水池平均的期望與方差)
對固定實數 ,設 、,並令 及 。若 是 的均勻 元子集,則蓄水池平均 無偏,其有限母體方差為
證明
(入選指標與成對入選)
寫 。計算子集數目可得 ,而對不同索引,。期望的線性性給出無偏性。再設 ,則 ,且 。展開 ,得到
亦即所需方差。
成對入選概率正是完整抽樣設計發揮作用的地方。當 ,方差為零;容量為零時,樣本平均沒有定義。若 ,則全部數據都保留;只要 ,把總和除以實際樣本數 ,就得到精確平均。當 且容量為正,這個平均的方差也為零;上述使用 的公式則假設 。這些是固定有限母體下基於抽樣設計的結論,並非對未知未來數據生成過程的置信保證。
例題 11.1.9
(核對有限母體修正)
對數值 和 ,三個等概率的配對平均是 。它們的平均為 ,方差為 。母體量為 ,所以 。若把保留的兩個值當作獨立抽取,就會漏掉不放回抽樣帶來的方差縮減。
練習與完整解答
快速檢查
(容量為二,讀完三筆後的蓄水池是均勻配對。讀入第四筆後,得到配對 及 的概率各是多少?)
追蹤先前配對,以及位置被取代的概率。
解答 · 答案
第一個配對要求先前配對為 ,概率 ,並且本次不取代,概率 ,故結果是 。若目標為 ,先前必須是 或 。每種先前配對的概率均為 ,而取代另一筆所在的唯一位置,概率是 。相加得到 。推理依賴位置被取代的概率,而不依賴陣列是否按數值排序。
快速檢查
(兩個工作節點及歸約器均使用容量三,兩分區大小為四與二。求各分配概率,以及指定子集 的概率。)
由 、 開始。
解答 · 答案
此時 。可行的 區數量為 ,概率分別是 、 及 。指定子集要求分兩個位置給 、一個給 。均勻子抽樣給出 。即使分配稍後才決定,第一節點容量三的蓄水池仍然足夠。
快速檢查
(容量為一。在 均勻抽一次 ,並重用它設定 、。兩個更新整數各自都在所需範圍均勻。求最終三筆的入選概率,並指出哪項定理假設失效。)
列出 的六個值,逐一跟隨兩次更新。
解答 · 答案
若 ,最後更新選位置零,保留第三筆。若 ,第二次更新保留第二筆,第三次不取代。若 ,兩次更新都不取代第一筆。因此第一、二、三筆的最終概率依次是 。這些決策共用 ,給定先前歷史後並不條件均勻。正確的一維邊際分佈,不能支持歸納中相乘的步驟。
快速檢查
(為甚麼蓄水池最多一百筆記錄,仍不能證明任意長度串流有固定的位元組記憶體上限?可否在合併樹中加入同一摘要兩次?)
考慮計數本身,以及合併定理的假設。
解答 · 答案
精確計數 需要約 位元,而保留記錄的位元組大小亦可能不同。除非另行限制整數範圍和記錄大小,否則界限只是記錄位置數。把同一摘要放入兩次,會同時破壞不重疊性與獨立性:記錄被重複計入,兩份副本也共用抽樣決策。合併定理因此不再描述原本只應計算一次的母體之均勻樣本。