Aprendizaje Computacional

El area de Inteligencia Artificial (IA) investiga la manera en que se puede crear/emular la inteligencia de manera artificial. Actualmente muchas de las formas de inteligencia artificial se prueban en una computadora, se puede llegar a pensar que la finalidad de IA es crear un programa inteligente, pero el área no se limita solamente a programas de computadora. Por otro lado, esta asignatura se encuentra dentro de la IA y tiene como objetivo el crear programas capaces de aprender.

Una manera de entender qué es aprendizaje computacional es describiendo lo opuesto, de manera general un algoritmo (programa) es una secuencia de pasos que se siguen para resolver un problema, aunque esta secuencia no es evidente en algunos casos, podemos asumir que está ahí, por ejemplo, una hoja de cálculo o un procesador de texto son programas donde se sabe exactamente que se requiere y se puede generar un algoritmo para resolverlo. También cabría en esta descripción el algoritmo para encontrar la ruta mas corta entre dos nodos en un grafo, dicho algoritmo lo encontramos en cualquier navegador gps.

Por otro lado, existen problemas para los cuales escribir una secuencia de pasos para su solución es prácticamente imposible. Por ejemplo, identificar el correo no deseado, traducciones automáticas, o simplemente identificar el código postal en una carta (ver http://​yann.​lecun.​com/​exdb/​mnist/​). Es en estos problemas donde recae el aprendizaje automático.

Objetivo

Conocer las características de problemas de aprendizaje supervisado. Conocer las fortalezas y debilidades de diferentes tipos de algoritmos de aprendizaje de tal manera de que se pueda seleccionar el algoritmo mas adecuado al problema planteado. Implementar y analizar el rendimiento de diferentes algoritmos de aprendizaje supervisado.

Introducción

Aprendizaje computacional es una rama de la IA que estudia los algoritmos que son capaces de aprender a partir una serie de ejemplos o con alguna guía. Existen diferentes tipos de aprendizaje computacional los mas comunes son: aprendizaje supervisado, aprendizaje no-supervisado y aprendizaje por refuerzo.

En aprendizaje supervisado se crean modelos partiendo de un conjunto de pares, entrada y salida, donde el objetivo es encontrar un modelo que logra aprender esta relación y logra predecir ejemplos no vistos en el proceso, en particular esto se le conoce como inductive learning. Complementando este tipo de aprendizaje supervisado se tiene lo que se conoce como transductive learning, en el cual se tiene un conjunto de pares y solamente se requiere conocer la salida en otro conjunto de datos. En este segundo tipo de aprendizaje todos los datos son conocidos en el proceso de aprendizaje.

Aprendizaje no-supervisado es aquel donde se tiene un conjunto de entradas y se busca aprender alguna relación de estas entradas, por ejemplo, se podrían generar grupos o utilizar estas entradas para hacer un transformación o encontrar un patrón.

Finalmente aprendizaje por refuerzo es aquel donde se aprender utilizando una función de refuerzo, es decir, se puede ver como un algoritmo que realiza una acción y la función de refuerzo regresa una calificación, de esta manera se puede saber cuáles son aquellas acciones que son mas recompensadas. En particular este último tipo de aprendizaje se puede entender mas claro con un ejemplo de control, ver el siguiente video.

AlphaGo

Estos tres tipos de aprendizaje no son excluyentes uno del otro, comúnmente para resolver un problema complejo se combinan diferentes tipos de aprendizaje y otras tecnologías de IA para encontrar una solución aceptable. Probablemente una de las pruebas más significativas de lo que puede realizarse con aprendizaje automático es lo realizado por AlphaGo, leer el resumen del siguiente artículo https://​www.​nature.​com/​articles/​nature16961 y recientemente se quita una de las restricciones originales, la cual consiste en contar con un conjunto de jugadas realizadas por expertos, publicando este descubrimiento en https://​www.​nature.​com/​articles/​nature24270.

Medicina

Es importante mencionar que no todo lo que se hace en aprendizaje automático está relacionado con juegos clásicos y que existen avances importantes en otros dominios. Como por ejemplo recientemente en el área de cardiología se presenta el siguiente artículo https://​www.​nature.​com/​articles/​s41591-​018-​0268-​3, o en dermatología para detección de cancer https://​www.​nature.​com/​articles/​nature21056 solo por mostrar algunos otros ejemplos.

Plataformas

Recientemente, en el área de aprendizaje, hay una tendencia de utilizar plataformas donde diferentes empresas u organismos gubernamentales o sin fines de lucro, ponen un problema e incentivas al publico en general a resolver este problema. La plataforma sirve de mediador en este proceso.

Ver por ejemplo https://​www.​kaggle.​com.

En el ámbito científico también se han generado este tipo de plataformas aunque su objetivo es ligeramente diferente, lo que se busca es tener una medida objetiva de diferentes soluciones y en algunos casos facilitar la reproducibilidad de las soluciones.

Ver por ejemplo http://​codalab.​org.

Aprendizaje Supervisado

Aprendizaje supervisado es un problema donde el componente inicial es un conjunto de pares, entrada y salida. Es decir se cuenta con $\mathcal X = \{ (x_1, y_1), \ldots, (x_N, y_N )\}$, donde $x_i$ corresponde a la $i$-ésima entrada y $y_i$ es la salida asociada a esa entrada. Cuando $y \in \{0, 1\}$ se dice que es un problema de clasificación binaria, por otro lado cuando $y \in \{0, 1\}^K$ se encuentra uno en clasificación multi-clase o multi-etiqueta y finalmente si $y \in \mathbb R$ entonces es un problema de regresión. Cabe mencionar que al conjunto $\mathcal X$ se le conoce como conjunto de entrenamiento y es en este conjunto donde el algoritmo de aprendizaje aprenderá.

Se puede asumir que existe una función $f$ que genera la relación entrada y salida mostrada en $\mathcal X$, es decir, que $\forall_{(x, y) \in \mathcal X} f(x) = y$. En este contexto, aprendizaje supervisado se entiende como el proceso de encontrar una función $h^*$ que se comporta similar a $f$.

Para encontrar $h^*$, se utiliza $\mathcal X$; el conjunto de hipótesis (funciones), $\mathcal H$, que se considera pueden aproximar $f$; una función de error, $L$; y el error empírico $E(h \mid \mathcal X) = \sum_{(x, y) \in \mathcal X} L(y, h(x))$. Utilizando estos elementos la función buscada es: $h^* = \textsf{argmin}_{h \in \mathcal{H}} E(h \mid \mathcal X)$.

El encontrar la función $h^*$ no resuelve el problema de aprendizaje en su totalidad, además se busca una función que sea capaz de generalizar es decir de predecir correctamente instancias no vistas. Asúmase que se tiene un conjunto de prueba, $\mathcal T={(x_i, y_i)}$ para $i=1 \ldots M$, donde $\mathcal X \cap \mathcal T = \emptyset$. La idea es que el error empírico sea similar en el conjunto de entrenamiento y prueba. Es decir $E(h^* \mid \mathcal X) \approx E(h^* \mid \mathcal T)$.

Utilizando $\mathcal X$ y $\mathcal T$ podemos definir inductive learning como el proceso de aprendizaje en donde solamente se utiliza $\mathcal X$ y el algoritmo debe de ser capaz de predecir cualquier instancia. Por otro lado, transductive learning es el proceso de aprendizaje donde se utilizar $\mathcal X \cup \{ x \mid (x, y) \in \mathcal T \}$ para aprender y solamente es de interés el conocer la clase o variable dependiente del conjunto $\mathcal T$.

Sobre-aprendizaje

Existen clases de algoritmos, $\mathcal H$, que tienen un mayor grado de libertad el cual se ve reflejado en una capacidad superior para aprender, pero por otro lado, existen problemas donde no se requiere tanta libertad, esta combinación se traduce en que el algoritmo no es capaz de generalizar y cuantitativamente se ve como $E(h^* | \mathcal X) \ll E(h^* | \mathcal T)$.

Para mostrar este caso supóngase que se tiene un algoritmo que guarda el conjunto de entrenamiento y responde lo siguiente:

$h^*(x) = \begin{cases} y &\text{si} (x, y) \in \mathcal X \\ 0&\end{cases}$.

Es fácil observar que este algoritmo tiene $E(h^* | \mathcal X) = 0$ dado que se aprende todo el conjunto de entrenamiento.

 Sub-aprendizaje

Por otro lado existen problemas donde el conjunto de algoritmos $\mathcal H$ no tienen los grados de libertad necesarios para aprender, dependiendo de la medida de error esto se refleja como $E(h^* | \mathcal X) \gg 0$.

La siguiente figura muestra un problema de clasificación donde el algoritmo de aprendizaje presenta el problema de sub-aprendizaje. El problema de clasificación es encontrar una función que logre separar las dos clases, las cuales están representadas por los puntos en color azul y verde, el algoritmo de aprendizaje intenta separar estás clases mediante una linea (dibujada en rojo) y como se puede observar una linea no tiene los suficientes grados de libertad para separar las clases.

Sub Aprendizaje

 Ejercicio: Implementar un algoritmo que sobre-aprenda

Implementar en python un algoritmo que implemente la siguiente función de aprendizaje $h^*(x) = \begin{cases} y &\text{si} (x, y) \in \mathcal X \\ 0&\end{cases}$ la cual se sabe que va a sobre-aprender.

La implementación debe de ser una clase que tenga dos métodos fit y predict.

fit recibe dos argumentos el conjunto de entradas utilizando un arreglo de dos dimensiones de numpy y el segundo argumento es un arreglo de una dimensión que corresponde a la variable dependiente.

predict recibe solamente un argumento que corresponde a los ejemplos que se quieren predecir, se espera que reciba un arreglo de dos dimensiones utilizando numpy, es decir, podría recibir la misma variable que se utiliza como primer argumento del método fit.

class Classifier(object):
  def __init__(self):
    pass
    
  def fit(self, X, y):
    pass
    
  def predict(self, X):
    pass

Finalmente probar su implementación utilizando uno de los problemas de clasificación mas populares en la literatura el cual es https://​archive.​ics.​uci.​edu/​ml/​datasets/​Iris

Cabe mencionar que la idea de implementar el algoritmo de aprendizaje utilizando estos dos métodos es seguir el formato utilizado por http://​scikit-​learn.​org

Métodos paramétricos

En la siguiente figura se muestra un conjunto de puntos en $\mathbb{R}^2$ los cuales tiene asociado un color. El objetivo es encontrar una función capaz de definir el color de un nuevo punto, $x \in \mathbb{R}^2$, dado.

Clusters

Una manera de abordar este problema es viéndolo como un problema de probabilidad, es decir, se busca la probabilidad de saber el color dado un un punto. La probabilidad de observar $x$ dado algún color se define como $p(x \mid C) = \frac{p(X \cap C)}{p(C)}$, donde $p(C)$ es la probabilidad del color C y $p(X \cap C)$ es la probabilidad del evento conjunto punto y color. Similarmente se define la probabilidad de observar un color dado un punto como $p(C \mid X) = \frac{p(X \cap C)}{p(X)}$.

Utilizando estas dos ecuaciones se puede llegar a la siguiente igualdad $p(X \mid C) p(C) = p(C \mid X) p(X)$ donde se puede observar el teorema de Bayes es decir

$p(C \mid X) = \frac{p(X \mid C) p(C)}{p(X)}$.

Sabiendo la probabilidad de observar un color dado un punto esta uno en la posición de plantear la función buscada como asociar el color que exhiba la mayor probabilidad, es decir:

$f(x) = \textsf{arg max}_{c \in C} p(c \mid x)$.

Naive Bayes

Asumiendo que el problema de clasificación se puede modelar como una distribución normal y además partiendo de que las variables son independientes la probabilidad quedaría como:

$p(x | c) = \frac{1}{\prod_i 2 \pi \sigma^2_{c_i}} \exp^{- \frac{1}{2} \sum_i \frac{(x - \mu_{c_i})^2}{\sigma_{c_i}^2}}$

donde $ \mu_{c_i} $ es la media de la clase $ c $ en la variable $ i $, equivalentemente se obtiene la varianza $ \sigma_{c_i}^2 $.

En muchos casos es mas conveniente utilizar el logaritmo de $ p(c \mid x) $ para identificar la clase, es fácil observar que el logaritmo no afecta el resultado y puede simplificar algunos cálculos.

La clase buscada se expresa como:

$f(x) = \textsf{arg max}_{c \in C} p(c \mid x)$

cambiando $p(c \mid x)$ por $\log p(c \mid x) $ no modifica en nada el resultado pero el cálculo se convierte en:

$ \log p(c \mid x) = \log p( x \mid c) p(c) - \log p(x).$

tomando en cuenta que el denominador es común para todas las clases, se puede uno enfocar en:

$\log p(x \mid c) p(c) = \log p(x \mid c) + \log p(c).$

Utilizando una distribución normal con el logaritmo podemos ver como los cálculos se simplifican pasando en productos a sumas, es decir,

$ \log p(x \mid c) = \log \frac{1}{\prod_i 2 \pi \sigma^2_{c_i}} + \log \exp^{- \frac{1}{2} \sum_i \frac{(x - \mu_{c_i})^2}{\sigma_{c_i}^2}}$

$ \log p(x \mid c) = \log \frac{1}{\prod_i 2 \pi \sigma^2_{c_i}} - \frac{1}{2} \sum_i \frac{(x - \mu_{c_i})^2}{\sigma_{c_i}^2}$

$ \log p(x \mid c) = - \sum_i \log 2 \pi \sigma^2_{c_i} - \frac{1}{2} \sum_i \frac{(x - \mu_{c_i})^2}{\sigma_{c_i}^2}.$

Esta última ecuación es normalmente la que se implementa en un Naive Bayes, se puede observar el código fuente de GaussianNB de la librería sklearn para corroborar este hecho.

 Bernoulli

En una distribución Bernoulli hay dos posible resultados, es decir el evento ocurre o no. Es decir, cuando el evento ocurre se tiene que la variable aleatoria $\mathcal X$ toma el valor de 1 con una probabilidad $p$ y que no ocurra tiene una probabilidad $1-p$, es decir,

$P(x) = p^x (1 - p)^{(1-x)}.$

Para obtener $p$ dado un conjunto de muestras independientes e idénticamente distribuidas, se utiliza:

$\hat p = \frac{\sum_i x_i }{N}.$

Clasificación de Texto

La clasificación de texto se puede pensar como un problema de aprendizaje supervisado donde se tiene un conjunto $\mathcal X = \{ (x_1, y_1), \ldots, (x_N, y_N)\}$ donde $x_i$ es un texto y $y_i$ es la clase asociada a ese texto, e.g., (que tengan un excelente día, positivo).

Este problema se puede modelar utilizando una distribución Bernoulli, asumiendo que cada palabra se encuentra o no en el documento o enunciado.

Por ejemplo supóngase que se tiene el siguiente conjunto.

Texto Clase
excelente día  positivo
buenas tardes positivo
odio el día lunes negativo
las vacas me deprimen negativo

Este conjunto se puede representar en una bolsa de palabras, es decir, indicando aquellas palabras que aparecen en el enunciado de la siguiente manera.

excelente  dia buenas tardes odio el lunes las vacas me deprimen
1 1
1 1
1 1 1 1
1  1 1 1

Utilizando esta representación y asumiendo que las palabras son independientes $p(x \mid c)$ quedaría como:

$p(x \mid c) = \prod_i \hat{p}_{ci}^{x_i}(1- \hat{p}_{ci})^{1-x_i}.$

donde

$\hat{p}_{ci} = \frac{ \mid \{ x \mid (x, y) \in \mathcal X_c, x_i=1 \} \mid}{\mid \mathcal X_c \mid}$

y $\mathcal X_c = \{ (x, y) \mid (x, y) \in \mathcal X, y=c \}$.

Regresión

Hasta este momento se han revisado métodos paramétricos en clasificación, ahora es el turno de abordar esto en el problema de regresión.

Recordando, regresión es un problema de aprendizaje supervisado, es decir se cuenta con un conjunto de entrenamiento, (\mathcal X = { (x_1, y_1), \ldots, (x_N, y_N )}), de pares entrada y salida; la salida es ( y_i \in \mathbb R).

Entonces se busca una función con la forma $f: \mathbb{ R^d } \rightarrow \mathbb R$ y que se comporte como: $\forall_{(x, y) \in \mathcal X} f(x) = y + \epsilon$.

Este problema se puede plantear como un problema de optimización o como un problema de algebra lineal. Viéndolo como un problema de algebra lineal lo que se tiene es

$X w = y$

donde $X$ son las observaciones, entradas o combinación de entradas, $w$, son los pesos asociados y $y$ es el vector que contiene las variables dependientes.

Tanto $X$ como $y$ son datos que se obtienen de $\mathcal X$ entonces lo que hace falta identificar es $w$, lo cual se puede realizar de la siguiente manera

$ X^T X w = X^T y $

donde $X^T$ es la transpuesta de $X$. Despejando $w$ se tiene

$w = (X^T X)^{-1} X^T y.$

Métodos no paramétricos

Los métodos paramétricos asumen que los datos provienen de un modelo común, esto da la ventaja de que el problema de estimar el modelo se limita a encontrar los parámetros del mismo, por ejemplo los parametros de una distribución gausiana. Por otro lado en los métodos no paramétricos asumen que datos similares se comportan de manera similar, estos algoritmos también se les conoces como algoitmos de memoría o basados en instancias.

Clasificador de Vecinos Cercanos

El clasificador de vecinos cercanos es un clasificador simple de entender, la idea es utilizar el conjunto de entrenamiento y una función de distancia para asignar la clase de acuerdo a los k-vecinos más cercanos al objeto deseado.

 Usando KDTree

La manera más sencilla de crear el clasificador de vecinos cercanos es utilizando un método exhaustivo en el cálculo de distancia. Otra forma de realizar esto es mediante el uso de alguna estructura de datos que te permita el no realizar todas las operaciones. Uno de estos métodos puede ser KDTree.

Regresión

Árboles de Decisión

Los árboles de decisión son una estructura de datos jerárquica, el cual se construye utilizando una estrategia de divide y vencerás. Los árboles están conformados por nodos internos, donde se realizan operaciones y hojas, las cuales indican la clase. En la siguiente figura se muestra un ejemplo de un árbol de decisión.

Árbol

Descripción

La construcción un árbol se realiza mediante un procedimiento recursivo en donde se aplica una función $f_m(x)$ que etiqueta cada hijo del nodo $m$ con respecto a las etiquetas del proceso de clasificación. Por ejemplo, en el árbol de la figura anterior, la función $f_m$ tiene la forma $f_m(x) = x_i \leq a$, donde el parámetro $i$ y $a$ son aquellos que optimizan una función de aptitud.

Optimización

La entropía $H(\mathcal X)$ es una medida de “caos” o sorpresa. En este caso, mide la “uniformidad” de la distribución de probabilidad. Se define como:

$H(\mathcal X) = \sum_{x \in \mathcal X} - p(x) \log_2 p(x)$.

Una manera de encontrar los parámetros $i$ y $a$ de la función de corte $f_m(x) = x_i \leq a$ es utilizando la entropía $H(\mathcal X)$. La idea es que en cada corte, se minimice la entropía.

https://link.springer.com/article/10.1007/BF00116251

Al evaluar cada posible corte, se calcula la ganancia de entropía en base a la siguiente ecuación:

$Ganancia = H( \mathcal X ) - \sum_m \frac{\mid \mathcal X_m \mid}{\mid \mathcal X \mid} H(\mathcal X_m)$

donde $\mathcal X$ representa todas las muestras, $\mid \mathcal X \mid$ el número total de muestras, $\mathcal X_m$ las muestras en el nodo $m$ y finalmente, $\mid \mathcal X_m \mid$ el número de muestras en el nodo $m$.

Finalmente, se selecciona el corte cuya ganancia sea máxima.

Regresión

Hasta este momento se ha visto como se optimizan los parámetros de la función de corte $f_m$ para problemas de clasificación.

La única diferencia con problemas de regresión es la función que se utiliza para optimizar los parámetros, en el caso de clasificación es entropía y en el caso de regresión podría ser el error cuadrático medio o la suma de los errores absolutos.

Diseño y análisis de experimentos de aprendizaje

Hasta este momento se han revisado varios algoritmos de aprendizaje supervisado:

Es importante tener los conocimientos para poder decidir cuál de ellos utilizar dado un problema, este es el tema central de esta sección.

Empezamos recordando que tenemos dos conjuntos, el de entrenamiento, $\mathcal X$ y el de prueba, $\mathcal T$; donde $\mathcal X$ se utiliza para entrenar el algoritmo y $\mathcal T$ se usa para probar la capacidad de generalización del algoritmo.

 Clasificación

En clasificación existen diferentes medidas para comparar los clasificadores, algunas de ellas son accuracy, precision, recall, y F1 score, entre otras.

En http://nmis.isti.cnr.it/sebastiani/Publications/ICTIR2015.pdf se describe de manera axiomática algunas de estas medidas y en el siguiente video se verá de manera práctica.

Comparación

Sea $\hat y_1$ y $\hat y_2$ las predicciones, en el conjunto de prueba ($y$), de dos algoritmos de clasificación o de regresión y sea la función $f$ una medida de rendimiento, entonces se puede comparar el rendimiento de estos dos algoritmos existiendo tres casos $f(y, \hat y_1) = f(y, \hat y_2) $, $f(y, \hat y_1) < f(y, \hat y_2) $ y $f(y, \hat y_1) > f(y, \hat y_2) $ .

En este contexto uno escogería el algoritmo que presenta el mejor rendimiento. Una limitante de este procedimiento es que no se ha medido la confianza que se tiene en esta decisión, es decir, el conjunto de prueba solamente es una muestra de todos los elementos y sería factible que en otro conjunto de prueba esta decisión sea equivocada.

Discriminantes lineales

En sesiones anteriores hemos visto diferentes técnicas para discriminar entre clases. Por un lado vimos métodos paramétricos que se basan en utilizar $ P(C \mid X) $ para decidir cuál es la clase, $ C $, mas probable, es decir, uno puede utilizar la regla $ \textsf{arg max}_{c} P( c \mid x) $. También se vieron no paramétricos, donde no se da una forma a la función discriminante, $ g $, como son los vecinos cercanos o los árboles de decisión.

En este apartado tratamos metodos lineales, donde se puede decidir la clase mediante la siguiente regla $ \textsf{arg max}_{i} g_i(x) $, donde $ g $ es una función lineal y la $i$ itera por las diferentes clases. En estos clasificadores no se asume cual es la distribución que modela el fenómeno, en su lugar se asume que la función discriminante es lineal y es capaz de discriminar las clases.

Regresión Logística

En regresión logística se asume que

$ \hat y(x) = \textsf{sigmoid}(x) = \frac{1}{1 + \exp{-(w^T \cdot x + w_0)}}$.

Se puede asumir que $ y $ sigue una distribución Bernoulli en el caso de dos clases, entonces la máxima verosimilitud quedaría como:

$l(w, w_0 \mid \mathcal X) = \prod_{(x, y) \in \mathcal X} (\hat y(x))^{y} (1 - \hat y(x)))^{1-y}$.

