Los algoritmos clásicos de inteligencia artificial tienen décadas a sus espaldas, y aunque tienen problemas que hacen necesario el deep learning, son buenas soluciones para algunos problemas.

Asumimos que tenemos un problema de clasificación con un dataset den clases, con m muestras agrupadas por cada una de las n clases. El modelo debe asignar satisfactoriamente los nuevos datos a alguno de los grupos existentes.

Si los vectores de datos tienen 2 o 3 dimensiones, podemos representarlos gráficamente y ver de forma empírica cómo serían estas agrupaciones espaciales. Si son más de 3 dimensiones no es posible representarlo, aunque no hay problema en calcularlo matemáticamente.

En el siguiente ejemplo se pueden ver los datos del dataset, simbólicamente etiquetados con figuras geométricas:

Es un ejemplo muy gráfico de cómo están agrupados los datos. En este modelo, un nuevo dato se asigna al grupo cuya posición media esté más cercana en línea recta. Las coordenadas de la posición media de cada grupo son la media de las coordenadas de los datos de cada grupo. En nuestro ejemplo las posiciones medias de cada grupo serían las siguientes:

Esta distancia es conocida como “Distancia Euclídea” y se calcula con la siguiente fórmula, en la que:

• w número de dimensiones de los vectores de datos.
• x₀ cada una de las dimensiones del nuevo dato.
• x₁ cada una de las dimensiones de la posición media del grupo.

En el ejemplo podemos ver las distancias de un dato nuevo a cada uno de los puntos medios, donde se ve perfectamente que pertenece al grupo “círculo”:

Este modelo tiene varios inconvenientes importantes:

• Es especialmente sensible a la “maldición de la dimensionalidad”. Si los vectores de datos tienen una gran cantidad de dimensiones, se necesita una cantidad ingente de datos para entrenar el modelo.
• En el caso del ejemplo los grupos están bien definidos. Pero si los datos están definidos de una forma más difusa, incluso solapándose, es aventurado pensar que para un nuevo dato, la posición media de grupo más cercana represente adecuadamente al grupo al que deba pertenecer este dato. Podría darse el caso incluso de que para representar adecuadamente a un grupo, éste necesite de 2 posiciones medias, en función de su dispersión.

Aunque tiene problemas importantes, no siempre nuestros datos tendrán muchas dimensiones, ni tendrán una distribución complicada. Para problemas de clasificación con datasets sencillos este puede ser un modelo válido con el que trabajar.

Con el fin de evitar los problemas del modelo anterior cuando los datos se encuentran agrupados de forma más compleja, surge el modelo K-nearest Neighbors KNN o “K vecinos más cercanos”.

Este modelo consiste en usar los K puntos del dataset más cercanos al nuevo punto a etiquetar para determinar su etiquetado, que será el mayoritario de entre estos puntos vecinos. En el caso de que se produzca “un empate”, hay que tomar una decisión. El nuevo punto puede ser etiquetado al azar, o como el del punto vecino más cercano de entre los que están empatados, por ejemplo.

Como el valor K se puede definir según nos interese, se suele hablar de este modelo como 1-NN classifier, 2-NN classifier, etc.

A continuación podemos ver un ejemplo de etiquetado de 3 puntos nuevos con un 3-NN classifier, en el que las formas de los puntos definen la clase a la que pertenecen:

Lo bonito de este modelo es que no requiere de entrenamiento, el propio dataset es el modelo.
Sin embargo sigue teniendo bastantes problemas. Los datos de entrenamiento deben transportarse con el modelo y, según el tamaño del conjunto de entrenamiento, encontrar los k vecinos más cercanos para una nueva muestra de entrada puede ser computacionalmente muy costoso.

Por otro lado, si el número de dimensiones no es demasiado elevado y el espacio de almacenamiento lo permite, para datasets con distribuciones espaciales relativamente complejas puede hacer este modelo una buena opción para problemas de clasificación frente al modelo de agrupación visto anteriormente.

Este modelo se basa en el Teorema de Bayes, que data de 1763 y que tiene en la actualidad la siguiente forma:

