¿Qué opinas sobre el nuevo LightGBM de código abierto de Microsoft?

Autor: Ke Guolin

Enlace: /question/51644470/answer/130946285

Fuente: Zhihu: Zhihu

Copyright. Para reimpresiones comerciales, comuníquese con el autor para obtener autorización. Para reimpresiones no comerciales, indique la fuente.

Actualizado el 19/10/2017:

La lista completa de actualizaciones se puede encontrar en: Microsoft/LightGBM/Key-Events.md

Enumeradas a continuación Algunas actualizaciones más importantes

Paquete R completado

Valores faltantes

Las funciones categóricas se han optimizado aún más y ya no utilizan codificación de clics para funciones categóricas con una gran cantidad de. categorías, el uso de codificación de un solo paso dará como resultado un árbol muy desequilibrado y no puede lograr una buena precisión. Este es el punto débil de los modelos tipo árbol cuando admiten características categóricas para encontrar la división óptima de características categóricas, es decir, de muchos a. -muchas segmentaciones. La complejidad temporal de encontrar la segmentación óptima se puede completar en tiempo lineal, que es casi la misma que la complejidad de la segmentación uno a muchos original.

cf: ¿Qué son los NIPS? ¿Lo más destacado de 2017?

Actualizado el 17 de diciembre de 2016:

Completa el paquete de Python, bienvenido

Soporte directo sin funciones categóricas desplegadas. Es más rápida y precisa que la solución 0/1 sin empaquetar.

La mayoría de las herramientas de aprendizaje automático no admiten directamente funciones categóricas como entrada. Es necesario convertirlas en funciones 0/1 multidimensionales. LightGBM agrega cálculos adicionales y consumo de memoria para las características de clasificación, que también están bien implementadas en los árboles de decisión. La idea principal es calcular la clasificación, no a través de umbrales como las características numéricas, sino directamente. utiliza una categoría como una categoría y las otras categorías como otra categoría. En realidad, esto tiene el mismo efecto que la expansión 0/1.

----------------. ----------------------

Resultó que fue de código abierto durante un mes, por lo que la respuesta es muy poderosa.

Aunque GBDT es un modelo potente, tiene un defecto fatal: no se puede entrenar en forma de mini lotes, lo que requiere realizar un número infinito de pasadas sobre los datos. debe precargar todos los datos en la memoria, pero luego los datos estarán limitados por el tamaño de la memoria; si desea entrenar más datos, debe usar la versión de memoria externa del algoritmo. optimizados y los SSD se están volviendo más populares, aún son más lentos bajo IO frecuente.

GBDT usa efectivamente más datos, recurrimos a GBDT distribuido y luego propusimos LightGBM. Su idea de diseño tiene dos puntos principales: 1. Una sola máquina puede utilizar la mayor cantidad de datos posible sin sacrificar la velocidad; 2.

Cuando varias máquinas funcionan en paralelo, el costo de comunicación es lo más bajo posible y se puede lograr una aceleración lineal en los cálculos.

Basándose en estos dos requisitos, LightGBM eligió el algoritmo de árbol de decisión basado en histograma. Los histogramas tienen muchas ventajas en términos de consumo de memoria y costo computacional en comparación con la clasificación previa, otro algoritmo convencional como el algoritmo exacto en xgboost.

El algoritmo de clasificación previa requiere aproximadamente el doble de memoria que los datos de entrenamiento (2 * #data * #features

* 4 bytes), requiere números de punto flotante de 32 bits para contener la característica. valores, y cada característica de columna requiere un índice de clasificación adicional, que también requiere 32 bits de espacio de almacenamiento.

