Ejemplo de algoritmo de impulso de gradiente

Question

Estoy tratando de comprender completamente el método de impulso de gradiente (GB). He leído algunas páginas y documentos de Wiki al respecto, pero realmente me ayudaría a ver un ejemplo sencillo completo realizado paso a paso. ¿Alguien puede proporcionarme uno o darme un enlace a tal ejemplo? El código fuente directo sin optimizaciones difíciles también satisfará mis necesidades.

Answer 1

Traté de construir el siguiente ejemplo simple (principalmente para mi autocomprensión) que espero que puedan ser útiles para ti. Si alguien más nota algún error, hágamelo saber. Esto se basa de alguna manera en la siguiente buena explicación del impulso de gradiente http://blog.kaggle.com/2017/01/23/a-kaggle-master-explains-gradient-boosting/

El ejemplo tiene como objetivo predecir el salario por mes (en dólares) en función de si la observación tiene o no casas propias, automóviles propios e propios familiares/hijos. Supongamos que tenemos un conjunto de datos de tres observaciones en las que la primera variable es 'tener su propia casa', la segunda es 'tener un auto propio' y la tercera variable es 'tener familia/hijos', y el objetivo es 'salario por mes'. Las observaciones son

1.- (sí, sí, sí, 10000)

2 .- (No, no, no, 25)

3 .- (Sí, no, no, 5000)

Elige un número $ M $ de impulso de etapas, digamos $ M = 1 $. El primer paso del algoritmo de impulso de gradiente es comenzar con un modelo inicial $ F_ {0} $. Este modelo es una constante definida por $ mathrm {arg min} _ { gamma} sum_ {i = 1}^3l (y_ {i}, gamma) $ en nuestro caso, donde $ L $ es la función de pérdida. Supongamos que estamos trabajando con la función de pérdida habitual $ L (y_ {i}, gamma) = frac {1} {2} (y_ {i}- gamma)^{2} $. Cuando este es el caso, esta constante es igual a la media de las salidas $ y_ {i} $, entonces en nuestro caso $ frac {10000+25+5000} {3} = 5008.3 $. Entonces nuestro modelo inicial es $ F_ {0} (x) = 5008.3 $ (que mapea cada observación $ x $ (por ejemplo (no, sí, no)) a 5008.3.

A continuación, debemos crear un nuevo conjunto de datos, que es el conjunto de datos anterior pero en lugar de $ y_ {i} $ Tomamos los residuos $ r_ {i0} =- frac { parcial {l (y_ {i}, f_ {0} (x_ {i}))}} { parcial {f_ {0} (x_ {i})}} $. En nuestro caso, tenemos $ r_ {i0} = y_ {i} -f_ {0} (x_ {i}) = y_ {i} -5008.3 $. Entonces nuestro conjunto de datos se convierte en

1.- (sí, sí, sí, 4991.6)

2 .- (No, no, no, -4983.3)

3 .- (Sí, no, no, -8.3)

El siguiente paso es adaptarse a un alumno base $ H $ a este nuevo conjunto de datos. Por lo general, el alumno base es un árbol de decisión, por lo que usamos esto.

Ahora suponga que construimos el siguiente árbol de decisión $ H $. Construí este árbol usando la entropía y las fórmulas de ganancia de información, pero probablemente cometí algún error, sin embargo, para nuestros propósitos podemos suponer que es correcto. Para obtener un ejemplo más detallado, verifique

https://www.saedsayad.com/decision_tree.htm

El árbol construido es:

Llamemos a este árbol de decisión $ H_ {0} $. El siguiente paso es encontrar una constante $ lambda_ {0} = mathrm {arg ; min} _ { lambda} sum_ {i = 1}^{3} l (y_ {i}, f_ {0} (x_ {i})+ lambda {h_ {0} (x_ {i})}) $. Por lo tanto, queremos una constante $ lambda $ minimización

$ C = frac {1} {2} (10000- (5008.3+ lambda*{4991.6}))^{2}+ frac {1} {2} (25- (5008.3+ lambda (-4983.3) ))^{2}+ frac {1} {2} (5000- (5008.3+ lambda (-8.3)))^{2} $.

Aquí es donde el descenso de gradiente es útil.

Supongamos que comenzamos en $ P_ {0} = 0 $. Elija la tasa de aprendizaje igual a $ eta = 0.01 $. Tenemos

$ frac { parcial {c}} { parcial { lambda}} = (10000- (5008.3+ lambda*4991.6)) (-4991.6)+(25- (5008.3+ lambda (-4983.3)))) *4983.3+(5000- (5008.3+ lambda (-8.3)))*8.3 $.

Entonces nuestro próximo valor $ P_ {1} $ es dado por $ P_ {1} = 0- eta { frac { parcial {c}} { parcial { lambda}} (0)} = 0 -.01 (-4991.6*4991.7+4983.4*(-4983.3)++ (-8.3)*8.3) $.

Repita este paso $ N $ tiempos, y suponga que el último valor es $ P_ {n} $. Si $ N $ es suficientemente grande y $ eta $ es suficientemente pequeño entonces entonces $ lambda: = p_ {n} $ debería ser el valor donde $ sum_ {i = 1}^{3} l (y_ {i}, f_ {0} (x_ {i})+ lambda {h_ {0} (x_ {i})}) $ se minimiza. Si este es el caso, entonces nuestro $ lambda_ {0} $ será igual a $ P_ {n} $. Solo por el bien, supongamos que $ P_ {n} = 0.5 $ (de modo que $ sum_ {i = 1}^{3} l (y_ {i}, f_ {0} (x_ {i})+ lambda {h_ {0} (x_ {i})}) $ se minimiza en $ lambda: = 0.5 $). Por lo tanto, $ lambda_ {0} = 0.5 $.

El siguiente paso es actualizar nuestro modelo inicial $ F_ {0} $ por $ F_ {1} (x): = f_ {0} (x)+ lambda_ {0} h_ {0} (x) $. Dado que nuestro número de etapas de aumento es solo una, entonces este es nuestro modelo final $ F_ {1} $.

Ahora suponga que quiero predecir una nueva observación $ x = $(Sí, sí, no) (Entonces, esta persona tiene su propia casa y auto propio pero no niños). ¿Cuál es el salario por mes de esta persona? Solo calculamos $ F_ {1} (x) = f_ {0} (x)+ lambda_ {0} h_ {0} (x) = 5008.3+0.5*4991.6 = 7504.1 $. Entonces, esta persona gana $ 7504.1 por mes según nuestro modelo.

Answer 2

Como dice, la siguiente presentación es una introducción 'suave' al impulso de gradiente, me pareció bastante útil al descubrir el impulso de gradiente; Hay un ejemplo completamente explicado incluido.

http://www.ccs.neu.edu/home/vip/teach/mlcourse/4_boosting/slides/gradient_boosting.pdf

Answer 3

Este es el repositorio donde reside el paquete xgboost. Ahí es de donde se bifurca la biblioteca XGBOOST para idiomas principales como Julia, Java, R, etc.

Este es la implementación de Python.

Caminar a través del código fuente (como se indica en los documentos "Cómo contribuir") lo ayudaría a comprender la intuición detrás de él.