Robuste mittlere Schätzung mit O (1) -Updateeffizienz

9

Ich suche eine robuste Schätzung des Mittelwerts, der eine bestimmte Eigenschaft hat. Ich habe eine Reihe von Elementen, für die ich diese Statistik berechnen möchte. Dann füge ich nacheinander neue Elemente hinzu und möchte für jedes weitere Element die Statistik neu berechnen (auch als Online-Algorithmus bezeichnet). Ich möchte, dass diese Aktualisierungsberechnung schnell ist, vorzugsweise O (1), dh nicht abhängig von der Größe der Liste.

Das übliche Mittel hat die Eigenschaft, dass es effizient aktualisiert werden kann, aber für Ausreißer nicht robust ist. Typische robuste Schätzer des Mittelwerts wie der Interquartilmittelwert und der getrimmte Mittelwert können nicht effizient aktualisiert werden (da eine sortierte Liste erforderlich ist).

Ich würde mich über Vorschläge für robuste Statistiken freuen, die effizient berechnet / aktualisiert werden können.

Bitweise
quelle
Warum nicht einfach ein erstes Segment der Daten verwenden - wie die ersten 100 oder die ersten 1000 oder was auch immer -, um "Zäune" ​​für das Screening von Ausreißern zu errichten? Sie müssen sie nicht erneut aktualisieren, sodass keine zusätzlichen Datenstrukturen verwaltet werden müssen.
whuber
@whuber Ich kann nicht garantieren, dass die erste Stichprobe den Rest der Daten darstellt. Zum Beispiel ist die Reihenfolge, in der ich die Daten erhalte, nicht zufällig (stellen Sie sich ein Szenario vor, in dem mir zuerst höhere und dann niedrigere Werte gegeben werden).
Bitwise
1
Das ist eine entscheidende Beobachtung. Dies bedeutet, dass Sie mehr Sorgfalt walten lassen müssen als gewöhnlich, da Sie zunächst eine "robuste" Schätzung der mittleren hohen Ausreißer erhalten. Wenn Sie diese Schätzung weiter aktualisieren, können Sie alle niedrigeren Werte verwerfen. Daher benötigen Sie eine Datenstruktur, in der wichtige Teile der gesamten Datenverteilung aufgezeichnet und regelmäßig aktualisiert werden. Schauen Sie sich unsere Threads mit den Schlüsselwörtern "online" und "quantile" für Ideen an. Zwei solche vielversprechenden finden Sie unter stats.stackexchange.com/questions/3372 und stats.stackexchange.com/q/3377 .
whuber
Ich würde ein Kopfgeld anbieten, aber ich habe nicht genug Ruf
Jason S
1
Um mit der Idee in @ whubers erstem Kommentar fortzufahren, können Sie aus allen bisher gesehenen Daten eine gleichmäßig abgetastete zufällige Teilmenge der Größe oder 1000 beibehalten . Dieser Satz und die zugehörigen "Zäune" ​​können in O (1) -Zeit aktualisiert werden. 1001000
Innuo

Antworten:

4

Diese Lösung implementiert einen Vorschlag von @Innuo in einem Kommentar zur Frage:

Sie können aus allen bisher angezeigten Daten eine gleichmäßig abgetastete zufällige Teilmenge der Größe 100 oder 1000 beibehalten. Dieser Satz und die zugehörigen "Zäune" ​​können in -Zeit aktualisiert werden.O(1)

Sobald wir wissen, wie diese Teilmenge beibehalten werden kann, können wir eine beliebige Methode auswählen , um den Mittelwert einer Population aus einer solchen Stichprobe zu schätzen. Dies ist eine universelle Methode, bei der keinerlei Annahmen getroffen werden und die mit jedem Eingabestream mit einer Genauigkeit funktioniert , die unter Verwendung statistischer Standardstichprobenformeln vorhergesagt werden kann. (Die Genauigkeit ist umgekehrt proportional zur Quadratwurzel der Stichprobengröße.)


