L6Medium★ Core Essential · Industrial BedrockPart L · Classical ML & Statistical Simulation
Welford's Algorithm for Online Mean & Variance
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?
💡
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
### Avoiding Catastrophic Cancellation in Online Variance
The naive one-pass identity subtracts two huge nearly equal numbers when variance is small relative to the mean (e.g., ), losing precision or even producing negative variances.
Welford's online algorithm updates running mean and centered sum of squares incrementally:
The naive one-pass identity subtracts two huge nearly equal numbers when variance is small relative to the mean (e.g., ), losing precision or even producing negative variances.
Welford's online algorithm updates running mean and centered sum of squares incrementally:
🔄 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 and , let , , then and 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.