¿Por qué XGBoost tiene una tasa de aprendizaje?

Question

Pregunta original

Después de haber utilizado XGBoost bastante, está claro que cambiar la tasa de aprendizaje afecta drásticamente al rendimiento del algoritmo. Dicho esto, realmente no puedo entender la justificación teórica para ello. Tiene sentido en el gradient boosting "vainilla", cuando no se utilizan segundas derivadas. Análogamente, no se necesita una tasa de aprendizaje si se utiliza Newton-Raphson para realizar la optimización encontrando los ceros de la derivada de la función de coste.

Pensé que podría tener que ver con asegurar que las actualizaciones que uno hace en cada paso son pequeñas, y por lo tanto la expansión del gradiente a segundo orden es válida, pero me parece que uno podría lograr lo mismo de manera más eficaz mediante la regularización?

Además, los documentos de XGBoost contienen una introducción teórica a XGBoost y no mencionan la tasa de aprendizaje en ninguna parte ( https://xgboost.readthedocs.io/en/latest/tutorials/model.html )

¿Es tan sencillo como "se ha observado experimentalmente que mejora el rendimiento" y, en caso afirmativo, es posible racionalizarlo a posteriori?

Actualización: Casi un año después, he pensado en actualizar mis ideas al respecto y afinar un poco mi pregunta.

Si bien es posible que la necesidad de una tasa de aprendizaje se haya comprobado experimentalmente, me parece probable que la razón por la que es necesaria tenga que ver con el hecho de que XGBOOST asume que la pérdida total $L$ de un clasificador consistente en un clasificador existente $F_{t}(x)$ más un nuevo clasificador $f_{t+1}(x)$ puede escribirse como una expansión de Taylor de $L$ acerca de $F_{t}(x)$ que requiere $f_{t+1}(x)$ para representar una corrección "suficientemente pequeña" para $F_{t}(x)$ que no necesitamos ampliar a un orden demasiado alto.

Hace tiempo que sospecho que el uso de mucha regularización debería solucionar este problema, de ahí que ¿por qué utilizar una tasa de aprendizaje? Otro enfoque podría ser decir que el árbol $f_{t+1}(x)$ que divide el espacio en varias regiones distintas (nodos terminales) $\{R_{j}\}$ produce una constante $\epsilon \cdot w_{j}$ en el $j^{th}$ región. Eligiendo una región $\epsilon$ podemos garantizar que $\epsilon \cdot w_{j}$ será suficientemente pequeño para cualquier partición y cualquier j.

Resulta, sin embargo, que si se sigue la derivación de los documentos XGBOOST pero se adopta este enfoque, y no se utiliza ninguna regularización, el peso $w_{j}^{*}$ debe asignar a la región $R_{j}$ viene dado por

$w_{j}^{*} = - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\epsilon \sum_{i \in R_{j}}\frac{\partial ^{2}\ell}{\partial \hat{y}_{i}^{2}}}$

en el que $L[F_{t}(x)+f_{t+1}(x)] = \sum_{i=1}^{N}\ell (y_{i}, \hat{y}_{i})=\sum_{i=1}^{N}\ell (y_{i}, F_{t}(x_{i}) + f_{t+1}(x_{i}))$

En otras palabras, si se establece que la salida de cada árbol en cada hoja será una constante $w_{j}$ multiplicado por un número muy pequeño $\epsilon$ , lo suficientemente pequeño como para garantizar que el producto sea siempre pequeño, $w_{j}^{*}$ simplemente compensará, así que cuanto más pequeño hagas $\epsilon$ cuanto mayor sea $w_{j}^{*}$ y el producto permanece inalterado. Crucialmente, el producto no será necesariamente "suficientemente pequeño" para que la serie de Taylor converja rápidamente y justifique la expansión de segundo orden. Sin embargo, si se utiliza un poco de regularización, lo suficiente para detener $w_{j}$ convirtiéndose en infinito y así garantizar que el producto sea siempre pequeño, entonces estás bien.

En esencia, tienes dos enfoques:

