Können CART-Modelle robust gemacht werden?

14

Ein Kollege in meinem Büro sagte mir heute: "Baummodelle sind nicht gut, weil sie von extremen Beobachtungen erfasst werden."

Eine Suche hier ergab diesen Thread , der im Grunde den Anspruch unterstützt.

Was mich zu der Frage führt: In welcher Situation kann ein CART-Modell robust sein und wie wird dies gezeigt?

Tal Galili
quelle

Antworten:

15

Nein, nicht in ihrer jetzigen Form. Das Problem ist, dass konvexe Verlustfunktionen nicht robust gegen Kontamination durch Ausreißer gemacht werden können (dies ist eine bekannte Tatsache seit den 70er Jahren, wird aber regelmäßig wiederentdeckt, siehe zum Beispiel dieses Papier für eine kürzlich erfolgte solche Neuentdeckung):

http://www.cs.columbia.edu/~rocco/Public/mlj9.pdf

Im Fall von Regressionsbäumen kann nun die Tatsache verwendet werden, dass CART Marginals (oder alternativ univariate Projektionen) verwendet: Man kann sich eine Version von CART vorstellen, bei der das SD-Kriterium durch ein robusteres Gegenstück (MAD oder besser noch) ersetzt wird. Qn-Schätzer).

Bearbeiten:

Ich bin kürzlich auf ein älteres Papier gestoßen, das den oben vorgeschlagenen Ansatz implementiert (indem ein robuster M-Schätzer anstelle des MAD verwendet wurde). Dies verleiht "y" Ausreißern Robustheit gegenüber CART / RFs (jedoch nicht Ausreißern, die sich im Entwurfsbereich befinden und die Schätzungen der Hyperparameter des Modells beeinflussen). Siehe:

Galimberti, G., Pillati, M. & Soffritti, G. (2007). Robuste Regressionsbäume basierend auf M-Schätzern. Statistica, LXVII, 173–190.

user603
quelle
Danke, Kwak. Dieser Artikel scheint über Boosting-Methoden zu sprechen. Halten die Ergebnisse, die sie präsentieren, für den einfachen Klassifikatorfall eines CART-Modells? (An der Oberfläche hört es sich so an, aber ich habe den Artikel nicht genug durchgearbeitet, um es wirklich zu wissen)
Tal Galili
Das Ergebnis, das sie präsentieren, gilt für jede konvexe Verlustfunktion und wurde ursprünglich von Tukey diskutiert. Zusammenfassend ist das Maß für die Ausbreitung (Gini oder Entropie), mit dem die Qualität eines Knotens quantifiziert wird, empfindlich gegenüber Kontamination durch Ausreißer (dh Beobachtungen, die im Datensatz falsch gekennzeichnet sind). Dieses Problem betrifft sowohl das Gebäude als auch die Prunning-Phase. Eine Kontamination eines Datensatzes durch Beobachtung mit einem falsch eingegebenen Etikett führt in der Regel dazu, dass der resultierende Baum viel zu komplex ist (dies können Sie recht einfach selbst überprüfen).
user603
Vielen Dank, Kwak! Und gibt es keine robuste Verlustfunktion?
Tal Galili
1
keine konvexe Verlustfunktion. In diesem Artikel "Ein schneller Algorithmus für den Minimum-Kovarianz-Determinantenschätzer" finden Sie ein Beispiel dafür, was mit nichtkonvexen Verlustfunktionen getan werden kann (obwohl der Artikel nicht mit der Klassifizierung zusammenhängt, ist er eine Lektüre wert).
user603
2
@Tal CART ist ein Äquivalent zum Boosten eines "Pivot-Klassifikators" (das Kriterium, das in jedem Baumknoten steht, wie eine Attribut-Reibe als etwas oder ein Attribut-Wert in einer Menge etwas).
6

Sie könnten Breimans Absackung oder zufällige Wälder in Betracht ziehen . Eine gute Referenz ist Breiman "Bagging Predictors" (1996). Ebenfalls zusammengefasst in Clifton Suttons "Klassifizierungs- und Regressionsbäume, Absacken und Boosten" im Handbuch der Statistik.

Sie können auch Andy Liaw und Matthew Wiener R News über das randomForest-Paket sehen.

Shane
quelle
2
Es ist ein Rätsel, die Party nicht zu verderben, aber wie willkürliche Wälder der Kontamination durch Ausreißer standhalten sollen.
user603
3
@kwak Trotzdem ist dies eine gute Antwort; Bäume in RF sehen nicht die gesamte Menge, so dass viele von ihnen nicht kontaminiert werden. Noch besser: Mithilfe der Verfolgung, in der Blätter in OOB-Fällen landen, können falsch beschriftete Objekte gefunden und beseitigt werden. (Soweit ich mich erinnere, wird dies in Breimans Artikel über RF erwähnt).
4
Das Problem ist, dass Ausreißer dazu führen, dass ein schlechter (dh kontaminierter) Baum besser aussieht als ein guter (nicht kontaminierter). Dies wird als Maskierungseffekt bezeichnet und ist einfach mit simulierten Daten zu replizieren. Das Problem tritt auf, weil das Kriterium, das Sie zur Bewertung von Bäumen verwenden, für Ausreißer an sich nicht robust ist. Ich weiß, ich fange an, wie ein fundamentalistischer Mullah zu klingen, aber es kann gezeigt werden, dass Ihr Verfahren (auf der einen oder anderen Ebene) empfindlich gegenüber Ausreißern ist (und daher nicht robust ist), es sei denn, jedes von Ihnen verwendete Werkzeug ist robust.
user603
3

Wenn Sie das 'gbm'-Paket in R (generalisierte Gradientenanhebung) auschecken, verwendet die' Anhebung 'Verlustfunktionen, die nicht unbedingt einen quadratischen Fehler bedeuten. Dies zeigt sich im Argument 'distribution' für die Funktion 'gbm ()'. Daher ist die Erstellung des Baums durch Boosten resistent gegen Ausreißer, ähnlich wie M-Schätzer funktionieren.

Sie könnten hier anfangen .

Ein anderer Ansatz wäre, den Baum auf die übliche Weise zu erstellen (Partitionen basierend auf SSE), den Baum jedoch mithilfe einer Kreuzvalidierung mit einem robusten Anpassungsmaß zu beschneiden. Ich denke, dass xpred in rpart kreuzvalidierte Prädiktoren (für eine Vielzahl unterschiedlicher Baumkomplexitäten) liefert, auf die Sie Ihr eigenes Fehlermaß anwenden können, beispielsweise den absoluten Mittelwert.

AlaskaRon
quelle