動機
數據量大,可以指記錄太多而無法全部放入記憶體,也可以指記錄持續到達,根本沒有讀取「全部數據」的時刻。平均數的公式雖然包含每筆觀測,計算時卻不必保留每筆觀測。關鍵是:處理完一塊數據之後,哪些資訊必須留下,才足以回答下一步的問題?
假設多部機器各自處理一批感應器讀數,最後要合併平均數與離散程度。只保存各機器的平均數並不足夠,因為不同機器可能處理不同數目的記錄。即使再保存方差,若沒有筆數,仍無法正確加權。此外,總體的變動同時包括塊內變動,以及不同塊的平均數之間的距離;第二部分不能忽略。
數值計算還有另一個難點。當讀數都靠近一個很大的偏移量,方差可能遠小於讀數的平方。用兩個幾乎相同的大數相減,可以把想要的有效資訊消掉。因此,實數上的代數等價,不代表浮點數上同樣準確。我們先證明精確恆等式,再分清它們在有限精度下能保證甚麼。
定義
定義 1.1.1
(數據塊摘要)
對非空有限數據塊 ,定義筆數、均值與中心平方和:
的摘要是三元組 。
這批記錄的描述性母體方差是 。如果記錄是來自有限方差分佈的獨立同分佈樣本,而且 ,無偏樣本方差則是 。分母不同,是因為估計的對象及解釋不同。沒有抽樣假設時,後一個式子仍能計算,但不能直接宣稱無偏。
串流算法依次讀取記錄,保留大小不隨記錄數目增長的狀態。這裏的狀態包含一個整數與兩個實數累加器。「常數記憶體」採用固定字長模型;若要求任意長串流的精確整數筆數,所需位元仍會增長。實作時要分別檢查整數溢出與浮點捨入。
定義 1.1.2
(分塊歸約)
分塊歸約把記錄分成互不重疊的塊,先計算每塊摘要,再沿一棵以各塊為葉節點的合併樹,反覆以二元合併組合摘要。空塊的筆數為零,作為單位元處理:與另一摘要合併時直接回傳後者。
空塊的平均數沒有必須指定的數學值;若隨便填零後套用除以總筆數的公式,兩塊皆空時就會出錯。
除非特別說明,下文先用精確實數運算。浮點運算會把結果捨入到可表示的數。相對誤差模型在遠離溢出與下溢時很有用,但不會令相近數相減變得良態。相近數相減本身可能暴露早先累積的誤差;如果輸入轉換時已把不同讀數捨入成同一個數,後面的方差遞推也無法恢復失去的差異。
定理 / 命題
命題 1.1.3
(加入一筆觀測)
設 是非空塊的摘要,加入 ,並設 。新摘要為
第一筆記錄的摘要是 。平方和的增量亦可寫成 ,故在精確運算下非負。
定理 1.1.4
(合併兩個非空塊)
兩個互不重疊的數據塊,摘要分別為 與 ,其中 。令 、,則合併後
在精確實數運算下,不同合併樹或輸入排列都得到整個多重集的同一摘要。
概念視角代數
以可加座標表示摘要
非空摘要與冪和 互相決定,其中 、。不相交數據塊的冪和直接相加,所以在這組座標下合併就是向量加法,結合律、交換律及空數據塊作為單位元都一目了然。合併定理正是把這個加法改寫到座標 。兩種描述在精確算術中一致;在浮點運算中則偏好中心化座標,因為由 還原 正是大偏移例子所示的抵消。
證明思路
證明
(在塊均值處分拆每個偏差)
均值公式由兩塊的總和直接相加而得:,故 。對中心平方和,把塊 中的偏差寫成 ,平方後求和。交叉項為零,因為相對於塊平均數的偏差總和是零。因此該塊貢獻 。塊 同理,貢獻 。又有 、,故兩個位移平方項相加恰為
至於最後一個斷言,對葉節點為互不重疊非空塊的合併樹作歸納。每個葉節點持有其塊的精確摘要。若某節點的兩個子節點分別持有各自葉節點(互不重疊)聯集的精確摘要,合併公式便給出該節點以下全部葉節點聯集的精確摘要。因此根節點持有整個多重集的摘要。這個摘要只依賴多重集,所以樹形及葉節點次序都不會改變它。
證明
(加入只有一筆的塊)
加入 ,即與 、、 的塊合併,於是 、。合併公式給出 及 。又 ,故 ,證明了遞推的另一寫法。它只涉及中心附近的差,避免先平方整個大讀數。
證明透視
精確性與互不重疊在哪裏起作用
唯一不顯然的一步,是把相對於總均值的偏差在塊均值處分拆。交叉項 之所以為零,是因為 正是塊 的均值;非空條件在這裏用到,因為空塊沒有可供分拆的均值。互不重疊用於把合併數據的中心平方和寫成 上的和加 上的和:每筆記錄只計一次。樹的歸納能夠閉合,是因為每個內部節點收到的都是互不重疊葉節點集合的精確摘要。在浮點數下,歸納假設在第一次捨入合併時已經失效,所以不繼承與樹無關的性質:固定樹可以令結果可重現,卻不會令結果變成精確值。
公式也揭示了為何不能只平均各塊的方差:不同塊均值的位移會帶來額外的平方和,而在精確運算下這部分非負。
反例模式
塊大小相同也不能直接平均塊方差
斷言:若兩塊大小相同,合併後的描述性方差等於兩塊描述性方差的平均。取 、。兩塊的中心平方和都是 ,方差都是 ,平均為 。合併時 、,,故合併方差為 ;直接看,相對於均值 的偏差是 。把合併公式除以 ,便得 時的正確結論:合併方差等於塊方差的平均加上 。只有塊均值相同時,原斷言才成立。
例題詳解
例題 1.1.5
(塊大小不等時的完整核查)
取 、。摘要分別是 、,故 、。新均值為 ,中心平方和為 。描述性方差是 ;若有相應抽樣解釋,樣本方差是 。
直接核查:相對於 的偏差是 ,平方和確為 。兩個塊均值的不加權平均是 ,連總均值也不正確。平均塊方差則還會漏掉兩組之間很大的位置差異。
例題 1.1.6
(大偏移量與細小離散程度)
考慮 。均值是 ,中心平方和是 ,描述性方差是 。雖然實數恆等式成立,
左邊卻要用約 的量相減來取回個位數量級的答案。逐項相加的直接 binary64 計算可以得到 ;這是某個具體運算次序的結果,並非所有語言與函數庫必然輸出同一錯值。
中心遞推的均值依次為 、、、,中心平方和依次為 。此例的差值容易準確表示。它展示了原始二階矩公式的失敗機制,並不證明中心遞推對任何輸入都完全無誤。
例題 1.1.7
(把歸約計劃與資源成本分開計算)
把 筆記錄分成 個非空塊,每個工作節點最多緩衝 筆。單次摘要的總算術工作為 ,每節點在輸入緩衝之外只需 狀態。每節點回傳三個摘要欄位,總摘要通訊為 ,無須把全部原始記錄送到歸約器;但最初讀取及分派輸入的成本仍在。
串行合併需 次操作,依賴鏈長度也是 。平衡二叉樹的總操作數相同,但有足夠工作節點及通訊支援時,深度為 。八塊需要七次合併、三層。較淺的樹可減少相依捨入階段,但單靠樹形不能替所有數據給出相對誤差界。延遲、負載不均及排程都可能主導實際時間。
若某節點超時後重試,歸約器必須只接納該塊一次。把相同摘要合併兩次,在代數上確實算出了「重複數據」的摘要,卻不是原任務的數據。正確公式不能代替恰好一次的記錄處理規約。
實作可從空狀態起步,以第一筆有效有限讀數初始化,其後套用更新。對遺漏值及非有限值,必須事先訂立政策。直接略過遺漏值可能改變目標群體,直接接納非有限值則可能污染其後所有摘要。除了接納筆數,也可保留拒絕筆數,讓讀者知道統計量到底描述了甚麼。
有意義的檢查包括:單筆、常數、大小不等的塊、大偏移量、空分區,以及重複分區識別碼。比較多種合併樹可以找出程式錯誤及評估數值敏感度;要求任意樹的結果逐位元相同,卻是在要求普通浮點加法本來就沒有的性質。
常見錯誤
常見錯誤
(精確不變性不等於數值可重現性)
要分清數學不變性與數值可重現性。精確摘要只依賴多重集;浮點摘要也可能依賴排列、樹形、精度及編譯選項。更改工作節點數目可能改變合併樹,即使輸入與隨機種子不變。需要重現時,應記錄相關選擇。
常見錯誤
(負的計算方差是診斷訊號)
把負的計算方差視為負的變異是錯的。精確平方和非負。微小負值須按已記錄的數值容差調查;很大的負值可能表示溢出、程式錯誤或不穩定公式。把所有負值一概改成零,可能掩蓋故障。只有一筆數據時, 也不是定義良好的樣本方差。
常見錯誤
(摘要不能決定數據本身)
筆數、均值與中心平方和不能重建分位數、異常值位置或多峰形狀。例如 與 的筆數都是 、均值都是 、中心平方和都是 ,但前者是兩個分開的群,後者中間有一對相同值。保留甚麼狀態,應由下游問題決定;若要研究分佈形狀,就需要更豐富的摘要或保留原始記錄。
總結
筆數、均值與中心平方和足以精確合併均值和方差。塊均值差的修正項計入塊間變動。中心遞推避開一種重要相消機制,而有限精度、輸入有效性與重複處理仍須各自核查。總工作、平行深度、記憶體、輸入搬移及摘要通訊是不同的資源指標。
練習
快速檢查
(由 的摘要開始,加入 。計算新均值、中心平方和、描述性方差及樣本方差,並以最終均值的偏差核查。)
解答 · 答案
原均值為 ,平方和為 。新偏差 ,新均值 ,新平方和 。描述性方差為 ,樣本方差為 。最終偏差 的平方和亦為 ;核查時必須用最終而非舊均值。
快速檢查
( 有四個 , 有兩個 ,兩塊方差皆零。求總均值及描述性方差,並解釋平均塊方差為何失敗。)
解答 · 答案
總均值 。塊均值差為 ,故 ,描述性方差為 。直接計算也得四個 加兩個 ,即 。塊內無變動,塊間卻有距離;零方差的平均把全部距離漏掉。
快速檢查
(證明每筆觀測同加常數 後,均值增加 ,而 不變。再解釋為何極大的偏移仍可能改變浮點計算的方差。)
解答 · 答案
新均值為 。每個偏差都是 ,平方和因此不變。浮點輸入卻可能在儲存時已捨入;當可表示數的間距大於原讀數差,原本不同的觀測會合併成同一值。其後相減不能恢復差異;即使輸入仍可分辨,不同捨入路徑也可能造成微小差別。
快速檢查
(有十六個非空分區。串行與平衡歸約各需多少次合併、依賴鏈多深?若重試時分區 5 被加入兩次,固定的樹能否修復統計錯誤?指出一項必要的數據處理不變量。)
解答 · 答案
兩者皆需十五次合併;串行深度十五,平衡深度四。重複分區改變了多重集,通常也改變統計量。固定樹只能穩定地重現錯誤,不能判斷重複。可要求:對固定輸入版本,每個預期分區識別碼恰好貢獻一份獲接納的摘要。先核查識別碼與筆數,再作數值合併,才符合定理的互不重疊假設。