Como ejemplo, tome la función objetivo del modelo XGBoost en la iteración :$t$

$$\mathcal{L}^{(t)}=\sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)}+f_t(\mathbf{x}_i))+\Omega(f_t)$$

donde es la función de pérdida, es la salida del árbol ' y es la regularización. Uno de los (muchos) pasos clave para el cálculo rápido es la aproximación:$\ell$$f_t$$t$$\Omega$

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)})+g_tf_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)+\Omega(f_t),$$

donde y son las derivadas primera y segunda de la función de pérdida.$g_i$$h_i$

Lo que estoy pidiendo es argumentos convincentes para desmitificar por qué funciona la aproximación anterior:

1) ¿Cómo se compara XGBoost con la aproximación anterior con XGBoost con la función objetivo completa? ¿Qué comportamiento potencialmente interesante de orden superior se pierde en la aproximación?

2) Es un poco difícil de visualizar (y depende de la función de pérdida) pero, si la función de pérdida tiene un componente cúbico grande, entonces la aproximación probablemente fallará. ¿Cómo es que esto no causa problemas para XGBoost?

Esta es una pregunta muy interesante. Para comprender completamente lo que estaba sucediendo, tuve que analizar lo que XGBoost está tratando de hacer y qué otros métodos teníamos en nuestra caja de herramientas para tratarlo. Mi respuesta es sobre los métodos tradicionales, y cómo / por qué XGBoost es una mejora. Si solo desea las viñetas, hay un resumen al final.

Aumento de gradiente tradicional

Considere el algoritmo tradicional de aumento de gradiente (Wikipedia) :

• Calcular modelo base$H_0$
• Para$m \leftarrow 1:M$
  • Calcule pseudo-residuos$r_{im} = -\frac{\partial \ell(y_i, H_{m-1}(x_i))}{\partial H_{m-1}(x_i)}$
  • Ajuste un alumno base a los seudo residuales$h_m(x)$
  • Calcule el multiplicador que minimiza el costo, , (usando la búsqueda de línea)$\gamma$$\gamma = \arg \min_\gamma \sum_{i=1}^N \ell(y_i, H_{m-1}(x_i) + \gamma h_m(x_i))$
  • Actualice el modelo .$H_m(x) = H_{m-1}(x) + \gamma h_m(x)$
• Obtiene su modelo impulsado .$H_M(x)$

La aproximación de la función es importante para la siguiente parte,

Ajuste un alumno base a los seudo residuales.$h_m(x)$

Imagínese dónde construir su algoritmo de aumento de gradiente ingenuamente. Construiría el algoritmo anterior utilizando los árboles de regresión existentes como alumnos débiles. Supongamos que no puede modificar la implementación existente de los alumnos débiles. En Matlab , el criterio de división predeterminado es el error cuadrático medio. Lo mismo vale para scikit learn .

Está tratando de encontrar el mejor modelo que minimice el costo . Pero para hacerlo, está ajustando un modelo de regresión simple a los residuos utilizando el MSE como función objetivo. Tenga en cuenta que no está minimizando directamente lo que desea, sino que usa los residuos y el MSE como proxy para hacerlo. Lo malo es que no necesariamente produce la solución óptima. Lo bueno es que funciona.$h_m(x)$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$

Descenso de gradiente tradicional

Esto es análogo al descenso de gradiente tradicional (Wikipedia) , en el que está tratando de minimizar una función de costo siguiendo el gradiente (negativo del) de la función, en cada paso.$f(x)$$-\nabla f(x)$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

No le permite encontrar el mínimo exacto después de un paso, pero cada paso lo acerca al mínimo (si la función es convexa). Esta es una aproximación, pero funciona muy bien y es el algoritmo que usamos tradicionalmente para hacer una regresión logística, por ejemplo.

Interludio

En este punto, lo que hay que entender es que el algoritmo general de aumento de gradiente no calcula la función de costo para cada posible división, sino que utiliza la función de costo del alumno débil de regresión para ajustar los residuos.$\ell$

