Rmd/05-classification/05-classification.html

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <title>Algoritmos de Clasificación</title>
    <meta charset="utf-8" />
    <meta name="author" content="Víctor Gallego y Roi Naveiro" />
    <meta name="date" content="2019-04-11" />
    <link href="libs/remark-css-0.0.1/default.css" rel="stylesheet" />
    <link rel="stylesheet" href="custom.css" type="text/css" />
  </head>
  <body>
    <textarea id="source">
class: center, middle, inverse, title-slide

# Algoritmos de Clasificación
## Curso de aprendizaje automático para el INE
### Víctor Gallego y Roi Naveiro
### 2019-04-11

---

class: middle, center, inverse

# Intro a git

---

* Git es un sistema de **control de versiones** utilizado para gestionar archivos de código.

### En la terminal de bash (Linux, MacOS)

* Obtener e instalar el programa **git**: https://git-scm.com/.

* Descarga de un repositorio: **git clone https://github.com/albertotb/curso-ml-R**.

  Esto nos creará un nuevo directorio **curso-ml-R**, descargando todo lo que hubiera en la copia remota (la alojada en Github en este caso).

* Actualización de cambios: **git pull** (ejecutado dentro del directorio del repositorio).

  En caso de que la copia remota tenga cambios respecto a nuestra copia local, actualiza nuestra copia local del repositorio. Esto evita volver a descargar todo como al usar git clone.

---

### En Windows

* Podemos utilizar la interfaz gráfica oficial desde https://desktop.github.com. Tras instalarlo, en el menú principal escogemos **Clone a new repository**:

![:scale 90%](./img/clone.PNG)


---

* Ésta es la pantalla por defecto del repositorio. Podemos abrir los archivos en el explorador, o ver los cambios recientes en el lateral.

![:scale 90%](./img/no_changes.PNG)

---

* Para **sincronizar** nuestra copia local con el remoto, pulsamos en **Fetch** arriba, y en caso de haber cambios, pulsamos en **Pull origin** para confirmar.

![:scale 90%](./img/fetch.PNG)


---

class: middle, center, inverse

# Regresión Lineal en problemas de clasificación

---

## ¿Cómo aplicar regresión lineal a problema de clasificación multiclase?


* Consideramos `\(K\)` clases.

* **One Hot Encoding** de las categorías: para categoría *k*, crear vector `\(K\)` dimensional `\(t_k\)` con tan solo un 1 en posición `\(k\)` (resto ceros).

* `\(y_i = t_k\)` si la categoría del ejemplo i-ésimo es `\(k\)`.

--

* Problema de predicción: reproducir el target de cada observación. Resolver

`\begin{equation}
\min_{\textbf{B}} \sum_{i=1}^N \Vert y_i - [(1,x_i^\top) \textbf{B}]^\top\Vert^2
\end{equation}`

* Para clasificar nueva observación se calcula el vector `\(\hat{f}(x)\)` y se clasifica resolviendo

`\begin{equation}
\arg \min_{k} \Vert \hat{f}(x) - t_k \Vert^2
\end{equation}`

* Es fácil ver que el problema desacopla en `\(K\)` problemas de regresión (uno para cada clase).

---

## Problema - *masking*

* Cuando `\(K \geq 3\)` unas clases pueden enmascarar otras.

![:scale 45%](./img/masking1.png) ![:scale 45%](./img/masking2.png)

*Fuente*: Elements of Statistical Learning

---

class: middle, center, inverse

# Introducción

---

## Teoría de la decisión estadística

* Sea `\(X \in \mathbb{R}^p\)`, vector de variables predictoras.

* Sea `\(Y \in  \lbrace Y_1, Y_2, \dots, Y_K\rbrace\)`, respuesta categórica.

* Distribución de los datos `\(X, Y \sim p(X,Y)\)`.

--

* Dado nuevo `\(X\)` necesitamos estimar `\(\widehat{Y} (X) \in \lbrace \lbrace Y_1, Y_2, \dots, Y_K \rbrace\)`.
 
* Definimos función de coste `\(L[Y, \widehat{Y} (X)]\)`. Una bastante común: coste `\(0/1\)` (0 si acertamos, 1 si nos equivocamos).

--

* Objetivo: Escoger `\(\widehat{Y} (X)\)` que minimice coste esperado

