\documentclass{beamer}
\usefonttheme{serif}
\usepackage[latin1]{inputenc}
\usepackage[spanish]{babel}
\usepackage{beamerthemesplit}
\usepackage{arev}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Obj}{Obj}
\title{XGBoost}
\author{Análisis de Datos 3}
\begin{document}
\maketitle
\begin{frame} {Métodos de \emph{gradient boosting}}
  \begin{itemize}
  \item \emph{Gradient Boosting = Gradient Descent + Boosting}
  \item Boosting : buscar un modelo, de manera iterativa, como suma de
    otros modelos :
    $$H(x)=\sum_{t} \rho_t \ h_t(x)$$
  \item En cada etapa se incluye (suma) un nuevo modelo
    para reducir los errores (residuos).
  \item El \emph{adaboost} asocia los errores con las modificaciones en los
    pesos de ciertos puntos.
  \item En los métodos de \emph{gradient boosting}
    los errores se identifican con los gradientes.
  \item Ambos puntos de vista se emplean para mejorar los modelos.
\end{itemize}
\end{frame}

\begin{frame} {\emph{Gradient boosting} para regresión}
  Dada una muestra $\bigl((x_1, y_1), \ldots, (x_n, y_n)\bigr)$ se
  puede usar la regresión simple para predecir de forma sencilla:
  $$ \hat{y}=F_1(x) = \bar{y} + \frac{{\Cov}(x,y)}{S^2_x}\, (x-\hat{x})$$

  La idea es buscar un nuevo modelo $F_2$ para estimar los errores del
  modelo previo:
  $$\Bigl(\bigl(x_1, y_1-F_1(x_1)\bigr), \ldots,
  \bigl(x_n, y_n- F_1(x_n)\bigr)\Bigr)$$
  El modelo resultante de esas dos etapas será:
  $$\hat{y} = F_1(x) + F_2(x)$$
  El proceso se puede repetir hasta cumplir algún criterio de parada.
\end{frame}