1. Establecer $\lambda$ sea "muy grande", esto garantizará que $w_{j}^{*}$ es pequeño, por lo que la expansión es válida
2. Utilizar un parámetro de velocidad de aprendizaje $\epsilon$ y una pequeña regularización, para garantizar que $w_{j}^{*}$ no puede ser arbitrariamente grande

Suenan igual, a nivel fenomenológico, pero investiguemos la $w_{j}^{*}$ implican. Usando el enfoque 1, sin tener una tasa de aprendizaje, obtenemos (como en los docs de xgboost, enlazados arriba)

$w_{j}^{*}= - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\lambda + \sum_{i \in R_{j}}\frac{\partial^{2} \ell}{\partial \hat{y}_{i}^{2}}\bigg|_{F_{t}(x_{i})}}$

mientras que si utilizamos también una tasa de aprendizaje, obtenemos

$w_{j}^{*}= - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\frac{\lambda}{\epsilon} + \epsilon \cdot \sum_{i \in R_{j}}\frac{\partial^{2} \ell}{\partial \hat{y}_{i}^{2}}\bigg|_{F_{t}(x_{i})}}$

Se parecen mucho y, en ambos casos, a medida que se aumenta el grado de regularización, al aumentar $\lambda$ el término de curvatura pierde relevancia. En el caso de que tenga una tasa de aprendizaje, puede conseguir este efecto aumentando $\lambda$ o disminuyendo $\epsilon$ .

Cualquiera de los dos enfoques me parece conceptualmente el mismo, pero ofrecen soluciones ligeramente distintas. Además, en la práctica, la tasa de aprendizaje es quizá el hiperparámetro más importante que hay que afinar en XGBOOST, aunque no he visto a nadie explorar si se podrían obtener resultados igual de buenos afinando más el parámetro de regularización. En concreto, ¿se me escapa algo de estas dos ecuaciones?

Otra actualización: un año más

Gracias a Andreas por su respuesta a continuación, que me llevó a esto.

Dado que se supone que la función de pérdida se aproxima mediante una función cuadrática en $w_{j}$ que es válido si $w_{j}$ es pequeño, sólo tendrá un mínimo (suponiendo que estemos haciendo una minimización de pérdidas). Por tanto, la pérdida evaluada en $\epsilon \cdot w^{*}_{j}$ será mayor que la pérdida evaluada en $w^{*}_{j}$ pero inferior a la pérdida evaluada en $w_{j}=0$ En otras palabras, actualizando su predicción mediante $\epsilon \cdot w^{*}_{j}$ , está garantizado que disminuirá su pérdida de entrenamiento. Si $\epsilon$ es muy pequeño, este proceso se produce muy lentamente, pero si $\epsilon$ es demasiado grande, entonces la serie de Taylor podría no ser válida. El punto clave aquí es que no se trata de encontrar el óptimo $w_{j}$ Se trata de encontrar un $w_{j}$ que garantiza que la pérdida de entrenamiento disminuye en cada iteración.

Creo que la lógica debe ser algo así, pero no puede ser del todo así. Aunque estoy de acuerdo en que si sabemos $w^{*}_{j}$ entonces $\epsilon w^{*}_{j}$ también disminuirá la pérdida de entrenamiento, pero esta lógica me parece circular. Si realmente supiéramos $w^{*}_{j}$ entonces mientras podría multiplicar por $\epsilon$ ¿por qué lo haríamos?

A la inversa, si queremos encontrar el óptimo $w_{j}$ siempre que $w_{j}$ es suficientemente pequeño, no parece correcto encontrar el óptimo $w_{j}$ suponiendo que $w_{j}$ es pequeño, descubrir que no es pequeño y multiplicarlo por un número pequeño para hacerlo pequeño.

Answer 1

En concreto, ¿se me escapa algo de estas dos ecuaciones?

