CS 229 - Aprendizaje automático


Hoja de referencia de Aprendizaje Supervisado
Star

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 Discriminative model Generative model
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]$
Least squared error Logistic loss Hinge loss Cross entropy
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:

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

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:

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

Gradient descent

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:

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

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:

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

Observación: la generalización multidimensional, también conocida como método de Newton-Raphson, tiene la siguiente regla de actualización:

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

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:

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

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:

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

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:

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

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:

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

Regresión logística ― Asumiendo que $y|x;\theta\sim\textrm{Bernoulli}(\phi)$, tenemos la siguiente forma:

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

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:

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

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:

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

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:

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$
$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$
$(3)\quad\boxed{\eta=\theta^Tx}$

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:

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

donde $(w, b)\in\mathbb{R}^n\times\mathbb{R}$ es la solución del siguiente problema de optimización:

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{tal que }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]
SVM

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:

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

Núcleo ― Dado un mapeo de características $\phi$, se define el núcleo $K$ (en inglés, Kernel) como:

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

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

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:

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

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:

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$
$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$
$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

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:

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

Soluciones ― Maximizar la log-probabilidad da las siguientes soluciones, con $k\in\{0,1\},l\in[\![1,L]\!]$

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ et }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ et }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

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

Teoría del aprendizaje

Desigualdad de Boole ― Sean $A_1, ..., A_k$ $k$ eventos, tenemos que:

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]
Union bound

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:

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

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:

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

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:

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

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:

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

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

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:

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]