`\begin{eqnarray}
\mathbb{E}_{X,Y} \left[ L(Y, \widehat{Y} (X)) \right] &amp;=&amp; \mathbb{E}_{X} \mathbb{E}_{Y\vert X}\left[ L(Y, \widehat{Y} (X)) \right] \\
&amp;=&amp; \mathbb{E}_{X} \sum_{i=1}^K L[Y_i, \widehat{Y} (X)] P(Y=Y_k \vert X)
\end{eqnarray}`
---

## Teoría de la decisión estadística

* Es suficiente minimizar el coste esperado para cada `\(x\)`

`\begin{eqnarray}
\widehat{Y} (x) = \arg \min_{y} \sum_{i=1}^K L[Y_i, y] P(Y=Y_k \vert X = x)
\end{eqnarray}`

--

* Con el coste `\(0/1\)` 

`\begin{eqnarray}
\widehat{Y} (x) = \arg \min_{y} \left[ 1 - P(y \vert X = x) \right]
\end{eqnarray}`

* Asignamos la clase con más probabilidad a posteriori.


---

## Teoría de la decisión estadística

* Hemos separado el problema de clasificación en dos partes

  1. **Inferencia**: usar datos de entrenamiento para encontrar `\(P(Y=Y_k \vert X = x)\)`.
  2. **Decisión**: usar las distribuciones a posteriori para tomar decisión óptima de clasificación (minimizar coste esperado, maximizar utilidad esperada...)
  
* Posibilidad alternativa: aprender directamente funciones que mapeen `\(X\)` en `\(Y\)`. 

  
---

## Tres maneras de enfrentar los problemas de clasificación

1. *Modelos generativos*: tratan de modelizar `\(P(Y,X)\)` (Naive-Bayes).

  + Permiten muestrear.
  + Detección de outliers (si `\(P(X)\)` es pequeño).
  - Más dífícil (si `\(X\)` es de dimensión alta...).
  
2. *Modelos discriminativos*: tratan de modelizar `\(P(Y \vert X)\)` (Regresión logística).

  + Si solo interesa clasificar: más fácil computacionalmente.
  
3. *Funciones discriminantes*: Aprenden funciones que mapean `\(X\)` en `\(Y\)` directamente (Perceptrón).
  
  - No tenemos acceso a las probabilidades a posteriori cada vez que queramos tomar nuevas decisiones.
  - Probabilidades a posteriori **muy útiles**: cambaimos frecuentemente función de coste, queremos tener opción de rechazo, combinar modelos, etc.

---

class: middle, center, inverse

# Análisis Discriminante Lineal

---

## LDA

* Sea `\(f_k(x)\)` la densidad de probabilidad de `\(x\)` condicionada a la clase `\(Y_k\)`. 
* Sea `\(\pi_k\)` el prior de la clase `\(Y_k\)`. Se tiene

`\begin{equation}
P(Y=Y_k \vert X=x) = \frac{f_k(x) \pi_k}{\sum_{i=1}^K f_i (x) \pi_{i}}
\end{equation}`

* ¿Es este un modelo generativo, discriminativo o función discriminante?

---

## LDA

* Asumamos modelo Gaussiano para `\(f_k(x)\)`

`\begin{equation}
f_k(x) = \frac{1}{(2 \pi)^{p/2} \vert \boldsymbol{\Sigma_k}\vert^{1/2}} \exp \left[ -\frac{1}{2} (x-\mu_k)^\top \boldsymbol{\Sigma_k}^{-1}(x-\mu_k) \right]
\end{equation}`

* LDA: Asume que las clases tienen matriz de covarianza común `\(\boldsymbol{\Sigma_k} = \boldsymbol{\Sigma}\)` `\(\forall k\)`.

--

* Comparamos dos clases

`\begin{eqnarray}
\log \frac{P(Y=Y_k \vert x)}{P(Y=Y_j \vert x)} &amp;=&amp; \log \frac{f_k(x)}{f_j(x)} + \log \frac{\pi_k(x)}{\pi_j(x)} \\
&amp;=&amp; \log \frac{\pi_k(x)}{\pi_j(x)} - \frac{1}{2} (\mu_k + \mu_j)^\top \boldsymbol{\Sigma}^{-1} (\mu_k + \mu_j) + x^\top {\Sigma}^{-1} (\mu_k - \mu_l)
\end{eqnarray}`

