Welford's Algorithm: Mean Update Rule

1. The Power of Online Algorithms

So far, the algorithms we've considered (both the naive single-pass and the stable two-pass methods) are "batch" algorithms. They require the entire dataset to be available before computation can begin. However, in many real-world data science applications, this isn't feasible or desirable.

What if you're analyzing a live stream of sensor data, user activity on a website, or financial transactions? You can't wait for the stream to end to compute statistics. You need to update your metrics as each new data point arrives. This is the domain of online algorithms.

The following resource provides a great introduction to this concept and why it's so crucial for modern data processing.

The key idea is to find a recursive formula: a rule that allows us to calculate the new mean using only the previous mean, the new data point, and the current count of items. This avoids storing the entire dataset and recomputing everything from scratch.

2. Deriving the Recursive Mean

Let's derive this recursive rule for the mean. The derivation is straightforward but reveals a very elegant and intuitive structure. We'll use the following notation:

• $x_n$: The $n$-th data point.
• ${\mu }_{n-1}$: The mean of the first $n-1$ data points.
• ${\mu }_n$: The mean of the first $n$ data points (our target).

The derivation is presented very clearly in the following resource. I'll ask you to read it, and then we will walk through the steps together to solidify your understanding.

Let's reconstruct that derivation step-by-step to ensure it's crystal clear.

1. Start with the definition of the new mean, ${\mu }_n$:
   ${\mu }_n=\frac{1}{n}{\sum }_{i=1}^n{x}_i$

2. Split the sum into two parts: the sum of the first $n-1$ elements and the new $n$-th element.
   ${\mu }_n=\frac{1}{n}\left(\left({\sum }_{i=1}^{n-1}{x}_i\right)+x_n\right)$

3. Recognize the definition of the old mean, ${\mu }_{n-1}$. We know that ${\mu }_{n-1}=\frac{1}{n-1}{\sum }_{i=1}^{n-1}{x}_i$. Rearranging this gives us ${\sum }_{i=1}^{n-1}{x}_i=(n-1){\mu }_{n-1}$.

4. Substitute this back into our equation for ${\mu }_n$:
   ${\mu }_n=\frac{1}{n}\left((n-1){\mu }_{n-1}+x_n\right)$

This is a perfectly valid recursive formula, but we can rearrange it into a more insightful form.

5. Rearrange the terms to isolate the old mean, ${\mu }_{n-1}$: $$\begin{array}{rl}{\mu }_n& =\frac{(n-1){\mu }_{n-1}+x_n}{n}\\ & =\frac{n{\mu }_{n-1}-{\mu }_{n-1}+x_n}{n}\\ & =\frac{n{\mu }_{n-1}}{n}+\frac{x_n-{\mu }_{n-1}}{n}\\ & ={\mu }_{n-1}+\frac{x_n-{\mu }_{n-1}}{n}\end{array}$$

This final equation is the recursive update rule for the mean:

${\mu }_n={\mu }_{n-1}+\frac{x_n-{\mu }_{n-1}}{n}$

3. Interpreting the Formula

This formula is more than just an algebraic trick. It provides a profound insight into how learning and updating can work.

New Mean = Old Mean + Correction Term

The term $(x_n-{\mu }_{n-1})$ represents the "error" or "surprise" of the new data point relative to our previous running average. The formula tells us to update our old mean by adding a fraction of this error. The fraction $\frac{1}{n}$ acts like a learning rate that decreases as we gain more confidence in our estimate of the mean.

This structure is a common pattern in many machine learning and optimization algorithms, including Stochastic Gradient Descent (SGD), where you update model weights based on the error of a single data point.

The practical benefits are immense:

• Time Complexity: Each update is an O(1) operation (a few simple arithmetic steps), regardless of how many data points you've already processed.
• Space Complexity: You only need to store three values: the current count ($n$), the current mean (${\mu }_n$), and (as we'll see later) one other value for the variance. This is O(1) space complexity. You can process a dataset of virtually any size without running out of memory.

Conclusion

In this lesson, we took the first crucial step toward building Welford's algorithm. We moved from a "batch" mindset to an "online" one, which is essential for handling large-scale or streaming data.

Key Takeaways:

• An online algorithm updates its results incrementally as each new data point arrives, without needing the entire dataset.
• The recursive formula for updating the mean is ${\mu }_n={\mu }_{n-1}+\frac{x_n-{\mu }_{n-1}}{n}$.
• This formula can be interpreted as updating the old estimate with a small correction based on the "surprise" of the new data point.
• This update rule is highly efficient, requiring constant time and memory for each new data point.

Preview of the Next Lesson:

We have successfully derived the recursive update for the mean. However, our ultimate goal is to compute variance in a stable way. The mean update is just a stepping stone. In the next lesson, we will tackle the core of Welford's method: deriving the recursive update rule for the sum of squared differences from the mean. This is the component that ingeniously avoids the catastrophic cancellation that plagued the naive formula.