Se puede observar que la ecuación anterior no tiene una solución cerrada y por lo tanto es necesario utilizar un método de optimización iterativo para encontrar los parámetros $w$ y $w_0$.

Un método adecuado para encontrar esta solución es el método de gradiente descendente. Tomando en cuenta una ecuación lineal, este método actualiza los coeficientes con la siguiente regla:

$w_i = w_i - \eta \frac{\partial E}{\partial w_i}$

donde $E$ es una función de error, la cual se puede definir como $E = -\log l $. Utilizando esta información la actualización de los coeficientes queda como:

$\frac{\partial E}{\partial w_i} = - \sum_{(x, y) \in \mathcal X} (y - \hat y(x)) x_i$

y para $w_0$

$\frac{\partial E}{\partial w_0} = - \sum_{(x, y) \in \mathcal X} (y - \hat y(x))$.

Máquinas de Soporte Vectorial

Las máquinas de soporte vectorial siguen la idea de encontrar una función discriminante lineal que separe las clase.

Se ha mencionado anteriormente, el conjunto de entrenamiento es un conjunto de pares entrada salida, i.e., $\mathcal X=\{ (x_i, y_i) \} $, donde $x$ es la entrada y $y$ es la salida. Suponiendo que tenemos un problema binario y las clases están representadas por $-1$ y $1$, es decir, $ y \in \{-1, 1\}$. Entonces, las máquinas de soporte vectorial tratan de encontrar una función con las siguientes características.