* Frontera de decisión lineal!!

* El hecho de que `\(\boldsymbol{\Sigma}\)` no dependa de la clase causa la linealidad.

---

## LDA

* Vemos que asignar a `\(X=x\)` la clase con más probabilidad a posteriori es equivalente a asignar la clase con *función discriminante lineal* `\(\delta_k (x)\)` más grande

`\begin{equation}
\delta_k (x) = x^\top \boldsymbol{\Sigma}^{-1} \mu_k - \frac{1}{2} \mu_k^\top \boldsymbol{\Sigma}^{-1}\mu_k + \log \pi_k
\end{equation}`

--

* Para estimar parámetros desconocidos, usamos datos de entrenamiento (MLE) 

  1. `\(\hat{\pi}_k = N_k/N\)`
  2. `\(\hat{\mu}_k = \sum_{x_i \vert y_i = Y_k} x_i/N_k\)`
  3. `\(\boldsymbol{\Sigma} = \sum_{k=1}^K \sum_{x_i \vert y_i = Y_k} (x_i - \hat{\mu}_k)(x_i - \hat{\mu}_k)^\top / (N-K)\)`

---

## QDA

* Si no asumimos que las matrices de covarianza son independientes de las clases, llegamos al **Análisis Discriminante Cuadrático**.

`\begin{equation}
\delta_k (x) = -\frac{1}{2} \log \vert \boldsymbol{\Sigma}_k \vert - \frac{1}{2} (x - \mu_k)^\top \boldsymbol{\Sigma}_k^{-1}(x - \mu_k) + \log \pi_k
\end{equation}`

* La frontera de decisión ahora es cuadrática.

--

* Para estimar parámetros desconocidos, usamos datos de entrenamiento (MLE) 

  1. `\(\hat{\pi}_k = N_k/N\)`
  2. `\(\hat{\mu}_k = \sum_{x_i \vert y_i = Y_k} x_i/N_k\)`
  3. `\(\boldsymbol{\Sigma}_k = \sum_{x_i \vert y_i = Y_k} (x_i - \hat{\mu}_k)(x_i - \hat{\mu}_k)^\top / (N-K)\)`


---

## Análisis Discriminante Regularizado

* Compromiso entre LDA y QDA, regularizando la matriz de covarianza.

`\begin{equation}
\hat{\boldsymbol{\Sigma}}_k(\alpha) = \alpha \hat{\boldsymbol{\Sigma}}_k + (1-\alpha)\hat{\boldsymbol{\Sigma}}
\end{equation}`

* `\(\alpha \in [0,1]\)` permite un contínuo de modelos entre LDA y QDA.

* `\(\alpha\)` suele escogerse usando validación cruzada, validación hold-out,...

* Otra posibilidad

`\begin{equation}
\hat{\boldsymbol{\Sigma}}_k(\gamma) = \gamma \hat{\boldsymbol{\Sigma}} + (1-\gamma) \sigma^2 \boldsymbol{I}
\end{equation}`

---

## Computación para LDA

* La computación se simplifica diagonalizando la matriz `\(\hat{\boldsymbol{\Sigma}}\)`.

* Sea `\(\hat{\boldsymbol{\Sigma}} = \boldsymbol{U} \boldsymbol{D} \boldsymbol{U}^\top\)` la descomposición en autovalores de la matriz de covarianza.

* Para clasificar podemos:

  1. *Esferizar* los datos usando `\(X^* = \boldsymbol{D}^{-\frac{1}{2}} \boldsymbol{U}^\top X\)`. Ahora la matriz de covarianza es la identidad.
  2. Clasificar una nueva instancia a la clase del centroide más cercano en el espacio transformado, modulo el efecto de los priors `\(\pi_k\)`.
  3. Esto es así pues podemos escribir la función discriminante como
  
  \begin{equation}
  \delta_k'(x) = -\frac{1}{2} (x - \mu_k)^\top \boldsymbol{\Sigma}^{-1}(x - \mu_k) + \log \pi_k
  \end{equation}


---


class: middle, center, inverse

# Regresión Logística y Optimización Estocástica

---

