Guía de lectura de Xgboost y comprensión del artículo
La implementación técnica del texto completo se divide en dos partes.
Obviamente, xgboost es un modelo aditivo no lineal.
Si es un problema de regresión, puede ser:
Shachihoko
? El problema de clasificación debe ser de entropía cruzada, aquí:
Dos problemas de clasificación:
Problema de clasificación múltiple:
Aquí para revisar, para clasificación múltiple y dos -clasificación, entropía cruzada y fórmula suave, la clasificación binaria es un caso especial de clasificación múltiple.
：
：
Descripción original: Dirección predeterminada, entiendo que debería ser: en cada iteración, cada árbol debe tratar una característica faltante en la misma dirección. pero las direcciones faltantes de diferentes características son aleatorias; diferentes subárboles iterativos tienen estrategias aleatorias.
En el proceso de construcción de árboles, lo que lleva más tiempo es encontrar el punto de división óptimo, y la parte de este proceso que lleva más tiempo es ordenar los datos. Para reducir el tiempo de clasificación, Xgboost utiliza una estructura de bloques para almacenar datos (los datos de cada bloque se almacenan en formato de columnas comprimidas (CSC) y cada columna se ordena según el valor de característica relevante).
Para algoritmos aproximados, Xgboost utiliza múltiples bloques, que existen en múltiples máquinas o discos. Cada fragmento corresponde a un subconjunto de los datos originales. Se pueden calcular diferentes bloques en diferentes máquinas. Este enfoque es particularmente eficaz para las estrategias locales, que regeneran puntos de división candidatos cada vez que se ramifican.
Una desventaja de utilizar la estructura de bloques es que al obtener el gradiente, se obtiene por índice, y el orden en que se obtienen estos gradientes se basa en el tamaño de la característica. Esto da como resultado un acceso discontinuo a la memoria, lo que puede resultar en una menor tasa de aciertos de la memoria caché de la CPU, lo que afecta la eficiencia del algoritmo.
¿En algoritmos codiciosos no aproximados? Utilice la captación previa con reconocimiento de caché. Específicamente, a cada subproceso se le asigna un búfer continuo, la información del gradiente se lee y se almacena en el búfer (realizando así la transición de discontinuo a continuo) y luego se cuenta la información del gradiente.
En el algoritmo de aproximación, el tamaño del bloque se establece adecuadamente. Defina el tamaño del bloque como el número máximo de muestras en el bloque. Establecer un tamaño adecuado es muy importante. Si es demasiado grande, fácilmente conducirá a una baja tasa de aciertos, y si es demasiado pequeño, conducirá a una baja eficiencia de paralelización. Mediante experimentos, se descubrió que 2 16 es mejor.
Cuando la cantidad de datos es demasiado grande para caber en la memoria principal, para hacer posible el cálculo fuera del núcleo, los datos se dividen en bloques y se almacenan en el disco. Durante el cálculo, se utiliza un subproceso independiente para colocar los bloques en la memoria principal con anticipación, de modo que el disco se pueda leer mientras se calcula. Pero debido a que la velocidad de E/S del disco es demasiado lenta, generalmente no es tan rápida como la velocidad de cálculo. Por lo tanto, necesitamos aumentar las ventas de disco IO. Xgboost utiliza dos estrategias:
Compresión de bloques: comprime bloques por columna (¿algoritmo de compresión LZ4?) y usa otro hilo para descomprimir al leer. Para los índices de fila, solo se guarda el primer valor del índice, y luego solo se guarda el desplazamiento entre los datos y el primer valor del índice, usando 16 bits para guardar un * * * bit.
Por lo tanto, un bloque generalmente tiene 16 muestras de 2.
Fragmentación de bloques: divida los datos en diferentes discos, asigne un subproceso de captación previa a cada disco y extraiga los datos en un búfer de memoria. Luego, el hilo de entrenamiento lee alternativamente datos de cada búfer. Esto ayuda a mejorar el rendimiento de lectura del disco cuando hay varios discos disponibles.
[1] ?r. El presente y el futuro de la competición de la Copa KDD: la perspectiva de un forastero. (Aplicación XG boost)
[2] ?Beckman, Bilenko y Langford. ? Ampliación del aprendizaje automático: enfoques paralelos y distribuidos. Cambridge University Press, Nueva York, NY, EE. UU., 2011. (Diseño distribuido en paralelo)
[3] Bennett y Ronning. Premios Netflix. ¿existir? Actas del simposio de la Copa KDD 2007, páginas 3 a 6, Nueva York, NY, agosto de 2007. (Aplicación XG Boost)
[4] ? Bosque aleatorio. ? Aprendizaje mecanizado, 45(1):5–32, octubre de 2006 5438+0. (Artículo forestal aleatorio de Breman)
[5] Burgess. De Rankne a Landarank y Landamat: descripción general. ? Aprendizaje, 11:23–581, 2010.
[6] ?O. Chapelle y Y. Chang. Yahoo! Una visión general del desafío de la alineación del aprendizaje. ? Revista de investigación sobre aprendizaje automático. CP, 14:1–24, 2011. (Aplicación XG Boost)
[7] Chen Tinghua, Li, Yang, Yu. Factorización de matrices de funciones generales mediante aumento de gradiente. ¿existir? En curso
30ª Conferencia Internacional sobre Aprendizaje Automático (la factorización matricial general se logra mediante el aumento de gradiente).
(ICML 13), Volumen 1, páginas 436–444, 2013.
[8] T. Chen, S. Singer, B. Tuskal y C. Gestrin. Eficiente
Mejora del gradiente de segundo orden de campos aleatorios condicionales. ¿existir? Actas de la 18.ª Conferencia sobre Inteligencia Artificial y Estadísticas (AI Stats' 15), Volumen 1, 2015. (Campos aleatorios condicionales con mejora de derivada cuadrática)
[9] Fan Ruoying, Zhang Guowei, Xie Zhenjie, Wang Xirui y Lin Zhenjie. LIBLINEAR: Gran biblioteca de clasificación lineal. ? Revista de investigación sobre aprendizaje automático, 9:1871–1874, 2008. (Aplicación XG Boost)
J. Aproximación de función codiciosa: refuerzo de gradiente. ? Anales de estadística, 29(5):1189–1232, 2001. (Algoritmo codicioso de GBM)
j. Aumento del gradiente estocástico. ? Estadística Computacional y Matemática. Análisis de datos, 38(4):367–378, 2002.
(Descenso de gradiente estocástico)
[12] J. Friedman, T. Hastie y R. Tiburani. Regresión logística aditiva: una perspectiva estadística sobre el impulso. ? Anales de estadística, 28(2):337–407, 2000. (Regresión logística superpuesta)
J.H Friedman y B.E. 2003. Conjuntos de aprendizaje de muestreo de importancia. (Aprendizaje por muestreo)
Sr. Greenwald y Sr. Khanna. Cálculo en línea con uso eficiente del espacio de resúmenes de cuantiles. ¿existir? Actas de la Conferencia Internacional ACM SIGMOD de 2001 sobre Gestión de Datos, páginas 58–66, 2001.
[15] X. He, J. Pan, O. Jin, T. Xu, B. Liu, T. Xu, Y. Shi,
Atala, R. Herbrich, S. Bowles y JQN Candela. Experiencia práctica en la predicción de clics en anuncios de Facebook. ¿existir?
Actas del 8º Taller Internacional sobre Minería de Datos para Publicidad Online, dkdd' 14, 2014. (Aplicación XG Boost)
Lee. Logitboost robusto y Logitboost de clase base adaptable (ABC). ¿existir? Actas de la 26ª Conferencia Anual sobre la Incertidumbre en la Inteligencia Artificial (UAI'10), páginas 302–311, 2010. (logitboost)
[17] P. Li, Q. Wu y C. J. Burgers. Mcrank: aprender a clasificar mediante clasificación multiclase y aumento de gradiente. ¿existir? Avances en sistemas de procesamiento de información neuronal 20, págs. 897-904, 2008. (Múltiples aplicaciones de clasificación)
[18] X. Meng, J. Bradley, B. Yavuz, E. Sparks,
Nan Venkatala Mann, Liu, Freeman, Cai, Ahmed, Owen, Xin,
Meter (abreviatura de metro)) Zahariya y Tavoka. ml lib: Aprendizaje automático en Apache Spark. ?
Revista de investigación sobre aprendizaje automático, 17(34):1–7, 2016. (Diseño de aprendizaje automático distribuido)
B. Panda, J. S. Herbach, S. Basu y R. J. Bayardo. Planeta: aprendizaje paralelo a gran escala de conjuntos de árboles utilizando mapreduce. ? Actas de VLDB Endurance Racing, 2(2):1426–1437, agosto de 2009.
(Diseño de aprendizaje automático distribuido)
[20] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel
B.Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Ampliar imagen autor: Jeffrey W.
D. Kullnerbo, M. Blucher, M. Perrot y E. Du Snee. sci kit-learn: aprendizaje automático en Python. ?
Revista de investigación sobre aprendizaje automático, 12:2825–2830, 2011. (sklearn)
g . ? Modelos de impulso generalizados: una guía para el paquete gbm.
[22] S. Tyree, K. Weinberger, K. Agrawal y J. Paykin. Árboles de regresión impulsados en paralelo para la clasificación de búsqueda web. ¿existir? Actas de la vigésima conferencia internacional sobre la World Wide Web, páginas 387-396. ACM, 2011.
[23]JJ Ye, JJ Zhou, JJ Chen y Zheng Zhijun. Árboles de decisión distribuidos con aumento de gradiente estocástico. ¿existir? Actas de la 18ª Conferencia ACM sobre Gestión de la Información y el Conocimiento de CIKM'09.
[24] Zhang Qiyue, Wang Wenwei. Un algoritmo rápido para aproximar cuantiles en flujos de datos de alta velocidad. ¿existir? Actas de la XIX Conferencia Internacional sobre Gestión de Bases de Datos Científicas y Estadísticas de 2007. (Computación acelerada para el procesamiento de datos)
25T Zhang y R. Johnson. Aprendizaje de funciones no lineales utilizando bosques codiciosos regularizados. ? Transacciones IEEE sobre análisis de patrones e inteligencia artificial, 36(5), 2014.