Sea $x_i$ un ejemplo que corresponde a la clase $ 1 $ entonces se busca $w$ tal que

$$w^T x_i + w_0 \geq +1.$$

En el caso contrario, es decir, $x_i$ un ejemplo de la clase $-1$, entonces

$$w^T x_i + w_0 \leq -1.$$

Estas ecuaciones se pueden escribir como

$$(w^T x_i + w_0) y_i \geq +1,$$

donde $(x_i, y_i) \in \mathcal X$.

Máquinas de Soporte

La función discriminante es $ w^T x + w_0 $ y la distancia que existe entre cualquier punto $x_i$ al discriminante está dada por

$$\frac{(w^T x_i + w_0) y_i }{\mid \mid w \mid \mid}$$

Entonces, se puede ver que lo que se busca es encontrar $w, w_0$ de tal manera que cualquier punto $x_i$ esté lo mas alejada posible del discriminante, esto se logra minimizando $w$, es decir, resolviendo el siguiente problema de optimización:

$$ \min \frac{1}{2} \mid \mid w \mid \mid $$

sujeto a $ (w^T x_i + w_0) y_i \geq +1, \forall (x_i, y_i) \in \mathcal X $.

Kernel

Existen problemas donde no es posible encontrar una función lineal que discrimine entre las clases, para estos problemas es común utilizar una transformación de tal manera que en el nuevo espacio el problema sea linealmente separable.