• P(A|B) Probabilidad de que un evento A ocurra, una vez haya ocurrido un evento B (llamada “probabilidad posterior”).
• P(B|A) Probabilidad de que un evento B ocurra, una vez haya ocurrido un evento A (probabilidad de B, dado A).
• P(A) Probabilidad de que ocurra un evento A. Llamada “probabilidad previa de A”.
• P(B) Probabilidad de que ocurra un evento B.

El teorema de Bayes nos da la probabilidad de que algo ocurra (evento A), dado que sabemos que algo ha sucedido (evento B).
Cómo aplicamos esto a nuestros problemas de clasificación:
Conocemos un vector de atributos, pero no conocemos su clase. Si tenemos un dataset de m vectores de atributos, donde cada vector tiene n atributos x={x₁, x₂, x₃, …, x_n}, entonces podemos reemplazar B (el suceso conocido) por los atributos del vector de atributos. Entonces podemos reemplazar A con y, la etiqueta de clase que queremos asignar al nuevo, desconocido, vector de atributos x.

Nos queda el teorema tal que así:

No nos liemos. Esto quiere decir que si conocemos la probabilidad de que x sea nuestro vector de atributos dada la clase y, y sabemos la probabilidad de que se dé la clase y (P(y)), entonces podemos calcular la probabilidad de que la clase del vector de atributos x pertenezca a la clase y.
Si hacemos esto para todas las posibles clases, podemos ver la que tiene una probabilidad mayor, y seleccionar ésta para nuestro vector x.

Tenemos un dataset de pares (xⁱ, yⁱ), en el que i representa cada vector de atributos del dataset.
Podemos calcular P(y) a partir del histograma del dataset, viendo con qué frecuencia a aparece cada clase.

Sin embargo, directamente, no podemos calcular la probabilidad P(x₁, x₂, x₃, …, x_n|y). Para poder calcular esto vamos a hacer una suposición: vamos a suponer que cada atributo del vector x es estadísticamente independiente del resto de atributos (esto no es siempre cierto, como en en el caso de los píxeles de una imagen, pero es una buena aproximación a la realidad que nos permite obtener buenos resultados).
Naïve indica que los atributos son independientes unos de otros, por lo que este modelo se denomina Naïve Bayes.
Cuando dos eventos son independientes, la probabilidad de que ambos ocurran, es el producto de la probabilidad de que cada uno ocurra por separado, de modo que obtenemos:

Entonces, a partir de los datos de entrenamiento, podemos sacar el histograma de los diferentes atributos para obtener la frecuencia con la que aparecen sus valores, obteniendo de este modo la probabilidad P(x_i|y) de cada atributo, para cada clase.

Para un nuevo vector de atributos a clasificar, podemos saber la probabilidad con la que aparecen los valores de sus atributos. Multiplicamos estas probabilidades obteniendo ∏P(x_i|y), y ésto a su vez lo multiplicamos por P(y). Y este proceso lo repetimos por cada una de las m clases del dataset, seleccionando finalmente la etiqueta que resulte una mayor probabilidad.

Esto funciona cuando los valores de P(x_i|y) son discretos, ¿cómo procedemos si son valores continuos? Para este caso haremos otra suposición: la distribución de los valores de los atributos x_i será normal (campana de Gauss).
Una distribución normal se define por su valor medio (µ) y su desviación estándar (σ). De modo que tenemos para cada atributo de nuestro vector:

N(µ_i, σ_i) significa que la distribución normal estará centrada en el valor medio, y con una extensión definida por σ a cada lado. No conocemos exactamente los valores µ y σ, pero podemos aproximarlos a partir de los datos de entrenamiento para cada clase.

Si, por ejemplo, deseamos conocer la probabilidad de que x₃ de nuestro vector de características a clasificar, se encuentre dentro de la distribución normal correspondiente a la etiqueta y=0, usaríamos la fórmula de densidad de probabilidad de una distribución normalfórmula de densidad de probabilidad de una distribución normal:
Hay que recordar que estamos haciendo 2 suposiciones: la independencia entre atributos, y la distribución normal de los valores de cada atributo.

En el ejemplo anterior multiplicaremos esa probabilidad de cada atributo, y el resultado por la “probabilidad previa” de la clase 0. Y repetiremos el proceso para cada clase, eligiendo finalmente la que tenga una mayor probabilidad, como hicimos en el caso de tener valores discretos.