Por lo que he mirado en El documento de Friedman la "tasa de aprendizaje $\epsilon$ (en este caso, denominada "contracción" y denotada por $\nu$ ) se aplica después de elegir esos pesos $w_j^*$ que minimizan la función de coste. Es decir, determinamos los pesos óptimos del impulso, $w_j^*$ primero, y sólo después consideramos multiplicar por $\epsilon$ .

¿Qué significaría esto?

Esto significaría que ninguna de las ecuaciones de la pregunta que presentan ambas $\epsilon$ y $w_j^*$ se utilizan en el algoritmo XGBoost.

Además, que $\lambda$ sigue siendo necesaria para garantizar la validez de la expansión de Taylor, y tiene un efecto no uniforme sobre la $w_j$ su efecto depende de las derivadas parciales de $\ell$ como escribiste antes: \begin{align*} w_{j}^{*}= - \frac{\sum_{i \in R_{j}}\frac{\partial \ell}{\partial \hat{y}_{i}}\bigg|_{F_{t}(x_{i})}}{\lambda + \sum_{i \in R_{j}}\frac{\partial^{2} \ell}{\partial \hat{y}_{i}^{2}}\bigg|_{F_{t}(x_{i})}} \end{align*}

La tasa de aprendizaje no entra en juego hasta después de este punto, cuando, habiendo determinado los pesos óptimos del nuevo árbol $\lbrace w_j^* \rbrace_{j=1}^T$ decidimos que, en realidad, no queremos añadir directamente lo que acabamos de considerar el "refuerzo óptimo", sino actualizar nuestro predictor aditivo $F_t$ añadiendo una versión a escala de $f_{t+1}$ Escalando cada peso $w_j^*$ uniformemente por $\epsilon$ y escalando así la contribución del conjunto de $f_{t+1}$ por $\epsilon$ También.

Desde donde estoy sentado, hay algunos analogía (débil) con la tasa de aprendizaje en la optimización por descenso de gradiente: suavemente agregando los predictores para iterar hacia lo que creemos que es un predictor general y descriptivo, pero manteniendo el control sobre la rapidez con la que llegamos a él. Por el contrario, una tasa de aprendizaje elevada implicará que utilicemos toda nuestra capacidad de predicción con relativa rapidez. Si lo hacemos demasiado deprisa con muy pocos árboles, entonces cualquier refuerzo posterior podría tener que hacer grandes correcciones, haciendo que la pérdida se mantenga en una meseta relativamente alta, tras unos pocos pasos de los cuales el algoritmo termina.

Mantener una tasa de aprendizaje más baja ayudaría a la generalizabilidad, ya que dependemos menos de las predicciones del nuevo árbol de refuerzo y, en cambio, permitimos que los refuerzos posteriores tengan más poder predictivo. Esto significa que necesitaremos más boosts y que el entrenamiento tardará más en terminar, en línea con los resultados empíricos mostrados en la respuesta de @Sycorax.

En resumen:

Según tengo entendido:

1. $\lambda$ se utiliza para regularizar las ponderaciones $\lbrace w_j\rbrace$ y justificar el truncamiento de 2º orden de la expansión de Taylor de la función de pérdida, lo que nos permite encontrar los pesos "óptimos". $\lbrace w_j^*\rbrace$ . Esto tiene un efecto no uniforme en cada uno de los pesos $w_j$ .

2. $\epsilon$ sólo se utiliza después de determinación de las ponderaciones óptimas $w_j^*$ y se aplica escalando todos los pesos uniformemente para obtener $\epsilon\, w_j^*$ .

Answer 2

En mi opinión, el boosting clásico y XGBoost tienen casi los mismos fundamentos para la tasa de aprendizaje. Personalmente veo dos tres razones para ello.

1. Un enfoque común es considerar el boosting clásico como un descenso de gradiente (DG) en el espacio de funciones ([1], p.3). En cuanto al GD univariante más sencillo, necesitamos definir una tasa de aprendizaje que garantice que damos pequeños pasos para no sobrepasar el mínimo. En este caso, XGBoost utiliza la aproximación de Taylor de 2º orden y, en este sentido, se aproxima al método de Newton. Aunque el uso de la tasa de aprendizaje no es un requisito del método de Newton, la tasa de aprendizaje peut utilizarse a veces para satisfacer las condiciones de Wolfe.