## Regresión logística (repaso)

* Clasificación binaria:

`\begin{equation*}
p(y = 1 | x) = \sigma (w^\intercal x + b)
\end{equation*}`

* Clasificación en `\(M &gt; 2\)` clases: cambiar la función sigmoide `\(\sigma\)` por la **softmax** `\(s: \mathbb{R}^M \rightarrow \mathbb{R}^M\)`, definida como

`\begin{equation*}
s(z)_i = \frac{e^{z_i}}{\sum_{j=1}^M e^{z_j}}
\end{equation*}`

donde `\(z = Wx + B\)`, con `\(W \in \mathbb{R}^{M \times D}, B \in \mathbb{R}^{M \times 1}\)`.

* Aprendizaje mediante mínimos cuadrados no lineales, descenso por el gradiente: los algoritmos vistos requieren acceso a la matriz `\(X\)` entera en cada iteración.

* ¿Qué hacer cuando `\(X\)` no cabe en memoria?

---


## Descenso por el gradiente (GD)

* Habitualmente se considera el problema de minimizar una función con la siguiente forma:

`\begin{equation*}
f(w) = \frac{1}{N}\sum_{i=1}^N f_i(w)
\end{equation*}`

(por ejemplo, al minimizar el error/pérdida promedio sobre la muestra de entrenamiento)

--

* Optimizamos iterando:

`\begin{equation*}
w^{t+1} = w^t - \eta_t \nabla_w f(w^t)
\end{equation*}`

* Problema: complejidad `\(\mathcal{O}(N)\)`


---

## Descenso por el gradiente estocástico (SGD)

* En cada iteración, barajeamos los datos y escogemos **uno** al azar

`\begin{equation*}
w^{t+1} = w^t - \eta_t \nabla_w f_i(w^t)
\end{equation*}`


* También podemos seleccionar un **minilote** `\(\mathcal{B} = \lbrace i_1, \ldots, i_B \rbrace \subset \lbrace 1, \ldots N \rbrace\)` al azar en cada iteración:

`\begin{equation*}
w^{t+1} = w^t - \eta_t \nabla_w \frac{1}{B} \sum_{i \in \mathcal{B}} f_i(w^t)
\end{equation*}`

* La complejidad pasa de `\(\mathcal{O}(N)\)` a `\(\mathcal{O}(B)\)`, además, no es necesario tener toda la matriz `\(X\)`, sino solo los datos del minilote `\(\mathcal{B}\)`.

* Otra ventaja: mayor probabilidad de escapar óptimos locales que con GD: un punto estacionario de la función objetivo en GD no lo será en SGD generalmente.


---

## Propiedades del SGD

* *Ejercicio: demostrar que el estimador por minilotes es **insesgado**. *

--

* Usando resultados de aproximación estocástica de Robbins &amp; Monro (1954), se puede demostrar que si las tasas de aprendizaje cumplen estas condiciones:

`\begin{align*}
\sum_{t=0}^\infty \eta_t &amp;= \infty \\
\sum_{t=0}^\infty \eta^2_t &amp;&lt; \infty
\end{align*}`

entonces 

`\begin{equation*}
| f(w^t) - f^* | = \mathcal{O}(1/t)
\end{equation*}`


---

## Nuevos desarrollos desde SGD

### Momento (1986)

Ayuda a amortiguar las oscilaciones que hacen que SGD sea lento.

`\begin{align*}
w^{t+1} &amp;= w^t - v^{t+1} \\
v^{t+1} &amp;= \gamma v^{t} + \eta_t \nabla_w f_i(w^t)
\end{align*}`

### AdaGrad (2011)

Adapta la tasa de aprendizaje a cada parámetro, disminuyéndola en parámetros con actualizaciones frecuentes (resp. aumentándola en parámetros con actualizaciones infrecuentes). Por esta razón, es adecuado para matrices de datos dispersas.

`\begin{equation*}
w^{t+1}_j = w^t_j - \frac{\eta}{\sqrt{G^t_{j,j} + \epsilon}} \nabla_w f_i(w^t)_j
\end{equation*}`

donde `\(G^t_{j,j} = \sum_{t'=0}^t (\nabla_w f_i(w^t)_j)^2\)` (la suma de los gradientes al cuadrado para esa coordenada hasta `\(t\)`)


