class: center, middle, inverse, title-slide # Conceptos generales de aprendizaje supervisado ## Curso de aprendizaje automático para el INE ### Alberto Torres Barrán ### 2019-04-24 --- <script type="text/x-mathjax-config"> MathJax.Hub.Config({ TeX: { Macros: { Xcal: "{\\mathcal{X}}", Xbf: "{\\mathbf{X}}", Hbf: "{\\mathbf{H}}", Rbb: "{\\mathbb{R}}" }, extensions: ["AMSmath.js","AMSsymbols.js"] } }); </script> # ¿Qué es el Aprendizaje Automático? De la Wikipedia: *Machine learning is a subfield of **computer science** that evolved from the study of **pattern recognition** and computational learning theory in artificial intelligence. In 1959, Arthur Samuel defined machinelearning as a “Field of study that gives computers the ability to learn without being **explicitly programmed**”. Machine learning explores the study and construction of algorithms that can learn from and make predictions on **data**.* --- class: center, middle  Fuente: [xkcd #1838](https://xkcd.com/1838/) ??? Aprendizaje automático en la práctica tiene mucho de ingeniería y no tanto de "ciencia" Mucho prueba y error La calidad del software ha aumentado mucho en los últimos años, casi cualquiera puede ajustar estos modelos sin conocimientos teóricos profundos --- class: center, middle  ??? * Statistics Más antigua (aprox. 1749), el resto de disciplinas utilizan algunas de sus técnicas: estadística descriptiva, análisis de regresión, inferencia. * Artificial Intelligence Más moderna, 1940. Algunos problemas que intenta resolver: procesamiento lenguaje natural, planificación, visión por computador, robótica. * Machine Learning Rama de la IA, 1946. Se utiliza para resolver algunos de los problemas que tiene la IA. * Pattern Recognition En general se usa como sinónimo de Machine Learning. * Data Mining Técnicas de modelado estad´ıstico y machine learning aplicadas a un dominio en concreto. * Data Science Término más moderno, mezcla de todo lo anterior. --- class: center # Data science  Fuente: [R for Data Science](http://r4ds.had.co.nz/) ??? Machine learning == parte de modelado Data Science == todos los pasos --- ## Casos de éxito * Coches autónomos * Análisis de imágenes médicas * Procesamiento de lenguaje natural * AlphaGo y juegos Atari * Generación de imágenes * Sistemas de recomendación --- class: middle, center ## Herramientas  ??? Un poco antigua, en la del 2018 Python supera a R pero ambos son muy populares --- # Tipos de aprendizaje Existen diversos tipos de tareas, dependiendo de la información disponible: - **supervisado**: tenemos acceso a pares de ejemplos entrada-salida - **no supervisado**: no tenemos acceso a las salidas - otros (limitando de alguna forma el acceso a las salidas): * *activo*: el algoritmo puede acceder a la salida para nuevos datos de entrada * *semi-supervisado*: solo se tienen salidas para algunos datos * *refuerzo*: no se tiene el valor de la salida, pero si una indicación de lo lejos o cerca que se encuentra --- # Referencias 1. Jerome H. Friedman. [Data Mining and Statistics: What's the Connection? (1998)](http://statweb.stanford.edu/~jhf/ftp/dm-stat.pdf) 2. Leo Breiman. [Statistical Modeling: The Two Cultures (2001)](http://projecteuclid.org/download/pdf_1/euclid.ss/1009213726) 3. Cross Validated. [What is the difference between data mining, statistics, machine learning and AI (2010).](http://stats.stackexchange.com/questions/5026/what-is-the-difference-between-data-mining-statistics-machine-learning-and-ai) 4. Sakthi Dasan Sekar. [What is the difference between Artificial Intelligence, Machine Learning, Statistics, and Data Mining (2014)](http://shakthydoss.com/what-is-the-difference-between-artificial-intelligence-machine-learning-statistics-and-data-mining/) 5. Cross Validated. [What exactly is Big Data? (2015)](http://stats.stackexchange.com/questions/173060/what-exactly-is-big-data) 6. David Donoho. [50 years of Data Science (2015)](http://pages.cs.wisc.edu/~anhai/courses/784-fall15/50YearsDataScience.pdf) ??? Dos culturas: Una asume que los datos han sido generados por un modelo estocástico específico. Otra usa modelos algorítmicos y asume que el mecanismo de generación de los datos es desconocido --- class: middle, center, inverse # Aprendizaje supervisado --- * Tenemos disponibles datos con múltiples observaciones: * ejemplos (*examples*) * muestras (*samples*) * ... -- * Varias variables por observación: * predictores * atributos (*atributes*) * características (*features*) * covariables (*covariates*) * variables independientes * variables explicativas * ... -- * Una de ellas es de especial interés: * variable respuesta * variable dependiente * objetivo (*target*) * salida (*output*) * etiqueta (*label*) * ... --- ## Objetivos 1. Predecir el valor de la variable respuesta para nuevas observaciones 2. Obtener información sobre la relación entre las variables independientes y la salida ??? Información sobre la relación, por ej: qué variables son más relevantes --- ## Tipos de problemas 1. Regresión, si la variable respuesta es continua 2. Clasificación, si la variable respuesta es discreta 3. Otros: por ejemplo, * salida continua pero valores enteros * salida discreta pero los valores tienen un orden --- ## Aprendizaje estadístico **Dados**: * Espacio de las muestras de entrada: `\(\mathcal{X}\)` * Conjunto de posibles salidas: `\(\mathcal{Y}\)` * Conjunto de **entrenamiento**: `\(S = \{x_i,\, y_i\}_{i=1}^n\)`, contenido en el espacio `\(\mathcal{X} \times \mathcal{Y}\)` -- **Objetivo**: * Aprender una regla de predicción (hipótesis), `\(h: \mathcal{X} \rightarrow \mathcal{Y}\)` -- **Asumimos**: * Los ejemplos se han generado por una distribución de probabilidad desconocida `\(\mathcal{P}\)` * Existe una función de pérdida `\(L: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}\)` que mide como de lejos se encuentra `\(h(x)\)` de `\(y\)` * El conjunto posible de hipótesis `\((\mathcal{F})\)` es finito --- ## Minimización del riesgo empírico Elegir `\(h\)` tal que minimice el riesgo esperado `$$R(h) = \int_{\mathcal{X} \times \mathcal{Y}} L(h(x), y)\, dP(x, y)$$` **Problema**: cómo podemos calcular `\(R\)` si `\(P\)` es desconocida? Podemos evaluar la función de pérdida en el conjunto `\(S\)` (riesgo empírico): `$$\hat{R}(h) = \frac{1}{n}\sum_{i=1}^{n} L(h(x_i), y_i)$$` Si `\(n\)` suficientemente grande, esperamos que `\(\hat{R}(x) \sim R(x)\)` `\(\rightarrow\)` minimizar el riesgo empírico es una buena aproximación de minimizar el riesgo esperado --- ## Descomposición del error Minimizador del riesgo: `$$h^* = \arg\min_{h \in \mathcal{F}}\, R(h)$$` Minimizador del riesgo empírico: `$$\hat{h}^* = \arg\min_{h \in \mathcal{F}}\, \hat{R}(h)$$` Riesgo de Bayes o error de Bayes: `$$R^* = \inf_h\, R(h)$$` *Nota*: sobre todas las funciones `\(h: \mathcal{X} \rightarrow \mathcal{Y}\)`, no solo las contenidas en `\(\mathcal{F}\)`!! --- La differencia entre el riesgo y el error de Bayes es: `$$R(h) - R^* = \underbrace{\big(R(h) - R(\hat{h}^*)\big)}_\text{error optimización} + \underbrace{\big(R(\hat{h}^*) - R(h^*)\big)}_\text{error estimación} + \underbrace{\big(R(h^*) - R^*\big)}_\text{error aproximación}$$` -- **Error optimización**: como de buena es la optimización que llevó a la hipótesis `\(h\)`, relativa a al óptimo del riesgo empírico * Disminuye al mejorar el algoritmo de optimización -- **Error de estimación**: surge por aproximar el riesgo esperado con el riesgo empírico * Disminuye si aumentamos el conjunto de datos de entrenamiento `\(n\)` -- **Error de aproximación**: surge por aproximar la mejor función posible por la mejor función dentro de `\(\mathcal{F}\)` * Disminuye si reemplazamos `\(\mathcal{F}\)` por otra clase más flexible ??? Si asumimos que el error de optimización es 0, existe un equilibrio entre el error de estimación y el error de aproximación: por un lado nos interesa elegir clases de funciones muy flexibles, pero por otro estas van a necesitar muchos más ejemplos para aproximar el riesgo esperado con el riesgo empírico de forma correcta --- ## Ejemplo * Elegimos `\(\mathcal{F}\)` como las clase de funciones del tipo `\(f(x) = w_0 + x^T w\)` * Función de pérdida: `\(L(y, f(x)) = (y - f(x))^2\)` * Riesgo empírico: `$$R(w) = \frac{1}{n} \sum_{i=1}^n (y_i - w_0 + x_i^T w)^2$$` ??? En este caso el riesgo es una función cuadrática de los parámetros w --- ## Regresión lineal Dado el conjunto de entrenamiento `\(S = \{y_i, x_i\}_{i=1}^n\)` * Agrupamos todos los ejemplos de entrada `\(x_i\)` en una matrix `\(\mathbf{X}\)` de tamaño `\(n \times d\)` * Agrupamos todas las salidas en un vector columna `\(y\)` de tamaño `\(n \times 1\)` Expresamos el riesgo empírico en notación matricial: `$$R(w) = (y - \mathbf{X}w)^T (y - \mathbf{X}w)$$` Gradiente: `$$\nabla_w R(w) = \mathbf{X}^T(y - \mathbf{X}w) = \mathbf{X}^Ty - \mathbf{X}^T\mathbf{X}w$$` Minimizamos el riesgo empírico: `$$\nabla_w R(w) = 0\quad \Rightarrow \quad w^* = (\mathbf{X}^T\mathbf{X})^{-1} \mathbf{X}^T y$$` Recuperamos mínimos cuadrados ordinarios! ??? El término `\(w_0\)` se incluye dentro del vector `\(w\)` añadiendo una columna constante de 1s como primer elemento de X --- Posibles problemas del modelo: * Teóricos: 1. asumimos que `\(y\)` depende linealmente de `\(x\)` 2. asumimos que el modelo está especificado correctamente (no faltan variables) * Numéricos: 1. hay menos variables que observaciones 2. no hay dos variables con correlación perfecta ??? En los problemas numéricos, en ambos casos hace que la matriz no tenga rango completo y por tanto no podemos calcular la inversa (de forma exacta!!) --- ## Selección de modelos * Para medir la calidad del modelo, podemos calcular el riesgo o error empírico en el conjunto de entrenamiento * Este error se puede disminuir de forma casi arbitraria aumentando la complejidad de la clase de funciones * **Ejemplo**: en el caso de la regresión lineal, podemos añadir nuevas variables que sean expansiones polinómicas de las ya existentes * Interesa el **error de generalización**, es decir, el error en nuevas observaciones no usadas para entrenar el modelo * Partir los datos iniciales en dos conjuntos: 1. conjunto de entrenamiento 2. conjunto de test ??? * El error de test es una buena aproximación del error de generalización * Estamos asumiendo que ambos provienen de la misma distribución * Por tanto, la partición tiene que ser aleatoria --- ## Equilibrio sesgo-varianza * Asumimos que los datos han sido generados por `$$Y = f(X) + \epsilon$$` con `\(\mathbb{E}[\epsilon] = 0\)` y `\(\text{Var}(\epsilon) = \sigma^2\)` * El error esperado de un estimador `\(\hat{f}(X)\)` en el punto `\(x\)` (usando pérdida cuadrática) es `$$\text{EPE} = \mathbb{E}[(Y - \hat{f}(x))^2]$$` * Podemos descomponerlo en: `$$\text{EPE} = \underbrace{\Bigl(\mathbb{E}[\hat{f}(x)] - f(x) \Bigr)^2}_{\text{Sesgo}^2} + \underbrace{E\Bigl[\hat{f}(x) - \mathbb{E}[\hat{f}(x)] \Bigr]^2}_{\text{Varianza}} + \underbrace{\vphantom{\Bigl(}\sigma^2}_{\text{Ruido}}$$` --- class: center, middle  --- ## Sobreajuste * Los términos de sesgo y varianza son opuestos: si disminuimos uno aumenta el otro y viceversa * El término de ruido es inherente a los datos * Si el modelo es muy simple, el estimador está sesgado y no se ajusta bien a los datos (infraajuste) * Si el modelo es demasiado complejo, es muy sensible a pequeñas variaciones en los datos * Además, el error de test será mucho más alto que el error de entrenamiento (**sobreajuste**) * **Solución**: encontrar un equilibrio que minimice el error en el conjunto de test --- class: middle, center  --- ## Simulación ```r set.seed(1) n <- 10 x <- seq(0, 1, length.out = n) y <- 1.5*x - x^2 + rnorm(n, 0, 0.05) data <- data.frame(x=x, y=y) x_new <- seq(0, 1, length.out=500) newdata <- data.frame(x=x_new) fit1 <- lm(y ~ x + I(x^2), data=data) fit2 <- lm(y ~ x + I(x^2) + I(x^3) + I(x^4) + I(x^5) + I(x^6) + I(x^7) + I(x^8) + I(x^9), data=data) fit3 <- lm(y ~ x, data=data) y_pred1 <- predict(fit1, newdata=newdata) y_pred2 <- predict(fit2, newdata=newdata) ntest <- 1 xtest <- runif(ntest) ytest <- 1.5*xtest - xtest^2 + rnorm(ntest, 0, 0.05) ``` --- ```r plot(data) lines(x_new, y_pred1, col="blue") lines(x_new, y_pred2, col="red") abline(fit3, col="purple") points(xtest, ytest, col="darkgreen") legend("bottomright", c(expression(w[0] + w[1]*x), expression(w[0] + w[1]*x + w[2]*x^2), expression(w[0] + w[1]*x + w[2]*x^2 + ldots + w[9]*x^9)), lty=1, lwd=1.5, col=c("purple", "blue", "red"), inset=0.04) ``` <img src="02-supervised_files/figure-html/unnamed-chunk-2-1.png" style="display: block; margin: auto;" /> --- class: center, middle  Ejemplo de clasificación en 2 dimensiones [ESL] --- ## Vecinos próximos * Modelo sencillo que usa las observaciones cercanas a `\(x\)` para realizar la predicción: `$$f(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i$$` donde `\(N_k(x)\)` son las `\(k\)` observaciones más cercanas * Necesaria una métrica (por ej. distancia euclidea) * Se puede usar tanto para problemas de clasificación como regresión * Muy sensible al valor de `\(k\)` --- class: center, middle  --- ```r library(class) n <- nrow(iris) # muestreo aleatorio idx <- sample(n, n*0.75) # partir en conjuntos de entrenamiento y test train <- iris[idx, ] test <- iris[-idx, ] # separar variables indenpendientes de la clase (variable respuesta) # entrenamiento y_train <- train[, 5] X_train <- train[, -5] # test y_test <- test[, 5] X_test <- test[, -5] # modelo knn y_pred <- knn(X_train, X_test, y_train, k=3) # tasa acierto mean(y_test == y_pred)*100 ``` ``` ## [1] 97.36842 ``` --- <img src="02-supervised_files/figure-html/unnamed-chunk-4-1.png" style="display: block; margin: auto;" /> --- class: center ## Maldición de la dimensionalidad  --- * En 2 dimensiones, para capturar un 10% del volumen necesitamos cubrir aprox. el 25% del rango de cada coordenada * En 10 dimensiones, necesitamos el 80% * Otro problema relacionado es la densidad del muestreo: * Si en 1 dimensión necesitamos `\(n=100\)` muestras para cubrir el espacio, en 10 dimensiones necesitamos `\(n=100^{10}\)` para tener la misma densidad de muestreo (crecimiento exponencial) * A medida que la dimensión crece, las observaciones están mas cerca de las esquinas del hipercubo que del centro * Observaciones cercanas a las esquinas son más difíciles de clasificar porque el valor de sus atributos cambia muy bruscamente * Resumiendo, si `\(d\)` es muy grande, métodos como KNN basados en distancias tienen problemas ??? Observaciones uniformes en un hipercubo de dimension d Cambio brusco: ejemplos en esquinas opuestas del cuadrado unidad los puntos que te pueden decir algo de valores tan extremos estan lejos: tienes que extrapolar de ejemplos cercanos no tan extremos en lugar de interpolar --- ## Regresión lineal vs vecinos próximos * La frontera de decisión de la regresión lineal es suave: tiene poca varianza pero potencialmente mucho sesgo * `\(k\)`-vecinos próximos no asume ninguna estructura en los datos: * la frontera de decisión depende localmente solo de los `\(k\)` puntos más cercanos * tiene poco sesgo pero mucha varianza, ya que es muy inestable * Elegir un modelo u otro depende de los datos del problema --- ## Vecinos próximos: dependencia de `\(k\)` <img src="02-supervised_files/figure-html/unnamed-chunk-5-1.png" style="display: block; margin: auto;" /> --- <img src="02-supervised_files/figure-html/unnamed-chunk-6-1.png" style="display: block; margin: auto;" /> --- <img src="02-supervised_files/figure-html/unnamed-chunk-7-1.png" style="display: block; margin: auto;" /> --- ## Selección de hiper-parámetros * `\(k\)` es un **hiper-parámetro** que controla la complejidad del modelo * Podemos realizar un argumento similar a la comparación con la regresión lineal: * Para `\(k\)` grande, la frontera es más suave pero tiene (potencialmente) mayor sesgo * Para `\(k\)` pequeño la frontera es muy inestable (mayor varianza), pero menos sesgo * Nota: usar el error de entrenamiento para elegir el valor de `\(k\)` es mala idea, para `\(k=1\)` tenemos error 0!! * Los distintos valores de `\(k\)` se pueden comparar usando el conjunto de test --- ## Conjunto de validación * Elegir `\(k\)` como el valor que minimiza error de test `\(\rightarrow\)` error de test ya **no** es una buena estimación del rendimiento del modelo en nuevos datos * Lo mismo ocurre si elegimos la clase de funciones (modelo) usando el error de test * **Solución**: crear un tercer conjunto, conjunto de validación, para seleccionar hiper-parámetros y comparar modelos * Finalmente, reportar el error de test como estimación del poder de generalización del modelo --- ## Validación cruzada * Se divide el conjunto de entrenamiento en `\(K\)` particiones * Usar `\(K-1\)` particiones como entrenamiento y la otra como test para ajustar `\(K\)` modelos * `\(\hat{f}^{-k}(x)\)` es el modelo entrenado con todas las particiones menos la `\(k\)` * Calcular el error de validación cruzada: `$$\text{CV}(\hat{f}) = \frac{1}{n}\sum_{i=1}^n{L(y_i, \hat{f}^{-\kappa(i)}(x_i))}$$` donde `\(\kappa: \{1, \dots, n\} \rightarrow \{1, \dots, K\}\)` es una función que indica a que partición pertenece cada observación `\(i\)` * Cuando `\(K = n\)` se conoce como validación cruzada *leave-one-out* ??? Tipicos valores para `\(K\)` son 5 o 10 LOOCV el estimador del error de generalizacion es aprox. no sesgado pero puede tener mucha varianza. Tambien es computacionalmente muy costoso --- class: middle, center  Wikipedia. [Cross-validation](https://en.wikipedia.org/wiki/Cross-validation_(statistics)) --- ## Regularización * A menudo se puede reducir la varianza de un estimador a cambio de introducir un pequeño sesgo * Este término también puede inducir propiedades en la solución, por ej. *sparsity* * Para ello limitamos la complejidad del modelo añadiendo a la función de pérdida un término de **regularización** `$$\hat{f} = \arg\min_f\; \{L(y, f(x)) + \lambda J(f)\}$$` * Muchos modelos en aprendizaje automático encajan en este paradigma --- ## Ejemplo * El estimador de mínimos cuadrados es el mejor estimador no sesgado (mejor = menos varianza) * Un término de regularización muy habitual es la norma `\(l_2\)`: `$$||w||^2_2 = w^T w$$` * Junto con la función de pérdida de la regresión lineal, el modelose conoce como regresión ridge: `$$w^* = \arg\min_w\; \{(y - \mathbf{X}w)^T (y - \mathbf{X}w) + \lambda w^Tw\}$$` * Tomando derivadas e igualando a 0 la solución es `$$w^* = (\mathbf{X}^T \mathbf{X} + \lambda \mathbf{I})^{-1} (\mathbf{X}^T y)$$` donde `\(\mathbf{I}\)` es la matriz identidad ??? BLUE = Best linear unbiased estimator (teorema de Gauss) Ahora siempre es invertible para `\(\lambda > 0\)` Funcion en R: lm.ridge(), paquete MASS --- ## Regresión ridge en R * La función `lm.ridge()` de la librería `MASS` entrena una regresión lineal con regularización *ridge* para varios valores del parámetro `\(\lambda\)` * La librería `ridge` implementa la función `linearRidge()` que selecciona automáticamente el valor óptimo del parámetro `\(\lambda\)` usando el método propuesto en [Cule et al (2012)](https://arxiv.org/pdf/1205.0686.pdf) --- ## Regresión logística Equivalente a la regresión lineal para problemas de clasificación **Objetivo**: estimar la probabilidad a posteriori de pertenencia a cada clase Función logística o sigmoidea: `$$\sigma(a) = \frac{1}{1 + \exp{(-a)}}$$` Para 2 clases con etiquetas `\(\{0, 1\}\)`, definimos: `$$p(y_i = 1\,|\, x_i) = \sigma(w^Tx_i)$$` Por tanto `$$p(y_i = 0\,|\, x_i) = 1 - \sigma(w^T x_i) = \sigma(-w^Tx_i)$$` ??? La funcion logistica es conveniente porque toma un argumento en el rango `\([-\inf, \inf]\)` y tiene como salida un numero en el rango `\([0, 1]\)` Ademas, satura muy pronto gracias a la exponencial --- class: center, middle ## Curva logística  Wikipedia, [Logistic function](https://en.wikipedia.org/wiki/Logistic_function) --- ## Interpretación: odds ratio * Dado un modelo lineal con una única variable independiente, el **odds ratio** se define como `$$\text{OR} = \frac{\exp(w_0 + w_1 (x + 1))}{\exp(w_0 + w_1 x)} = \exp(w_1)$$` * Es decir, como cambian las probabilidades de la salida cuando la variable `\(x\)` aumenta una unidad: 1. Si `\(\text{OR} = 1\)` la variable x no tiene ninguna asociación con la salida 2. Si `\(\text{OR} > 1\)` la variable está asociada con una mayor probabilidad de la salida 3. Si `\(\text{OR} < 1\)` la variable está asociada con una menor probabilidad de la salida --- ## Calidad modelos clasificación .pull-left[  ] .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}}\)` ] --- ## Regresión logística: optimización Estos modelos se optimizan usando el log de la verosimilitud condicionada a `\(\Xbf\)`: `$$\mathcal{L}(w) = \sum_{i=1}^n{y_i \log [\sigma(w^T x_i)] + (1-y_i)\log[ \sigma(-w^T x_i)]} = y_i(w^Tx_i)+\log[\sigma(-w^T x_i)]$$` Derivada: `$$\partial_w \mathcal{L}(w) = x_i(y_i - \sigma(w^T x_i))$$` Son `\(d+1\)` ecuaciones no lineales en `\(w\)` Se pueden resolver usando una variante específica de Newton-Raphson: Iteratively Re-weighted Least Squares (IRLS) Segunda derivada: `$$\partial^2 \mathcal{L}(w) = -\sum_{i=1}^n{x_i x_i^T \sigma(w^T x_i)(1-\sigma(w^T x_i))}$$` --- class: middle, center, inverse # Optimización numérica: Introducción --- ## Descenso por gradiente * Dada una función convexa y diferenciable `\(f(w)\)`, podemos encontrar su mínimo iterando: `$$w^{k+1} = w^k - \eta \nabla f(w^k)$$` * `\(\eta\)` es un parámetro que controla la longitud del paso * Si `\(\eta\)` es suficientemente pequeño, el valor de `\(f(w)\)` decrece de forma monótona en cada paso * También se puede demostrar que la secuencia `\(\{w^k\}\)` converge al óptimo `\(w^*\)` * Método de primer orden, ya que solo usa información de la primera derivada (gradiente) ??? En R la función `lm()` usa descomposición QR, no descenso por gradiente [ref](https://stats.stackexchange.com/questions/94496/lm-function-in-r) --- class: middle, center  --- ## Newton-Raphson (N-R) * Queremos minimizar una función convexa dos veces diferenciable, `\(f: \Rbb^d \rightarrow \Rbb\)` * Expansión de Taylor de segundo orden de `\(f\)` en `\(x\)`: `$$f(x+h) \approx f(x) + \nabla f(x)^T h + \frac{1}{2}h^T \Hbf h$$` donde `\(\Hbf\)` es la matriz de segundas derivadas (Hessiana) * Entonces `$$\nabla_h f(x+h) = \nabla f(x) + \Hbf h$$` * Por tanto el `\(h\)` que minmiza la aproximación de segundo orden es `$$h^* = -\Hbf^{-1}\nabla f(x)$$` * Iteramos: `$$x^{k+1} = x^k -\Hbf^{-1}\nabla f(x)$$` --- ## N-R para regresión logística Resscribimos las derivadas en notación matricial: `\begin{align} \partial \mathcal{L}(w) &= \Xbf^T(y - p) \\ \partial^2 \mathcal{L}(w) &= -\Xbf^T\mathbf{W}\Xbf \end{align}` donde `\(p_i = \sigma(w^T x_i)\)` y `\(\mathbf{W}_{ii} = \sigma(w^T x_i)(1 - \sigma(w^T x_i))\)` Actualización de N-R: `\begin{align} w^{k+1} &= w^k + (\Xbf^T\mathbf{W}\Xbf)^{-1} \Xbf^T(y - p) \\ &= (\Xbf^T\mathbf{W}\Xbf^T) \Xbf^T\mathbf{W} z \end{align}` con `\(z = \Xbf w^k + \mathbf{W}^{-1}(y - p)\)` Es decir, en cada iteración se resuelve el problema de mínimos cuadrados `$$w^{k+1} = \arg\min_w\; (z - \Xbf w)^T \mathbf{W} (z - \Xbf w)$$` --- ## *Iteratively Re-weighted Least Squares* * Dado un valor inicial `\(w^0\)` * Iterar para `\(k=0, 1, 2, 3, \dots\)` 1. Calcular `\(p^k\)` con `\(p_i = \sigma((w^k)^T x_i)\)` 2. Calcular `\(\mathbf{W}^k\)` con elementos diagonales `\(\mathbf{W}_{ii}^k = \sigma((w^k)^T x_i)(1 - \sigma((w^k)^T x_i)\)` 3. Calcular `\(z^k = \Xbf w^k + (\mathbf{W}^k)^{-1}(y - p^k)\)` 4. Actualizar pesos `\(w\)` `$$w^{k+1} = \arg\min_{w^k}\; (z^k - \Xbf w^k)^T \mathbf{W}^k (z^k - \Xbf w^k)$$` * Hay que establecer un criterio de parada * Puede tener problemas de convergencia dependiendo del valor inicial ??? Parar si el gradiente es muy pequeño Parar si la diferencia entre dos valores consecutivos de f(x) esta por debajo de un umbral --- class: center, middle  ??? Descenso por gradiente (verde) Newton (rojo) Newton toma un camino mas directo al optimo porque puede usar información de la curvatura --- class: middle, center, inverse # Aprendizaje supervisado en la práctica --- ## Primeros pasos * Los datos a analizar a menudo provienen de fuentes variadas (redes sociales, sensores, encuestas, ...) y están almacenados en diferentes soportes (ficheros de texto, base de datos, ficheros binarios, streams...) * Lo primero es identificar el problema qué queremos resolver y cuales son las variables que tenemos disponibles y pueden aportar información * Ante la duda, no descartar variables/información ni observaciones antes de tiempo * Lo segundo es combinar todas esa información y transformarla en una mezcla de variables numéricas (valores continuos) y categóricas (valores discretos) * El objetivo final del preproceso es organizar esos datos en un formato tabular (filas y columnas) --- ## Distintos tipos de información * En ocasiones no es trivial transformar ciertos tipos de información en variables numéricas y/o categóricas * Para estos casos a menudo es necesario un preproceso extra, muy dependiente del problema a resolver y específico del dominio * Ejemplos: 1. Texto (tweets, páginas web, documentos): word2vec, bag-of-words, modelos n-gram 2. Imágenes: valores RGB de los píxeles, intensidad de gris 3. Audio: transformada de Fourier, coeficientes MFCC 4. Video: secuencia de frames 5. Series temporales: añadir *lags* como variables --- ## Valores que faltan * Es importante distinguir cuando una variable tiene valor 0 de "no conocido" * Si es posible, nos gustaría saber también el mecanismo que origina el valor que falta: 1. MCAR (*Missing Completely At Random*): el motivo por el que falta un valor no está relacionado con otras variables 2. MAR (*Missing At Random*): el motivo está relacionado con otras variables 3. NMAR (*Not Missing At Random*): no sabemos el motivo por el que falta * Estos valores pueden venir representados por múltiples caracteres (“*”, “-”, campo vacio, etc.) * Hay que codificarlos de manera especial para tenerlos en cuenta en los análisis (en R `NA`) **Ejemplo**: en datos que provienen de un reconocimiento médico varios pacientes no tienen ningún valor en el campo de “Fármacos”. ¿No toman ninguna medicación o el médico no ha registrado la respuesa? ??? MCAR: se pueden ignorar o completar con los valores de esa variable MAR: se pueden completar con los valores de esa variable teniendo en cuenta los valores de las variables con las que asumimos que está relacionado NMAR: no podemos hacer gran cosa --- ## Completar valores que faltan 1. Ignorar observaciones donde falte alguna variable 2. Completar observaciones con: * media o mediana, datos continuos * moda, datos categóricos usando: * todas las observaciones de esa variable * observaciones pero agrupadas por otras variables 3. Modelos predictivos * Paquete `mice` en R * KNN: usar solo observaciones cercanas Otras [librerías](https://medium.com/coinmonks/dealing-with-missing-data-using-r-3ae428da2d17) ??? 1. se pierden datos, solo es completamente seguro para MCAR 2. para datos MAR, dificil saber de antemano por que variables hay que agrupar 3. KNN: muy costoso si hay muchas observaciones, elegir valor de k es critico --- ## Valores extremos * Distinguir si un valor es erróneo o válido pero extremo es muy complicado y dependiente del dominio * Existen diversas reglas para identificarlos (paquete `outliers`) * Pueden perjudicar a ciertos algoritmos de aprendizaje, mientras que otros son robustos frente a este tipo de datos * Comprobar siempre que no hay valores imposibles Ejemplo: en datos provenientes de un reconocimiento médico, aparece un paciente con un IMC de 50 --- ## Tratamiento valores extremos 1. Eliminar la observación 2. Asignar como nuevo valor el límite inferior/superior de los valores normales 3. Asignar al valor extremo `NA` e imputar su nuevo valor usando las técnicas para valores que faltan ??? Ejemplo, distancia de Cooke? --- ## Normalización * Las variables numéricas suelen tener rangos muy diversos * **Ejemplo**: salario (10,000 – 100,000 EUR) y edad (0–100) * Algunos modelos interpretan esta diferencia de escalas como que unas variables son más importantes que otras o las observaciones están más próximas * En ocasiones normalizar las variables también puede ayudar a que el algoritmo de optimización converja más rápido * Cuidado al analizar los resultados, ya que están en los nuevos rangos --- ## Métodos * Media 0 varianza 1 (estandarizar): `$$z = \frac{x - \text{mean}(x)}{\text{std}(x)}$$` * Escalar a un intervalo, por ej. `\([−1,\, 1]\)`: `$$z = \frac{x - \min(x)}{\max(x) - \min(x)}$$` * Estandarización robusta: `$$z = \frac{x - \text{median}(x)}{\text{IQR(x)}}$$` * Otros ??? Se puede escalar a otro rango arbitrario Escalar a [-1, 1] preserva los 0, pero es sensible a outliers --- ## Variables categóricas * Muy comunes en todo tipo de fuentes de datos * Muy pocos algoritmos de aprendizaje son capaces de tratarlas directamente * Por tanto, tenemos que convertirlas en numéricas * La transformación donde se asigna a cada uno de sus valores un número entero no suele ser buena idea, ya que crea una relación artificial de orden y falsea las distancias * Estándar: utilizar una codificación *dummy* (*one-hot encoding*) --- ## Codificación *dummy*  * Finalmente, podemos eliminar una de las dos nuevas variables puesto que tienen correlación 1 * En general, para una variable categórica con `\(p\)` valores añadimos `\(p−1\)` variables nuevas ??? En R, la funcion `dummy_cols()` de la libreria `fastDummies` --- ## Otras codificaciones * Codificación **ordinal**: variables ordinales, por ej. puntuación: {baja, media, alta} `\(\Rightarrow\)` {1,2,3} (cuidado con las distancias!) * Codificación **binaria**: variables ordinales con alta dimensión, transformar la codificación a código binario * **Hashing**: codificar los valores usando una función de *hash*, que transforma cualquier valor a un número fijo de bits (columnas) * **Leave One Out**: el valor `\(C\)` de la variable categórica para la observación `\(i\)` se codifica como la media de la salida para todas las observaciones con valor `\(C\)` en la variable categórica, excluyendo `\(i\)` * [Codificación de similitud](https://arxiv.org/pdf/1806.00979.pdf) * ... --- ## Codificaciones específicas del dominio * Ejemplo si hay relación de orden y no queremos falsear las distancias:  --- ## Variables categóricas en R * Las variables categóricas en R se codifican con el tipo `factor` * Muchas funciones que implementan algoritmos de aprendizaje con interfaz para fórmulas aceptan factores directamente y los convierte usando una codificación *dummy* * Tenemos que hacer la codificación explícitamente si: 1. el algoritmo no tiene interfaz para fórmulas y solo acepta variables numéricas 2. queremos usar otra codificación distinta de la codificación *dummy* * Función `dummy_cols()` de la librería [`fastDummies`](https://cran.r-project.org/web/packages/fastDummies/index.html) * Librería [`vtreat`](https://arxiv.org/abs/1611.09477)