增量浮点均值算法的选择(java)

Question

我想计算双打流的平均值.这是一个简单的任务,只需要存储double和int.我是使用apache commons SummaryStatistics类做的.但是,在测试时我注意到SummaryStatistics意味着浮点错误,我自己的python实现没有.经过进一步检查,我发现公共区域正在使用以下算法的版本:

static double incMean(double[] data) {
    double mean = 0;
    int number = 0;
    for (double val : data) {
        ++number;
        mean += (val - mean) / number;
    }
    return mean;
}

这有时会导致小的浮点错误,例如

System.out.println(incMean(new double[] { 10, 9, 14, 11, 8, 12, 7, 13 }));
// Prints 10.500000000000002

这也是番石榴实用程序DoubleMath.mean使用的平均算法.我觉得他们都使用上面的算法而不是更天真的算法似乎很奇怪:

static double cumMean(double[] data) {
    double sum = 0;
    int number = 0;
    for (double val : data) {
        ++number;
        sum += val;
    }
    return sum / number;
}

System.out.println(cumMean(new double[] { 10, 9, 14, 11, 8, 12, 7, 13 }));
// Prints 10.5

我可以想到为什么人们可能更喜欢前一种算法,这有两个原因.一个是如果你在流媒体中大量查询平均值,那么只需要复制一个值而不是进行除法可能更有效率,除非看起来更新步骤明显更慢,这几乎总是超过这个成本(注意,我实际上没有时间差异).

另一种解释是前者可以防止溢出问题.浮点数似乎不是这种情况,最多这会导致均值降低.如果出现此错误,我们应该能够将结果与使用BigDecimal类完成的相同cumMean进行比较.这导致以下功能:

public static double accurateMean(double[] data) {
    BigDecimal sum = new BigDecimal(0);
    int num = 0;
    for (double d : data) {
        sum = sum.add(new BigDecimal(d));
        ++num;
    }
    return sum.divide(new BigDecimal(num)).doubleValue();
}

这应该是我们可以获得的最准确的平均值.从以下代码的一些轶事运行来看,平均值和最准确值之间似乎没有显着差异.有趣的是,它们往往与数字上的准确平均值不同,并且两者都不总是比另一个更接近.

Random rand = new Random();
double[] data = new double[1 << 29];
for (int i = 0; i < data.length; ++i)
    data[i] = rand.nextDouble();

System.out.println(accurateMean(data)); // 0.4999884843826727
System.out.println(incMean(data));      // 0.49998848438246
System.out.println(cumMean(data));      // 0.4999884843827622

有没有人有任何理由为什么apache公共和番石榴选择前一种方法而不是后者？

编辑:我的问题的答案似乎很明确,答案是Knuth在编程艺术第二卷4.2.2(15)中提出它(感谢Louis Wasserman提示看番石榴来源).然而,在本书中,Knuth提出了这种方法来计算平均值以引导标准偏差的稳健计算,不一定说这是最优平均值计算.基于阅读本章的更多内容,我实现了第四个意思:

static double kahanMean(double[] data) {
    double sum = 0, c = 0;
    int num = 0;
    for (double d : data) {
        ++num;
        double y = d - c;
        double t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }
    return sum / num;
}

执行与上面相同的测试(少数几次,没有任何统计意义),我得到与BigDecimal实现完全相同的结果.我可以想象,knuth意味着更新比使用更复杂的求和方法更快,但更复杂的方法似乎在经验上更准确地估计平均值,我天真地期望也会导致更好的标准偏差更新.有没有其他理由使用knuth方法,除了它可能更快？

Answer 1

简短的回答：增量更新方法是默认的首选方法，因为它可以避免数值错误，并且不会比求和除法方法花费更多的时间/空间。

当取大量样本的平均值时，增量更新方法在数值上更加稳定。您可以看到，incMean所有变量始终按典型数据值的顺序排列；然而，在求和版本中，变量sum是有序的N*mean，由于浮点数学的有限精度，这种比例差异可能会导致问题。

在 的情况下float（16 位），我们可以构造人工问题案例：例如，很少有稀有样本，O(10^6)其余的是O(1)（或更小），或者通常如果您有数百万个数据点，那么增量更新将提供更准确的结果。

这些有问题的情况不太可能使用doubles （这就是为什么您的测试用例都给出几乎相同的结果），但对于具有大量值的非常大的数据集，可能会出现相同的数值问题，因此它是普遍接受的好方法练习使用增量方法来取平均值（以及其他时刻！）

Kahan方法的优点是：

1. 只有一次除法运算（增量方法需要N除法），

2. 这种时髦的、几乎循环的数学是一种减少暴力求和中出现的浮点错误的技术。将变量视为c应用于下一次迭代的“修正”。

然而，增量方法更容易编码（和阅读）。