-
Notifications
You must be signed in to change notification settings - Fork 1
/
gradient-boosting.Rmd
142 lines (83 loc) · 8.83 KB
/
gradient-boosting.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
---
title: "Sobre Gradient Boosting y Tumbas"
output:
html_document:
toc: true
toc_float: true
theme: sandstone
knit: (function(input, ...) {
rmarkdown::render(input, output_dir="docs")
})
---
<!-- TODO: generalidades de aprendizaje supervisado (ver slides) -->
<!-- ## Aprendizaje supervisado -->
<!-- Función de pérdida $J(y,\hat{y})$ -->
Boosting
--------
Las técnicas de ensamble estiman el target $y$ con una suma de $M$ estimadores base $b$ que dependen de $\mathbf{x} \in \mathbb{R}^p$ tal que para cada observación $i$:
$$\hat{y}_i = f(\mathbf{x}_i) = \sum_{m=1}^{M} b_m(\mathbf{x}_i)$$
En **boosting** en particular, los modelos $b_m$ son modelos "débiles" (**weak learners**) que se entrenan secuencialmente con versiones continuamente alteradas de los datos, de modo que la predicción general vaya mejorando lentamente en áreas donde no ajusta bien. Los modelos son débiles en el sentido en que son simples y reducen la pérdida $J$ en una magnitud levemente por encima de lo que lo haría una estimación al azar. Es necesario que sean poco complejos para evitar el sobreajuste.
El problema de optimización general
$$\min J(y,\hat{y}) = J(y,\sum_{m=1}^{M} b_m(\mathbf{x}_i))$$
se resuelve en *boosting* mediante una simplificación: en cada iteración $m$ se resuelve el problema más simple
$$\min J(y,b_m(\mathbf{x}))$$
Es decir que en cada iteración se ajusta el estimador base $b_m$ y se agrega a la estimación general $f(\mathbf{x})$ tomando como dadas las estimaciones anteriores --los $b_m$ no se modifican una vez que se pasa a las iteraciones subsiguientes. Esta solución se conoce como **forward stagewise additive modeling**.
Si la primera ronda de boosting comienza en $m=1$, decimos entonces que $f$ se inicializa con un valor constante $b_0$ tal que $b_0 = \arg\min_b J(y,b)$ --es decir, se usa la constante que minimiza la pérdida en las instancias de entrenamiento (por ejemplo, la media de $y$ cuando la función de pérdida es el error cuadrático medio).
Gradient Boosting
-----------------
La técnica de *gradient boosting* ajusta la función $f$ usando **descenso por el gradiente en el espacio funcional**.
En el caso más tradicional de descenso por el gradiente, el descenso se hace en el espacio de los parámetros. Por ejemplo, si la predicción $\hat{y}=f(\mathbf{x},\mathbf{\theta})$ dependiera de un vector de parámetros $\mathbf{\theta} \in \mathbb{R}^p$, se puede ajustar $f$ ajustando $\mathbf{\theta}$ secuencialmente desciendendo por el gradiente de la pérdida $J$ con respecto a $\theta$:
$$ \mathbf{\theta}^{(m)} = \mathbf{\theta}^{(m-1)} - \eta \frac{\partial J}{\partial \mathbf{\theta}^{(m-1)}} $$
donde $\eta$ representa la tasa de aprendizaje --es decir, el tamaño del ajuste que se realiza en la dirección del gradiente-- y $\theta$ se inicializa en valores al azar. Desde luego, la forma específica que tome la derivada $\frac{\partial J}{\partial \mathbf{\theta}^{(m)}}$ dependerá de la función de pérdida elegida --que asumimos es diferenciable con respecto a $\mathbf{\theta}$-- y de la forma de $f(\mathbf{x},\mathbf{\theta})$. El vector $\mathbf{\theta}$ que se obtiene luego de las $M$ iteraciones puede usarse para predecir $y$ cualquier set de observaciones.
Es posible usar descenso por el gradiente en el espacio de los parámetros solamente para ciertas configuraciones del problema --por ejemplo, si $f$ fuera una proyección lineal $f(\mathbf{x},\mathbf{\theta})=\mathbf{x}^T\mathbf{\theta}$.
En algunos contextos esto no es posible y podemos recurrir al descenso por el gradiente en el espacio funcional: el objetivo $J$ se optimiza secuencialmente usando el gradiente de $J$ con respecto a las predicciones $\hat{y}$ tal que:
$$ \hat{y}^{(m)} = \hat{y}^{(m-1)} - \eta \frac{\partial J}{\partial \hat{y}^{(m-1)}} $$
donde $\hat{y}$ se iniciliza en valores al azar.
Sin embargo esta forma de descender por el gradiente no devuelve ninguna forma funcional que se pueda aplicar a nuevas observaciones. Solo nos permite obtener predicciones $\hat{y}_i$ para las mismas observaciones $i$ con las que se realiza la optimización. De hecho, lo único que estamos haciendo es corregir $\hat{y}$ iterativamente para que se acerque a $y$, haciendo tender la pérdida a 0 en los datos de entrenamiento.
Este problema se puede resolver de la siguiente manera:
En lugar de actualizar las predicciones con el verdadero valor del gradiente según las datos de entrenamiento, se puede entrenar un modelo en cada iteración que estime esta dirección. Estos modelos son los estimadores base $b_m$ de *boosting*.
Definiendo $r^{(m-1)}=-\frac{\partial J}{\partial \hat{y}^{(m-1)}}$ podemos redefinir la ecuación de ajuste como:
$$ \hat{y}^{(m)} = \hat{y}^{(m-1)} + \eta b_m(\mathbf{x}) $$
donde cada estimador $b_m$ de aprende un *mapping* de ${\mathbf{x}}$ hacia $r^{(m-1)}$. La magnitud de las predicciones de $b_m$ en cada iteración dependerá entonces de la magnitud de los gradientes $r^{(m-1)}$ durante el entrenamiento, que decrece tendencialmente a medida que crece $m$. De hecho, los gradientes negativos $r$ pueden entenderse como **residuos generalizados** entre $y$ y $\hat{y}$ que aplican a cualquier función de pérdida.
Este abordaje nos permite usar *boosting* con estimadores base CART y con cualquier función de pérdida diferenciable. En particular, podemos usar funciones de pérdida robustas a observaciones atípicas (como la *deviance* o *log-loss* en el contexto de clasificación, o *absolute loss* para regresión). La inducción de árboles es particularmente difícil para estas funciones de pérdida, y justamente la motivación del *gradient boosting* es superar esta dificultad.
<!-- en particular lo que es dificil de resolver es (10.29) de ESL -->
Gradient Boosted Trees
----------------------
### CART
Los *Gradient Boosted Trees* usan CART como estimadores base para resolver un problema de optimización con *gradient boosting*. Los CART particionan el espacio de los predictores $\mathbf{x}$ en $T$ regiones disjuntas $R_t$ --las hojas--, y le asignan a cada una un *score* $w_t$. De esta manera se genera una predicción para $y$ según la regla
$$
\hat{y} = tree(\mathbf{x},\theta) = \sum_{t=1}^{T} w_tI(\mathbf{x} \in R_t)
$$
Se puede definir el conjunto de parámetros a estimar durante el ajuste del modelo como $\theta = \{R_t,w_t\}_{t=1}^T$. Es decir, es necesario definir (a) qué variables usar para particionar el espacio, (b) con qué puntos de corte y (c) qué *score* asignar a cada región del espacio. En particular buscamos encontrar $\theta$ tal que se minimice la pérdida $J$ en los datos de entrenamiento.
Desde luego se trata un problema complejo que requiere recorrer muchas soluciones posibles para encontrar la óptima, sobre todo cuando el número de predictores $p$ es muy alto. La estrategia subóptima que usa CART es un algoritmo *greedy* que va particionando el espacio recursivamente usando las variables con los puntos de corte que optimizan algún criterio adecuado de pérdida --el índice Gini para problemas de clasficación o la suma de residuos al cuadrado para regresión, por ejemplo.
Dadas las regiones $R_t$, en cada una se computa un *score* constante $w_t$ según
$$
w_t = \arg\min_w \sum_{\mathbf{x} \in R_t} J(y,w)
$$
de modo tal de minimizar la función de pérdida acorde al problema para las observaciones que pertenecen a la región.
### CART + Gradient Boosting
En el contexto de *boosting* se ajustan $M$ CARTs $b_m = tree_m$, que al sumarse dan lugar a la predicción final para cada observación $i$:
$$\hat{y}_i = f(\mathbf{x}_i) = \sum_{m=1}^{M} tree_m(\mathbf{x}_i, \theta_m)$$
Al tratarse de *gradient boosting*, los parámetros de cada $tree_m$ se ajustan para predecir los residuos generalizados $r$ de la iteración anterior. Una vez ajustado $tree_m$, la predicción $\hat{y}$ se corrige según la regla $\hat{y}^{(m)} = \hat{y}^{(m-1)} + \eta tree_{m}$.
<!-- TODO: -->
<!-- 2. ver si se puede incorporar numero de leaves (T) como param separado -->
<!-- entender algoritmo 10.3 parte (c) en ESL -- en cada región se encuentra w que minimiza la misma función de pérdida general -- por qué se incluyen f_{m-1} en la minimizacion) --comparar con XGB -->
<!-- SEGUIR DESDE ACÁ -->
<!-- (describir gbm con hiperaparametros ya mencionadas y el agregado de subsampling) -->
<!-- Implementaciones -->
<!-- ---------------- -->
<!-- ### GBM -->
<!-- GBM/MART -->
<!-- - Número de iteraciones $M$ -->
<!-- - Tasa de aprendizaje $\eta$ -->
<!-- - """Tamaño""" de los árboles $XXX$ -->
<!-- Subsampling (ver en ESL) -->
<!-- ### XGBoost -->
<!-- En XGB que usar 2nd order (Newton) es una ventaja (+precision?) -->
<!-- ### LightGBM -->
Referencias
-----------
- https://web.stanford.edu/~hastie/ElemStatLearn/
- https://explained.ai/gradient-boosting/
- http://nicolas-hug.com/blog/gradient_boosting_descent
- https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf