Online 演算法入門：一次掃描資料也能完成計算

文章說明

這是統計學家與應用數學家 John D. Cook 撰寫的技術科普文，介紹 online（one-pass）演算法的核心概念：只需掃描資料流一次，無需儲存完整資料集，就能精確或近似計算統計量。文章以樣本變異數為範例，並延伸到高階動差、回歸分析等應用。

經典範例：樣本變異數

標準的樣本變異數公式看起來需要兩次掃描：

$$s^2 = \frac{1}{n-1}\sum_{i=1}^n (x_i - \bar{x})^2$$

先算平均值 $\bar{x}$，再回頭計算每個點與平均值的平方差。

教科書會給另一個「等價」公式（基於平方和）：

$$s^2 = \frac{1}{n(n-1)}\left(n\sum_{i=1}^n x_i^2 - \left(\sum_{i=1}^n x_i\right)^2\right)$$

這個公式理論上正確，但數值不穩定（numerically unstable）。Cook 實際見過它在真實資料上返回負數（理論上不可能），導致程式在計算標準差時崩潰（對負數開根號）。

Welford 演算法（1962）：

真正的解法是 B. P. Welford 在 1962 年提出的演算法，能在一次掃描中精確計算平均值與變異數，且數值穩定。Cook 在另一篇文章中提供完整實作。

"Online" 一詞的歷史：

Cook 澄清，電腦科學中的 "online algorithm" 這個術語遠早於網際網路。他引用 1965 年的論文 [1]，當時 "online" 意指：

"在 online 計算中，輸入資料一次一個符號地提供給機器……在 offline 計算中，所有輸入符號在計算開始前就寫在磁帶上。"

現在為了避免與「線上服務」混淆，現代文獻也使用 "streaming algorithm"（串流演算法）一詞。

擴展應用：

高階動差：不只平均值與變異數，偏度（skewness）與峰度（kurtosis）也能 online 計算
簡單線性回歸：單變數回歸係數可以用類似方法遞增更新，Cook 有舊筆記說明
多元回歸：多變數情況更複雜，需要遞迴最小平方法（recursive least squares, RLS）。Cook 引用兩篇論文 [2][3] 但未深入

與函數式編程的連結：

Online 演算法的概念與函數式編程中的 fold（摺疊）操作密切相關。Cook 列出相關文章：

參考文獻：

[1] F. C. Hennie, "One-Tape, Off-Line Turing Machine Computations," Information and Control 8, 553-578 (1965)

[2] Arthur Albert & Robert W. Sittler, "A Method for Computing Least Squares Estimators that Keep Up with the Data," SIAM Journal on Control, 1965

[3] Petre Stoica & Per Ashgren, "Exact initialization of the recursive least-squares algorithm," Int. J. Adapt. Control Signal Process., 2002