了解 Welford 在线算法的必要性

计算科学 算法 样本统计
2021-12-17 09:45:41

我对 Wikipedia 条目讨论许多用于计算样本方差的在线算法感到困惑,包括Welford 的在线算法

特别是样本方差sn2可以从样本中计算{X1,..,Xn}作为:

xn=n1nxn1+1nXn
sn2=n2n1sn12+1n(Xnxn1)2
需要注意的是

这些公式存在数值不稳定性,因为它们反复从一个随 n 缩放的大数中减去一个小数。

我可以看到,因为n第一项是方差的顺序,而第二项是 0。我可以看到浮点数的有限精度引起的数值问题。

该条目继续认为 Welford 的在线算法旨在解决此问题:

Mn2=Mn12+(Xnxn)(Xnxn1),sn2=Mn2n1.

我的问题是:它是如何解决的?我没有看到它发生。Mn12是看起来像第二个的项的总和,所以不仅容易溢出,而且相对于第二项变得太大,最终可能会小于最后一位Mn12. 在我看来,除了冒浮点溢出的风险之外,没有取得任何改进。

1个回答

维基百科是错误的。您引用的两个公式中的第一个实际上在数值上并不是不稳定的;他们只是将一个小数字添加到一个大数字中(这也是 Welford 公式所做的),只要您的浮点数中有足够的数字而不会失去太多的准确性,这是一件合理的事情。以今天的双精度浮点精度,您需要在n=1012样本,以便您得到少于 4 位数字的正确答案。在大多数情况下,这已经足够了。

维基百科页面应该与页面上的第一组公式进行 正确比较:

σ2=(x2)¯x¯2=i=1Nxi2(i=1Nxi)2/NN.
这个公式是不稳定的,因为它减去两个(通常)大小相等的数字,因此可能导致灾难性的数字取消。

作为旁注,我同意不要每次都除以大小的说法n不好,因为它会导致溢出。维基百科页面中关于 Welford 算法的部分中的第一组公式正确地做到了这一点。


维基百科,就像这个页面一样,是一个志愿者项目。您可能想借此机会更新那里的文字!