Lo que su pregunta parece implicar es que el "XGBoost verdadero" debe calcular la función de costo para cada división, y que el "XGBoost aproximado" está utilizando una heurística para aproximarlo. Puede verlo de esa manera, pero históricamente, hemos tenido el algoritmo general de aumento de gradiente, que no utiliza información sobre la función de costo, excepto la derivada en el punto actual. XGBoost es una extensión de Gradient Boosting que intenta ser más inteligente sobre el crecimiento de los árboles de regresión débiles utilizando una aproximación más precisa que solo el gradiente.

Otras formas de elegir el mejor modelo$h_m(x)$

Si miramos a AdaBoost como un caso especial de aumento de gradiente, no selecciona regresores sino clasificadores como estudiantes débiles. Si establecemos , la forma en que AdaBoost selecciona el mejor modelo es encontrar$h_m(x) \in \{-1,1\}$

$$h_m = \arg \max_{h_m} \sum_{i=1}^N w_i h_m(x_i)$$

donde son los residuos ( fuente, comienza en la diapositiva 20 ). El razonamiento para el uso de esta función objetivo es que si y van en la misma dirección / tienen el mismo signo, el punto se mueve en la dirección correcta y está tratando de maximizar la cantidad máxima de movimiento en la dirección correcta.$w_i$$w_i$$h_m(x_i)$

Pero una vez más, esto no mide directamente qué minimiza . Mide qué tan bueno es el movimiento , con respecto a la dirección general que debe seguir, medido con los residuos , que también son una aproximación. Los residuos le indican en qué dirección debe moverse por su signo, y aproximadamente por su magnitud, pero no le dicen exactamente dónde debe detenerse.$h_m$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$$h_m$$w_i$

Mejor descenso de gradiente

Los siguientes tres ejemplos no son esenciales para la explicación y solo están aquí para presentar algunas formas de hacerlo mejor que un descenso de gradiente de vainilla, para apoyar la idea de que lo que hace XGBoost es solo otra forma de mejorar el descenso de gradiente. En una configuración de descenso de gradiente tradicional, cuando se trata de minimizar , es posible hacerlo mejor que simplemente seguir el gradiente. Se han propuesto muchas extensiones (Wikipedia) . Estos son algunos de ellos, para mostrar que es posible hacerlo mejor, dado más tiempo de cálculo o más propiedades de la función .$f(x)$$f$

• Búsqueda de línea / Retroceso: en Pendiente de gradiente, una vez que se calcula el gradiente , el siguiente punto debe ser$-\nabla f(x^{(i)})$

  $$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

  Pero el gradiente solo da la dirección en la que se debe mover, no realmente "cuánto", por lo que se puede utilizar otro procedimiento para encontrar el mejor modo que$c > 0$

  $$x_c^{(i+1)} = x^{(i)} - c \nabla f(x^{(i)})$$

  minimiza la función de costo. Esto se hace evaluando para algunos , y dado que la función debe ser convexa, es relativamente fácil hacerlo a través de Búsqueda de línea (Wikipedia) o Búsqueda de línea de retroceso (Wikipedia) . Aquí, el costo principal es la evaluación . Entonces, esta extensión funciona mejor si es fácil de calcular. Tenga en cuenta que el algoritmo general para el aumento de gradiente utiliza la búsqueda de línea, como se muestra al comienzo de mi respuesta.$f(x_c^{(i+1)})$$c$$f$$f(x)$$f$

• Método rápido de gradiente proximal: si la función para minimizar es fuertemente convexa, y su gradiente es suave ( Lipschitz (Wikipedia) ), entonces hay algún truco que usa esas propiedades que acelera la convergencia.

• Descenso de gradiente estocástico y el método Momentum: en Descenso de gradiente estocástico, no evalúa el gradiente en todos los puntos, sino solo en un subconjunto de esos puntos. Da un paso, luego calcula el gradiente en otro lote y continúa. El Descenso de gradiente estocástico puede usarse porque el cálculo en todos los puntos es muy costoso, o tal vez todos esos puntos ni siquiera caben en la memoria. Esto le permite dar más pasos, más rápidamente, pero con menos precisión.

  Al hacerlo, la dirección del gradiente puede cambiar según los puntos que se muestreen. Para contrarrestar este efecto, los métodos de impulso mantienen un promedio móvil de la dirección para cada dimensión, reduciendo la varianza en cada movimiento.

