\documentclass{beamer}
\usepackage[latin1]{inputenc}%
\usepackage[T1]{fontenc}%
\usepackage[spanish]{babel}%
\usepackage{graphicx}
\usepackage{beamerthemesplit}
\usepackage{color}
%\spanishdecimal{.}
\title {Boosting}
\author{Carleos Artime, C.; Corral Blanco, N.}
%\pgfdeclareimage[width=1.0cm]{escudo}{escudoAC}
%\% titlegraphic{\pgfuseimage{escudo}}
% \institute{.\\[0pt]\vspace*{-10mm}%
%   \parbox[b][24mm][b]{40mm}{Facultad de Ciencias\\ C/ Federico García Lorca, s/n.\\ 33007-OVIEDO\\
% \textcolor{blue}{\url{www.unioviedo.es/ciencias}}}\\[-3mm]}
% \date{\footnotesize Octubre 2017\\[-3mm]}
% \hypersetup{
%    bookmarks=false,         % show bookmarks bar?
%    pdfauthor={Norberto Corral }%,    % author
% }

\begin{document}

\frame{\titlepage}


%\part{Puntos Fuertes de PISA}
%---------------
\begin{frame}\frametitle{Boosting}

Boosting es un procedimiento de aprendizaje supervisado que consiste en crear modelos diferentes, cuyos resultados se combinan
para obtener una predicción más precisa que la obtenida con cada modelo. \\
\vspace{0.3cm}
Se basa en las ideas desarrolladas por Kearns y Valiant (1988, 1989) acerca de si dado un conjunto de clasificadores débiles 
es posible crear un clasificador eficiente.\\
\vspace{0.3cm}
En le boosting siempre se utiliza el conjunto completo de datos, aunque en cada iteración se van variando su peso, ya que los 
casos que son mal clasificados ganan peso y los otros lo pierden peso.\\

\end{frame}


\begin{frame}\frametitle{AdaBoost}

Este algoritmo fue desarrolado por Freund y Schapire en 1995.\\
\vspace{0.3cm}
El algoritmo trabaja con el conjunto de datos  $(\vec{x}_i,y_i)$,i=1,...n donde $x_i \in X$ representa a las variables predictoras ; 
$y_i \in Y={-1, 1}$ la variable dependiente.\\
\vspace{0.3cm}

El algoritmo AdaBoost trabaja de manera iterativa utilizando en cada etapa $t$ un procedimiento base de clasificación y una 
distribución de pesos $D_t$\\
\vspace{0.3cm}

En cada iteración se modifican las ponderaciones del conjunto de entrenamiento, aumentando la de los individuos mal clasificados y 
 disminuyedo la del resto.\\
 \vspace{0.3cm}
En cada iteración el objetivo es calcular un criterio de clasificación $h_t:X \rightarrow Y$ 
\end{frame}


\begin{frame}\frametitle{AdaBoost}

 Para una muestra de tamaño $n$, la distribución de pesos inidiales en el conjunto de entrenamiento es  $D_1(i)=\frac{1}{n}$.
 
 \vspace{0.3cm}
El algoritmo AdaBoost tiene los siguiente pasos:\\

 \begin{itemize}
  \item Calcular la función de clasificación $h_t$ que haga mínimo el error 
  $$e_i=\sum_{h_t(x_i) \ne y_i} D_t(i)$$
  \item Calcular la ponderación $\alpha_t$ del clasificador $h_t$ definida por 
  $$ \alpha_t = \frac{1}{2} \, ln(\frac{1-e_t}{e_t})$$
  \item Actualizar la distribución de pesos
  $$ D_{t+1}(i) = \frac{D_{t}(i) \, exp(-\alpha_t\, y_i \, h_t(x_i))}{Z_t}$$
$Z_t$ es un factor para conseguir que $D_{t+1}$ sea una probabilidad
 \end{itemize}
 \end{frame} 
 
 
 \begin{frame}\frametitle{AdaBoost}
 El clasificador final del algoritmos se define mediante la función:
 $$H(x) = sign(\sum_{t=1}^{T} \alpha_t \, h_t(x))$$
 
 que es un promedio ponderado de todas los clasificadores obtenidos en las T iteraciones.
\end{frame} 


\begin{frame}\frametitle{Real AdaBoost}

