5.5 Bootstrap

Ergänzung, nicht auf den Folien: Der Zeitplan nennt für diesen Termin „evtl. Bootstrap“. Die Folien enthalten dazu nichts, deshalb hier eine kurze Einführung in die Grundidee.

Idee

Man hätte gern viele unabhängige Datensätze aus der wahren Verteilung, um zu sehen, wie stark ein Schätzer schwankt (das ist genau die Varianz aus 5.4). Man hat aber nur einen Datensatz mit $n$ Beispielen.

Der Bootstrap (Efron, 1979) behandelt den vorhandenen Datensatz als Ersatz für die Grundgesamtheit: Man zieht aus ihm $n$ Beispiele mit Zurücklegen (sampling with replacement). Das ergibt eine Bootstrap-Stichprobe (bootstrap sample). Manche Beispiele kommen darin mehrfach vor, andere gar nicht. Das wiederholt man $B$ mal (typisch $B=200$ bis $1000$).

Der Name kommt von „sich an den eigenen Stiefelschlaufen aus dem Sumpf ziehen“: Man schätzt die Unsicherheit allein aus den Daten selbst.

Anwendung 1: Standardfehler eines Schätzers

1. $B$ Bootstrap-Stichproben ziehen.
2. Auf jeder den Schätzer berechnen: $\hat\theta^{*1},\dots,\hat\theta^{*B}$ (z. B. einen Median, einen Regressionskoeffizienten $\hat\beta$ oder die AUC eines Modells).
3. Die Standardabweichung dieser $B$ Werte schätzt den Standardfehler von $\hat\theta$.

Die Werte zwischen dem 2,5-%- und dem 97,5-%-Quantil der $\hat\theta^{*b}$ bilden ein einfaches 95-%-Konfidenzintervall (percentile interval). Das ist ein Weg, an die Fehlerbalken zu kommen, die 📄 07_roc_xval_bias_var_ws26.pdf, Folie 17 fordert, auch für Größen ohne einfache Formel.

Mini-Beispiel: Daten $(1,\,3,\,4,\,8)$, Schätzer Mittelwert ($=4$). Drei mögliche Bootstrap-Stichproben: $(3,3,4,8)$ mit Mittel $4{,}5$, $(1,1,4,8)$ mit $3{,}5$, $(1,3,8,8)$ mit $5$. Die Streuung dieser Mittelwerte (bei großem $B$) schätzt, wie stark der Mittelwert bei neuen Daten schwanken würde.

Anwendung 2: Out-of-Bag-Fehler

Wie groß ist die Chance, dass ein bestimmtes Beispiel nicht in einer Bootstrap-Stichprobe landet? Bei jedem der $n$ Züge wird es mit Wahrscheinlichkeit $1-\tfrac1n$ nicht gezogen:

$$P(\text{nicht enthalten}) = \Bigl(1-\frac1n\Bigr)^n \xrightarrow{n\to\infty} e^{-1} \approx 0{,}368.$$

Eine Bootstrap-Stichprobe enthält also nur etwa 63,2 % der verschiedenen Beispiele. Die übrigen rund 36,8 % heißen Out-of-Bag (OOB). Trainiert man auf der Bootstrap-Stichprobe und testet auf den OOB-Beispielen, bekommt man eine Fehlerschätzung ähnlich der Kreuzvalidierung.

Wie bei der 2-fachen CV sieht jedes Modell effektiv weniger verschiedene Daten, die Schätzung ist daher eher pessimistisch. Korrekturen wie der „.632-Bootstrap“ gleichen das aus. In der Praxis ist für die Modellbewertung meist 10-fache CV Standard, der Bootstrap ist vor allem für Unsicherheitsangaben beliebt.

Ausblick: Bagging

Die letzte Folie (📄 07_roc_xval_bias_var_ws26.pdf, Folie 31) kündigt Ensemble-Methoden an. Die wichtigste davon beruht direkt auf dem Bootstrap: Bagging (bootstrap aggregating). Man trainiert auf jeder von $B$ Bootstrap-Stichproben ein Modell mit hoher Varianz und kleinem Bias (z. B. einen tiefen Entscheidungsbaum) und mittelt die Vorhersagen.

Warum hilft das? Der Mittelwert von $B$ unabhängigen Zufallsgrößen mit Varianz $v$ hat Varianz $v/B$, der Erwartungswert, und damit der Bias, bleibt gleich. Die Bootstrap-Modelle sind zwar nicht unabhängig (sie teilen sich viele Beispiele), die Varianz sinkt aber trotzdem deutlich. Random Forests verstärken diesen Effekt, indem sie die Bäume zusätzlich dekorrelieren.