La extensión más relevante para el descenso de gradiente en nuestra discusión sobre XGBoost es el método de Newton (Wikipedia) . En lugar de simplemente calcular el gradiente y seguirlo, usa la derivada de segundo orden para recopilar más información sobre la dirección en la que debe ir. Si usamos la pendiente de gradiente, tenemos que en cada iteración, actualizamos nuestro punto siguiente manera,$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

Y dado que el gradiente apunta a la dirección de mayor aumento en , sus puntos negativos en la dirección de mayor disminución, y esperamos que . Esto podría no ser válido, ya que podríamos ir demasiado lejos en la dirección del gradiente (de ahí la extensión de búsqueda de línea), pero es una buena aproximación. En el método de Newton, actualizamos siguiente manera,$\nabla f(x^{(i)})$$f$$f(x^{(i+1)}) < f(x^{(i)})$$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \frac{\nabla f(x^{(i)})}{\text{Hess} f(x^{(i)})}$$

Donde es el hessiano de en . Esta actualización tiene en cuenta la información de segundo orden, por lo que la dirección ya no es la dirección de mayor disminución, sino que debe apuntar con mayor precisión hacia modo que (o el punto donde es mínimo, si no hay cero). Si es un polinomio de segundo orden, entonces el método de Newton junto con una búsqueda de línea debería poder encontrar el mínimo en un solo paso.$\text{Hess} f(x)$$f$$x$$x^{(i+1)}$$f(x^{(i+1)}) = 0$$f$$f$

El método de Newton contrasta con el descenso de gradiente estocástico. En el Descenso de gradiente estocástico, usamos menos puntos para tomar menos tiempo para calcular la dirección hacia la que debemos ir, a fin de hacer más de ellos, con la esperanza de llegar más rápido. En el método de Newton, nos tomamos más tiempo para calcular la dirección en la que queremos ir, con la esperanza de que tengamos que dar menos pasos para llegar allí.

Ahora, la razón por la cual funciona el método de Newton es la misma por la que funciona la aproximación XGBoost, y se basa en la expansión de Taylor (Wikipedia) y el teorema de Taylor (Wikipedia) . La expansión de Taylor (o serie de Taylor) de una función en un punto es$f(x + a)$

$$f(x) + \frac{\partial f(x)}{\partial x}a + \frac{1}{2}\frac{\partial^2 f(x)}{\partial x^2}a^2 + \cdots = \sum_{n=0} ^\infty \frac{1}{n!} \frac{\partial^n f(x)}{\partial x^n}a^n.$$

Tenga en cuenta la similitud entre esta expresión y la aproximación que XGBoost está utilizando. El teorema de Taylor establece que si detiene la expansión en el orden , entonces el error o la diferencia entre y , es como máximo , donde es una función con la propiedad agradable que tiende a cero cuando va a cero.$k$$f(x+a)$$\sum_{n=0}^k \frac{1}{n!}\frac{\partial^n f(x)}{\partial x^n}a^n$$h_k(x) a^k$$h_k$$a$

Si desea una visualización de cuán bien se aproxima a algunas funciones, eche un vistazo a las páginas de Wikipedia, tienen algunos gráficos para la aproximación de la función no polinómica, como , .$e^x$$\log(x)$

Lo que hay que tener en cuenta es que la aproximación funciona muy bien si desea calcular el valor de en la vecindad de , es decir, para cambios muy pequeños . Esto es lo que queremos hacer en Boosting. Por supuesto, nos gustaría encontrar el árbol que haga el mayor cambio. Si los alumnos débiles que construimos son muy buenos y quieren hacer un gran cambio, entonces podemos obstaculizarlo arbitrariamente aplicando solo o$f$$x$$a$$0.1$$0.01$de su efecto. Este es el tamaño del paso o la tasa de aprendizaje del descenso de gradiente. Esto es aceptable, porque si nuestros alumnos débiles están obteniendo muy buenas soluciones, esto significa que el problema es fácil, en cuyo caso vamos a terminar con una buena solución de todos modos, o estamos sobreajustados, por lo que vamos un poco o muy mucho en esta mala dirección no cambia el problema subyacente.