2. La tasa de aprendizaje proporciona contracción. Cada aprendiz débil es débil lo que significa que no puede reconstruir perfectamente los residuos (y no debería: si no, sobreajustaríamos). Así pues, la tasa de aprendizaje reduce el efecto de cada uno de esos aprendices débiles erróneos: vamos en la dirección correcta (opuesta al gradiente de la pérdida), pero no se nos permite dar pasos tan grandes como los que daríamos con aprendices fuertes. Esto es similar al descenso por gradiente estocástico: estamos obligados a mantener una tasa de aprendizaje pequeña, ya que nuestras estimaciones del gradiente son imprecisas. El efecto es aún más pronunciado en XGBoost, donde se añade una aleatorización adicional del árbol mediante el muestreo fila/columna. Los aprendices débiles subsiguientes proporcionan pequeñas correcciones paso a paso. Estas correcciones se acumulan con las iteraciones del algoritmo y si no se realiza una parada temprana en algún momento, a menudo se ajustará perfectamente al conjunto de entrenamiento (es decir, es probable que se sobreajuste).

3. (Añadido a la respuesta original). Regularización (Casi se me olvida la más relevante para la pregunta). Una tasa de aprendizaje más pequeña permite añadir más aprendices débiles hasta que el error de la prueba empieza a aumentar([1], p.15). Al promediar más aprendices débiles, se puede conseguir un error de generalización potencialmente menor. De nuevo, el efecto es aún más evidente en XGBoost, donde el muestreo de columna/fila reduce la correlación entre los aprendices débiles, lo que añade cierto efecto de "embolsamiento" al modelo de refuerzo.

Entonces, ¿podrías proporcionar derivaciones más detalladas de las ecuaciones de tu post? Parece extraño que la tasa de aprendizaje acabe en el denominador.

[1]Friedman, Jerome H. "Greedy function approximation: a gradient boosting machine". Anales de estadística (2001): 1189-1232.

Answer 3

Parámetros para Tree Booster eta [por defecto=0.3, alias: learning_rate] Tamaño del paso de reducción utilizado en la actualización para evitar el sobreajuste. [ ] Después de cada paso de refuerzo, podemos obtener directamente los pesos de las nuevas características. y eta reduce los pesos de las características para que el proceso de refuerzo sea más conservador. más conservador. rango: [0,1]

De: manual

Según esta fuente: matemáticas , learning_rate afecta al valor de la función de cálculo del gradiente que incorpora derivadas de primer y segundo orden. Acabo de mirar en el código, pero no soy bueno en Py, así que mi respuesta es realmente una guía para que usted pueda explorar más.

Answer 4

Encontrará más explicaciones en " XGBoost: Un sistema de refuerzo arbóreo escalable "por Tianqi Chen y Carlos Guestrin.

Además del objetivo regularizado mencionado en la sección 2.1, se utilizan dos técnicas adicionales para evitar el sobreajuste. La primera técnica es la contracción introducida por Friedman [11]. La contracción escala los pesos recién añadidos en un factor $\eta$ después de cada paso del refuerzo del árbol. De forma similar a la tasa de aprendizaje en [ sic ] cada árbol individual y deja espacio para que los árboles futuros mejoren el modelo.

Podemos consultar la cita para más información. En " Potenciación por gradiente estocástico escribe Friedman

que el parámetro "contracción $0 < \eta \le 1$ controla el ritmo de aprendizaje del procedimiento. Empíricamente (Friedman 1999), se comprobó que valores pequeños ( $\eta \le 0.1$ ) conducen a un error de generalización mucho mejor.

(Excepto que he editado la cita para usar un símbolo diferente por claridad y coherencia con el resto de este hilo).

