Revelando matemáticas detrás de XGBoost
Por Ajit Samudrala Aspiring Data Scientist
Este artículo está dirigido a personas que les resulta difícil comprender el documento original. Sígueme hasta el final, y te aseguro que al menos obtendrás una idea de lo que sucede debajo del revolucionario modelo de aprendizaje automático. Vamos a empezar.
Curioso caso de John y Emily
John y Emily se embarcaron en una aventura para arrancar manzanas del árbol ubicado en el punto más bajo de la montaña. Mientras que Emily es una chica inteligente y aventurera, John es un poco cauteloso y lento.
Sin embargo, solo John puede escalar un árbol y arrancar manzanas. Veremos cómo logran su objetivo.
John y Emily comienzan en el punto ‘a’ en la montaña y el árbol está ubicado en el punto ‘g’. Hay dos maneras en que pueden alcanzar el punto ‘g’:
1. Emily calcula la pendiente de la curva en el punto ‘a’; si la pendiente es positiva, se mueven en la dirección opuesta o en la misma dirección. Sin embargo, la pendiente da dirección pero no dice cuánto necesitan moverse en esa dirección.
Por lo tanto, Emily decide dar un pequeño paso y repetir el proceso para que no terminen en el punto equivocado. Mientras que la dirección del paso está controlada por el gradiente negativo, la magnitud del paso está controlada por la tasa de aprendizaje.
Si la magnitud es demasiado alta o demasiado baja, pueden terminar en un punto incorrecto o tomar demasiado tiempo para llegar al punto ‘g’.
John es escéptico acerca de este enfoque y no quiere caminar más si por casualidad terminan en el punto equivocado.
Entonces, a Emily se le ocurre un nuevo enfoque:
2. Emily sugiere que primero vaya a los siguientes puntos potenciales y calcule el valor de la función de pérdida en esos puntos. Ella mantiene una nota del valor de la función en todos esos puntos, y le indicará a John que llegue a ese punto donde el valor es menor.
John amaba este enfoque ya que nunca terminará en un punto equivocado. Sin embargo, la pobre Emily necesita explorar todos los puntos en su vecindario y calcular el valor de la función en todos esos puntos.
La belleza de XGBoost es que aborda de forma inteligente estos dos problemas.Tenga en cuenta que puedo usar la función / base alumno / árbol indistintamente.
Gradient Boosting
Muchas implementaciones de Gradient Boosting siguen el enfoque 1 para minimizar la función objetivo. En cada iteración, ajustamos un alumno base al gradiente negativo de la función de pérdida y multiplicamos nuestra predicción con una constante y lo agregamos al valor de la iteración anterior.
Fuente: Wikipedia La intuición consiste en adaptar a un alumno base al gradiente negativo en cada iteración, esencialmente realizando un descenso de gradiente en la función de pérdida.
Los gradientes negativos a menudo se denominan pseudo residuos, ya que indirectamente nos ayudan a minimizar la función objetivo.
XGBoost
Fue el resultado de la investigación de Tianqi Chen, Ph.D. estudiante de la Universidad de Washington. XGBoost es un modelo de conjunto de aditivos que está compuesto por varios alumnos de base.
¿Cómo deberíamos elegir una función en cada iteración?
Elegimos una función que minimiza la pérdida total.
En el algoritmo de aumento de gradiente indicado anteriormente, obtuvimos f t (x i ) en cada iteración ajustando un alumno base al gradiente negativo de la función de pérdida con respecto al valor de la iteración anterior.
En XGBoost, exploramos varios aprendices o funciones básicos y elegimos una función que minimiza la pérdida (el segundo enfoque de Emily).
Como dije anteriormente, hay dos problemas con este enfoque:
1. explorando diferentes aprendices de base
2. calculando el valor de la función de pérdida para todos esos principiantes.
XGBoost usa la serie de Taylor para aproximar el valor de la función de pérdida para un principiante de base f t (x i ) , por lo tanto, reduciendo la carga en Emily para calcular la pérdida exacta para diferentes posibles alumnos de base.
Solo utiliza la expansión hasta la derivada de segundo orden suponiendo que este nivel de aproximación sería suficiente.
El primer término “C” es constante independientemente de cualquier f t (x i ) que seleccionamos. ‘G i ‘ es la derivada de pérdida de primer orden en la iteración anterior con respecto a las predicciones en la iteración anterior.
‘H i ‘ es la derivada de pérdida de segundo orden en la iteración anterior con respecto a las predicciones en la iteración anterior.
Por lo tanto, Emily puede calcular ‘g i ‘ y ‘f i ‘ antes de comenzar a explorar diferentes aprendices de base, ya que será solo una cuestión de multiplicaciones a partir de entonces. Plug and play, ¿no?
Así que XGBoost ha reducido una de las cargas en Emily. Todavía tenemos un problema de explorar diferentes principiantes base.
Supongamos que Emily arregló una base principiante ft que tiene nodos hoja ‘K’. Permítaseme j que el conjunto de instancias que pertenecen al nodo ‘j’ y ‘w j ‘ sea la predicción para ese nodo.
Así que para una instancia “yo” que pertenece a I j f t (x i ) = w j . Por lo tanto, obtuvimos la ecuación 3 de la ecuación 2 sustituyendo f t (x i ) con las respectivas predicciones.
Después de sustituir las predicciones, podemos tomar la derivada de la función de pérdida con respecto al peso de cada nodo de la hoja, para obtener un peso óptimo.
Sustituyendo los pesos óptimos en la ecuación 3 se obtiene la ecuación 4. Sin embargo, esta es la pérdida óptima para una estructura de árbol fija. Habrá varios cientos de árboles posibles.
Formulemos la posición actual de Emily. Ahora sabe cómo aliviar la carga de la pérdida de la informática mediante la expansión de Taylor.
Ella sabe para una estructura de árbol fija cuáles deberían ser los pesos óptimos en el nodo de la hoja. Lo único que sigue siendo una preocupación es cómo explorar todas las diferentes estructuras de árbol posibles.
En lugar de explorar todas las estructuras de árbol posibles, XGBoost crea astutamente un árbol. Se elige la división que da como resultado la reducción máxima de pérdida.
En la imagen de arriba, el árbol comienza en el Nodo ‘I’. En función de algunos criterios divididos, el nodo se divide en ramas izquierda y derecha.
Entonces, algunas instancias caen en el nodo izquierdo y otras instancias caen en el nodo hoja derecho. Ahora, podemos calcular la reducción en la pérdida y elegir la división que cause la mejor reducción en la pérdida.
Pero todavía Emily tiene un problema más. ¿Cómo elegir los criterios de división?
XGBoost usa diferentes trucos para llegar a diferentes puntos de división como histograma, exacto, etc. No trataré con esa parte, ya que este artículo ya ha crecido en tamaño.
Puntos negativos para recordar
- Mientras Gradient Boosting sigue gradientes negativos para optimizar la función de pérdida, XGBoost usa la expansión de Taylor para calcular el valor de la función de pérdida para diferentes principiantes básicos. Aquí está el mejor video en Internet que explica la expansión de Taylor .
- XGBoost no explora todas las estructuras de árbol posibles, sino que construye un árbol con avidez.
- El término de regularización de XGBoost penaliza la construcción de un árbol complejo con varios nodos hoja.
- XGBoost tiene varios otros trucos bajo su manga como submuestreo de Columna, contracción, criterios de división, etc. Recomiendo seguir leyendo el documento original aquí .
Puede ver la derivación completa aquí .
Lea mi otro artículo sobre PCA aquí .
Bio: Ajit Samudrala es un aspirante a Data Scientist y Data Science en SiriusXM.
Original . Repostado con permiso.
