algorithm - 计算 "moving"协方差

Question

我一直在尝试弄清楚如何有效地计算移动窗口中的协方差，即从一组值 (x[0], y[0])..(x[n-1], y[n-1]) 到一组新值 (x[1], y[1])..(x[n], y[n])。换句话说，值 (x[0], y[0]) 被值 (x[n], y[n]) 替换。出于性能原因，我需要在我想表达新协方差 Cov(x[1]..x[n], y[1]..y[n]) 的意义上逐步计算协方差先前的协方差 Cov(x[0]..x[n-1], y[0]..y[n-1]).

从这里描述的朴素的协方差公式开始:

[ https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Covariance][1]

我能想到的是:

Cov(x[1]..x[n], y[1]..y[n]) =
Cov(x[0]..x[n-1], y[0]..y[n-1]) +
(x[n]*y[n] - x[0]*y[0]) / n -
AVG(x[1]..x[n]) * AVG(y[1]..y[n]) +
AVG(x[0]..x[n-1]) * AVG(y[0]..y[n-1])

我对符号感到抱歉，我希望它或多或少能清楚我想表达的意思。

但是，我不确定这在数值上是否足够稳定。处理大值时，我可能会遇到算术溢出或其他(例如取消)问题。

有更好的方法吗？

感谢您的帮助。

Answer 1

看起来您正在尝试某种形式的“添加新值并减去旧值”。您的担心是正确的:此方法在数值上不稳定。以这种方式求和容易发生漂移，但真正的 killer 是这样一个事实，即在每一步，您都在从另一个大数中减去一个大数，得到的可能是一个非常小的数。

一个改进是独立维护您的总和(x_i、y_i 和 x_i*y_i)，并重新计算原始公式从他们的每一步。你的运行总和仍然会漂移，朴素的公式在数值上仍然不稳定，但至少你只有一步数值不稳定。

解决此问题的一种稳定方法是实现用于(稳定地)合并统计集的公式，并使用合并树评估整体协方差。移动你的窗口会更新你的一个叶子，需要更新从那个叶子到根的每个节点。对于大小为 n 的窗口，此方法每次更新将花费 O(log n) 时间，而不是 O(1) 天真的计算，但结果将是稳定和准确的。此外，如果您不需要每个增量步骤的统计信息，您可以为每个输出样本更新一次树，而不是每个输入样本更新一次。如果每个输出样本有 k 个输入样本，这会将每个输入样本的成本降低到 O(1 + (log n)/k)。

来自评论:您引用的维基百科页面包括关于 Knuth 在线算法的部分，该部分 相对稳定，但仍然容易出现偏差。您应该能够为协方差做一些类似的事情；并且每 K*n 个样本重置计算应该以最小的成本限制漂移。