Como ocurre con cualquier técnica de regularización, la gente la utiliza porque mejora el error de generalización en sus tareas de modelado. No conozco ningún estudio que examine si el parámetro de la tasa de aprendizaje es estrictamente necesario en el contexto de XGBoost (¡pero me interesaría leer uno!). Si nos basamos en la forma en que se presenta "XGBoost: A Scalable Tree Boosting System", parece que los autores no han realizado un análisis de este tipo, sino que se han basado en resultados anteriores de otros algoritmos de refuerzo.

Dado que en el artículo de Friedman también se discuten los efectos de añadir aleatoriedad adicional a los árboles reforzados (por ejemplo, bootstrapping), parece razonable suponer que en el contexto de las submuestras aleatorias, usted podría no quiere que los primeros árboles dominen la decisión de clasificación, ya que esos primeros árboles no son más que muestras aleatorias específicas de todos los datos de entrenamiento. En lugar de que todos los árboles posteriores se vean fuertemente influidos por las peculiaridades de las primeras muestras aleatorias, la introducción de la "tasa de aprendizaje" parece una forma inteligente de reducir la ponderación de los árboles.

Hablando desde la experiencia personal, la diferencia entre utilizar una tasa de aprendizaje de 1,0 y una tasa de aprendizaje menor, como 0,1, es que los modelos con la tasa de aprendizaje mayor reducen rápidamente la pérdida, pero también alcanzan rápidamente una meseta. He aquí un ejemplo en el que se comparan los mismos modelos sobre los mismos datos con diferentes tasas de aprendizaje. La tasa de aprendizaje menor disminuye más lentamente y alcanza una pérdida menor.

$$ \begin{array}{r|r|r|} \text{Iteration number} & \eta = 1 & \eta = 0.1 \\ \hline 1 & 0.216 & 0.373 \\ 2 & 0.138 & 0.245 \\ 3 & 0.109 & 0.176 \\ 4 & 0.100 & 0.136 \\ 5 & 0.103 & 0.110 \\ 6 & 0.111 & 0.0952 \\ 7 & 0.110 & 0.0845 \\ 8 & \text{terminated} & 0.0783 \\ 9 & - & 0.0758 \\ 10 & - & 0.0739 \\ 11 & - & 0.0716 \\ 12 & - & 0.0700 \\ 13 & - & 0.0702 \\ 14 & - & 0.0697 \\ 15 & - & 0.0703 \\ 16 & - & 0.0705 \end{array} $$

Esta observación

Después de haber utilizado XGBoost bastante, está claro que cambiar la tasa de aprendizaje afecta drásticamente al rendimiento del algoritmo. Dicho esto, realmente no puedo entender la justificación teórica para ello. Tiene sentido en el gradient boosting "vainilla", cuando no se utilizan segundas derivadas. Análogamente, no se necesita una tasa de aprendizaje si se utiliza Newton-Raphson para realizar la optimización encontrando los ceros de la derivada de la función de coste.

sugiere que quizás has confundido el aumento de gradiente con el gradiente descenso . Es muy común en la comunidad de redes neuronales llamar "tasa de aprendizaje" al "tamaño del paso" de un algoritmo de descenso por gradiente. Pero esto no es lo mismo que la "tasa de aprendizaje" en el algoritmo de descenso de gradiente. impulsar . En el refuerzo por gradiente, la "tasa de aprendizaje" se utiliza para "amortiguar" el efecto de cada árbol adicional al modelo. En el artículo de Friedman, el modelo tiene esta forma:

$$ F_m(x) = F_{m-1}(x) + \eta \cdot \gamma_{lm} \mathbf{1}(x \in R_{lm}) $$

que es una forma matemática de decir que a la redonda $m$ la función de predicción es la predicción de la ronda anterior $F_{m-1}$ más un múltiplo escalar $\eta$ de la nueva predicción. La expresión $\gamma_{lm} \mathbf{1}(x \in R_{lm})$ representa la solución a una optimización y una función indicadora de si $x$ es miembro de esa región.

Answer 5

Me sumo a la respuesta de Montol:

Creo que tiene razón en la mayoría de los puntos, excepto en que, a mi entender, es la tasa de aprendizaje