\begin{frame} {\emph{Gradient boosting} para regresión}
  En la regresión se emplea el criterio de mínimos cuadrados, es decir,
  se trata de buscar el mínimo de la función de pérdida
  $$L(y, F(x)) = \frac{(y-F(x))^2}{2}$$
  $$J = \sum_{i=1}^n L(y_i, F(x_i)) =
  \frac{1}{2} \, \sum_{i=1}^n (y_i - F(x_i)^2$$
  Considerando cada $F(x_i)$ como un parámetro y derivando, se tiene:
  $$ \frac{\partial J}{\partial F(x_i)} =
  \frac{\partial \sum_{j} L(y_j,F(x_j))}{\partial F(x_i)} =
  \frac{ \partial  L(y_i,F(x_i))}{\partial F(x_i)} = F(x_i)-y_i$$
  El gradiente cambiado de signo se puede identificar con los errores:
  $$y_i-F(x_i) = -\frac{\partial J}{\partial F(x_i)} = -g(x_i)$$
\end{frame}

\begin{frame} {\emph{Gradient boosting} para regresión}

  La regresión lineal se puede expresar como un método
  \emph{gradient boosting}.
  \begin{itemize}
  \item Se inicia el proceso estimando $y$ mediante
    $$\hat{y} = F_1(x) = \bar y = \frac{\sum_{i=1}^{n} y_i}{n}$$
  \item Se calculan los menos gradientes $-g(x_i) = y_i-F_1(x_i)$
  \item Se busca una nueva función $F_2$ para ajustar $-g(x_i)$
    $$-\hat g(x)=F_2(x)$$
  \item El modelo final es $\hat{y} = F_1(x) +F_2(x)$
 \end{itemize} 
\end{frame}

\begin{frame} {\emph{eXtreme Gradient Boosting} (XGBoost)}
 \begin{itemize}
  \item Pertenece a la familia de métodos \emph{gradient boosting}.
  \item Se basa en modelos de árboles.
  \item Ganó varias competiciones de \texttt{kaggle}.
  \item Se puede usar desde \texttt{R}.
 \end{itemize}
\end{frame}

\begin{frame} {XGBoost}
  En la etapa $t$, el modelo predictivo es
  $\displaystyle F(x) = \sum_{k=1}^t F_k(x) $
  
  Los predictores $F_k$ están asociados a la función de
  pérdida elegida. Las más usuales son:
\begin{itemize}
\item Cuadrática
  $$L= \sum_{i=1}^n (y_i - \hat{y}_i)^2$$
\item Clasificación binaria (logística)
  $$L = -\sum_{i=1}^n \Bigl(y_i \log p_i  + (1-y_i)\log\bigl(1-p_i )\Bigr)$$
\item Clasificación múltiple 
  $$L = -\sum_{i=1}^n\sum_{j=1}^c \, y_{i,j} \log p_{i,j}$$
 \end{itemize}
\end{frame}

\begin{frame} {XGBoost}
  En la búsqueda del modelo se incluye un término de regularización,
  que penaliza la complejidad e impide el sobreajuste. Cuando se
  usan árboles, se puede definir mediante la expresión
  $$ \Omega = \gamma \, T  + \lambda \sum_{j=1}^p w_j^2$$
  donde $T$ = número de hojas y $w_j$ = puntuación de la hoja $j$-ésima.

  La función objetivo que se maneja para construir el modelo es
  $$ \text{Objetivo} = \Obj(y, \hat{y})= L + \Omega $$

  En cada etapa se calcula
  $\dfrac{\partial \Obj(y,\hat{y})}{\strut\partial \hat{y}}$ y se modifican
  las predicciones siguiendo la dirección del gradiente.
\end{frame}

\begin{frame} {XGBoost}
  En la iteración $t$, la búsqueda del nuevo predictor se basa en
  \begin{itemize}
  \item  La expresión de cada predicción:
    $$\hat{y}_i^t = \hat{y}_i^{t-1} + F_t(x_i)$$
  \item La función objetivo 
    $$ \Obj^t = \sum_{i=1}^n L\bigl(y_i, \hat{y}_i^{t-1}+F_t(x_i)\bigr)
    + \sum_{j=1}^t \Omega(F_j)$$
    Si la función de pérdida es cuadrática se tiene:
    $$ \Obj^t= \sum_{i=1}^n \Bigl((y_i - \hat{y}_i^{t-1}) - F_t(x_i)\Bigr)^2
    + \sum_{j=1}^{t-1} \Omega(F_j) + \Omega(F_t)$$
    $$= \sum_{i=1}^n 
    \Bigl( -2\,(y_i - \hat{y}_i^{t-1}) \, F_t(x_i) + F_t(x_i)^2\Bigr)
    + \Omega(F_t)+ \text{C}^{\text{te}}$$
  \end{itemize}
\end{frame}

\begin{frame} {XGBoost}
  La búsqueda de la solución se hace usando una aproximación de Taylor
  de orden dos de la función objetivo.
 $$f(x+\Delta x) \approx f(x) + f'(x) \, \Delta x 
 + \frac{1}{2} \, f''(x) \, \Delta x^2$$ 
 $$ \Obj^t = \sum_{i=1}^n \Bigl(
 L(y_i, \hat{y}_i^{t-1}) + g_i \, F_t(x_i) +
 \frac{1}{2} \, h_i\, F^2_t(x_i)\Bigr)  + \Omega(F_t) + \text{C}^{\text{te}} $$
 
 con $g_i= \dfrac{ \partial L(y_i, \hat{y}_i^{t-1})} {\partial \hat{y}_i^{t-1}}$
 y $h_i= \dfrac{ \partial^2 L(y_i, \hat{y}_i^{t-1})}
 {\partial (\hat{y}_i^{t-1})^2}$.
\end{frame}

\begin{frame} {XGBoost}
  Si las funciones predictoras se construyen usando árboles, la
  función objetivo se puede reescribir de manera sencilla:
  $$\Obj^t \approx \sum_{i=1}^n 
  g_i \, F_t(x_i) + \frac{1}{2} \, h_i\, F^2_t(x_i)
  + \Omega (F_j) + \text{C}^{\text{te}} ={}$$
  $${} = \sum_{i=1}^n g_i \, F_t(x_i) + \frac{1}{2} \, h_i\, F^2_t(x_i)
  + \gamma \, T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2
  + \text{C}^{\text{te}}={}$$
  $${} = \sum_{j=1}^T \, \left( 
    \sum_{i\in I_j} g_i \,w_j + \frac{1}{2} \,
    \sum_{i\in I_j} (h_i+ \lambda) \,w_j^2\right) + \gamma \, T$$
  donde $I_j = \{i\mid i \in \text{hoja }j\}$
\end{frame}

\begin{frame} {XGBoost}
  Datos perdidos:\bigskip

  \begin{enumerate}
  \item En un árbol binario, se asignan todos los casos con datos perdidos
    \begin{itemize}
    \item al nodo izquierdo, y se calcula la mayor ganancia.
    \item al nodo derecho, y se calcula la mayor ganancia.
    \end{itemize}
  \item Se elige la dirección con mayor ganancia.
    \end{enumerate}\bigskip
  Al final, todo nodo tiene una \emph{dirección por omisión}
    para datos con valores perdidos.
\end{frame}

\begin{frame} {XGBoost}
  El manejo del XGBoost depende de muchos parámetros que se utilizan
  para resolver los siguientes problemas:
  \begin{itemize}
  \item Evitar el sobreajuste.
  \item Muestras muy desbalanceadas.
  \end{itemize}
  Los parámetros se pueden agrupar en tres clases:
  \begin{itemize}
  \item Generales
  \item Relacionados con el \emph{boosting}
%    \begin{enumerate}
%    \item Stepsize
%    \item Regularización
%    \end{enumerate}
  \item Parámetros operativos
%    \begin{enumerate}
%    \item Función objetivo
%    \item Métricas de evalucación
%    \end{enumerate} 
  \end{itemize}   
\end{frame}

\begin{frame}{XGBoost}
  Parámetros generales\bigskip
  \begin{description}
  \item[booster] árbol o modelo lineal\\
    (casi siempre es mejor el árbol)
  \item[nthread] número de hilos de ejecución
  \end{description}
\end{frame}

\begin{frame}{XGBoost}
  Parámetros de \emph{boosting}\bigskip
  \begin{description}
  \item[eta] tasa de aprendizaje (más o menos conservadora)
  \item[gamma] reducción mínima para dividir
  \item[lambda] coeficiente de suma de pesos$^2$
  \item[max\_depth] máxima profundidad del árbol
  \item[min\_child\_weight] peso mínimo para dividir
  \item[subsample] proporción de entrenamiento
  \end{description}
\end{frame}

\begin{frame}[fragile]{XGBoost}
  Parámetros operativos\bigskip
  \begin{description}
  \item[objective] función de pérdida para el aprendizaje (por omisión,
    regresión de mínimos cuadrados)
    \begin{itemize}
    \item \verb+"reg:linear"+ (por omisión)
    \item \verb+"binary:logistic"+ (0 y 1)
    \item \verb+"multi:softmax"+ \\
      \verb+num_class=+$k\implies(0, ..., k-1)$
    \end{itemize}
  \item[eval\_metric] medida para validación (por omisión, raíz cuadrada
    del error cuadrático medio)
    \begin{itemize}
    \item \verb+rmse+
    \item \verb+error+ (proporción)
    \item \verb+auc+
    \end{itemize}
  \end{description}
\end{frame}

\begin{frame}[fragile]{XGBoost}
Bibliografía
\begin{itemize}
\item \verb+https://hastie.su.domains/Papers/ESLII.pdf+ \\
  Elements of Statistical Learning
\item \verb+https://github.com/dmlc/xgboost/+
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Paquete \texttt{xgboost} de R}
\begin{verbatim}
install.packages("xgboost")
library("xgboost")
?agaricus.train # referencia: label = poisonous
data(agaricus.train) ; atr <- agaricus.train
data(agaricus.test)
str(atr)
atr$data$Dimnames[[2]] # nombres de variables
b <- xgboost(atr$data, atr$label, nrounds=100)
b <- xgboost(atr$data, atr$label, nrounds=100,
             nthread=parallel::detectCores(),
             objective="binary:logistic")
table(agaricus.test$label,
      predict(b, agaricus.test$data) > .5)
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Paquete \texttt{xgboost} de R}
\begin{verbatim}
download.file(paste0(
 "http://bellman.ciencias.uniovi.es/~carleos",
 "/master/manadine/curso1/AnalisisDatos1",
 "/4-neuronas/dat/mnist.rda"),"/tmp/mnist.rda")
load("/tmp/mnist.rda")
Me <- M[1:60000,] # entrenamiento
b <- xgboost(as.matrix(Me[-785]), # -Label
        as.numeric(as.character(Me$Label)) - 1,
        nrounds=100, num_class=10,
        objective="multi:softmax")
Mv <- M[60001:70000,]
t <- table(Mv$Label,
           predict(b, as.matrix(Mv[-785])))
sum(diag(t)) # 98%
\end{verbatim}
\end{frame}
\end{document}