---

## Efecto de la estocasticidad

![:scale 100%](./img/sgd.png)

---

## Con o sin momento

![:scale 100%](./img/momentum.png)
* Símil físico con la **inercia** de una partícula.

---

## SGD con datos dispersos

* Caso real: recomendación de películas a usuarios. Las observaciones son del tipo *(id_usuario, id_pelicula, rating)*

* Los identificadores son variables categóricas (factor). Por ejemplo, asumiendo 50.000 usuarios:

`\begin{equation*}
\mbox{id_usuario = 24678} \rightarrow \left( 0, 0, 0, \ldots, 0, 1, 0, \ldots \right) \in \mathbb{R}^{50000}
\end{equation*}`

* Esto produce una explosión en el número de variables dummy necesarias: riesgo de que **no quepa en memoria** la matriz de datos dummies.

* Solución: trabajar directamente sin dummificar, usando librerías especializadas como Vowpal Wabbit (Microsoft): https://github.com/VowpalWabbit/vowpal_wabbit

* SGD (o variantes) solo actualizarán el peso correspondiente, ignorando los que tendrían el dummy a 0.

---

## Feature hashing trick

* En muchas ocasiones, las variables categóricas están representadas como **cadenas alfanuméricas**.

* Ejemplo en datos de ad-server: un identificador de un cookie es **76c24efd-ec42-492a-92df-c62cfd4540a3**.

* ¿Cómo lo convertimos a un índice entero de forma eficiente?

--

* Solución: usar una **función de hash** sobre la representación en binario de la cadena

`\begin{equation*}
\mathcal{H} : \lbrace 0, 1 \rbrace^{D} \rightarrow \lbrace 0, 1 \rbrace^{d}
\end{equation*}`

* donde `\(d &lt; D\)`. Típicamente `\(d\)` se toma entre 15 y 30.

* Por ejemplo, `\(\mathcal{H}(\mbox{76c24efd-ec42-492a-92df-c62cfd4540a3}) = 65538\)`

* El algoritmo de optimización solo hace la computación para actualizar el peso `\(w_{65538}\)`


---


class: middle, center, inverse

# Interacciones y Máquinas de Factorización (FMs)

---
## Fm's - Problema

* ¿Cómo modelizar interacciones cuando nos enfrentamos a variables categóricas con número alto de categorías?

* **Una** variable con `\(K+1\)` categorías `\(\rightarrow\)` `\(K \choose 2\)` interacciones a pares. Explota rápido...

* Número medio de valores distintos de cero en los vectores de variables predictoras mucho menor que su dimensión.

* Datos muy dispersos (sparse)! No hay datos suficientes para estimar interacciones complejas de manera independiente...

---
## FM's - Idea

* El modelo de una FM de grado 2 (solo interacciones a pares)

`\begin{equation}
\widehat{y}(x) := \sigma \left[ \omega_0 + \sum_{i=1}^p \omega_{i} x_i \sum_{i=1}^p \sum_{j=i+1}^p \langle v_i, v_j\rangle x_i x_j \right]
\end{equation}`

* Donde los parámetros a estimar son

`\begin{eqnarray}
\omega_0 \in \mathbb{R}, ~ &amp; \boldsymbol{\omega} \in \mathbb{R}^p, ~ &amp; \boldsymbol{V} \in \mathbb{R}^{p \times k}
\end{eqnarray}`

--

* `\(k\)` es la dimensión latente! `\(\langle v_i, v_j\rangle\)` es un producto escalar

`\begin{equation}
\langle v_i, v_j\rangle = \sum_{f=1}^k v_{i,f} v_{j,f}
\end{equation}`

--

* Reducimos número de parámetros de `\(1 + p + \frac{p(p-1)}{2}\)` a `\(1 + p + kp\)`.


---
## FM's - Intuición y computación

* Con datos sparse, no hay datos suficientes para estimar todas las interacciones de manera independiente.

* Las FMs pueden estimar interacciones incluso en este contexto porque rompen la independencia entre los parámetros de las interacciones, factorizandolos.

* Los datos de una interacción ayudan a estimar los parámetros de otras interacciones relacionadas.

* La complejidad de computar el modelo de FMs es `\(\mathcal{O} (kp^2)\)`, pues hay que computar todas las interacciones!

