Warum enthält jede Bootstrap-Stichprobe im Durchschnitt ungefähr zwei Drittel der Beobachtungen?

42

Ich habe über die Behauptung ausgeführt , dass jede Bootstrap Probe (oder eingetütet Baum) im Durchschnitt enthält etwa 2/3 der Beobachtungen.

Ich verstehe , dass die Wahrscheinlichkeit , sich in keiner der ausgewählt ist n von zieht n Proben mit Ersatz ist (11/n)n , die etwa ausarbeitet 1/3 Chance, nicht ausgewählt zu werden.

Was ist eine mathematische Erklärung dafür , warum diese Formel immer gibt 1/3 ?

xyzzy
quelle
10
Ich glaube, das ist der Ursprung der .632 in der Bootstrap 632+ -Regel.
gung - Wiedereinsetzung von Monica

Antworten:

29

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

Es funktioniert nicht bei sehr kleinem - zB bei , . Es passiert bei , passiert bei und bei . Wenn Sie über hinausgehen , ist eine bessere Annäherung als .nn=2(11/n)n=1413n=60.35n=110.366n=99n=111e13

Bildbeschreibung hier eingeben

Die graue gestrichelte Linie befindet sich bei . Die rote und graue Linie befindet sich bei .131e

Anstatt eine formale Ableitung zu zeigen (die leicht gefunden werden kann), werde ich einen Umriss (das ist ein intuitives, handwaviges Argument) geben, warum ein (etwas) allgemeineres Ergebnis gilt:

ex=limn(1+x/n)n

(Viele Leute halten dies für die Definition von , aber Sie können es durch einfachere Ergebnisse wie die Definition von als beweisen .)exp(x)elimn(1+1/n)n

Fakt 1: Dies folgt aus grundlegenden Ergebnissen über Potenzen und Potenzierungexp(x/n)n=exp(x)

Fakt 2: Wenn groß ist, Dies folgt aus der Reihenerweiterung für .nexp(x/n)1+x/nex

(Ich kann zu jedem dieser Punkte ausführlichere Argumente anführen, aber ich gehe davon aus, dass Sie sie bereits kennen.)

Ersetzen Sie (2) in (1). Getan. (Damit dies als formelleres Argument funktioniert, ist etwas Arbeit erforderlich, da Sie zeigen müssen, dass die verbleibenden Terme in Fakt 2 nicht groß genug werden, um ein Problem zu verursachen, wenn sie zur Potenz . Aber das ist Intuition eher als formeller Beweis.)n

[Alternativ können Sie auch die Taylor-Reihe für zur ersten Ordnung nehmen. Ein zweiter einfacher Ansatz besteht darin, die Binomialerweiterung von nehmen und das Limit termweise zu bestimmen. Dabei werden die Terme in der Reihe für .]exp(x/n)(1+x/n)nexp(x/n)

Wenn also , ersetzen Sie einfach .ex=limn(1+x/n)nx=1

Wir haben sofort das Ergebnis oben in dieser Antwort:limn(11/n)n=e1


Wie Gung in Kommentaren ausführt, ist das Ergebnis Ihrer Frage der Ursprung der 632-Bootstrap-Regel

zB sehen

Efron, B. und R. Tibshirani (1997),
"Improvements on Cross-Validation: The .632+ Bootstrap Method",
Journal der American Statistical Association Vol. 92, Nr. 438. (Jun), S. 548-560

Glen_b
quelle
41

Genauer gesagt enthält jedes Bootstrap-Beispiel (oder jeder eingesackte Baum) des Beispiels.11e0.632

Sehen wir uns an, wie der Bootstrap funktioniert. Wir haben ein Originalmuster von mit Elementen. Wir zeichnen Artikel mit Ersatz aus diesem Originalsatz, bis wir einen weiteren Satz der Größe .x1,x2,xnnn

Daraus folgt, dass die Wahrscheinlichkeit, einen Gegenstand (zB ) bei der ersten Ziehung zu wählen, . Daher ist die Wahrscheinlichkeit , diesen Gegenstand nicht zu wählen, . Das ist nur für die erste Auslosung; Es gibt insgesamt Ziehungen, die alle unabhängig voneinander sind. Daher ist die Wahrscheinlichkeit, dass Sie diesen Gegenstand bei keiner Ziehung auswählen, .x11n11nn(11n)n

Überlegen wir nun, was passiert, wenn immer größer wird. Wir können die Grenze nehmen, wenn gegen Unendlich geht, indem wir die üblichen Kalkültricks (oder Wolfram Alpha) : nn

limn(11n)n=1e0.368

Das ist die Wahrscheinlichkeit, dass ein Gegenstand nicht ausgewählt wird. Subtrahieren Sie es von eins, um die Wahrscheinlichkeit zu ermitteln, mit der der ausgewählte Artikel ausgewählt wird. Dies ergibt 0,632.

Matt Krause
quelle
5

Die Abtastung mit Ersetzung kann als Folge von Binomialversuchen modelliert werden, bei denen "Erfolg" eine ausgewählte Instanz ist. Für einen ursprünglichen Datensatz von Instanzen beträgt die Wahrscheinlichkeit eines "Erfolges" und die Wahrscheinlichkeit eines "Scheiterns" . Bei einer Stichprobengröße von ergibt sich die Wahrscheinlichkeit, dass eine Instanz genau mal ausgewählt wird, aus der Binomialverteilung:n1/n(n1)/nbx

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

Im speziellen Fall eines Bootstrap-Beispiels entspricht die Beispielgröße der Anzahl der Instanzen . Letting gegen unendlich, erhalten wir:bnn

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

Wenn unser ursprünglicher Datensatz groß ist, können wir diese Formel verwenden, um die Wahrscheinlichkeit zu berechnen, dass eine Instanz in einem Bootstrap-Beispiel genau mal ausgewählt wird. Für beträgt die Wahrscheinlichkeit oder ungefähr . Die Wahrscheinlichkeit, dass eine Instanz mindestens einmal abgetastet wird, beträgt somit .xx=01/e0.36810.368=0.632

Unnötig zu erwähnen, dass ich dies sorgfältig mit Stift und Papier hergeleitet habe und nicht einmal daran gedacht habe, Wolfram Alpha zu verwenden.

retsreg
quelle
3

Wenn Sie nur die Antwort von @ retsreg hinzufügen, können Sie dies auch ganz einfach durch numerische Simulation in R demonstrieren:

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
vonjd
quelle
1

Dies kann leicht durch Zählen gesehen werden. Wie viele mögliche Proben insgesamt? n ^ n. Wie viele enthalten keinen bestimmten Wert? (n-1) ^ n. Wahrscheinlichkeit, dass eine Stichprobe keinen bestimmten Wert hat - (1-1 / n) ^ n, was etwa 1/3 der Grenze entspricht.

Maxim Khesin
quelle