Gradient Boosting

Idee

Gradient Boosting versucht sich durch mehrer Iterationen an den minimalen Fehler anzunähern. Das geschieht durch Anwendung der stepest descent Methode. Hierfür wird zu jedem Merkmalvektor ein Gradient gebildet, welchen der Algorithmus für das Training berücksichtigt. So nähert er sich durch viele Iterationen mehr und mehr einem minimalen Fehler an. Meist wird Boosting mit einem Entscheidungsbaum als Grundlage verwendet.[1]

Algorithmus

Quelle:[2] vgl. [1]

Erklärung

1. Initialisierung der Funktionswerte gemäß der Verteilung der Parameter. Im binären Fall, wenn eine Gleichverteilung vorliegt, wird mit 0,5 initialisiert.

1. Wiederholen von folgenden für T Iterationen:

1. Berechnen des Gradienten bzw. des pseudo Residuals für jeden Datenpunkt

1. Trainieren des Entscheidungsbaums mit den Gradienten als Zielwert

1. Bilden der Schrittweite für jede Endregion des Entscheidungsbaums

1. Aktualisieren der Entscheidungsfunktion

Parameter

Um die optimale Leistung des Algorithmus zu erreichen, ist es Wichtig, dass verschiedene Parameter berücksichtigt werden. Die wichtigsten werden hier kurz vorgestellt:

1. Die Tiefe des Entscheidungsbaums. Diese hat auch einen direkten Einfluss auf die Anzahl an Endregionen. Die Anzahl an Endregionen verdoppelt sich, mit zunehmender Tiefe. Dies erhöht die Rechenzeit zusätzlich.

1. Eine Schrumpf bzw. Lernrate, welche eine Überanpassung an die neue Hypothese verhindert. Diese hat einen Wert zwischen 0 und 1. Ein Standardwert hierfür ist 0,1.

1. Die Größe des Trainingsraums. Dies verringert die Trainingszeit und kann die Varianz verringern. Der Wert kann zwischen 0 und 1 liegen, wobei 1 bedeutet, dass alle Daten der Trainingsmenge verwendet werden. [1]

Implementationen

Gradient Boosting Phyton
XGBoost

Literatur

[1] Hastie T., Tibshirani R. and Friedman J. (2009): Elements of Statistical Learning - Data Mining, Inference, and Prediction; Springer
[2] Dietz T. (2018): Bachelorarbeit “Automatisches rechnerbasiertes Lernen mit Ensemble-Methoden ”, Hochschule Schmalkalden