Wie würde man formal beweisen, dass der OOB-Fehler in einer zufälligen Gesamtstruktur unvoreingenommen ist?

8

Ich habe diese Aussage oft gelesen, bin aber nie auf einen Beweis gestoßen. Ich würde gerne versuchen, selbst eine zu produzieren, bin mir aber nicht einmal sicher, welche Notation ich verwenden soll. Kann mir jemand dabei helfen?

JEquihua
quelle
1
OOB ist nicht voreingenommen. Die einzige - oft: wichtigste - Komponente der Verzerrung, die von OOB beseitigt wird, ist der „Optimismus“, unter dem eine Anpassung in der Stichprobe leidet. ZB OOB ist pessimistisch in vorbelastet , dass es auf den gemittelten Prognosen von nur basiert der Bäume im Wald. EDIT: wie in der Antwort von @cbeleites unten ausgeführt. 36.8%.
Jim

Antworten:

4

Ich weiß nicht, ob dies die endgültige Antwort ist, aber diese Dinge passen nicht zu einem Kommentar.

Die Aussage, dass OOB-Fehler unvoreingenommen sind, wird oft verwendet, aber ich habe nie eine Demonstration gesehen. Nach vielen Suchen gab ich schließlich nach sorgfältiger Lektüre die bekannte Seite von Breiman für RF Section: Die Out-of-Bag (oob) -Fehlerschätzung . Falls Sie es nicht bemerkt haben (wie ich es einige Zeit verpasst habe), ist der letzte Satz der wichtige: Dies hat sich in vielen Tests als unvoreingenommen erwiesen . Also keine Anzeichen einer formalen Ableitung.

Darüber hinaus scheint es bewiesen zu sein, dass dieser Schätzer für den Fall, dass Sie mehr Variablen als Instanzen haben, voreingenommen ist. Siehe hier .

Für In-the-Bag-Fehler gibt es eine formale Ableitung. Der In-the-Bag-Fehler ist der Bootstrap-Fehler, und es gibt reichlich Literatur, beginnend mit "Eine Einführung in die Bootsrap von Efron und Tibshirani". Die sauberste Demonstration, die ich gesehen habe, ist hier .

Wenn Sie anfangen möchten, einen Beweis zu finden, ist der Vergleich dieser Schätzung mit der N-fachen Kreuzvalidierung meiner Meinung nach ein guter Ausgangspunkt. In ESTL wird angegeben, dass es eine Identität im Grenzwert gibt, da die Anzahl der Proben gegen unendlich geht.

Rapaio
quelle
1
np
3

Warum erwarten Sie, dass der oob-Fehler unvoreingenommen ist?

  • Für die im Ersatzwald verwendeten Bäume steht (mindestens) 1 Trainingsfall weniger zur Verfügung als für den "ursprünglichen" Wald. Ich würde erwarten, dass dies zu einer kleinen pessimistischen Tendenz führt, die in etwa mit einer einmaligen Kreuzvalidierung vergleichbar ist.

  • 1e13

Beide Gedanken hängen eng mit der Lernkurve des Klassifikators und der betreffenden Anwendung / Daten zusammen: der erste mit der durchschnittlichen Leistung als Funktion der Trainingsstichprobengröße und der zweite mit der Varianz um diese durchschnittliche Kurve.

1e13n- -1

Beachten Sie auch, dass Breiman "unvoreingenommen" für Out-of-Bootstrap verwendet, genauso wie er es für die Kreuzvalidierung verwendet, bei der wir auch eine (kleine) pessimistische Tendenz haben. Ich komme aus einem experimentellen Bereich und kann damit sagen, dass beide praktisch unvoreingenommen sind, da die Verzerrung normalerweise viel weniger problematisch ist als die Varianz (Sie verwenden wahrscheinlich keine zufälligen Wälder, wenn Sie den Luxus haben, viele Fälle zu haben). .

cbeleites unzufrieden mit SX
quelle
3
Ich habe es nicht erwartet. Es wird von Leuten an vielen Orten erwähnt, also habe ich es einfach akzeptiert. Jetzt, wo ich darüber nachgedacht habe, wollte ich es beweisen. Ich mag deine Antwort. Lass mich ein bisschen mit deinen Informationen herumspielen, um zu sehen, was ich daraus schließen kann.
JEquihua
@JEquihua: Das Ergebnis würde mich sicherlich interessieren.
cbeleites unglücklich mit SX
1
Der OOB-Wald ist ungefähr 1/3 des ursprünglichen Waldes, nicht 2/3 (also mehr Grund, warum der OOB-Fehler pessimistisch ist!). Die Wahrscheinlichkeit, einen gegebenen Baum T für den oob-Wald einer gegebenen Beobachtung (x, y) auszuwählen, ist die Wahrscheinlichkeit, dass (x, y) nicht in T ist, dh ((N-1) / N) ^ N = ( 1 + (-1) / N) ^ N -> exp (-1) = ~ 1/3. Die erwartete Größe des OOB-Waldes für (x, y) beträgt also ungefähr B / 3, wenn B die Größe des ursprünglichen Waldes ist.
Memeplex
@memeplex: natürlich - danke fürs entdecken. Repariert.
cbeleites unglücklich mit SX