Solidne oszacowanie średnie z wydajnością aktualizacji O (1)

Szukam dokładnego oszacowania średniej, która ma określoną właściwość. Mam zestaw elementów, dla których chcę obliczyć tę statystykę. Następnie dodaję nowe elementy pojedynczo i dla każdego dodatkowego elementu chciałbym ponownie obliczyć statystyki (znane również jako algorytm online). Chciałbym, aby to obliczenie aktualizacji było szybkie, najlepiej O (1), tzn. Nie zależy od wielkości listy.

Zwykły środek ma tę właściwość, że może być skutecznie aktualizowany, ale nie jest odporny na wartości odstające. Typowe solidne estymatory średniej, takie jak średnia między kwartylami i średnia obcięta, nie mogą być skutecznie aktualizowane (ponieważ wymagają utrzymania posortowanej listy).

Byłbym wdzięczny za wszelkie sugestie dotyczące solidnych statystyk, które można skutecznie obliczać / aktualizować.

To rozwiązanie implementuje sugestię @Innuo w komentarzu do pytania:

Możesz zachować jednolicie próbkowany losowy podzbiór o wielkości 100 lub 1000 na podstawie wszystkich danych do tej pory obserwowanych. Ten zestaw i związane z nim „ogrodzenia” można zaktualizować w czasie .$O(1)$

Kiedy już wiemy, jak zachować ten podzbiór, możemy wybrać dowolną metodę, którą chcemy oszacować średnią populacji z takiej próby. Jest to metoda uniwersalna, nie zakładająca żadnych założeń, która będzie działać z dowolnym strumieniem wejściowym z dokładnością, którą można przewidzieć za pomocą standardowych wzorów statystycznego próbkowania. (Dokładność jest odwrotnie proporcjonalna do pierwiastka kwadratowego z wielkości próby).

Ten algorytm przyjmuje jako dane wejściowe strumień danych wielkość próbki , i wysyła strumień próbek z których każda reprezentuje populację . W szczególności dla , jest prostą losową próbką o rozmiarze z (bez zamiany).$x(t),$ $t=1, 2, \ldots,$$m$$s(t)$$X(t) = (x(1),x(2), \ldots, x(t))$$1\le i \le t$$s(i)$$m$$X(t)$

W tym stanie, wystarczy, że każdy -elementowe podzbiór mają równe prawdopodobieństwo być indeksów w . Oznacza to szansę, że jest w równa się pod warunkiem, że .$m$$\{1,2,\ldots,t\}$$x$$s(t)$$x(i),$ $1\le i\lt t,$$s(t)$$m/t$$t \ge m$

Na początku zbieramy strumień, dopóki nie zostanie zapisanych elementów. W tym momencie istnieje tylko jedna możliwa próbka, więc warunek prawdopodobieństwa jest trywialnie spełniony.$m$

Algorytm przejmuje, gdy . Indukcyjnie załóżmy, że jest prostą losową próbką dla . Wstępnie ustawione . Niech będzie jednolitą zmienną losową (niezależną od poprzednich zmiennych używanych do konstruowania ). Jeśli to zamień losowo wybrany element na . To cała procedura!$t=m+1$$s(t)$$X(t)$$t\gt m$$s(t+1) = s(t)$$U(t+1)$$s(t)$$U(t+1) \le m/(t+1)$$s$$x(t+1)$

Wyraźnie ma prawdopodobieństwo przebywania w . Ponadto, zgodnie z hipotezą indukcyjną, miało prawdopodobieństwo bycia gdy . Z prawdopodobieństwem = zostanie on usunięty ze , stąd prawdopodobieństwo pozostania równe$x(t+1)$$m/(t+1)$$s(t+1)$$x(i)$$m/t$$s(t)$$i\le t$$m/(t+1) \times 1/m$$1/(t+1)$$s(t+1)$

dokładnie w razie potrzeby. Dzięki indukcji wszystkie prawdopodobieństwa włączenia w są prawidłowe i jasne jest, że nie ma specjalnej korelacji między tymi wtrąceniami. To dowodzi, że algorytm jest poprawny.$x(i)$$s(t)$

Efektywność algorytmu wynosi ponieważ na każdym etapie obliczane są co najwyżej dwie liczby losowe i co najwyżej jeden element tablicy wartości jest zastępowany. Wymagane miejsce to .$O(1)$$m$$O(m)$

Struktura danych dla tego algorytmu składa się z próbki wraz z indeksem populacji , którą próbkuje. Początkowo bierzemy i postępujemy zgodnie z algorytmem dla Oto implementacja do aktualizacji o wartości do wyprodukowania . (Argument odgrywa rolę i jest . Indeks będzie utrzymywana przez dzwoniącego).$s$$t$$X(t)$$s = X(m)$$t=m+1, m+2, \ldots.$R$(s,t)$$x$$(s,t+1)$n$t$sample.size$m$$t$

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