Entonces, ¿qué está haciendo XGBoost y por qué funciona?

XGBoost es un algoritmo de aumento de gradiente que crea árboles de regresión como alumnos débiles. El algoritmo tradicional de aumento de gradiente es muy similar a un descenso de gradiente con una búsqueda de línea, donde la dirección en la que ir se extrae de los alumnos débiles disponibles. La implementación ingenua de Gradient Boosting utilizaría la función de costo del alumno débil para ajustarlo al residual. Este es un proxy para minimizar el costo del nuevo modelo, que es costoso de calcular. Lo que XGBoost está haciendo es construir una función de costo personalizada para que se ajuste a los árboles, utilizando la serie Taylor de orden dos como una aproximación para la función de costo real, de modo que pueda estar más seguro de que el árbol que elige es bueno. A este respecto, y como una simplificación, XGBoost es a Gradient Boosting lo que el Método de Newton es a Gradient Descent.

¿Por qué lo construyeron de esa manera?

Su pregunta de por qué usar esta aproximación llega a un compromiso costo / rendimiento. Esta función de costo se usa para comparar divisiones potenciales para árboles de regresión, por lo que si nuestros puntos tienen, por ejemplo, 50 características, con un promedio de 10 valores diferentes, cada nodo tiene 500 divisiones potenciales, por lo que 500 evaluaciones de la función. Si suelta una característica continua, el número de divisiones explota y la evaluación de la división se llama cada vez más (XGBoost tiene otro truco para lidiar con las características continuas, pero eso está fuera del alcance). Como el algoritmo pasará la mayor parte del tiempo evaluando divisiones, la forma de acelerar el algoritmo es acelerar la evaluación de árbol.

Si evaluó el árbol con la función de costo total, , es un nuevo cálculo para cada nueva división. Para realizar la optimización en el cálculo de la función de costo, necesitaría tener información sobre la función de costo, que es el punto principal del aumento de gradiente: debería funcionar para cada función de costo.$\ell$

La aproximación de segundo orden es computacionalmente agradable, porque la mayoría de los términos son iguales en una iteración dada. Para una iteración dada, la mayor parte de la expresión puede calcularse una vez y reutilizarse como constante para todas las divisiones:

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n \underbrace{\ell(y_i,\hat{y}_i^{(t-1)})}_{\text{constant}}+\underbrace{g_i}_{\text{constant}}f_t(\mathbf{x}_i)+\frac{1}{2}\underbrace{h_i}_{\text{constant}}f_t^2(\mathbf{x}_i)+\Omega(f_t),$$

Entonces, lo único que tiene que calcular es y , y luego lo que queda son mayormente adiciones y algunas multiplicaciones. Además, si echas un vistazo al documento XGBoost (arxiv) , verás que usan el hecho de que están construyendo un árbol para simplificar aún más la expresión a un conjunto de suma de índices, que es muy, muy rápido.$f_t(x_i)$$\Omega(f_t)$

Resumen

Puede ver XGBoost (con aproximación) como una regresión de la solución exacta, una aproximación del "verdadero XGBoost", con una evaluación exacta. Pero dado que la evaluación exacta es tan costosa, otra forma de verlo es que en grandes conjuntos de datos, la aproximación es todo lo que podemos hacer de manera realista, y esta aproximación es más precisa que la aproximación de primer orden que haría un algoritmo de refuerzo de gradiente "ingenuo" .

La aproximación en uso es similar al Método de Newton , y está justificada por Taylor Series (Wikipedia) y Taylor Theorem (Wikipedia) .

De hecho, la información de orden superior no se utiliza por completo, pero no es necesaria, porque queremos una buena aproximación en la vecindad de nuestro punto de partida .

Para la visualización, consulte la página de Wikipedia de la serie Taylor / Teorema de Taylor , o la Academia Khan sobre aproximación de la serie Taylor , o la página MathDemo sobre aproximación polinómica de no polinomios