L6Medium★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation

Welford's Algorithm for Online Mean & Variance

⚡Flashcard Drill➔

Single-pass Welford online mean and variance updating centered differences to prevent catastrophic cancellation.

⏱️ Time: O(1) 每次更新仅需常数次加减乘除
💾 Space: O(1) 仅需维护 count, mean, M2 三个浮点数
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
class WelfordAccumulator:
def __init__(self):
self.count = 0
self.mean = 0.0
self.M2 = 0.0
def update(self, x: float):
self.count += 1
delta =
self.mean += delta / self.count
delta2 = x - self.mean
self.M2 += delta * delta2
@property
def variance_sample(self) -> float:
"""样本无偏方差 (除以 n - 1)"""
if self.count < 2:
return 0.0
return self.M2 / (self.count - 1)
@property
def variance_population(self) -> float:
"""总体方差 (除以 n)"""
if self.count == 0:
return 0.0
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How can independent Welford statistics from distributed workers be merged cleanly?
Next: Reservoir Sampling Algorithm →
💡

Core Mental Anchor / Mnemonic

Update mean by delta/n, then accumulate M2 += (x - old_mean)*(x - new_mean) in one pass.

📐 Mathematical Derivation & Core Formula

μk=μk−1+xk−μk−1k,M2,k=M2,k−1+(xk−μk−1)(xk−μk),s2=M2,kk−1\mu_k = \mu_{k-1} + \frac{x_k - \mu_{k-1}}{k}, \quad M_{2, k} = M_{2, k-1} + (x_k - \mu_{k-1})(x_k - \mu_k), \quad s^2 = \frac{M_{2, k}}{k - 1}
### Avoiding Catastrophic Cancellation in Online Variance
The naive one-pass identity 1N∑xi2−(1N∑xi)2\frac{1}{N}\sum x_i^2 - (\frac{1}{N}\sum x_i)^2 subtracts two huge nearly equal numbers when variance is small relative to the mean (e.g., 109+1,109+210^9 + 1, 10^9 + 2), losing precision or even producing negative variances.
Welford's online algorithm updates running mean and centered sum of squares incrementally:
μk=μk−1+xk−μk−1k,M2,k=M2,k−1+(xk−μk−1)(xk−μk)\mu_k = \mu_{k-1} + \frac{x_k - \mu_{k-1}}{k}, \quad M_{2,k} = M_{2,k-1} + (x_k - \mu_{k-1})(x_k - \mu_k)

🔄 Tensor Dimensions & Shape Flow

stream scalar x -> delta = x - mean -> mean += delta/n -> M2 += delta*(x - new_mean) -> var = M2/(n-1)

🛡️ Numerical Stability & Pitfalls Checklist

  • Multiply delta = (x - old_mean) by (x - new_mean) using the updated mean.
  • Supports O(1) memory streaming and lossless parallel merging via Chan's formula.

💻 Reference Code Implementation

import numpy as np

class WelfordAccumulator:
    def __init__(self):
        self.count = 0
        self.mean = 0.0
        self.M2 = 0.0
        
    def update(self, x: float):
        self.count += 1
        delta = x - self.mean
        self.mean += delta / self.count
        delta2 = x - self.mean
        self.M2 += delta * delta2
        
    @property
    def variance_sample(self) -> float:
        """样本无偏方差 (除以 n - 1)"""
        if self.count < 2:
            return 0.0
        return self.M2 / (self.count - 1)
        
    @property
    def variance_population(self) -> float:
        """总体方差 (除以 n)"""
        if self.count == 0:
            return 0.0
        return self.M2 / self.count

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
wf = WelfordAccumulator()
# 输入极容易导致传统公式精度截断崩溃的大数
data = [1e9 + 1.0, 1e9 + 2.0, 1e9 + 3.0]
for d in data:
    wf.update(d)
assert np.isclose(wf.mean, 1e9 + 2.0)
# 样本方差对于 [1, 2, 3] 应精确为 1.0
assert np.isclose(wf.variance_sample, 1.0), f"实际方差: {wf.variance_sample}"
print("✓ Welford 单遍流式方差算法自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How can independent Welford statistics from distributed workers be merged cleanly?
Using Chan's parallel formula: given (nA,μA,M2,A)(n_A, \mu_A, M_{2,A}) and (nB,μB,M2,B)(n_B, \mu_B, M_{2,B}), let n=nA+nBn = n_A + n_B, δ=μB−μA\delta = \mu_B - \mu_A, then μ=μA+δnBn\mu = \mu_A + \delta \frac{n_B}{n} and M2=M2,A+M2,B+δ2nAnBnM_2 = M_{2,A} + M_{2,B} + \delta^2 \frac{n_A n_B}{n} without raw data.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Bootstrap Resampling & 95% Confidence IntervalBack to Part L & All 105Next: Reservoir Sampling Algorithm →