antecedentes:
En xgboost, la iteración intenta ajustar un árbol sobre todos los ejemplos, lo que minimiza el siguiente objetivo:
donde son primer orden y de segundo orden sobre nuestra mejor estimación anterior (de la iteración ):
y es nuestra función de pérdida.
La pregunta (finalmente):
Cuando y consideran una característica específica en una división específica, usan la siguiente heurística para evaluar solo algunos candidatos divididos: clasifican todos los ejemplos por su , pasan la lista ordenada y suman su segunda derivada . Consideran un candidato dividido solo cuando la suma cambia más de . ¿¿¿Porqué es eso???
La explicación que me dan se me escapa:
Afirman que podemos reescribir la ecuación anterior así:
y no sigo el álgebra, ¿puedes mostrar por qué es igual?
Y luego afirman que "esto es exactamente una pérdida cuadrática ponderada con etiquetas y pesos ", una declaración con la que estoy de acuerdo, pero no entiendo cómo se relaciona con el algoritmo de candidato dividido que están usando ...
Gracias y lo siento si es demasiado largo para este foro.
Simplemente agregando la parte algebraica a la respuesta @Winks:
La segunda ecuación debe tener su signo invertido, como en:
El último término es de hecho constante: recuerde que y están determinados por la iteración anterior, por lo que son constantes cuando se intenta establecer .gi hi ft
Entonces, ahora podemos afirmar "esto es exactamente una pérdida cuadrática ponderada con las etiquetas y pesos "−gi/hi hi
El crédito va para Yaron y Avi de mi equipo por explicarme esto.
fuente
Si solo hay una muestra, y está optimizando el en la iteración , es fácil ver que el valor sería , explicandow t−th w∗=−gi/hi (ft−−(gi/hi))2
Ahora tiene un conjunto de datos completo. En un caso donde la función de pérdida tiene una segunda derivada idéntica, la se convertiría en lugar de . Lo escribí de esta manera porque en ese caso, el sería irrelevante para la diferencia de entre las muestras, ya que no hay diferencia. Sin embargo, en realidad, al mantener sin cambios, la fluctúa con la distribución de .w∗ −avg(gi)/const −sigma(gi)/sigma(hi) w∗ hi gi w∗ hi
Creo que explica por qué funciona, ya que está ponderado por .hi
fuente