El algoritmo de histograma solo requiere (#datos

* #características * 1Bytes), que es 1/8 del consumo de memoria del algoritmo de clasificación previa. Esto se debe a que el algoritmo de histograma solo necesita almacenar características. /p>

valores bin (valores discretos), en lugar de valores propios sin procesar, por lo que no se requiere clasificación, mientras que un valor bin

de tipo uint8_t (256

bins ) es generalmente suficiente.

La ventaja computacional del algoritmo del árbol de decisión radica en la "partición de datos". El algoritmo del árbol de decisión tiene dos operaciones principales: una es "encontrar el punto de división" y la otra es "división de datos". Desde la perspectiva de la complejidad temporal del algoritmo, el algoritmo de histograma y el algoritmo de clasificación previa cuestan lo mismo para "encontrar el punto de segmentación", ambos son O (#características*#datos). En "División de datos", el algoritmo de clasificación previa requiere O(#features*#data), mientras que el algoritmo de histograma es O(#data). El algoritmo de histograma no requiere clasificación, todas las características están en la misma tabla de índice y solo se requiere una división en esta tabla de índice. (Actualización: esto no es del todo correcto. Cuando la clasificación previa se combina con la clasificación por niveles, en realidad puede usar una tabla de índice (row_idx_to_tree_node_idx). Luego, cuando busque el punto de división, ambas operaciones de nodo del mismo nivel, eliminando así el paso de división. pero el problema con esto es que habrá muchos accesos aleatorios, habrá muchos errores de chche y la velocidad seguirá siendo muy lenta (...).

Otra ventaja computacional es que la cantidad de cálculos de ganancias de puntos de división se reduce considerablemente. Para una característica, la clasificación previa requiere calcular la ganancia de división una vez para cada valor de característica diferente, mientras que el histograma solo necesita calcular el #bin una vez (el eje horizontal del número de histograma).

Finalmente, el uso de histgoram reduce significativamente el costo de comunicación cuando se usa el algoritmo de clasificación previa. Es por eso que xgoobst usa histogramas por razones de comunicación. Tiene sus desventajas: no puede encontrar puntos de segmentación muy precisos y el error de entrenamiento no es tan bueno como el algoritmo de clasificación previa. Sin embargo, a juzgar por los resultados experimentales, el algoritmo de histograma no es muy diferente del error centralizado. El algoritmo de clasificación previa, de hecho, a veces es incluso mejor. Esto puede deberse a que el árbol de decisión no es muy sensible a la precisión de los puntos de división y los puntos de división "más gruesos" también tienen su propio efecto de regularización. p>

Basado en el algoritmo de histograma, LightGBM se ha optimizado aún más. En primer lugar, abandona la estrategia de crecimiento del árbol de decisión paso a paso utilizada por la mayoría de las herramientas GBDT y, en su lugar, utiliza un algoritmo de profundidad limitada. El algoritmo de nivel puede dividir las hojas de la misma capa en los datos al mismo tiempo, lo que es fácil de realizar una optimización de subprocesos múltiples y no es propenso a sobreajustarse. Pero, de hecho, el algoritmo de nivel es ineficiente porque lo hace. No se aplica a la misma capa. Las hojas de la capa se tratan indiscriminadamente, lo que genera muchos gastos generales innecesarios. De hecho, la ganancia de segmentación de muchas hojas es muy baja, por lo que no es necesario buscarlas y segmentarlas. hojas" es una forma más eficiente. La estrategia es encontrar la hoja con la mayor ganancia dividida (generalmente la mayor cantidad de datos) de todas las hojas actuales, y luego dividirla, y así sucesivamente. Por lo tanto, en comparación con el nivel , En la misma división, al mismo tiempo, la forma de hoja puede reducir más errores y obtener una mayor precisión. La desventaja de la forma de hoja es que puede generar árboles de decisión más profundos, lo que lleva a un sobreajuste. sabio se agrega un límite de profundidad máxima para evitar el sobreajuste y al mismo tiempo garantizar una alta eficiencia.

Otra optimización inteligente es la aceleración de diferencia de histograma. No es difícil encontrar que el histograma de una hoja se puede distinguir por su padre. Se obtienen el histograma del nodo y el histograma de sus nodos hermanos.

Normalmente, para construir un histograma, es necesario recorrer todos los datos de esa hoja, pero la diferenciación de histogramas solo requiere atravesar k depósitos del histograma. Usando este enfoque, LightGBM puede construir el histograma de una hoja y luego obtener el histograma de sus hojas hermanas a una fracción del costo, duplicando así la velocidad.

Para más información, consulta la documentación en github:/Microsoft/LightGBM/wiki/Features