Benötigen Sie Hilfe beim Verständnis des ungefähren Split-Points-Vorschlags von xgboost

Hintergrund:

in xgboost der Iteration versucht , einen Baum zu passen f t über alle n Beispiele , die die folgende objektiv minimieren:$t$$f_t$$n$

$$\sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]$$

wobei sind erste Ordnung und zweite Ordnung Derivate über unsere frühere beste Schätzung y (von Iteration t - 1 ):$g_i, h_i$$\hat{y}$$t-1$

• $g_i=d_{\hat{y}}l(y_i, \hat{y})$
• $h_i=d^2_{\hat{y}}l(y_i, \hat{y})$

und ist unsere Verlustfunktion.$l$

---

Die Frage (endlich):

Wenn sie und ein bestimmtes Merkmal k in einem bestimmten Split berücksichtigen , verwenden sie die folgende Heuristik, um nur einige Split-Kandidaten zu bewerten: Sie sortieren alle Beispiele nach ihrem x k , gehen über die sortierte Liste und summieren ihre zweite Ableitung h i . Sie betrachten einen geteilten Kandidaten nur dann, wenn sich die Summe um mehr als ϵ ändert . Warum das???$f_t$$k$$x_k$$h_i$$\epsilon$

Die Erklärung, die sie geben, entgeht mir:

Sie behaupten, wir könnten die vorherige Gleichung folgendermaßen umschreiben:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - g_i/h_i]^2 + constant$$

und ich folge der Algebra nicht - können Sie zeigen, warum sie gleich ist?

Und dann behaupten sie, dass "dies genau der gewichtete quadratische Verlust mit den Bezeichnungen und Gewichten h i ist " - eine Aussage, der ich zustimme, aber ich verstehe nicht, wie sie sich auf den von ihnen verwendeten Split-Candidate-Algorithmus bezieht. ..$gi/hi$$h_i$

Danke und Entschuldigung, wenn dies für dieses Forum zu lang ist.

Ich werde nicht auf Details eingehen, aber das Folgende soll Ihnen helfen, die Idee zu verstehen.

Sie verwenden Quantile (Wikipedia) , um zu bestimmen, wo geteilt werden soll. Wenn Sie 100 mögliche Teilungspunkte haben, (sortiert), können Sie die 10- Quantil-Teilungspunkte { x 10 , x 20 , ⋯ , x 90 } ausprobieren und haben bereits eine gute Annäherung. Dies ist, was der Parameter ϵ tut. Sie betrachten einen Split - Punkt , wenn die Spaltung hat ~ ε N mehr Punkte unter ihm als dem letzten Splitpunkt. Wenn ϵ = $\{x_1, \cdots, x_{100}\}$$10$$\{x_{10}, x_{20}, \cdots, x_{90}\}$$\epsilon$$\sim \epsilon N$$\epsilon = 0.01$Sie erhalten Teilungspunkte, die größer als { 1 % , 2 % , . . . , 99 % } der anderen Punkte. Sie berücksichtigen keine neue Aufteilung, wenn "die Summe mehr als ϵ ändert ", aber wenn die Anzahl der Punkte unter dem aktuellen Punkt um ϵ größer ist als der letzte.$\sim 100$$\{1\%, 2\%, ..., 99\%\}$$\epsilon$$\epsilon$

Wenn Sie viele fortlaufende Punkte haben, die bereits gut klassifiziert sind, ist es möglicherweise sinnlos, zwischen ihnen aufzuteilen. Sie möchten die Teile Ihres Datensatzes aufteilen, die sehr falsch und schwer zu erlernen sind. Dazu verwenden sie gewichtete Quantile. Hier spielen die Gewichte eine Rolle. Das erste Quantil ist nicht der erste Punkt, der größer als 10 % der Punkte ist, sondern der erste Punkt, der größer als 10 % der Gewichte ist.$10$$10\%$$10\%$

Fügen Sie einfach den algebraischen Teil zu @Winks hinzu. Antwort:

Das Vorzeichen der zweiten Gleichung sollte umgekehrt sein, wie in:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - (-g_i/h_i)]^2 + constant = \sum_{i=1}^n\frac{1}{2}h_i[f_t^2(x_i) + 2\frac{f_t(x_i)g_i}{h_i} + (g_i/h_i)^2] = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i) + \frac{gi^2}{2h_i}]$$

$g_i$$h_i$$f_t$

$-gi/hi$$h_i$

Dank geht an Yaron und Avi von meinem Team, die mir das erklärt haben.

Und dann behaupten sie, dass "dies genau der gewichtete quadratische Verlust mit den Bezeichnungen gi / higi / hi und gewichtet hihi ist" - eine Aussage, der ich zustimme, aber ich verstehe nicht, wie sie sich auf den von ihnen verwendeten Split-Candidate-Algorithmus bezieht. .

1. $w$$t-t_h$$w* = -gi/hi$$(ft - -(gi/hi))^2$

2. $w*$$-avg(gi)/const$$-sigma(gi)/sigma(hi)$$w*$$hi$$gi$$w*$$hi$

$hi$