La distribución de pesos iniciales es  $D_1(i)=\frac{1}{n}$.
 
 \vspace{0.3cm}
El algoritmo Real AdaBoost tiene los siguiente pasos:\\

 \begin{itemize}
 \item Usar un clasificador para estimar las probabilidades $$p_t(\vec{x})= \hat{P}_{D_t}(y=1|\vec{x})$$
  \item Calcular  
  $$h_t(\vec x) = \frac{1}{2} \, \ln \frac{P_{D_t}(y=1\mid\vec x)}{P_{D_t}(y=-1\mid\vec x)}$$
  \item Actualizar la distribución de pesos
  $$ D_{t+1}(i) = \frac{D_{t}(i) \, exp(y_i \, h_t(x_i))}{Z_t}$$
$Z_t$ es un factor para conseguir que $D_{t+1}$ sea una probabilidad
 \end{itemize}
  \end{frame} 
  
  \begin{frame}\frametitle{Real AdaBoost}
 El clasificador final del algoritmos se define mediante la función:
 $$H(x) = sign(\sum_{t=1}^{T}\, h_t(x))$$
 \vspace{0.4cm}
 
Su mayor inconveniente es que $h_t(\vec x)$ depende del cociente de probabilidades
   $$ \frac{P_{D_t}(y=1\mid\vec x)}{P_{D_t}(y=-1\mid\vec x)}$$
 \end{frame} 


 \begin{frame}\frametitle{Logit AdaBoost}

La distribución de pesos iniciales es  $D_1(i)=\frac{1}{n}$.

Las probabilidades iniciales son $$p_1(\vec{x}_i)= \hat{P}_{D_1}(y=1|\vec{x}_i)=\frac12$$

Se define $y^* = \frac{y+1}2$
 
 \vspace{0.3cm}
El algoritmo Logit AdaBoost tiene los siguiente pasos:\\

 \begin{itemize}
  \item Calcular $$ z_i = \frac {y_i^* - p_{t-1}(\vec x_i)} {p_{t-1}(\vec x_i)(1-p_{t-1}(\vec x_i))} $$
  $$ D_t(i) = p_{t-1}(\vec x_i)(1-p_{t-1}(\vec x_i)) $$
  \item Calcular  
  $h_t(\vec x)$ mediante una regresión mínimo-cuadrática $D_t$-ponderada de $z_i$ sobre $\vec x_i$
  \item Actualizar $H(\vec x)\gets H(\vec x)+\frac12 h_t(\vec x)$ y 
  $p_t(x)\gets \frac {e^{F(\vec x)}} {e^{F(x)}+e^{-F(x)}}$.
 \end{itemize}
\end{frame} 
  
\begin{frame}\frametitle{Logit AdaBoost}
 El clasificador final del algoritmos se define mediante la función:
 $$H(x) = \text{signo}\biggl(\sum_{t=1}^{T}\, h_t(x)\biggr)$$
 \vspace{0.4cm}
 
 Cuando $p(\vec x)$ está cerca de 0 o de 1 puede problemas de estabilidad en el cálculo de $z_i$.

En esos casos, se acota entre $-z_{\text{max}}$ y $z_{\text{max}}$
 
 Valores recomendados: $2 < z_{\text{max}} < 4$
 
 \vspace{0.3cm}
 Los pesos $D_t$ no deben ser menores que 2 $\times$ el cero de la máquina.
 
 \end{frame} 

 
 
\begin{frame}\frametitle{Gentle AdaBoost}

 Gentle AdaBoost usa un algoritmo tipo Newton por etapas en lugar de calcular el óptimo en cada una de ellas\\

En la etapa inicial $H(\vec{x})=0$
 \vspace{0.3cm}

 \begin{itemize}
  \item Calcular  
  $h_t(\vec x)$ mediante una regresión ponderada de mínimos cuadrados de $y$ sobre $\vec x$
  \item Actualizar la distribución de pesos
  $$ D_{t+1}(i) = \frac{D_{t}(i) \, exp(y_i \, h_t(x_i))}{Z_t}$$
$Z_t$ es un factor para conseguir que $D_{t+1}$ sea una probabilidad
 \end{itemize}
 
  \end{frame} 
  
  \begin{frame}\frametitle{Gentle AdaBoost}

 
