Wahl des Algorithmus für inkrementelle Gleitkomma-Mittelwert (Java)

Question

Ich möchte den Mittelwert eines Doppelstroms berechnen. Dies ist eine einfache Aufgabe, die nur das Speichern eines double und eines int erfordert. Ich habe dies mit der Apache Commons SummaryStatistics Klasse getan. Beim Testen habe ich jedoch gemerkt, dass die ZusammenfassungStatistiken Gleitkommafehler hatten, die meine eigene Python-Implementierung nicht hatte. Bei einer weiteren Untersuchung fand ich heraus, dass Gemeingut werden mit einer Version des folgenden Algorithmus:

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

Dies führt manchmal zu kleinen Fließkommafehlern z.B.

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

Dies ist auch der mittlere Algorithmus, der vom Guava-Dienstprogramm DoubleMath.mean verwendet wird. Es scheint mir seltsam, dass sie beide den obigen Algorithmus verwenden anstelle dem naiven Algorithmus:

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 

Es gibt zwei Gründe, warum ich für von begreifen kann, warum man könnte den früheren Algorithmus bevorzugen. Eine davon ist, dass wenn man den Mittelwert während des Streamings abfragt, es effizienter ist, nur einen Wert zu kopieren, als eine Division durchzuführen, außer es scheint, dass der Aktualisierungsschritt signifikant langsamer ist, was diese Kosten fast immer überwiegen würde (Anmerkung Ich habe den Unterschied nicht wirklich gemessen.

Die andere Erklärung ist, dass ersteres Überlaufprobleme verhindert. Bei Gleitkommazahlen scheint dies nicht der Fall zu sein, dies sollte allenfalls zu einer Verschlechterung des Mittelwerts führen. Wenn dieser Fehler der Fall ist, sollten wir in der Lage sein, die Ergebnisse mit demselben cumMean zu vergleichen, der mit der BigDecimal-Klasse durchgeführt wurde. Daraus ergibt sich die folgende Funktion:

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(); 
} 

Dies sollte vernünftigerweise das genaueste Mittel sein, das wir bekommen konnten. Von einigen anekdotischen Läufen des folgenden Codes scheint es keinen signifikanten Unterschied zwischen entweder dem gemeinen und dem genauesten zu geben. Anekdotisch neigen sie dazu, sich von dem genauen Mittelwert an der Ziffer zu unterscheiden, und keiner ist immer näher als der andere.

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 

Hat jemand eine Begründung, warum beide Apache Commons und Guave die frühere Methode anstelle des letzteren entschieden?

Edit: Die Antwort auf meine Frage scheint klar zu sein, die Antwort ist, dass Knuth es in der Kunst der Programmierung Bd. II vorgeschlagen hat. 4.2.2 (15) (Dank Louis Wasserman für den Tipp auf die Guava-Quelle zu sehen). In dem Buch schlägt Knuth diese Methode vor, um das Mittel zu berechnen, um eine robuste Berechnung der Standardabweichung zu starten, nicht unbedingt, dass dies die optimale Durchschnittsberechnung ist. Basierend auf mehr des Kapitels lesen ich ein viertes Mittel umgesetzt:

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; 
} 

Durchführen der gleichen Tests wie oben (ein paar Mal, nichts statistisch signifikant), erhalte ich genau das gleiche Ergebnis wie die BigDecimal Umsetzung. Ich kann mir vorstellen, dass die knuth mittlere Aktualisierung schneller ist als die Verwendung der komplizierteren Summationsmethode, aber die kompliziertere Methode scheint empirisch genauer bei der Schätzung des Mittelwerts zu sein, was ich naiverweise erwarten würde, dass auch bessere Standardabweichungsaktualisierungen resultieren. Gibt es einen anderen Grund, die knuth-Methode zu verwenden, als dass sie wahrscheinlich schneller ist?

Answer 1

Kurze Antwort: Der inkrementelle Update-Ansatz wird als Standard bevorzugt, da er numerische Fehler vermeidet und nicht so viel mehr Zeit/Platz benötigt als der Summen-und-Teile-Ansatz.

Der Ansatz der inkrementellen Aktualisierung ist numerischer stabil, wenn der Durchschnitt einer großen Anzahl von Proben genommen wird. Sie können sehen, dass in incMean alle Variablen immer in der Reihenfolge eines typischen Datenwerts sind; In der summierten Version ist jedoch die Variable sum der Reihenfolge N*mean, dieser Skalenunterschied kann aufgrund der endlichen Genauigkeit der Fließkomma-Mathematik Probleme verursachen.

Im Fall von float 's (16Bits) kann man künstliche Problemfälle konstruieren: z.B. einige seltene Beispiele sind O(10^6) und der Rest sind O(1) (oder kleiner), oder allgemein, wenn Sie Millionen von Datenpunkten haben, dann wird die inkrementelle Aktualisierung genauere Ergebnisse liefern.

Diese problematischen Fälle sind weniger wahrscheinlich mit double s (weshalb Ihre Testfälle alle ziemlich genau das gleiche Ergebnis liefern), aber für sehr große Datensätze mit einer großen Streuung von Werten könnten die gleichen numerischen Probleme auftauchen es ist eine allgemein anerkannte gute Praxis den inkrementellen Ansatz zur Einnahme mittelt verwenden

die Vorteile der Kahan method sind (und andere Momente!):

1. es gibt nur eine Teilungsoperation (inkrementeller Ansatz erfordert N Abteilungen),

2. Die funky, fast kreisförmige Mathematik ist eine Technik, um Fließkommafehler zu mindern, die bei der Brute-Force-Summation auftreten. Stellen Sie sich die Variable c als eine "Korrektur" vor, die auf die nächste Iteration angewendet werden soll.

jedoch ist es einfacher, den inkrementellen Ansatz zu programmieren (und zu lesen).