Derivación de la fórmula xgboost

Como algoritmo de aprendizaje supervisado, el árbol impulsado contiene varias partes importantes: modelo, parámetros, función objetivo, algoritmo de optimización.

Modelo

El modelo se refiere a cómo será el la salida y se puede predecir dada la entrada x

Parámetros

Los parámetros se refieren a lo que necesitamos aprender. En el modelo lineal, los parámetros se refieren a nuestro coeficiente lineal w.

Función objetivo

Función objetivo: pérdida + ley, enséñenos cómo encontrar mejores parámetros

La función objetivo general consta de los dos elementos siguientes:

Compensación sesgo-varianza, el sesgo puede entenderse como el error causado al suponer que podemos entrenar el mejor modelo con datos ilimitados. La variación se debe a que solo tenemos datos limitados y la aleatoriedad generará errores.

La función de error intenta ajustar los datos de entrenamiento lo más cerca posible, mientras que el término de regularización fomenta la construcción de un modelo más simple. Esto se debe a que cuando el modelo es relativamente simple, la aleatoriedad de los resultados ajustados a datos limitados es menor y es menos probable que se produzca un sobreajuste, lo que hace que los resultados de predicción del modelo final sean más estables.

Algoritmo de optimización

El problema de cómo aprender dada la función objetivo

CART asigna la entrada a los nodos hoja de acuerdo con los atributos de la entrada, y cada El nodo de hoja corresponde a la parte superior con una puntuación verdadera.

CART suele ser demasiado simple para hacer predicciones efectivas, por lo que un modelo más potente se denomina conjunto de árboles. Nuestra predicción para cada muestra es la suma de las puntuaciones de predicción de cada árbol.

Conjunto de árboles

Función de predicción:

Función objetivo:

La primera parte es el error de entrenamiento y la segunda parte es el error de cada árbol La suma de la complejidad.

Cada vez mantenemos el modelo original sin cambios y agregamos una nueva función f a nuestro modelo.

¿Cómo elegimos qué funciones añadir en cada ronda?

Intente elegir una función f que minimice nuestra función objetivo (agregar f dará un error menor entre el resultado previsto y el resultado real).

Para el caso donde l es un error al cuadrado:

Para el caso donde l no es un error al cuadrado:

Utilice la siguiente aproximación de expansión de Taylor para definir una función objetivo aproximada

Al eliminar el término constante (la diferencia entre el valor verdadero y la ronda anterior de valores predichos), la función objetivo depende de la primera y segunda derivada de la función de error para cada punto de datos

Lo anterior es la función de entrenamiento en el programa de entrenamiento. p> Lo anterior es la parte del error de entrenamiento de la función objetivo, y luego se define la complejidad del árbol.

Para la definición de f, haga un pequeño refinamiento y divida el árbol en la función de estructura q (índice de nodo de hoja de entrada x salida) y la parte de peso de la hoja w (índice de nodo de hoja de entrada puntuación de nodo de hoja de salida ), la función de estructura q asigna la entrada a los números de índice de las hojas y w proporciona la puntuación de las hojas correspondiente a cada número de índice.

La complejidad de un árbol se define de la siguiente manera:

El número de nodos de hoja en el árbol y el cuadrado del módulo L2 de la puntuación de salida sobre cada nodo de hoja.

La función objetivo se reescribe de la siguiente manera:

donde I se define como el conjunto de muestras Ij={i|q(xi)=ji} encima de cada hoja (las muestras dentro de cada conjunto de nodos de hoja);

f(xi) es equivalente a encontrar el valor de w(q(xi)) (la fracción del índice de hoja donde se encuentra cada muestra T es el número de hoja); nodos.

Defina Gj (suma de gradientes de primer orden dentro de cada nodo hoja) Hj (suma de gradientes de segundo orden dentro de cada nodo hoja):

Reescritura de función objetivo:

Encuentre la derivada parcial:

Obj indica cuánto se puede reducir el objetivo del objetivo como máximo cuando especificamos la estructura del árbol. Se puede llamar ejemplo de cálculo de estructura de Obj.

Algoritmo codicioso exacto Algoritmo codicioso para obtener el punto de corte óptimo

Utilice esta función de puntuación para encontrar una estructura de árbol óptima, agréguela a nuestro modelo y repita la operación.

Un método común es el método codicioso, que agrega un punto de división a una hoja existente en cada intento. Para un escenario de división específico, calcule la ganancia:

Para cada expansión, ¿cómo podemos enumerar eficientemente todas las divisiones?

Supongamos que queremos enumerar todas las x

El objetivo de la optimización corresponde a la poda de árboles, por lo que cuando la ganancia de una división introducida es menor que un umbral, podemos podar la división.

El objetivo de la optimización corresponde a la poda del árbol.

Esto introduce la selección de nodos divididos para calcular la puntuación y calcula el término de penalización de las hojas en función de la derivación, reemplazando el coeficiente de Gini y las operaciones de poda del árbol de regresión.

Reducción, en la que el resultado generado de cada árbol se multiplica por un factor de paso para evitar el sobreajuste

El muestreo de selección de columnas es similar al bosque aleatorio en el muestreo de las características de cada árbol para evitar sobreajuste

Algoritmo codicioso

Algoritmo 1 Algoritmo codicioso exacto: el algoritmo codicioso obtiene el punto de división óptimo

Algoritmo aproximado Algoritmo aproximado

Algoritmo 2 Utilice Sk

Idea central:

A través de la distribución de características, determine un conjunto de puntos de segmentación candidatos de acuerdo con el algoritmo de histograma ponderado distribuido y encuentre el mejor punto de segmentación atravesando todos los puntos de segmentación candidatos.

Al buscar puntos de división, en lugar de enumerar todos los valores de las características, los valores de las características se resumen y cuentan, y luego se forman varios depósitos y solo se utilizan los valores de las características en los límites del depósito. como puntos de división para lograr mejoras de rendimiento.

Bosquejo de cuantificación ponderada: algoritmo de histograma ponderado distribuido

Cómo encontrar Sk

Determine los puntos de segmentación candidatos calculando el peso de cada punto dentro de cada característica (interpretado como un histograma dispuesto en un orden determinado, con no más de un punto candidato adyacente). Umbrales que controlan el ancho de cada histograma)

Referencia

Algoritmo para procesar la segmentación de entidades dispersas

Para entidades discretas dispersas, al buscar puntos de segmentación, no se requiere recorrido Se realizará y calculará muestras con características faltantes, mientras que solo atravesará y calculará muestras con valores de características no faltantes en la columna. Recorra solo los valores propios correspondientes en muestras con valores propios no faltantes en la columna. Esta técnica de ingeniería reduce el tiempo necesario para encontrar puntos de segmentación para características discretas dispersas. En la implementación lógica, los dos casos de asignación de muestras con valores de características faltantes a los nodos de la hoja izquierda y a los nodos de la hoja derecha se manejan por separado para garantizar la integridad. Para valores faltantes o valores especificados, se puede especificar la dirección predeterminada de la rama, lo que puede mejorar en gran medida la eficiencia del algoritmo y se menciona 50 veces en el artículo.

Paralelización

Antes del entrenamiento, cada característica se clasifica internamente para encontrar puntos de corte candidatos y luego se guarda como una estructura de bloque para ser reutilizada en iteraciones posteriores, lo que reduce en gran medida la cantidad de cálculo. Al dividir un nodo, es necesario calcular la ganancia de cada característica y, finalmente, seleccionar la característica con la mayor ganancia para dividir. Luego, el cálculo de la ganancia de cada característica se puede realizar en varios subprocesos, es decir, utilizando diferentes atributos de característica para. Encuéntrelo en forma paralela de subprocesos múltiples. El mejor punto de división.

Aunque las iteraciones del algoritmo de impulso deben ser en serie, se pueden paralelizar a medida que se procesa cada columna de características.

La optimización hará que la información de gradiente de cada muestra en la memoria sea discontinua y la acumulación directa puede causar errores de caché. Por lo tanto, xgboost primero llevará los datos estadísticos de la muestra al búfer interno del hilo. y luego Acumulación por lotes.

El almacenamiento por columnas de características puede optimizar la búsqueda de puntos de división óptimos, pero el cálculo de datos de gradiente por filas conducirá a un acceso discontinuo a la memoria, lo que provocará errores de caché y reducirá la eficiencia del algoritmo. El artículo menciona que los datos se pueden recopilar en el búfer interno del hilo antes del cálculo para mejorar la eficiencia del algoritmo.

Oficial

Parámetros generales:

Parámetros generales:

booster [default=gbtree] Selecciona clasificador básico gbtree, gblinear tree o Lineal clasificador