x(t), t=1,2,,ms(t)X(t)=(x(1),x(2),,x(t))1its(i)mX(t)

m{1,2,,t}xs(t)x(i), 1i<t,s(t)m/ttm

m

t=m+1s(t)X(t)t>ms(t+1)=s(t)U(t+1)s(t)U(t+1)m/(t+1)sx(t+1)

x(t+1)m/(t+1)s(t+1)x(i)m/ts(t)itm/(t+1)×1/m1/(t+1)s(t+1)

mt(11t+1)=mt+1,

x(i)s(t)

O(1)mO(m)

stX(t)s=X(m)t=m+1,m+2,.R(s,t)x(s,t+1)ntsample.sizemt

update <- function(s, x, n, sample.size) {
  if (length(s) < sample.size) {
    s <- c(s, x)
  } else if (runif(1) <= sample.size / n) {
    i <- sample.int(length(s), 1)
    s[i] <- x
  }
  return (s)
}

s(t)X(t)m=50

n <- 10^3
x <- sapply(1:(7*n), function(t) cos(pi*t/n) + 2*floor((1+t)/n))
n.sample <- 50
s <- x[1:(n.sample-1)]
online <- sapply(n.sample:length(x), function(i) {
  s <<- update(s, x[i], i, n.sample)
  summary(s)})
actual <- sapply(n.sample:length(x), function(i) summary(x[1:i]))

online50actualactual

plot(x, pch=".", col="Gray")
lines(1:dim(actual)[2], actual["Mean", ])
lines(1:dim(online)[2], online["Mean", ], col="Red")

Zahl


Für zuverlässige Schätzer des Mittelwerts durchsuchen Sie bitte unsere Website nach und verwandten Begriffen. Zu den erwägenswerten Möglichkeiten zählen Winsorized-Mittel und M-Schätzer.

whuber
quelle
Mir ist nicht klar, wie die Ablehnungsschwelle bei diesem Ansatz aussieht (z. B. die Schwelle, ab der Beobachtungen als Ausreißer abgelehnt werden). Können Sie sie dem Plot hinzufügen?
user603
@ user603 Der "Ablehnungsschwellenwert" oder eine robuste Methode zur Schätzung des Mittelwerts ist irrelevant: Wählen Sie die Methode aus, mit der Sie den Mittelwert schätzen möchten. (Nicht alle robusten Methoden arbeiten, indem sie Schwellenwerte festlegen und Daten ablehnen, übrigens.) Dies würde im Code meiner Antwort durch Ersetzen summarydurch eine robuste Variante erfolgen.
whuber
In diesem Beispiel ist mir etwas nicht klar. Sind die grauen Daten "gut" oder "Ausreißer"? Wenn dies der Fall ist, scheint die Anpassung voreingenommen zu sein (sie sollte besser zu ihnen passen, da die Situation dem Abwärtstrend von @ Bitwise ähnlich wäre, dem wir folgen möchten). Wenn die Graudaten bei höheren Indexwerten Ausreißer sind, scheint die Anpassung nach oben verzerrt zu sein. Was ist das Ziel, das Sie hier passen möchten? Die aktuelle Anpassung scheint zwischen diesen beiden Szenarien hin und her gerissen zu sein.
Deathkill14
@Death Wie im Text unmittelbar vor der Abbildung erläutert, sind die grauen Daten der ursprüngliche Datenstrom. Sein laufender Mittelwert ist die schwarze Kurve. Die farbigen Kurven basieren auf dem Algorithmus. Vertikale Abweichungen der farbigen Kurven relativ zur schwarzen Kurve sind auf die Zufälligkeit bei der Stichprobe zurückzuführen. Der erwartete Betrag der Abweichung bei einem Index ist proportional zur Standardabweichung der Grauwerte vor diesem Index und umgekehrt proportional zur Quadratwurzel der Stichprobengröße (in diesem Beispiel als 50 angenommen).
whuber
3