* Se puede reducir esta complejidad a `\(\mathcal{O} (kp)\)` (tiempo lineal) !! 

* Fácil de probar:
S. Rendle [Factorization Machines](https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf)

---

class: middle, center, inverse

# Clasificador Naive-Bayes

---
## Clasificador NB

* Sea `\(f_k(x)\)` la densidad de probabilidad de `\(x\)` condicionada a la clase `\(Y_k\)`. 
* Sea `\(\pi_k\)` el prior de la clase `\(Y_k\)`. Se tiene

`\begin{equation}
P(Y=Y_k \vert X=x) = \frac{f_k(x) \pi_k}{\sum_{i=1}^K f_i (x) \pi_{i}}
\end{equation}`

--

* El modelo NB asume que las variables predictoras son **condicionalmente independientes** dada la clase. O lo que es lo mismo

`\begin{equation}
f_k(X) = \prod_{j=1}^p f_{kj}(X_k)
\end{equation}`

* Esto en general no es cierto...

---

## Clasificador NB

* ...pero simplificar tremendamente la estimación, cada marginal `\(f_{kj}\)` puede ser estimada por separado.

* Especialemente apropiado cuando la dimensión `\(p\)` es grande (pues la estimación de densidad se vuelve inviable).

* También cuando el vector de variables predictoras contiene variables discretas y continuas (pues cada una se modeliza por separado).

* Aunque la hipótesis es fuerte, el modelo puede funcionar porque la frontera de decisión puede "no sentir" detalles de las densidades condicionadas a la clase.


---
## Clasificador NB en la práctica - estimación de parámetros

* Los parámetros se estima usando máxima verosimilitud con los datos de entrenamiento.

* Para **variables predictoras contínuas** - NB Gaussiano

`\begin{equation}
P(X_i = x_i \vert Y = Y_k) =  \frac{1}{\sqrt{2 \pi \sigma_{ki}^2}} \exp \left[- \frac{(x_i-\mu_{ki})^2}{2 \sigma_{ki}^2}\right]
\end{equation}`

---
## Clasificador NB en la práctica - estimación de parámetros

* Para **variables predictoras que son cuentas** - Versión suavizada de máxima verosimilitud con modelo multinomial

* Un vector de variables predictoras es un histograma con `\(x_i\)` el número de veces que sucede el evento `\(i\)`.  

`\begin{equation}
P(X_i = x \vert Y = Y_k) = \frac{N_{ki} + \alpha}{N_k + \alpha p}
\end{equation}`

* `\(N_{ki}\)` es el número total de cuentas del evento `\(i\)` en la clase `\(k\)` y `\(N_k\)` es el número total de cuentas en la clase `\(k\)`.

* `\(\alpha\)` se puede interpretar como prior, evita probabilidades 0. `\(\alpha = 1\)` *Laplace smoothing*. `\(\alpha &lt; 1\)` *Lidstone smoothing*.

---
## Clasificador NB en la práctica - estimación de parámetros

* Para **variables predictoras categóricas** - MLE con modelo Bernoulli multivariante.

* Cada variable predictora es un booleano, `\(x_i \in \lbrace 0,1 \rbrace\)`.

`\begin{equation}
P(X_i = x \vert Y = Y_k) = \frac{\sum_{j=1}^N I(X_i = x)*I(Y = Y_k)}{\sum_{j=1}^N I(Y = Y_k) }
\end{equation}`


---


class: middle, center, inverse

# k Vecinos Más Próximos (k-NN)

---

## Fundamentos

* k-NN es un algoritmo robusto y versátil que suele usarse como base antes de modelos más complejos.

* Es de tipo **supervisado**: aprende una función `\(h: \mathcal{X} \rightarrow \mathcal{Y}\)`, donde `\(\mathcal{Y}\)` puede ser discreto (clasificación) o continuo (regresión).