silencioso [predeterminado= 0] Si se genera información detallada 0 No generar 1 Salida

nthread [valor predeterminado es el número máximo de subprocesos disponibles si no está configurado] Número máximo predeterminado de subprocesos

Parámetros de Tree Booster:

1.eta [predeterminado=0.3]: parámetro de contracción multiplicado al actualizar los pesos de los nodos de hoja para evitar un tamaño de paso demasiado grande. Cuanto mayor sea el valor del parámetro, más probable será que no se produzca convergencia. Establecer una tasa de aprendizaje más pequeña eta. Una tasa de aprendizaje más pequeña puede hacer que el aprendizaje posterior sea más cauteloso.

2. min_child_weight [predeterminado=1]: Este parámetro por defecto es 1, que es la suma mínima de h en cada hoja. Para una clasificación 0-1 con muestras positivas y negativas desequilibradas, suponiendo que h sea alrededor de 0,01, un min_child_weight de 1 significa que los nodos de hoja deben contener al menos 100 muestras.

3. max_ Depth [default=6]: La profundidad máxima de cada árbol Cuanto más profundo sea el árbol, más fácil será sobreajustarlo.

4.

4. gamma [predeterminado = 0]: la reducción de pérdida mínima requerida para una mayor partición en los nodos de hoja del árbol. Cuanto mayor es, más conservador es el algoritmo. [0,∞]

5. max_delta_step [valor predeterminado = 0]: este parámetro juega un papel en el paso de actualización. Si el valor es 0, significa que no hay límite si el valor es positivo. , significa que los pasos de actualización son más conservadores. Evita que el tamaño del paso de actualización sea demasiado grande y hace que las actualizaciones sean más suaves. Normalmente, este parámetro no es necesario, pero en regresión logística puede resultar útil cuando las clases están muy desequilibradas. Establecer esto en un valor de 1 a 10 puede ayudar a controlar las actualizaciones.

6. submuestra [predeterminado = 1]: muestreo aleatorio, cuanto menor es el valor, más conservador es el algoritmo, lo que puede evitar el sobreajuste, pero un valor demasiado pequeño también provocará un subajuste.

7. colsample_bytree [predeterminado = 1]: muestreo de columnas, realiza muestreo de columnas en las características utilizadas para generar cada árbol. Generalmente se establece en 0.5-1

8. lambda [predeterminado = 1]: parámetro del término de regularización L2, utilizado para controlar el valor de peso de la complejidad del modelo, cuanto mayor es el parámetro, menos probable es el modelo; es sobreajustar.

9. alfa [predeterminado = 0]: parámetro de regularización L1, utilizado para controlar el valor de peso de la complejidad del modelo. Cuanto mayor sea el valor del parámetro, es menos probable que el modelo se sobreajuste.

10. scale_pos_weight [predeterminado=1]: Si el valor de scale_pos_weight es mayor que 0, ayudará a converger rápidamente en el caso de muestras desequilibradas.

11.tree_method [default='auto'] opcional {'auto', 'exact', 'approx'} algoritmo codicioso (conjunto de datos pequeño) / algoritmo aproximado (conjunto de datos grande)

Parámetros de la tarea de aprendizaje:

objetivo [default=reg:linear] define el tipo de función de pérdida de minimización

El valor más común:

binario: logístico Regresión logística binaria, devuelve probabilidades predichas (en lugar de categorías).

multi:softmax Un clasificador múltiple que utiliza softmax y devuelve clases predichas (en lugar de probabilidades).

En este caso, necesitas un parámetro más: num_class (número de categorías).

Los parámetros de multi:softprob son los mismos que los de multi:softmax, pero devuelve la probabilidad de que cada dato pertenezca a cada categoría.

semilla [predeterminado=0] Semilla aleatoria

eval_metric [valor predeterminado basado en el objetivo objetivo]

Métrica de datos válidos.

El valor predeterminado es rmse para problemas de regresión y error para problemas de clasificación.

Los valores típicos son:

error cuadrático medio de la raíz rmse ( ∑Ni=1?2N√ )

error absoluto medio de mae ( ∑Ni=1 |? |N )

valor de la función de probabilidad logarítmica negativa logloss

tasa de error binario de error (umbral 0,5)

tasa de error de clasificación múltiple de merror

función de pérdida de logloss multiclase mlogloss

área auc bajo la curva

Parámetros de la línea de comando:

num_round número de iteraciones/número de árboles