7

double のストリームの平均を計算したい。これは、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

これは、guava ユーティリティ 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

前者のアルゴリズムが好まれる理由として、2 つの理由が考えられます。1 つは、ストリーミング中に平均を何度もクエリする場合、除算を行うよりも値をコピーするだけでよい場合があることです。 、私は実際に違いを測定していません）。

他の説明は、前者がオーバーフローの問題を防ぐということです。これは実際には浮動小数点数には当てはまらないようで、せいぜいこれは平均値の低下につながるはずです。このエラーが発生した場合、結果を 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 commons と guava の両方が後者ではなく前者の方法を選択した理由について、正当な理由がある人はいますか?

編集:私の質問に対する答えは明らかです。答えは、Knuth が Art of Programming Vol II 4.2.2 (15) でそれを提案したことです (guava ソースを見るためのヒントを提供してくれた Louis Wasserman に感謝します)。ただし、本の中で、Knuth は、標準偏差のロバストな計算をブートストラップするために平均を計算するこの方法を提案していますが、必ずしもこれが最適な平均計算であるとは言いません。この章をさらに読んだことに基づいて、4番目の手段を実装しました。

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 メソッドを使用する他の理由はありますか?

4

1 に答える 1

2

簡単な答え: 増分更新アプローチは、数値エラーを回避し、合計と除算のアプローチよりも多くの時間/スペースを必要としないため、デフォルトとして推奨されます。

増分更新アプローチは、多数のサンプルの平均を取得する場合、数値的に安定しています。incMeanすべての変数が常に典型的なデータ値の順序になっていることがわかります。ただし、加算されたバージョンでは、変数sumは次数N*meanです。このスケールの違いは、浮動小数点演算の有限精度のために問題を引き起こす可能性があります。

's (16 ビット) の場合、float人為的な問題のケースを構築できます: たとえば、まれなサンプルはほとんどなくO(10^6)、残りはO(1)(またはそれより小さい)、または一般的に数百万のデータ ポイントがある場合、インクリメンタル更新はより正確な結果を提供します。

これらの問題のあるケースではdoubles を使用する可能性は低くなります (これが、すべてのテスト ケースでほぼ同じ結果が得られる理由です)。平均（およびその他の瞬間）を取得するために増分アプローチを使用する練習をします。

Kahan メソッドの利点は次のとおりです。

  1. 分割操作は 1 つだけです (インクリメンタル アプローチにはN分割が必要です)。

  2. ファンキーでほぼ循環的な計算は、力ずくの合計で発生する浮動小数点エラーを軽減する手法です。変数cを次の反復に適用する「修正」と考えてください。

ただし、インクリメンタル アプローチの方がコーディング (および読み取り) が容易です。

于 2014-06-03T19:35:34.953 に答える