Hoja de referencia de Aprendizaje Supervisado
Contenido original por Afshine Amidi y Shervine Amidi
Traducido por Juan P. Chavat. Revisado por Fernando Gonzalez-Herrera, Alonso Melgar-Lopez y Fernando Diaz.
Introducción al Aprendizaje Supervisado
Dado un conjunto de puntos $\{x^{(1)}, ..., x^{(m)}\}$ asociado a un conjunto de etiquetas $\{y^{(1)}, ..., y^{(m)}\}$, queremos construir un clasificador que aprenda cómo predecir $y$ dado $x$.
Tipo de predicción Los diferentes tipos de modelos de predicción se resumen en la siguiente tabla:
Regresión | Clasificador | |
Etiqueta | Continuo | Clase |
Ejemplos | Regresión lineal | Regresión logística, SVM, Naive Bayes |
Tipo de modelo Los diferentes tipos de modelos se resumen en la siguiente tabla:
Modelo discriminatorio | Modelo generativo | |
Objetivo | Estima directamente $P(y|x)$ | Estima $P(x|y)$ para luego deducir $P(y|x)$ |
Qué se aprende | Límite de decisión | Distribución probabilística de los datos |
Ilustración | ![]() |
![]() |
Ejemplos | Regresiones, SVMs | GDA, Naive Bayes |
Notación y conceptos generales
Hipótesis La hipótesis se representa con $h_\theta$ y es el modelo que elegimos. Para un dato de entrada $x^{(i)}$, la predicción dada por el modelo se representa como $h_\theta(x^{(i)})$.
Función de pérdida Una función de pérdida es una función $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ que toma como entrada el valor predicho $z$ y el valor real esperado $y$, dando como resultado qué tan diferentes son ambos. Las funciones de pérdida más comunes se detallan en la siguiente tabla:
Mínimo error cuadrático | Pérdida logística | Pérdida de bisagra | Entropía cruzada |
$\displaystyle\frac{1}{2}(y-z)^2$ | $\displaystyle\log(1+\exp(-yz))$ | $\displaystyle\max(0,1-yz)$ | $\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$ |
![]() |
![]() |
![]() |
![]() |
Regresión lineal | Regresión logística | SVM | Red neuronal |
Función de costo La función de costo $J$ es comúnmente utilizada para evaluar el rendimiento de un modelo y se define utilizando la función de pérdida $L$ de la siguiente forma:
Descenso de gradiente Siendo $\alpha\in\mathbb{R}$ la tasa de aprendizaje, la regla de actualización de descenso en gradiente se expresa junto a la tasa de aprendizaje y la función de costo $J$ de la siguiente manera:
![Gradient descent](teaching/cs-229/illustrations/gradient-descent.png?01662c4a8147a55ba09f4f5c047641ba)
Observación: El descenso en gradiente estocástico (en inglés, Stochastic Gradient Descent) actualiza el parámetro basándose en cada ejemplo de entenamiento, mientras que el descenso por lotes realiza la actualización del parámetro basándose en un conjunto (un lote) de ejemplos de entrenamiento.
Verosimilitud La verosimilitud de un modelo $L(\theta)$ dados los parámetros $\theta$ es utilizada para hallar los valores óptimos de $\theta$ a través de la verosimilitud. En la práctica se utiliza la log-verosimilitud $\ell(\theta)=\log(L(\theta))$ la cual es fácil de optimizar. Tenemos:
Algoritmo de Newton El algoritmo de Newtow es un método numérico para hallar $\theta$ tal que $\ell'(\theta)=0$. Su regla de actualización es:
Observación: la generalización multidimensional, también conocida como método de Newton-Raphson, tiene la siguiente regla de actualización:
Modelos lineales
Regresión lineal
Asumimos que $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$
Ecuaciones normales Sea $X$ la matriz de diseño, el valor de $\theta$ que minimiza la función de costo es una solución en forma cerrada tal que:
Algoritmo LMS Sea $\alpha$ la tasa de aprendizaje, la regla de actualización del algoritmo LMS (en inglés, Least Mean Squares) para el entrenamiendo de $m$ puntos, conocida también como tasa de aprendizaje de Widrow-Hoff, se define como:
Observación: la regla de actualización es un caso particular del ascenso de gradiente.
LWR Regresión local ponderada, LWR (en inglés, Locally Weighted Regression) es una variante de la regresión lineal que pondera cada ejemplo de entrenamiento en su función de costo utilizando $w^{(i)}(x)$, la cual se define con el parámetro $\tau\in\mathbb{R}$ as:
Clasificación y regresión logística
Función sigmoide La función sigmoide $g$, también conocida como la función logística, se define de la siguiente forma:
Regresión logística Asumiendo que $y|x;\theta\sim\textrm{Bernoulli}(\phi)$, tenemos la siguiente forma:
Observación: no existe solución en forma cerrada para los casos de regresiones logísticas.
Regresión softmax La regresión softmax, también llamada regresión logística multiclase, es utilizada para generalizar regresiones logísticas cuando hay más de dos clases resultantes. Por convención, se define $\theta_K=0$, lo que hace al parámetro de Bernoulli $\phi_i$ de cada clase $i$ igual a:
Modelos lineales generalizados
Familia exponencial Se dice que una clase de distribuciones está en una familia exponencial si es posible escribirla en términos de un parámetro natural, también llamado parámetro canónico o función de enlace, $\eta$, un estadístico suficiente $T(y)$ y una función de log-partición (log-partition function) $a(\eta)$ de la siguiente manera:
Observación: comúnmente se tiene $T(y)=y$. Además, $\exp(-a(\eta))$ puede ser visto como un parámetro de normalización que asegura que las probabilidades sumen uno.
La siguiente tabla presenta un resumen de las distribuciones exponenciales más comunes:
Distribución | $\eta$ | $T(y)$ | $a(\eta)$ | $b(y)$ |
Bernoulli | $\log\left(\frac{\phi}{1-\phi}\right)$ | $y$ | $\log(1+\exp(\eta))$ | $1$ |
Gaussiana | $\mu$ | $y$ | $\frac{\eta^2}{2}$ | $\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$ |
Poisson | $\log(\lambda)$ | $y$ | $e^{\eta}$ | $\displaystyle\frac{1}{y!}$ |
Geométrica | $\log(1-\phi)$ | $y$ | $\log\left(\frac{e^\eta}{1-e^\eta}\right)$ | $1$ |
Supuestos de los modelos GLM Los modelos lineales generalizados (en inglés, Generalized Linear Models) (GLM) tienen como objetivo la predicción de una variable aleatoria $y$ como una función de $x\in\mathbb{R}^{n+1}$ bajo los siguientes tres supuestos:
Observación: los métodos de mínimos cuadrados ordinarios y regresión logística son casos particulares de los modelos lineales generalizados.
Máquinas de vectores de soportes
El objetivo de las máquinas de vectores de soportes (en inglés, Support Vector Machines) es hallar la línea que maximiza la mínima disancia a la línea.
Clasificador de margen óptimo El clasificador de márgen óptimo $h$ se define de la siguiente manera:
donde $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ es la solución del siguiente problema de optimización:
![SVM](teaching/cs-229/illustrations/svm-es.png?048e1f171050c8a3e3061fec3ee83c67)
Observación: la línea se define como $\boxed{w^Tx-b=0}$.
Función de pérdida de tipo bisagra La función de pérdida de tipo bisagra (en inglés, Hinge loss) es utilizada en la configuración de SVMs y se define de la siguiente manera:
Núcleo Dado un mapeo de características $\phi$, se define el núcleo $K$ (en inglés, Kernel) como:
En la práctica, el núcleo $K$ definido por $K(x,z)=\exp\left(-\frac{||x-z||^2}{2\sigma^2}\right)$ es conocido como núcleo Gaussiano y es comúnmente utilizado.
![SVM kernel](teaching/cs-229/illustrations/svm-kernel-es.png?89ea1cbd5481757c318021644b1d5f65)
Observación: decimos que utilizamos el "truco del núcleo" (en inglés, kernel trick) para calcular la función de costo porque en realidad no necesitamos saber explícitamente el mapeo $\phi$ que generalmente es muy complicado. En cambio, solo se necesitan los valores $K(x,z)$.
Lagrangiano Se define el Lagrangiano $\mathcal{L}(w,b)$ de la siguiente manera:
Observación: los coeficientes $\beta_i$ son llamados multiplicadores de Lagrange.
Aprendizaje generativo
Un modelo generativo primero trata de aprender como se generan los datos estimando $P(x|y)$, lo que luego podemos utilizar para estimar $P(y|x)$ utilizando el Teorema de Bayes.
Análisis discriminante Gaussiano
Marco El Análisis discriminante Gaussiano (en inglés, GDA - Gaussian Discriminant Analysis) asume que $y$, $x|y=0$ y $x|y=1$ son de la siguiente forma:
Estimación La siguiente tabla resume las estimaciones encontradas al maximizar la probabilidad:
$\widehat{\phi}$ | $\widehat{\mu_j}\quad{\small(j=0,1)}$ | $\widehat{\Sigma}$ |
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$ | $\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$ | $\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$ |
Naive Bayes
Supuestos El modelo Naive Bayes supone que las características de cada punto de los dato son todas independientes:
Soluciones Maximizar la log-probabilidad da las siguientes soluciones, con $k\in\{0,1\},l\in[\![1,L]\!]$
Observación: Naive Bayes es comúnmente utilizado para la clasificación de texto y la detección de correo no deseado (spam).
Métodos basados en árboles y conjuntos
Estos métodos pueden ser utilizados tanto en problemas de regresión como de clasificación.
CART Árboles de clasificación y regresión (en inglés, Classification and Regression Trees) (CART), comúnmente conocidos como árboles de decisión, pueden ser representados como árboles binarios. Presentan la ventaja de ser muy interpretables.
Bosques aleatórios Es una téctica (en inglés, Random Forest) basada en árboles que utiliza una gran cantidad de árboles de decisión construidos a partir de conjuntos de características seleccionadas al azar. A diferencia del árbol de decisión simple, la solución del método de bosques aleatórios es difícilmente interpretable aunque por su frecuente buen rendimiento es un algoritmo muy popular.
Observación: el método de bosques aleatorios es un típo de método de conjuntos.
Potenciación La idea de la potenciación (en inglés, Boosting) es combinar varios métodos de aprendizaje débiles para conformar uno más fuerte. La siguiente tabla resume los principales tipos de potenciamiento:
Potenciamiento adaptativo | Potenciamiento del gradiente |
• Se pondera fuertemente en los errores para mejorar en el siguiente paso del potenciamiento | • Los métodos de aprendizaje débiles entrenan sobre los errores restantes |
Otros métodos no paramétricos
$k$ vecinos más cercanos El algorítmo de $k$ vecinos más cercanos (en inglés, $k$-nearest neighbors algorith), comunmente conocido como $k$-NN, es un método no paramétrico en el que la respuesta a un punto de los datos está determinada por la naturaleza de sus $k$ vecinos del conjunto de datos. El método puede ser utilizado tanto en clasificaciones como regresiones.
Observación: Cuanto mayor es el parámetro $k$, mayor es el sesgo, y cuanto menor es el parámetro $k$, mayor la varianza.
![k nearest neighbors](teaching/cs-229/illustrations/k-nearest-neighbors.png?02f80a524bb11e2b7a70b58c9ed3b0f4)
Teoría del aprendizaje
Desigualdad de Boole Sean $A_1, ..., A_k$ $k$ eventos, tenemos que:
![Union bound](teaching/cs-229/illustrations/union-bound.png?aab917859fa8e260e865def69a2889b8)
Desigualdad de Hoeffding Sean $Z_1, .., Z_m$ $m$ variables iid extraídas de una distribución de Bernoulli de parámetro $\phi$. Sea $\widehat{\phi}$ su media emprírica y $\gamma>0$ fija. Tenemos que:
Observación: esta desigualdad se conoce también como el límite de Chernoff.
Error de entrenamiento Para un clasificador dado $h$, se define el error de entrenamiento $\widehat{\epsilon}(h)$, también conocido como riesgo empírico o error empírico, de la siguiente forma:
Aprendizaje correcto probablemente aproximado (PAC) PAC es un marco bajo el cual se probaron numerosos resultados en teoría de aprendizaje, y presenta los siguientes supuestos:
- los conjuntos de entrenamiento y de prueba siguen la misma distribución
- los ejemplos de entrenamiento son escogidos de forma independiente
Shattering Dado un conjunto $S=\{x^{(1)},...,x^{(d)}\}$, y un conjunto de clasificadores $\mathcal{H}$, decimos que $\mathcal{H}$ destroza (shatters) $S$ si para cualquier conjunto de etiquietas $\{y^{(1)}, ..., y^{(d)}\}$, tenemos que:
Teorema de la frontera superior Sea $\mathcal{H}$ una clase de hipótesis finita tal que $|\mathcal{H}|=k$ y sea $\delta$ y el tamaño de la muestra $m$ fijo. Entonces, con probabilidad de al menos $1-\delta$, tenemos:
Dimensión VC La dimensión de Vapnik-Chervonenkis (VC) de una clase de hipótesis finita $\mathcal{H}$, denotada como $\textrm{VC}(\mathcal{H})$, es el tamaño del conjunto más grande destrozado (shattered) por $\mathcal{H}$.
Observación: la dimensión VC de ${\small\mathcal{H}=\{\textrm{set of linear classifiers in 2 dimensions}\}}$ es 3.
![VC dimension](teaching/cs-229/illustrations/vc-dimension.png?73859dedcc66a0e47526936f801b7b56)
Teorema (Vapnik) Dado $\mathcal{H}$, con $\textrm{VC}(\mathcal{H})=d$ y $m$ el número de ejemplos de entrenamiento. Con probabilidad de al menos $1-\delta$, tenemos que: