半方差的鲁棒在线算法

Question

我正在寻找welford's algorithm的等价物，用于在线计算半方差(下行偏方差)。有没有人知道好的推荐信？这样的算法是否存在呢？

编辑:相对于固定目标采用半方差的情况是微不足道的。问题是计算与均值相关的半方差。

Answer 1

我相信答案是不存在的，我将尝试勾勒出为什么会这样的证据。

考虑由两个标准定义的“uesful”在线算法：

在processing.

• Each更新期间，

1. 必须具有固定的内存要求应花费固定的时间。

这比顺序/增量/在线算法的文字定义更严格，后者实际上只要求数据可以一次传递一块。然而，考虑到如果1)或2)不为真，那么在处理足够多的元素之后，运行算法所需的内存或所需的时间最终将变得不可行。通常，使用在线算法的原因之一是它们可以连续使用，而不用担心性能会慢慢变差。另外，请注意，有一些在线算法可以计算同时满足1和2的均值和方差，我认为这就是我们的目标。

现在来看一下提出的问题。在处理过程中，均值将随着新数据的每一位而变化。这反过来意味着低于均值的一组观察值将发生变化。当这种情况发生时，我们需要根据集合“增量”调整我们的运行半方差，“增量”定义为不在旧均值下的元素集和新均值下的元素集之间的并集的元素。在新数据存在的情况下，我们必须在将旧半方差调整为新半方差的过程中计算此增量。

现在让我们考虑一下计算这个集合增量的复杂性。我们需要找到所有介于旧均值和新均值之间的元素。我们将始终跟踪旧的平均值，而新的平均值可以在固定的时间内增量计算，因此它们不会造成问题。然而，要计算增量本身，除了要求我们跟踪集合中所有以前的元素之外，没有其他方法。这立即打破了在线算法的内存条件。其次，即使我们对集合中以前的元素进行排序，找到介于旧均值和新均值之间的元素的最佳速度也是O(log(元素数))，这比固定的速度更差。所以最终，有了足够的元素，在线算法不仅需要比我们拥有的更多的内存，而且还需要更多的时间。

Answer 2

http://www3.sympatico.ca/jean-v.cote/computation_of_semi-variance.pdf P.S.：这不是增量计算。我有另一个想法。我会和你保持联系的。

Answer 3

Here is an Adaptation of the Welford Method in order to Compute Semi-Variances