Online-Varianzschätzung mit begrenztem Speicher

Ich erstelle eine Komponente, die darauf abzielt, den Durchschnitt und die Varianz einer Metrik zu berechnen, die mit Ereignissen verbunden ist, die während der Zeit auftreten, aber mit einem begrenzten internen Speicher.

Stellen Sie sich vor, die Ereignisse sind Besucher, die einen Laden betreten, und die Metrik entspricht ihrem Alter.

Im Laufe der Zeit erhält meine Komponente Ereignisse mit dem Alter jedes Besuchers. Ich möchte nicht, dass meine Komponente die Geschichte jedes Zeitalters auswendig lernt. Idealerweise möchte ich nur eine leichte Komponente speichern: den Durchschnitt A, die Varianz V und die Anzahl der Ereignisse N.

Nach jedem Ereignis mit dem Alter Emöchte ich diese drei Werte aktualisieren:

N<=N+1
A<=(A*N+E)/(N+1)
V<=???

Wofür V? Ich denke an etwas wie:

V<=(V*N+(E-A)^2)/(N+1)

Ich weiß, dass es nicht genau ist, da mein Vorgänger Vdas Alte verwendet, Awas nicht mehr der Durchschnitt ist.

Q1 - Gibt es eine genaue Formel?
F2 - Wenn nicht, ist mein Vorschlag eine gute Schätzung? Ist es voreingenommen? Konvergiert es korrekt, wenn es Nzunimmt?
Q3 - Gibt es eine bessere Formel?

Ein guter und einfacher Algorithmus zur Online-Berechnung der Varianz wurde von Welford (1962) beschrieben. Unten sehen Sie die C ++ / Rcpp-Implementierung, die offline funktioniert, aber leicht an das Online-Szenario angepasst werden kann:

List welford_cpp(NumericVector x) {

  int n = x.length();
  double delta;
  double msq = 0;
  double mean = x[0];

  if (n > 1) {
    for (int i = 1; i < n; i++) { 
      delta = x[i] - mean;
      mean += delta / (i+1);
      msq += delta * (x[i] - mean);
    }
    return Rcpp::List::create(Rcpp::Named("mean") = mean,
                              Rcpp::Named("variance") = msq / (n-1));
  }

  return Rcpp::List::create(Rcpp::Named("mean") = mean,
                            Rcpp::Named("variance") = NAN);
}

Wie Sie sehen können, braucht es nur vier Variablen speichern: n, delta, msqund meanund berechnet Mittelwert und die Varianz gleichzeitig , wie man wollte.

---

Welford, BP (1962). Hinweis zu einer Methode zur Berechnung korrigierter Summen von Quadraten und Produkten . Technometrics 4 (3): 419 & ndash; 420.

Die Varianz kann als proportional zur quadratischen Differenz zwischen jedem Wert und dem Mittelwert ausgedrückt werden oder (wie viele Threads hier in stats.SE dokumentiert sind, wie diese Antwort, die ich auf eine andere Frage geschrieben habe) alternativ als proportional zum Quadrat ausgedrückt werden paarweiser Unterschied zwischen jeder Probe.

Wir wissen also:

$$\text {Var}(x) = \frac{1}{n} \cdot \sum_{i}(X_i-\overline{X})^2 = \frac{1}{2n^2} \cdot \sum_{i,j}(X_i-X_j)^2$$

Angenommen, Sie fügen ein weiteres Beispiel hinzu, das als letzter Index indiziert ist, . Ihre vorherige Abweichung wäre:$k$

$$\text {Var}_{old}(x) = \frac{1}{2(n-1)^2} \cdot \sum_{i<k,j<k}(X_i-X_j)^2$$

Ihre neue Varianz ist

$$\text {Var}_{new}(x) = \frac{1}{2n^2} \cdot \sum_{i,j}(X_i-X_j)^2 = \frac{1}{2n^2} \cdot \left( \sum_{i<k,j<k}(X_i-X_j)^2 + \sum_{j<k}(X_k-X_j)^2 + \sum_{i<k}(X_i-X_k)^2 \right)$$

Aber

$$\sum_{j<k}(X_k-X_j)^2 = \sum_{i<k}(X_i-X_k)^2\\ \sum_{i<k,j<k}(X_i-X_j)^2 = {2(n-1)^2} \cdot \text {Var}_{old}(x)$$

Damit

$$\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2} \sum_{j<k}(X_k-X_j)^2$$

Wie @ MarkL.Stone in den Kommentaren sagte, ist dies immer noch nicht effizient, da wir jedes behalten müssen . Erweitern wir also die Formel, um zu etwas Traktablerem zu gelangen.$X_i$

$$\frac{1}{n^2}\sum_{j<k}(X_k-X_j)^2=\\ \frac{1}{n^2}\sum_{j<k}(X_k^2 - 2 \cdot X_j \cdot X_k + X_j^2)=\\ \frac{1}{n^2}\left(\sum_{j<k}X_k^2 - 2 \cdot X_k \cdot \sum_{j<k} X_j + \sum_{j<k} X_j^2\right)=\\ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \overline{X^2_{old}}\right)\\ $$ Weil $$\sum_{j<k} X_j = (k-1) \cdot \overline{X_{old}}\\ \sum_{j<k} X_j^2 = (k-1) \cdot \overline{X^2_{old}}$$

Die endgültige Form ist dann

$$\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \overline{X^2_{old}}\right)$$

Sie können diese Formel verwenden, um die Varianz in Bezug auf den Speicher effektiv zu aktualisieren. Sie können es auch ergänzen, um Stapel anstelle von Einzelpunktaktualisierungen zu verwenden.

Grundsätzlich müssen Sie den Durchschnitt, den Durchschnitt der quadratischen Stichproben und die Varianz bei jeder Iteration speichern und zum Aktualisieren der Varianzformel verwenden.

---

Des Weiteren

$$\overline{X^2_{old}} = \text{Var}_{old}(x) + (\overline{X_{old}})^2\\ \therefore\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \left(\text{Var}_{old}(x) + (\overline{X_{old}})^2\right)\right)$$

Dies reduziert die Anzahl der Mengen, die gelagert werden müssen, auf 2.

OK Andy W gab die Antwort. Indem Sie den Durchschnitt auf die gleiche Weise wie den E-Durchschnitt , können Sie .$E^2$$V = exp(E^2)-exp(E)^2$