Dlaczego średnio każda próbka bootstrap zawiera około dwie trzecie obserwacji?


42

Mam natknąć się na twierdzeniu, że każda próbka bootstrap (lub workach drzewa) będą zawierały średnio około 2/3 z obserwacjami.

I zrozumieć, że prawdopodobieństwo nie wybiera się w jednym z n czerpie n próbek z wymianą jest (11/n)n , co przekłada się na około 1/3 przypadek nie zostanie wybrane.

Co jest matematycznym wyjaśnienie dlaczego ta formuła zawsze daje 1/3 ?


10
Wierzę, że to jest początek .632 w regule bootstrap 632+.
gung - Przywróć Monikę

Odpowiedzi:


29

limn(11/n)n=e1
e1=1/e1/3

Nie działa przy bardzo małym - np. Przy , . Przechodzi przy , przechodzi przy , a przez . Gdy przekroczysz , jest lepszym przybliżeniem niż .nn=2(11/n)n=1413n=60.35n=110.366n=99n=111e13

wprowadź opis zdjęcia tutaj

Szara linia przerywana to ; czerwona i szara linia to .131e

Zamiast przedstawiać formalne wyprowadzenie (które można łatwo znaleźć), przedstawię zarys (jest to intuicyjny, praktyczny argument), dlaczego (nieco) bardziej ogólny wynik zawiera:

ex=limn(1+x/n)n

(Wiele osób podejmuje to być definicja z , ale można to udowodnić z prostszych wyników takich jak definiowanie jako .)exp(x)elimn(1+1/n)n

Fakt 1: Wynika to z podstawowych wyników na temat mocy i potęgowaniaexp(x/n)n=exp(x)

Fakt 2: Gdy jest duże, Wynika to z rozszerzenia szeregu dla .nexp(x/n)1+x/nex

(Mogę podać pełniejsze argumenty dla każdego z nich, ale zakładam, że już je znasz)

Zastępuje (2) w (1). Gotowy. (Aby działało to jako bardziej formalny argument, zajęłoby trochę pracy, ponieważ musiałbyś wykazać, że pozostałe warunki w Fakcie 2 nie stają się wystarczająco duże, aby spowodować problem, gdy przejmie się władzę . Ale to intuicja zamiast formalnego dowodu).n

[Alternatywnie, po prostu weź serię Taylora dla do pierwszego rzędu. Drugim łatwym podejściem jest wzięcie dwumianowego rozszerzenia i przyjęcie limitu termin po semestrze, pokazując, że daje on warunki w szeregu dla .]exp(x/n)(1+x/n)nexp(x/n)

Więc jeśli , wystarczy podstawić .ex=limn(1+x/n)nx=1

Natychmiast mamy wynik u góry tej odpowiedzi:limn(11/n)n=e1


Jak wskazuje Gung w komentarzach, wynikiem twojego pytania jest pochodzenie reguły 632 bootstrap

np. patrz

Efron, B. i R. Tibshirani (1997),
„Improvements on Cross-Validation: The .632+ Bootstrap Method”,
Journal of the American Statistics Association Vol. 92, nr 438. (Jun), s. 548–560


41

Dokładniej, każda próbka bootstrap (lub spakowane drzewo) będzie zawierać próbki.11e0.632

Zobaczmy, jak działa bootstrap. Mamy oryginalną próbkę z elementami w niej. Rysujemy elementy z zamiennikiem z tego oryginalnego zestawu, dopóki nie otrzymamy innego zestawu o rozmiarze .x1,x2,xnnn

Z tego wynika, że ​​prawdopodobieństwo wybrania dowolnego elementu (powiedzmy ) przy pierwszym losowaniu wynosi . Dlatego prawdopodobieństwo nie wybrania tego elementu wynosi . To tylko pierwsze losowanie; jest w sumie losowań, z których wszystkie są niezależne, więc prawdopodobieństwo, że nigdy nie wybierzesz tego elementu na żadnym z losowań, wynosi .x11n11nn(11n)n

Zastanówmy się teraz, co się stanie, gdy coraz większe. Możemy przyjąć limit, gdy idzie w kierunku nieskończoności, używając zwykłych sztuczek rachunku różniczkowego (lub Wolfram Alpha): nn

limn(11n)n=1e0.368

Takie jest prawdopodobieństwo, że element nie zostanie wybrany. Odejmij go od jednego, aby znaleźć prawdopodobieństwo wyboru przedmiotu, co daje 0,632.


5

Pobieranie próbek z wymianą można modelować jako sekwencję prób dwumianowych, w których wybierany jest „sukces”. Dla oryginalnego zestawu danych instancji prawdopodobieństwo „sukcesu” wynosi , a prawdopodobieństwo „awarii” wynosi . Dla wielkości próbki prawdopodobieństwo wybrania instancji dokładnie razy daje rozkład dwumianowy:n1/n(n1)/nbx

P(x,b,n)=(1n)x(n1n)bx(bx)

W konkretnym przypadku próbki ładowania początkowego wielkość próbki jest równa liczbie instancji . Pozwalając zbliżyć się do nieskończoności, otrzymujemy:bnn

limn(1n)x(n1n)nx(nx)=1ex!

Jeśli nasz oryginalny zestaw danych jest duży, możemy użyć tej formuły do ​​obliczenia prawdopodobieństwa, że ​​wystąpienie zostanie wybrane dokładnie razy w próbce ładowania początkowego. Dla prawdopodobieństwo wynosi lub około . Prawdopodobieństwo, że próbka zostanie co najmniej raz pobrana, wynosi zatem .xx=01/e0.36810.368=0.632

Nie trzeba dodawać, że skrupulatnie wyprowadziłem to z pióra i papieru i nawet nie rozważałem użycia Wolfram Alpha.


3

Dodając do odpowiedzi @ retsreg, można to również dość łatwo zademonstrować za pomocą symulacji numerycznej w R:

N <- 1e7 # number of instances and sample size
bootstrap <- sample(c(1:N), N, replace = TRUE)
round((length(unique(bootstrap))) / N, 3)
## [1] 0.632

1

Można to łatwo zliczyć. Ile wszystkich możliwych próbek? n ^ n. Ile NIE zawiera określonej wartości? (n-1) ^ n. Prawdopodobieństwo, że próbka nie będzie miała określonej wartości - (1-1 / n) ^ n, co stanowi około 1/3 granicy.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.