El algoritmo Gentle AdaBoost usa una regresión de mínimos cuadrados ponderada
para calcular $h_t(\vec x)$.
 \vspace{0.3cm}

Su principal diferencia con el Real AdaBoost es que evita calcular
el log del cociente de probabilidad
  
 El clasificador final del algoritmos se define mediante la función:
 $$H(x) = sign(\sum_{t=1}^{T}\, h_t(x))$$
 \end{frame} 


 
\begin{frame}\frametitle{AdaBoost para clasificación múltiple}

Dado un conjunto de datos $(\vec{x}_i,y_i),$ donde $y_i \in \{1, \ldots, J\}$


 \vspace{0.3cm}
El algoritmo AdaBoost.M1 tiene los siguiente pasos:\\

 \begin{itemize}
  \item Obtener la función de clasificación $h_t(\vec{x}) \in \{1,\ldots, J\}$ 
  \item Calcular el error 
  $$e_t=\sum_{h_t(\vec{x}_i) \ne y_i} D_t(i)$$
  \item Calcular la ponderación $\alpha_t$ del clasificador $h_t$ definida por 
  $$ \alpha_t = \frac{1}{2} \, ln(\frac{1-e_t}{e_t})$$
  \item Actualizar la distribución de pesos
   $$ D_{t+1}(i) = \frac{D_{t}(i) \, exp(-\alpha_t\, I(h_t(\vec{x}_i) \ne y_i) )}{Z_t}$$
$Z_t$ es un factor para conseguir que $D_{t+1}$ sea una probabilidad
 \end{itemize}
 \end{frame} 

 
 \begin{frame}\frametitle{AdaBoost para clasificación múltiple}
 
El algoritmo AdaBoost.M1 modifica el cálculo de $ \alpha_t $ y considera que la busqueda es adecuada cuando 
$e_t < \frac{1}{2}$

   \vspace{0.4cm}
 El clasificador final del algoritmos se define mediante la función:
  $$H(x) = arg \, max_{j \in Y}(\sum_{t=1}^{T} \alpha_t \, I(h_t(\vec{x}) = j))$$
 
 que representa la categoría 'más votada', para la muestra $\vec{x}$, en las T iteraciones.
 

\end{frame} 
 
 
 \begin{frame}\frametitle{AdaBoost para clasificación múltiple}

Dado un conjunto de datos $(\vec{x}_i,y_i),$ donde $y_i \in \{1, \ldots, J\}$


 \vspace{0.3cm}
El algoritmo SAMME tiene los siguiente pasos:\\

 \begin{itemize}
  \item Obtener la función de clasificación $h_t(\vec{x}) \in \{1,\ldots, J\}$ 
  \item Calcular el error 
  $$e_t=\sum_{h_t(\vec{x}_i) \ne y_i} D_t(i)$$
  \item Calcular la ponderación $\alpha_t$ del clasificador $h_t$ definida por 
  $$ \alpha_t =  ln(\frac{1-e_t}{e_t}) + ln(k-1)$$
  \item Actualizar la distribución de pesos
   $$ D_{t+1}(i) = \frac{D_{t}(i) \, exp(-\alpha_t\, I(h_t(\vec{x}_i) \ne y_i) )}{Z_t}$$
$Z_t$ es un factor para conseguir que $D_{t+1}$ sea una probabilidad
 \end{itemize}
 \end{frame} 

 
 \begin{frame}\frametitle{AdaBoost para clasificación múltiple}
 
 El algoritmo AdaBoost.M1 considera que la busqueda es adecuada cuando 
$e_t < \frac{1}{J}$

   \vspace{0.4cm}
   
 El clasificador final del algoritmos se define mediante la función:
  $$H(x) = arg \, max_{j \in Y}(\sum_{t=1}^{T} \alpha_t \, I(h_t(\vec{x}) = j))$$
 
 que representa la categoría 'más votada', para la muestra $\vec{x}$, en las T iteraciones.\\

\end{frame} 



\begin{frame}\frametitle{AdaBoost para clasificación múltiple. Logit AdaBoost}

El algoritmo Logit AdaBoost aborda la clasificación de un individuo entre $J$ clases como $J$ problemas de clasificación binaria

\vspace{0.4cm}
 
Se consideran $J$ variables de clasificación $y_{i\,j}^* = \frac{y_{i\, j}+1}2$\\
\vspace{0.4cm}