Aby to zilustrować i przetestować, użyję zwykłego (nieelastycznego) estymatora średniej i porównuję średnią oszacowaną na podstawie z rzeczywistą średnią (skumulowany zestaw danych widoczny na każdym etapie ). Wybrałem nieco trudny strumień wejściowy, który zmienia się dość płynnie, ale okresowo przechodzi dramatyczne skoki. Wielkość próby jest dość mała, co pozwala nam zobaczyć fluktuacje próbkowania na tych wykresach.$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]))

W tym momencie onlinejest sekwencja średnich oszacowań uzyskanych przez utrzymanie tej bieżącej próbki wartości, podczas gdy jest sekwencją średnich oszacowań uzyskanych ze wszystkich danych dostępnych w każdym momencie. Wykres pokazuje dane (w kolorze szarym), (w kolorze czarnym) i dwa niezależne zastosowania tej procedury próbkowania (w kolorach). Umowa mieści się w oczekiwanym błędzie próbkowania:$50$actualactual

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

Aby uzyskać wiarygodne estymatory średniej, wyszukaj naszą stronę w poszukiwaniu odstającei powiązane warunki. Wśród możliwości wartych rozważenia są środki Winsorized i estymatory M.

Możesz pomyśleć o powiązaniu swojego problemu z problemem rekurencyjnej karty kontrolnej. Taki wykres kontrolny ocenia, czy nowa obserwacja jest pod kontrolą. Jeśli tak, to obserwacja ta jest uwzględniona w nowym oszacowaniu średniej i wariancji (niezbędnym do ustalenia limitów kontrolnych).

Niektóre informacje na temat solidnych, rekurencyjnych, jednowymiarowych wykresów kontrolnych można znaleźć tutaj . Jeden z klasycznych tekstów na temat kontroli jakości i tabel kontroli wydaje się być dostępny tutaj online .

Intuicyjnie, wykorzystując jako dane wejściowe średnią, i wariancję , możesz określić, czy nowa obserwacja w czasie jest wartością odstającą na podstawie wielu podejść. Można by zadeklarować wartość odstającą, jeśli jest ona poza pewną liczbą standardowych odchyleń (biorąc pod uwagę , ale może to mieć problemy, jeśli dane niezgodne z niektórymi założeniami dystrybucyjnymi. Jeśli chcesz iść tą drogą, załóżmy, że ustaliłeś, czy nowy punkt nie jest wartością odstającą, i chciałbyś uwzględnić go w swoich średnich szacunkach bez specjalnego wskaźnika zapominania. Nie możesz zrobić nic lepszego niż:$\mu_{t-1}$$\sigma^2_{t-1}$$t$$x_t$$\mu_{t-1}$$\sigma^2_{t-1})$

$\mu_t = \frac{t-1}{t}\mu_{t-1}+\frac{1}{t}x_t$

Podobnie musisz zaktualizować wariancję rekurencyjnie:

$\sigma^2_t = \frac{t-1}{t}\sigma^2_{t-1}+\frac{1}{t-1}(x_t-\mu_t)^2$

Możesz jednak wypróbować bardziej konwencjonalne tabele kontrolne. Zalecane są inne wykresy kontrolne, które są bardziej odporne na dystrybucję danych i mogą nadal obsługiwać niestacjonarność (np. twojego procesu powoli idzie wyżej), są EWMA lub CUSUM (więcej informacji na ten temat znajduje się w podręczniku do którego prowadzi link wykresy i ich granice kontroli). Metody te będą zwykle mniej obciążające obliczeniowo niż niezawodne, ponieważ mają tę zaletę, że po prostu muszą porównać jedną nową obserwację z informacjami uzyskanymi z obserwacji nietypowych. Możesz sprecyzować swoje szacunki dotyczące długoterminowego procesu i wykorzystywanego w obliczeniach limitów kontrolnych tych metod za pomocą formuł aktualizacyjnych podanych powyżej, jeśli chcesz.$\mu$$\mu$$\sigma^2$

Jeśli chodzi o wykres podobny do EWMA, który zapomina o starych obserwacjach i nadaje większą wagę nowym, jeśli uważasz, że twoje dane są nieruchome (co oznacza, że ​​parametry rozkładu generującego nie zmieniają się), nie ma potrzeby, by zapomnieć o starszych obserwacjach wykładniczo. Możesz odpowiednio ustawić współczynnik zapominania. Jeśli jednak uważasz, że to niestacjonarność, musisz wybrać dobrą wartość dla czynnika zapominania (ponownie zobacz podręcznik, jak to zrobić).

Powinienem również wspomnieć, że zanim zaczniesz monitorować i dodawać nowe obserwacje online, będziesz musiał uzyskać oszacowania i (początkowe wartości parametrów oparte na zbiorze danych szkoleniowych), na które nie mają wpływu wartości odstające. Jeśli podejrzewasz, że w danych treningowych występują wartości odstające, możesz zapłacić jednorazowy koszt użycia solidnej metody ich oszacowania.$\mu_0$$\sigma^2_0$

Myślę, że takie podejście doprowadzi do najszybszej aktualizacji Twojego problemu.