Existen varias funciones que son utilizadas para este fin, en general cualquier función con la forma (K(x, y) \rightarrow \Re) funcionaría.

La idea es que en este nuevo espacio los coeficientes ( w ) están asociados a ejemplos del conjunto de entrenamiento, es decir, para un ejemplo (x_i), se busca lo siguiente

$(\sum_{(x, y) \in \mathcal X} w_x K(x, x_i) + w_0) y_i \geq +1$.

Ensambles

Una manera de reducir la varianza de un clasificador o regresor es mediante el uso de ensambles. Los ensambles son maneras de combinar clasificadores que presentan algunas diferencias, es decir, estos pueden ser entrenados con diferentes particiones del conjunto de entrenamiento, o tienen diferentes parámetros o son diferentes algoritmos.

 Bagging

Bagging es un método sencillo para la creación de un ensamble, la idea original es hacer un muestreo con repetición y así generar un nuevo conjunto de entrenamiento.

Se ha probado que en promedio bagging es equivalente al seleccionar el 50% de los datos sin reemplazo y entrenar con este subconjunto, en el siguiente video vemos los efectos de bagging utilizando una máquina de soporte vectorial lineal.

Stack Generalization

Este tipo de ensamble es una generalización a todos los ensambles, la idea es utilizar las predicciones de varios clasificadores para generar la predicción final.

En bagging la función que se utilizó fue simplemente utilizar la media de las predicciones hecha por los clasificadores base, pero la media podría no ser la mejor función que una esta información.

Por otro lado en Stack Generalization se entrena otro clasificador sobre las predicciones para tomar la decisión final.

En el siguiente video se muestra este procedimiento.

Autores

Mario Graff

Investigador Cátedras CONACYT asignado a INFOTEC

112 Circuito Tecnopolo Norte Col. Tecnopolo Pocitos II,
C.P. 20313, Aguascalientes, Ags, México.

Tel. +52 (555) 624 28 00 Ext. 6315
email: mario.graff at infotec.mx

Claudia Nallely Sánchez Gómez

INFOTEC
Universidad Panamericana

112 Circuito Tecnopolo Norte Col. Tecnopolo Pocitos II,
C.P. 20313, Aguascalientes, Ags, México.

email: cnsanchez at up.com.mx