En ningún momento hemos hecho nada con el denominador P(B) del teorema de Bayes. Esto es porque es constante en todos los casos, por lo que sea cual sea su valor, no va a influir en qué clase es más probable que se dé.

También puede ocurrir que en el caso de tener valores discretos, un valor que aparece raramente, no aparezca en nuestro dataset. Esto provocará que cuando aparezca tendrá una probabilidad P(x_i) = 0.
Esto pueede solucionarse con una técnica llamada Laplace smoothing o “suavizado de Laplace”, aunque un buen dataset debería incluir todos los posibles valores que los atributos puedan tener.
El clasificador Naïve Bayes para datos discretos de sklearn MultinomialNB, usa el suavizado de Laplace por defecto.

Un “árbol de decisión” es un modelo que está formado por un conjunto de nodos. Cada nodo define una condición, y en función de que la condición sea verdadera o falsa, el nodo se bifurca en otros dos.
Si el nodo no se bifurca y asigna una clase en particular, se denomina nodo “hoja”. El primer nodo del que parte toda la estructura se denomina nodo “raíz”. La estructura de este modelo es similar a la de un “árbol”, y de ahí estas denominaciones.

Podemos ver un ejemplo usando el dataset irises:

Los árboles de decisión se consideran “human friendly“ya que es posible seguir todo el proceso de clasificación, que en ocasiones puede resultar muy útil. Un árbol de decisión “se explica a sí mismo”.

El algoritmo de construcción un árbol de decisión es recursivo. Comienza seleccionando una condición para el nodo raíz, después se llama a sí mismo en la bifurcación izquierda, y trabaja como si fuese el nodo raíz y así constantemente hasta llegar a una condición de parada (asignación de la clase correspondiente en un nodo hoja).

Una vez se ha llegado a un nodo hoja, vuelve al nodo padre y explora la otra bifurcación, y así constantemente. De este modo se crea toda la estructura del modelo. Cada vez que se crea una bifurcación, el dataset de entrenamiento también se parte, asignándose a cada nodo la porción del dataset que le corresponde según la condición del nodo padre.

La decisión para seleccionar la regla adecuada en cada nodo para crear una bifurcación se hace por fuerza bruta: se comprueban todas las combinaciones de atributos y valores, agrupando los valores continuos para “discretizarlos”, y evaluando la “pureza” del dataset de las ramas derecha e izquierda. La mejor opción es la que separa las clases del dataset de ese nodo en 2 grupos, y será la condición que quedará en el nodo.

Para determinar “la pureza” de los datasets resultantes de cada rama, usamos el Gini index, o índice de Gini, como hace sklearn:

P(y_i) es la fracción de datos de entrenamiento en el subconjunto del nodo actual, que tienen una clase i determinada. Una partición perfecta de las clases del dataset de un nodo (una rama con una única clase en su subconjunto del dataset, y ninguna de ésta en la otra rama) tiene un índice Gini de 0, dando lugar a un nodo hoja. Una partición en la que haya en su subconjunto de datos de entrenamiento resultante, el mismo número de datos para 2 clases diferentes, tendrá un índice Gini de 0.5. El algoritmo se queda con la condición que genera un índice Gini más bajo.

Esto puede verse en el ejemplo anterior del dataset irises. En cada nodo hay varias líneas:

1. La condición que genera un menor índice Gini, con el subconjunto de datos de entrenamiento de ese nodo.
2. El índice Gini.
3. El número de datos de entrenamiento en ese nodo.
4. El valor es el nº de datos de entrenamiento por cada clase.
5. La clase es la que se asignaría si fuese un nodo hoja, es decir, la que tiene etiquetada un mayor número de datos de entrenamiento de ese nodo.

Cuando se introduce un valor nuevo en el modelo, siempre se ejecuta desde el nodo raíz, hasta los nodos hoja.

Los árboles de decisión son útiles cuando tenemos datos discretos o categorizados, o valores desaparecidos. Valores continuos requieren de ser agrupados, pero sklearn puede hacer esto por nosotros.

El problema de los árboles de decisión es que son muy sensibles al overfiting. Esto quiere decir que son propensos a aprender las particularidades del dataset, en lugar aprender a generalizar a partir éste para etiquetar correctamente nuevas muestras. Es como si se “aprendiera” el dataset y categorizase mal nuevas muestras que no estén incluidas en él.
Además, también tienen el problema de que son demasiado grandes a medida que crece el número de dimensiones.

El overfitting, a veces indicado como “sobreentrenamiento”, puede mitigarse usando “bosques aleatorios” que por norma general, intentaremos usar siempre en lugar de un árbol de decisión.
Para pasar de un árbol de decisión a un bosque aleatorio, usaremos 3 conceptos:

• Ensamblado de clasificadores y votación entre ellos.
• Remuestreo de set de entrenamiento, seleccionando muestras “con reemplazo”.
• Selección de submuestras de atributos aleatorias.

El ensamblado de clasificadores hace referencia a tener varios clasificadores (por ejemplo k-NN, o Naïve Bayes) y que se usen sus salidas para votar la asignación de la categoría correspondiente. La idea es hacer esto con varios árboles de decisión.
El problema es que el algoritmo de creación de un árbol de decisión es determinístico, es decir, el mismo dataset dará lugar siempre al mismo árbol de decisión.

Para solucionar esto podemos entrenar nuestros árboles tomando “nuevas muestras” del dataset de entrenamiento, permitiendo que puedan usarse para entrenar el modelo más de una vez. Como si sacamos canicas de una bolsa y cada vez que sacamos una y la anotamos, la volvemos a meter en la bolsa. Esto es lo que llamamos “muestras con reemplazo”. El dataset completo, con estas nuevas muestras se denomina bootstrap sample, y una colección de datasets construidos de este modo es el bagging. De este modo tenemos diferentes árboles de decisión, con las características del dataset original, y diferentes unos de otros.
El problema que tenemos ahora, es que si tenemos un “bosque” con árboles “ligeramente diferentes” que pueden votar el resultado, aunque seguramente mejoren los resultados respecto de un único árbol, si algún atributo es altamente predecible, todos serán demasiado similares y esto dará problemas.

Entra entonces el tercer concepto que convierte nuestro “bosque” en “bosque aleatorio”. La idea es seleccionar por cada árbol, un subconjunto de atributos y entrenar sólo estos atributos. Hacer esto romperá la correlación entre árboles y aumentaría la solidez general del bosque. En la práctica si tenemos n atributos por cada vector de atributos, cada árbol seleccionará aleatoriamente √n de ellos para construir el árbol. Los bosques aleatorios también están soportados en sklearn.

Las máquinas de vectores de soporte (SVM) es un modelo con un enfoque muy elegante y muy bien fundamentado matemáticamente, que mantuvo a raya a las redes neuronales durante los 90, que representan un modelo empírico basado en datos.

Como las matemáticas que tienen lugar son complejas y quedan lejos del objetivo de estas notas (artículo “Support-Vector Networks” by Cortes and Vapnik (1995)), para comprender el funcionamiento de este modelo, veremos varios conceptos relacionados de forma individual: Margins, support vectors, optimization y kernels.

Parta entender el concepto “márgenes”, vamos a proponer un ejemplo. Vamos a suponer un dataset con vectores de atributos con 2 atributos (2 dimensiones), con 2 posibles clases a etiquetar, y que los representamos de la siguiente manera:

La clase 0 se representa con círculos, y la clase 1 con diamantes, en el eje X se representa el primer atributo y en el eje Y el segundo.

Un clasificador puede ser ideado como un “plano” o “hiperplano” que separa el espacio de los datos de entrenamiento en función de su etiquetado. Este “plano” tendrá n - 1 dimensiones, siendo n el número de dimensiones de los vectores de atributos.
En nuestro caso, tenemos 2 dimensiones, por lo que nuestro hiperplano tendrá 1 dimensión: será una línea.

Cuando tenemos que etiquetar un dato de entrada desconocido, según en el lado del hiperplano que quede, será etiquetado de una forma u otra.
En este contexto, lo que que hay que averiguar es dónde situar este hiperplano. Lo más lógico es pensar que el hiperplano debe encontrarse lo más alejado de todas las clases, tanto como le sea posible. Es decir, el hiperplano es el lugar de máximo margen, en nuestro caso, la línea que de lugar al mayor margen entre clases. Y localizar esta posición es el objetivo de toda SVM.

En nuestro ejemplo podemos visualizar la línea de separación de margen máximo (continua) y los márgenes máximos (discontinua):