Las ponderaciones iniciales son: $D_1(i)=\frac{1}{n}$ \\
\vspace{0.4cm}
Las probabilidades iniciales son $$p_1(\vec{x}_i)= \hat{P}_{D_1}(y=1|\vec{x}_i)=\frac{1}{J}$$

Los $J$ clasificadores $H_j(\vec{x}) = 0$

\end{frame} 

\begin{frame}\frametitle{AdaBoost para clasificación múltiple. Logit AdaBoost}
Los etapas que sigue son las siguientes:

 \begin{itemize}
 \item Repetir para $t \in \{1, \ldots, T\}$
 \begin{itemize}
 \item Repetir para $j \in \{1, \ldots, J\}$
   \begin{itemize}
       \item Calcular $$ z_{i\, j} = \frac {y_{ij}^* - p_{j(t-1)}(\vec x_i)} {p_{j(t-1)}(\vec x_i)(1-p_{j (t-1)}(\vec x_i))} $$
        $$ D_t(i,j) = p_{j (t-1)}(\vec x_i)(1-p_{j (t-1)}(\vec x_i)) $$
       \item Calcular  
     $h_jt(\vec x)$ mediante una regresión mínimo-cuadrática $D_t$-ponderada de $z_{i j}$ sobre $\vec x_i$
  \end{itemize}
     \item Actualizar $H_j(\vec x)\gets H_{j}(\vec x)+\frac12 h_t(\vec x)$ y 
  $p_{j t}(x)\gets \frac {e^{F_j(\vec x)}} {e^{F_(x)}+e^{-F_(x)}}$\\
    con la restrición $\sum_{j=1}^{J} H_j(\vec{x})=0$.
 \end{itemize}
  \end{itemize}
 \vspace{0.3cm}
   El clasificador final del algoritmos vale:
 \vspace{-0.2cm}    
   $$H(x) = arg \, max_{j} H_j(\vec{x})$$
\end{frame} 
  

\begin{frame}\frametitle{Coeficiente kappa de Cohen}

\begin{itemize}
\item Mide el grado de concordancia entre dos observadores.
\item Se clasifican $N$ individuos en $k$ categorias excluyentes.
\item Se elimina el efecto de coincidencias por azar.
\item Inconvenientes:
\begin{itemize}
\item Las frecuencias marginales se consideran fijas
\item Esa corrección tiene sentido cuando los observadores responden al azar cuando no tienen una respuesta clara. 
\end{itemize}
\end{itemize}
\end{frame}


\begin{frame}\frametitle{Coeficiente kappa de Cohen}
$$
\kappa ={\frac {\Pr(C)-\Pr(Ca)}{1-\Pr(Ca)}}
$$
P(C) = Probabilidad de Concordancia entre los observadores 

P(Ca) = Probabilidad de Concordancia al azar entre los observadores

Si $\kappa$ = 1, acuerdo total. 

Si no hay acuerdo entre los calificadores distinto al que cabría esperar por azar, $\kappa$ = 0.

Estadísticos similares:
\begin{description}
 \item [pi de Scott (1955)]
Difieren en cuanto a la forma de cálculo de Pr(Ca).
\item [kappa de Fleiss (1971)]
Se usa cuando hay más de dos observadores.  Generaliza la pi de Scott.
\end{description}

\end{frame}


\begin{frame}\frametitle{Coeficiente kappa de Cohen: Ejemplo}

Se tiene un grupo de 50 personas que presentan una solicitud de subvención. 

Cada propuesta de subvención es analizada por dos evaluadores (A y B) que anotan un "Sí" o un "No".

\begin{center}
 \begin{tabular}{lrr}
	A: $\backslash$ B:	&Sí& 	No\\
 	Sí 	&20& 	5\\
	No 	&10& 	15
 \end{tabular}
\end{center}
Diagonal $\Rightarrow$ concordancia.

Antidiagonal $\Rightarrow$ discordancia.
$$
\Pr(C)=\frac {20+15}{50}=0.7
$$
$$
\Pr(Ca)=\frac{25}{50}\frac{30}{50}+\frac{25}{50}\frac{20}{50}=0.5
$$
$$
\kappa ={\frac {0.7-0.5}{1-0.5}}=0.4
$$

\end{frame}


\end{document}