* Es **no paramétrico**: no hace ninguna suposición acerca de la estructura de `\(h\)` (por ejemplo, que sea lineal, `\(h(x) = w^{\intercal} x)\)`. Esto ayuda para prevenir errores de modelización.

* El aprendizaje es **basado en instancias**: en lugar de aprender parámetros, **memoriza** los datos de entrenamiento, que serán usados directamente como *conocimiento* para la fase de inferencia.

* En consecuencia: solo al predecir sobre datos de test el algoritmo usa los datos de entrenamiento.


---

## Algoritmo

### (Pre)entrenamiento

1. Almacenar el dataset de entrenamiento `\(\mathcal{D}_{tr}\)`.

2. Especificar una función de distancia `\(d : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}_{+}\)`

--

### Predicción 

1. Dado una instancia de test `\(x_0\)`, encontrar los `\(k\)` puntos `\(\lbrace x_{(1)}, \ldots, x_{(k)} \rbrace := \mathcal{A} \subset \mathcal{D}_{tr}\)` más cercanos a `\(x_0\)` según `\(d\)`.

2. La clase predicha será la **mayoritaria** de las clases de los elementos en `\(\mathcal{A}\)`, es decir,

`\begin{equation*}
P(y = j | x_0 ) = \frac{1}{k} \sum_{i \in \mathcal{A}} I(y_{(i)} = j)
\end{equation*}`

donde `\(I\)` es la función indicatriz.

---

## Funciones de distancia

* Supongamos `\(x_1, x_2 \in \mathcal{X} = \mathbb{R}^D\)`.

* **Distancia L1**: `\(d_1(x_1, x_2) = \sum_{d=1}^D | x_{1,d} - x_{2,d} |\)`.

* **Distancia L2**: `\(d_2(x_1, x_2) = \sqrt{\sum_{d=1}^D (x_{1,d} - x_{2,d})^2 }\)`.

* **L1 vs L2**: la L2 penaliza mucho más puntos alejados que la L1.

* ¡Es conveniente estandarizar las variables a media 0 y varianza 1 ya que pueden estar en distintas escalas!

---

## El hiperparámetro `\(k\)`

* Intuititivamente, aumentar `\(k\)` tiende a suavizar la frontera de decisión, es decir, el clasificador es más resistente a outliers. 

![:scale 50%](./img/knn1.png)

*Fuente*: Elements of Statistical Learning


---

## El hiperparámetro `\(k\)`

* Intuititivamente, aumentar `\(k\)` tiende a suavizar la frontera de decisión, es decir, el clasificador es más resistente a outliers. 

![:scale 50%](./img/knn15.png)

*Fuente*: Elements of Statistical Learning


---

## Ventajas

* Sencillo y válido para regresión y clasificación multiclase (no solo binaria).

* **No hace suposiciones** sobre la estructura de los datos.

## Inconvenientes

* Predicción **muy costosa en tiempo**: en la mayoría de las aplicaciones, interesa que la predicción sea rápida y el entrenamiento lento.

* Necesario almacenar todo el dataset de entrenamiento.

* En **alta dimensión**, las distancias no son intuitivas.


---

## Propiedades asintóticas

* **Ejercicio**: probar que a medida que el número de observaciones de entrenamiento `\(N \rightarrow \infty\)`, 1-NN tiene una tasa de error acotada por el doble la tasa de error de Bayes.

--

* Error de Bayes = `\(1 - p_{k^*}(x)\)`.
* Error de 1-NN = `\(\sum_{k=1}^K p_k(x) (1 - p_k(x)) \geq 1 - p_{k^*}(x)\)`.
* Si `\(K = 2\)`: Error de 1-NN = `\(2 p_{k^*}(x) (1 - p_{k^*}(x)) \leq 2 (1 - p_{k^*}(x))\)`


---

## En la práctica: resumen

* Preprocesar los datos: estandarizar.

* Si los datos tienen mucha dimensionalidad, considera utilizar técnicas de reducción de dimensionalidad.

* Validar en el hiperparámetro `\(k\)` y la distancia `\(d\)`.

* Si tiempo es crítico, considerar usar variantes aproximadas: https://github.com/eddelbuettel/rcppannoy


---

class: middle, center, inverse

# Métricas para clasificación

---

## Problema

* La **tasa de acierto** (accuracy) no basta en problemas con clases poco equilibradas.

* Caso real: predicción de CTR (**click-through rate**, click 1, no click 0).

* Alrededor de `\(10^8\)` anuncios (observaciones), de los cuales clicks solo 80.000 clicks.

* Un modelo que clasifique siempre 0, obtiene una tasa de acierto del **99.92 %**...

---

## Calidad modelos clasificación

.pull-left[
![](./img/confusion_matrix.png)
]

.pull-right[

Medidas:
* Tasa de acierto: `\(\frac{\text{TP} + \text{TN}}{\text{P} + \text{N}}\)`

* Sensitividad, recall, TPR: `\(\frac{\text{TP}}{\text{TP} + \text{FN}}\)`

* Especificidad, TNR: `\(\frac{\text{TN}}{\text{TN} + \text{FP}}\)`

* Precisión, PPV: `\(\frac{\text{TP}}{\text{TP} + \text{FP}}\)`

* F1-score: `\(2\times \frac{\text{PPV} \times \text{TPR}}{\text{PPV} + \text{TPR}}\)`
]

**Tutorial muy extenso**: http://people.cs.bris.ac.uk/~flach/ICML04tutorial/

(Análisis ROC, generalizaciones a clasificación n-aria,...)
    </textarea>
<style data-target="print-only">@media screen {.remark-slide-container{display:block;}.remark-slide-scaler{box-shadow:none;}}</style>
<script src="https://remarkjs.com/downloads/remark-latest.min.js"></script>
<script src="macros.js"></script>
<script>var slideshow = remark.create({
"highlightStyle": "github",
"highlightLines": true,
"countIncrementalSlides": false
});
if (window.HTMLWidgets) slideshow.on('afterShowSlide', function (slide) {
  window.dispatchEvent(new Event('resize'));
});
(function(d) {
  var s = d.createElement("style"), r = d.querySelector(".remark-slide-scaler");
  if (!r) return;
  s.type = "text/css"; s.innerHTML = "@page {size: " + r.style.width + " " + r.style.height +"; }";
  d.head.appendChild(s);
})(document);

(function(d) {
  var el = d.getElementsByClassName("remark-slides-area");
  if (!el) return;
  var slide, slides = slideshow.getSlides(), els = el[0].children;
  for (var i = 1; i < slides.length; i++) {
    slide = slides[i];
    if (slide.properties.continued === "true" || slide.properties.count === "false") {
      els[i - 1].className += ' has-continuation';
    }
  }
  var s = d.createElement("style");
  s.type = "text/css"; s.innerHTML = "@media print { .has-continuation { display: none; } }";
  d.head.appendChild(s);
})(document);
// delete the temporary CSS (for displaying all slides initially) when the user
// starts to view slides
(function() {
  var deleted = false;
  slideshow.on('beforeShowSlide', function(slide) {
    if (deleted) return;
    var sheets = document.styleSheets, node;
    for (var i = 0; i < sheets.length; i++) {
      node = sheets[i].ownerNode;
      if (node.dataset["target"] !== "print-only") continue;
      node.parentNode.removeChild(node);
    }
    deleted = true;
  });
})();</script>

<script>
(function() {
  var links = document.getElementsByTagName('a');
  for (var i = 0; i < links.length; i++) {
    if (/^(https?:)?\/\//.test(links[i].getAttribute('href'))) {
      links[i].target = '_blank';
    }
  }
})();
</script>

<script>
slideshow._releaseMath = function(el) {
  var i, text, code, codes = el.getElementsByTagName('code');
  for (i = 0; i < codes.length;) {
    code = codes[i];
    if (code.parentNode.tagName !== 'PRE' && code.childElementCount === 0) {
      text = code.textContent;
      if (/^\\\((.|\s)+\\\)$/.test(text) || /^\\\[(.|\s)+\\\]$/.test(text) ||
          /^\$\$(.|\s)+\$\$$/.test(text) ||
          /^\\begin\{([^}]+)\}(.|\s)+\\end\{[^}]+\}$/.test(text)) {
        code.outerHTML = code.innerHTML;  // remove <code></code>
        continue;
      }
    }
    i++;
  }
};
slideshow._releaseMath(document);
</script>
<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
(function () {
  var script = document.createElement('script');
  script.type = 'text/javascript';
  script.src  = 'https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-MML-AM_CHTML';
  if (location.protocol !== 'file:' && /^https?:/.test(script.src))
    script.src  = script.src.replace(/^https?:/, '');
  document.getElementsByTagName('head')[0].appendChild(script);
})();
</script>
  </body>
</html>