Sie könnten daran denken, Ihr Problem mit dem des rekursiven Kontrolldiagramms in Beziehung zu setzen. Ein solches Kontrolldiagramm bewertet, ob eine neue Beobachtung die Kontrolle hat. Wenn dies der Fall ist, wird diese Beobachtung in die neue Schätzung des Mittelwerts und der Varianz einbezogen (erforderlich zur Bestimmung der Kontrollgrenzen).

Einige Hintergrundinformationen zu robusten, rekursiven, univariaten Kontrolldiagrammen finden Sie hier . Einer der klassischen Texte zur Qualitätskontrolle und zu Kontrollkarten scheint hier online verfügbar zu sein .

μt1σt12txtμt1σt12)Dies kann jedoch zu Problemen führen, wenn die Daten bestimmten Verteilungsannahmen nicht entsprechen. Wenn Sie diesen Weg gehen möchten, nehmen wir an, Sie haben festgestellt, ob ein neuer Punkt kein Ausreißer ist, und möchten ihn ohne besondere Vergessensrate in Ihre mittlere Schätzung aufnehmen. Dann können Sie es nicht besser machen als:

μt=t1tμt1+1txt

Ebenso müssen Sie die Varianz rekursiv aktualisieren:

σt2=t1tσt12+1t1(xtμt)2

μμσ2

In Bezug auf ein Diagramm wie das EWMA, das alte Beobachtungen vergisst und neuen mehr Gewicht verleiht, müssen Sie ältere Beobachtungen nicht exponentiell vergessen, wenn Sie der Meinung sind, dass Ihre Daten stationär sind (dh die Parameter der Erzeugungsverteilung ändern sich nicht). Sie können den Vergessensfaktor entsprechend einstellen. Wenn Sie jedoch der Meinung sind, dass es sich um eine Nichtstationarität handelt, müssen Sie einen guten Wert für den Vergessensfaktor auswählen (eine Möglichkeit hierzu finden Sie im Lehrbuch).

μ0σ02

Ich denke, ein Ansatz in dieser Richtung wird zur schnellsten Aktualisierung Ihres Problems führen.

Deathkill14
quelle
1
xt=cos(πt/106)+2t/106
@Bitwise sagt, dass die erste Stichprobe möglicherweise keine zukünftigen Daten darstellt. Ohne Informationen darüber, wie unterschiedlich der Rest der Daten sein wird, können Sie im Wesentlichen nichts tun. Wenn die anfänglichen Daten jedoch Informationen über die Nichtstationarität des Prozesses enthalten (z. B. einen Abwärtstrend), können neue Beobachtungen zugelassen werden, um die Tatsache zu berücksichtigen, dass wir davon ausgehen, dass sie niedriger sind. Es werden jedoch einige Informationen zur Nichtstationarität benötigt. Sie schlagen eine pathologische Art der Nichtstationarität vor. Einige Methoden, z. B. die EWMA, sind für einen bestimmten Prozess optimal, aber im Allgemeinen ziemlich gut. Ihr Prozess würde einen benutzerdefinierten Job erfordern.
Deathkill14
(Ich erkenne einen Mathematiker in dir, weil es ein sehr mathematischer Schritt ist, etwas als "pathologisch" abzutun, mit dem du nicht umgehen kannst :-). Aber ich bin anderer Meinung als Ihre Prognose: Methoden wie die von @Innuo vorgeschlagenen können tatsächlich vor solchen "Pathologien" und allem anderen schützen, was die reale Welt auf Sie werfen könnte, insbesondere wenn die Randomisierung in die Stichprobe einbezogen wird.
whuber
Eigentlich stimme ich zu, dass man ein Problem, mit dem man konfrontiert ist, nicht abweisen sollte. Könnten Sie mich bitte mit den besprochenen Methoden @Innuo verknüpfen (ich kann sie in diesem Beitrag nicht finden - befanden sie sich in den oben angegebenen Links und ich habe sie verpasst?). Vielen Dank.
Deathkill14
O(1)