頻數也可能減少
事件計數常常需要更正:刪除重複記錄、修改較早的數值,或把兩個時段的頻數向量相減。這些運算產生的座標不一定非負。前一個 Count-Min 單元已解釋,這時取最小值便失去「一定不會低估」的性質;與負座標碰撞,可能把計數器拉到真值以下。
CountSketch 改變處理碰撞的方法。每個鍵除了桶編號,還有一個隨機正負號。更新加入桶之前先乘上該鍵的符號,讀取時再乘上被查詢鍵的符號。符號的平方是一,所以目標鍵的貢獻完整還原;其他鍵的貢獻則可能為正,也可能為負。我們會證明它們的期望互相抵消,並用二階矩量度誤差。
本單元證明的是指定鍵查詢保證,不包含找出所有高頻鍵的算法。
固定串流與精確的正負計數器
定義 14.1.1
(淨頻數與一般 turnstile 模型)
設 為有限的鍵集合。一次更新 的鍵是 ,更新量 可為任意實數。在固定時刻 , 的淨頻數定義為
允許負更新量,而且允許淨座標為負,稱為一般 turnstile(可增減)模型。
若要求每個座標的淨頻數始終非負,則是較嚴格的 turnstile 模型;本篇證明不需要這項限制。完整的有限串流要在摘要的隨機選擇以外固定。我們先處理亦獨立於這些隨機選擇的指定鍵 及時刻 。若輸入本身隨機,但與摘要獨立,可以先對輸入作條件化。
定義 14.1.2
(CountSketch 的各行與更新規則)
選擇寬度 及奇數行數 。第 行選擇桶函數 及符號函數 ,並要求:
- 不同鍵 滿足 。
- 任意兩個不同鍵的符號獨立,而且每個符號均勻分佈於 。
- 同一行的整個符號函數與整個桶函數獨立。
- 不同行的函數對 互相獨立。
所有計數器 由零開始。對更新 ,在每一行執行
第一項是通用雜湊族的碰撞界,並不要求所有鍵的桶編號共同獨立。下面的指定鍵二階矩計算只需要兩兩獨立的符號。使用一個確定性的雜湊程式,或重複同一個種子,都不是上述性質的證明。
整個摘要生命週期內,符號及雜湊函數保持不變。因此,一次更新及其精確相反數的效果會抵消。按更新次數作歸納可得,每一時刻都有
這是精確算術下的恆等式。用有界整數實作時要避免溢出,用浮點數時則需要另外分析捨入誤差。
定義 14.1.3
(各行估計與中位數估計)
對被查詢的鍵 ,各行估計及最後的指定鍵估計為
因為 是奇數,中位數就是排序後的中間一項。它容許少數行非常不準確。
概念視角代數
每一行都是一個隨機線性映射
固定第 行並把鍵排序。令 為 矩陣,元素為 ;每一列恰有一個非零元素,等於 。計數器恆等式說:計數器陣列的第 行就是 。此外
所以第 行對所有鍵的估計 等於 。對角元為一,而性質 2 與 3 使非對角元的均值為零,故 。下面的命題正是說:這個隨機矩陣平均而言是單位矩陣,而每個座標的離散程度受到控制。 的線性使相容摘要可以相加相減;跨行取中位數是唯一的非線性步驟。
為甚麼每一行的平均估計正確
省略固定時刻的記號,寫成
誤差中沒有目標座標 。把其他座標的平方質量記為
也就是刪去被查詢座標後,剩餘向量的歐幾里得(Euclidean)長度平方。即使目標座標很大,也不會把自己的碰撞誤差界放大;其他大座標才會影響這個界。正負淨頻數在平方和中不會互相抵消。
命題 14.1.4
(一次固定指定鍵查詢的期望與方差)
在上述假設下,每一行都滿足
期望針對隨機函數而取;頻數向量及被查詢鍵均獨立於這些函數而固定。
證明
(展開單行誤差)
設 。兩兩獨立的均勻符號給出 ,其中 。由於符號函數與桶函數獨立,這個期望可與 的期望分開。因此 的每一項都是零,證得無偏性。
再展開誤差平方。由 及 ,
對不同的 ,符號函數與桶函數獨立,所以交叉項的期望可寫為 。指示變量本身不必獨立。對角項則由碰撞界至多為 ,故 。誤差均值是零,所以這亦是方差界。
證明透視
共同的查詢符號先平方,才處理交叉項
各個誤差項共用 ,不能直接說它們互相獨立;證明其實不需要這樣說。平方後,共同的符號變為 ,每個剩餘交叉項只含兩個不同符號,其乘積期望為零。這解釋了為何此處兩兩獨立已足夠。把符號部分和桶部分的期望分開,需要兩個函數獨立;不同行的獨立性則稍後才用到。
命題說的是每一行,而非中位數;不能因為各行無偏,就直接宣稱其中位數亦保持期望。下一個證明會建立中位數的置信保證。
從方差界提高到高成功概率
若 ,其餘座標全為零,每一行的誤差都恆為零,最後答案精確。以下設 。對 ,Chebyshev 不等式給出
選 ,每一行失敗的概率便至多為 。增加桶數先降低單行失敗概率,再用獨立行進一步降低整體失敗概率。
定理 14.1.5
(固定鍵及時刻的中位數置信保證)
設 。採用寬度 ,以及任意滿足 的奇數行數 。對上述固定串流、鍵及時刻,
這裏的常數足夠使用,而且刻意採取較保守的選擇。
證明
(中位數失敗需要過半數的壞行)
設 。若至少 個行估計落在 內,中間次序統計量亦在此區間內。假如中位數低於區間,全部 個準確值都嚴格大於它,但排序後中位數後面只有 個位置,矛盾。高於區間的情況同理。因此,中位數失敗必須有至少 行失敗。
對任何預先指定的 行,行與行獨立,所以它們全部失敗的概率至多為 。若有至少 行失敗,必然存在這樣的一個集合。對 個可能集合用聯集界,得
這裏用了 ,以及 ;後者是因為全部子集共有 個。 的情況已是精確。證明完成,過程沒有假設不同查詢互相獨立。
證明透視
為甚麼寬度常數取八而非四
證明分為確定性與概率兩半。次序統計量一步不用任何隨機性:中位數失敗必須有過半數的壞行。行之間的獨立性只用來把某組指定的過半數行全壞的概率界為 ,其中 是單一行的失敗概率。聯集界於是給出 ,只有當 時才會衰減。寬度取 時 Chebyshev 給出 ,所以任何 都可行;取 令 ,得到簡潔的深度 。
摘要恰需 個計數器,另加隨機函數的描述。若 取最小允許奇數,計數器數目是 ;加一項反映即使 接近一,行數仍至少為一。一次更新接觸 個計數器;一次查詢讀出 個值並找中位數。把值排序是一個簡單做法,線性時間的選取方法則可避免完整排序。這些是運算量及計數器數目的界,並非固定的位元組儲存界。若更新是整數,而且已知更新量絕對值的總和為 ,每個計數器的絕對值至多為 ,故每個帶號計數器用 位元便足夠。
包含低估的正負頻數例子
例題 14.1.6
(先還原每行的符號,再取中位數)
設 。用三個桶,並考慮下表已實現的函數值。例如 代表桶零及符號負一。
| 鍵 | 淨頻數 | 第 1 行 | 第 2 行 | 第 3 行 |
|---|---|---|---|---|
| 5 | ||||
| -3 | ||||
| 2 | ||||
| 1 |
各行計數器是 、 及 。查詢 時,乘回其符號後得到 ,中位數是 5。查詢 時,各行估計是 ,中位數正是帶負號的真值 。
對 ,碰撞誤差的平方尺度是 。小表展示運算方法,不代表寬度三滿足某個置信要求。取 、 時,上述充分定理要求寬度 128、行數 9,共 1152 個計數器;成功事件保證誤差至多 ,約為 。
誤差尺度是平方和,而非其餘頻數的帶符號總和;下一個例子把兩者的分別具體化。
例題 14.1.7
(相反的頻數仍會進入誤差尺度)
設被查詢鍵 有 ,另外兩個鍵有 及 。它們的帶符號總和為零,但 ,故 。在一個已實現、滿足 而 的行中,
雖然其餘頻數總和為零,該行誤差的絕對值仍是 100,而且如尺度所預期,不超過 。由於 ,「誤差至多 」這個加性陳述仍有意義,除以 的相對誤差卻沒有定義。因此定理並不是小座標的相對誤差保證。
常見錯誤
(讀取桶值而忘記還原查詢符號)
在上表中, 所在的桶值是 ,其中位數是 2。計數器儲存的是 加上噪音,只有乘以 才能還原 。各行估計 的中位數是 5,正是準確值。
常見錯誤
(對帶符號的各行取最小值)
在 Count-Min 中每次碰撞只加入非負量,所以每一行都高估,最小值是最安全的一行。有了符號,行誤差可以為負,最小值會選中最負的一個。上表中 的最小值是 2,低估了 3,而中位數是準確的。
獨立性的字句為甚麼不能省略
反例模式
符號的邊際分佈正確,仍不能把碰撞與符號綁在一起
取兩個鍵 ,寬度二,並設 、。獨立抽取均勻符號 。設 ;若兩符號相同就設 ,否則設 。符號仍兩兩獨立,碰撞概率亦恰為 ,符合寬度二的要求;然而兩個函數互相依賴。
符號相同時,查詢 得到 2;符號不同時得到 0。兩種情況各有概率 ,所以估計期望是 1,而非真值零。無偏性證明用到的一階矩項 ,不能再分解為 。修正方法是把符號函數與桶函數獨立抽取;分別檢查兩者的邊際性質並不足夠。
行與行的獨立性,即性質 4,是另一項要求;多存幾份副本並不能提供它。
常見錯誤
(複製一行而非重新抽取)
副本的失敗事件與原行完全相同,複製九次仍保持同一個失敗概率。中位數證明只可對獨立構造的行把概率相乘;增加重複儲存並沒有增加獨立資訊。
線性合併、非線性查詢與有限查詢預算
分別摘要兩個輸入時,保留相同維度、雜湊及符號。計數器恆等式對 是線性的,所以向量 的摘要逐項相加,恰為 的摘要;逐項相減則恰為 的摘要。如此就可比較兩個固定時段,而不用保留每一個事件。合併前的輸入向量仍須獨立於隨機函數。
對合併後的向量使用指定鍵定理。相減時,尺度是 。座標抵消可能降低尺度,卻不能單憑帶符號總和為零就把尺度設成零。若兩個摘要使用不同函數,逐項合併便沒有上述恆等式。
例題 14.1.8
(中位數相減不等於查詢差摘要)
假設兩個相容摘要對同一個鍵的三行估計分別是 及 。兩者的中位數均為零,所以已回傳中位數之差是零。逐行差為 ,其中位數是十。陣列之差就是 的摘要,查詢它才是合併向量保證所涵蓋的運算;已回傳中位數之差並沒有這種保證,因為中位數是非線性的。
對獨立固定串流上 個預先指定的鍵與時刻配對,以上述寬度計算,每個配對失敗的概率至多為 。聯集界給出整體失敗概率至多 ,所以任何滿足 的奇數都足夠。查詢可以共用計數器,其誤差不必互相獨立。
若鍵集合大小是有限的 ,而已知有限時限 ,取 便可用同一事件保護所有鍵及截至 的每個前綴。在該事件上,讀者可看過輸出後才選查詢,或選一個不超過 的停止時刻,因為所有可能的鍵與時刻已受保護。底層更新仍須獨立於摘要而固定。這並不是針對依照輸出選擇未來更新的對手、無界時間或無限鍵集合的證明。
練習與完整解答
快速檢查
(對算例的頻數向量查詢 ,改用寬度 20。求單行方差及絕對誤差大於 2 的概率上界。前者必定等於真正方差嗎?)
使用其餘座標的平方質量。
解答 · 答案
其餘座標的平方質量是 14,所以方差至多為 。Chebyshev 不等式把指定概率界為 。碰撞假設本身只是上界,故方差未必等於 0.7。這個計算不需要不同碰撞指示變量互相獨立。
快速檢查
(用本篇的充分構造,取 及整體失敗預算 。對一次固定查詢,求寬度、最小允許奇數行數及計數器數目;再對 16 次預先指定查詢重算。)
多次查詢時,在行數條件中以 代替 。
解答 · 答案
寬度為 。一次查詢要求 ,故最小奇數為 7,共 224 個計數器。16 次查詢要求 ,故取 15,共 480 個計數器。這是在分配同時失敗的預算,並沒有假設查詢誤差互相獨立。
快速檢查
(一個固定向量只有 非零。查詢 必得甚麼結果?若改查詢一個未出現的鍵 ,是否必定得到零?)
比較 與 。
解答 · 答案
對 ,每行都回傳 ,所以中位數精確。對 ,碰撞會貢獻 ,個別行估計可以非零,中位數亦不保證對每次隨機構造都為零。兩個查詢的尺度不同:,但 。近似答案非零,本身並不能證明該鍵曾出現。
快速檢查
(在耦合雜湊的反例中,把 改成任意固定實數 。計算查詢 的期望,並指出究竟哪項假設失效。)
按兩個符號是否相同分情況。
解答 · 答案
符號相同時答案為 ,否則為零,所以期望是 。除非 ,否則估計有偏。符號仍兩兩獨立且均勻,碰撞界仍為 ;失效的是整個符號函數與整個桶函數的獨立性,因而不能作證明所需的期望分解。
快速檢查
(兩個時段各有鍵 一百次;鍵 在第一時段有 12 次,第二時段有 7 次。每次出現都是 更新,兩個時段均無其他鍵出現。差向量是甚麼?相容的差摘要查詢 會回傳甚麼?為甚麼不能據此在一般情況下直接把已回傳的中位數相減?)
先把陣列相減,再查詢。
解答 · 答案
差向量的 座標是 , 座標是 。相容陣列逐項相減後,只剩下 非零,所以查詢 時每一行都精確為 5。這個結論是在查詢前先抵消座標所得。一般而言,逐行差的中位數與中位數之差不同,前面的三行例子已展示這點,所以不能把相同論證移到後一種程序。
本單元完成的是正負指定鍵更新、精確陣列恆等式、單行無偏性與方差、中位數置信保證,以及明確有限查詢假設下的相容線性合併。候選鍵搜尋、刪去多個大座標後的更強誤差界、對抗性適應串流及具體雜湊族實作,仍未涵蓋。