Los datos de entrenamiento que definen los márgenes, se dice que los “soportan”. Estos puntos forman los “vectores de soporte” de los márgenes, y de ahí el nombre de “máquina de vectores de soporte” support Vector Machine (SVM).

Usar los vectores de soporte para localizar la posición del margen, da lugar a un cálculo matemático muy complejo que no es objeto de estas notas. Pueden verse estas matemáticas en el artículo: “A Tutorial on Support Vector Machines for Pattern Recognition” by Christopher Burges (1998).

Matemáticamente, podemos encontrar el hiperplano de margen máximo resolviendo un problema de optimización. En este tipo de problemas, dependemos de una serie de parámetros de los cuales debemos encontrar su valor.

En una SVM, la orientación del hiperplano viene definida por el vector ⃗w. Hay un offset b que debemos encontrar. Para hacer la condición de optimización más simple, cambiamos las clases 0 y 1, por -1 y +1.

Matemáticamente queremos encontrar ⃗w y b, tal que la cantidad ½ || ⃗w||² sea tan pequeña como sea posible, dado que y_i( ⃗w· ⃗x - b) ≥ 1, para todas las etiquetas y_i y los vectores x_i del dataset.
Este tipo de problemas de optimización se resuelven a través de una técnica denominada “programación cuadrática” quadratic programming. De nuevo, no nos vamos a parar en las matemáticas, que incluyen la resolución de un Lagrangiano. No nos vamos a meter en el fango, no es lo nuestro.

La formulación anterior sirve para el caso en que tengamos sólo 2 clases que puedan ser separadas por un hiperplano, y no siempre nos encontraremos en este caso. La forma completa del problema de optimización incluye un fudge factor C que afecta al tamaño del margen encontrado.

El factor C no se averigua en el entrenamiento, si no que depende del problema y se le debe de asignar un valor para poder entrenar el modelo (por ejemplo con sklearn). Este tipo de parámetros, como C o k para k-NN, son denominados “hiperparámetros”.

Hay un concepto matemático más que debemos presentar. La descripción anterior es para una SVM lineal y usa los datos de entrenamiento directamente.

En caso de que la SVM sea no lineal (es decir, los datos están mezclados y no se puede hacer mediante un hiperplano “recto”), usamos el “truco” del kernel. En este caso, los datos de entrenamiento se transforman a a otro espacio a través de una función Φ(⃗x), que produce una nueva versión del vector de datos de entrenamiento. Siendo ⃗x los datos de entrenamiento clasificados '0', y ⃗z los datos de entrenamiento clasificados '1', el algoritmo SVM podría separar estos datos de forma lineal (hiperplano “recto”) a través de la expresión: ⃗x^T ⃗z, es decir: Φ(⃗x)^TΦ(⃗z).

Esta expresión se denomina kernel (lineal) y se escribe:

Hay varios tipos de kernel, en función de la complejidad de la clasificación de los datos. Como por ejemplo el polinomial, que podemos decir “malamente” que en lugar de tener un hiperplano “recto”, este va presentando “curvas” para adecuarse a la clasificación.
Un kernel muy común es el Gaussian kernel, también conocido como Radial Basis Function (RBF) kernel, que introduce un nuevo parámetro γ, que según aumenta su valor, aumentan las “curvaturas” del hiperplano.

En resumen, una máquina de vectores de soporte utiliza los datos de entrenamiento transformados, a través de una función kernel, para optimizar la orientación y la ubicación de un hiperplano que produce el margen máximo entre el hiperplano y los vectores de soporte de los datos de entrenamiento. El usuario debe seleccionar la función del kernel y los parámetros asociados como C e γ para que el modelo se ajuste mejor a los datos de entrenamiento.

Las SVM dominaron el aprendizaje automático en la década de 1990 y principios de la de 2000, antes de la llegada del aprendizaje profundo. Esto se debe a su eficiencia y a que no necesitan grandes recursos computacionales.
Después llegó el aprendizaje profundo, que con las redes neuronales han conseguido hacer cosas que con las SVM hubiera sido imposibles.
Aún así, las SVM tienen aplicaciones en la actualidad. Es común usar una gran red neuronal entrenada con un dataset concreto, como preprocesador para un dataset diferente, con una SVM entrenada a la salida de la red neuronal (menos las capas superiores).