Maquinas de Soporte Vectorial

Óscar Belmonte Fernández

Introducción

Las máquinas de soporte vectorial (Support Vector Machines) son un modelo muy potente para tareas de clasificación.

La idea base es encontrar un hiperplano de separación entre dos clases con margen máximo.

La potencia de esta aproximación aumenta gracias a la introducción de lo que se conoce como el truco del kernel que consiste en utilizar un espacio de representación con más dimensiones que el número de características que inicialmente tiene el conjunto de datos.

Objetivos de aprendizaje

  • Resumir cuál es la estrategia del algoritmo SVM.
  • Interpretar en qué consiste el truco del kernel.
  • Decidir cuándo puede ser útil el algoritmo SVM para tareas de clasificación.
  • Plantear una solución basada en SVM.

Referencias

  • Hands-on Machine Learning. Capítulo 5.
  • Pattern recognition and Machine Learning. Capítulos 6 y 7.

Objetivo de las Máquinas de Soporte Vectorial

Objetivo

El objetivo de las Máquinas de Soporte Vectorial es crear un modelo de clasificación que dada una muestra me prediga a cuál de entre dos clases pertenece.

Clasificación binaria.

Hiperplano de separación entre dos clases

Vamos a empezar con un conjunto de datos sencillo, en dos dimensiones, y separable mediante una recta (un hiperplano en dos dimensiones)

Hiperplano de separación entre dos clases

¿Cuál es la mejor recta que separa las muestras dejando a un lado las positivas y al otro las negativas? En principio, tenemos muchas opciones.

Hiperplano de separación entre dos clases

Vamos a definir como mejor solución aquella línea que deja un mayor margen entre los dos conjuntos de datos.

Hiperplano de separación entre dos clases

Ya tenemos definido nuestro objetivo, encontrar el hiperplano de separación que deja el mayor margen entre las muestras de los dos conjuntos de datos.

Construir la solución

Ecuación de la recta

Los puntos de la recta que estamos buscando cumplen la siguiente ecuación:

\[ y(x) = \theta^T x + \theta_0 = 0 \]

Cuidado

\(\theta\) no es el vector director de la recta, de hecho es un vector perpendicular a la recta (Demostración).

Ecuación de la recta

Los puntos de la recta que estamos buscando cumplen la siguiente ecuación:

\[ y(x) = \theta^T x + \theta_0 = 0 \]

Cuidado

\(\theta_0\) no es el punto de corte con el eje de ordenadas.

Ecuación de la recta

Sí que es interesante que veamos cómo calcular la distancia de la recta al origen, que viene dada por la siguiente expresión (Demostración):

\[ d = \frac{\theta^T x}{\|\theta\|} = \frac{-\theta_0}{\| \theta \|} \]

Dónde \(x\) es cualquier punto que pertenezca a la recta.

Importante

Si multiplicamos el vector \(\theta\) y el escalar \(\theta_0\) por la misma constante:

  • La dirección del vector director no cambia.
  • La distancia de la recta al origen tampoco cambia.

Criterio de clasificación

El siguiente paso es establecer un criterio para decidir si una muestra la clasificamos como positiva o negativa.

Criterio de clasificación

La primera idea brillante es, ya que podemos ajustar \(\theta\) y \(\theta_0\) con una constante y seguir teniendo la misma recta, lo vamos a hacer de tal modo que:

Las muestras positivas cumplan:

\[ y(x_{+}) = \theta^T x_+ + \theta_0 \ge 1 \]

Y las negativas:

\[ y(x_{-}) = \theta^T x_- + \theta_0 \le -1 \]

Criterio de clasificación

Vamos intentar condensar ambas expresiones en una única expresión, para ello definimos:

\[ t_n = +1 \: si \: x_n: positiva \\ t_n = -1 \: si \: x_n: negativa \]

Ahora podemos escribir:

\[ t_n(y(x_n)) = t_n(\theta^T x_n + \theta_0) \ge 1 \\ \]

Criterio de clasificación

O lo que es lo mismo:

\[ \boxed{t_n(\theta^T x_n + \theta_0) - 1 \ge 0} \]

Donde la igualdad se cumple justo para los puntos que están en las líneas de margen.

Anchura del margen

La anchura del margen \(a\) es (Demostración):

\[ a = \frac{\theta^T}{\| \theta \|} (v_+ - v_-) = \frac{1}{\| \theta \|} (\theta^T v_+ - \theta^T v_-) \]

\[ t_n(\theta^T x_n + \theta_0) - 1 = 0 \]

\[ v_+ \rightarrow 1(\theta^T v_+ + \theta_0) - 1 = 0 \\ \theta^T v_+ = 1 - \theta_0 \\ v_- \rightarrow -1(\theta^T v_- + \theta_0) - 1 = 0 \\ \theta^T v_- = -1 - \theta_0 \]

Anchura del margen

Finalmente:

\[ a = \frac{1}{\| \theta \|} [1 - \theta_0 - (-\theta_0 - 1)] = \frac{2}{\| \theta \|} \]

Problema de optimización

Resumiendo, la anchura que debemos maximizar es:

\[ a = \frac{2}{\| \theta \|} \]

Pero es más interesante minimizar su inversa al cuadrado:

\[ h = \frac{1}{2} \| \theta \|^2 \]

Con las restricciones (una por cada elemento del conjunto):

\[ t_n(\theta^T x_n + \theta_0) - 1 \ge 0 \]

Que es un problema de optimización.

Problema de optimización

Para solucionarlo vamos a hacer uso de los multiplicadores de Lagrange (Ver Apéndice E de libro de Bishop) lo que implica definir la siguiente Lagrangiana (Ejemplo):

\[ L(\theta, \theta_0, \alpha_n) = \frac{1}{2} \| \theta \|^2 - \sum_{n=1}^N \alpha_n [t_n(\theta^T x_n + \theta_0) - 1] \]

Con todos los parámetros de Lagrange \(\alpha_n \ge 0\).

Fíjate en que la Lagrangiana depende de \((\theta, \theta_0, \alpha_n)\), y lo que conocemos son las \(x_n\) y \(t_n\). Es un problema de optimización difícil de resolver.

Problema de optimización

\[ L(\theta, \theta_0, \alpha_n) = \frac{1}{2} \| \theta \|^2 - \sum_{n=1}^N \alpha_n [t_n(\theta^T x_n + \theta_0) - 1] \]

Nota

Los signos en la Lagrangiana son opuestos porque estamos maximizando la primera expresión, pero minimizando la segunda.

Problema de optimización

El siguiente paso es encontrar los extremos de la Lagrangiana con respecto de \(\theta\) y \(\theta_0\). Para ello, derivamos la Lagrangiana con respecto a ellos, igualamos a cero y despejamos:

\[ \frac{\partial L}{\partial \theta} = \theta - \sum_{n=1}^N \alpha_n t_n x_n = 0 \rightarrow \boxed{\theta = \sum_{n=1}^N \alpha_n t_n x_n} \\ \frac{\partial L}{\partial \theta_0} = - \sum_{n=1}^N \alpha_n t_n = 0 \rightarrow \boxed{\sum_{n=1}^N \alpha_n t_n = 0} \]

Parece que ya tenemos parte del problema solucionado, pero aún no del todo, porque no conocemos el valor de las \(\alpha_n\) y, de momento, no tenemos una expresión para calcular \(\theta_0\).

Problema de optimización

La segunda idea brillante es sustituir la expresión para \(\theta\) de la anterior expresión en la Lagrangiana, y hacer uso de la segunda expresión, con lo que la Lagrangina nos queda como (Demostrar):

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m x_n^T x_m + \sum_{n=1}^N \alpha_n \]

Problema de optimización

Si comparamos las dos expresiones:

\[ L(\theta, \theta_0, \alpha_n) = \frac{1}{2} \| \theta \|^2 - \sum_{n=1}^N \alpha_n [t_n(\theta^T x_n + \theta_0) - 1] \]

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m x_n^T x_m + \sum_{n=1}^N \alpha_n \]

La segunda tiene menos parámetros desconocidos. De hecho, la nueva expresión de la Lagrangiana es un problema cuadrático de minimización que siempre tiene solución numérica.

Problema de optimización

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m x_n^T x_m + \sum_{n=1}^N \alpha_n \]

Se puede demostrar que este problema de optimización añade una nueva restricción a las dos que ya tenemos, con lo que tenemos esta serie de restricciones:

\[ \alpha_n \ge 0 \\ t_n y(x_n) - 1 \ge 0 \\ \alpha_n [t_n y(x_n) - 1] = 0 \]

La última restricción es la clave.

Problema de optimización

\[ \alpha_n [t_n y(x_n) - 1] = 0 \]

Para que se cumpla esta condición tenemos dos opciones:

\[ \alpha_n = 0 \\ t_n y(x_n) - 1 = 0 \]

La primera opción nos dice que el vector \(x_n\) (dato de entrenamiento) no contribuye a la solución para obtener el valor de \(\theta\).

\[ \theta = \sum_{n=1}^N \alpha_n t_n x_n \]

Problema de optimización

La segunda opción:

\[ t_n y(x_n) - 1 = 0 \]

Nos dice que el vector \(x_n\) (dato de entrenamiento) está sobre la recta del margen, y sí contribuye a la solución de \(\theta\).

\(x_n\) es un vector de soporte!!!.

Con toda esta información, ahora sí, podemos calcular el valor de \(\theta_0\) que lo tenemos aún pendiente.

Problema de optimización

Sustituyendo en la expresión de la condición que el vector esté sobre la recta del margen:

\[ t_n (\theta^T x_n + \theta_0) = 1 \]

La expresión de \(\theta\) (sumatorio sólo se extiende sobre los vectores de soporte):

\[ \theta = \sum_{x_m \in S} \alpha_m t_m x_m \]

Problema de optimización

Tenemos:

\[ t_n \left[ \left( \sum_{x_m \in S} \alpha_m t_m x_m^T x_n \right) + \theta_0 \right] = 1 \]

Que se puede modificar para facilitar el trabajo de los algoritmos de optimización (Bishop, 2006).

Problema de optimización

Si la anterior expresión la multiplicamos por \(t_n\) y sumamos sobre todos los vectores de soporte, podemos despejar \(\theta_0\) (Demostración):

\[ \theta_0 = \frac{1}{N_S} \left[ \sum_{x_n \in S} \left( t_n - \sum_{x_m \in S} \alpha_m t_m x_m^T x_n \right) \right] \]

Que junto a:

\[ \theta = \sum_{x_m \in S} \alpha_m t_m x_m \]

Resuelve el problema de clasificación.

Problema de optimización

En la solución sólo están implicadas las \(x_n \in S\), que hemos encontrado resolviendo un problema de optimización cuadrático, las que hemos llamado vectores de soporte.

Cuando tenemos que clasificar una nueva muestra, aplicamos:

\[ y(x) = \theta^T x + \theta_0 \]

Si \(y(x) > 0\) la muestra la clasificamos como positiva.

Si \(y(x) <0\) la muestra la clasificamos como negativa.

El algoritmo de clasificación es muy rápido.

Resumen

Lo que buscamos es la recta (hiperplano) que separa las muestras y tiene mayor margen.

  1. Hemos partido de la ecuación de la recta.
  2. Hemos definido el criterio de clasificación de muestra positiva o negativa.
  3. Hemos construido la Lagrangiana \(\rightarrow\) problema de optimización.
  4. En la solución que encontramos sólo participan algunos de los datos dentro de todo el conjunto.

Resumen

Las máquinas de soporte vectorial funcionan muy bien cuando nuestro conjunto de entrenamiento contiene unos cuantos miles de muestras. Si tenemos muchas muestras, el entrenamiento puede ser lento.

Show me the code

Después de la teoría, veamos cómo utilizar la implementación de scikit-learn (¿Qué es eso del kernel?)

from sklearn import svm
from sklearn.inspection import DecisionBoundaryDisplay

clasificador = svm.SVC(kernel="linear")
clasificador.fit(X, y);
plt.scatter(X[:5,0], X[:5,1])
plt.scatter(X[5:,0], X[5:,1])
plt.legend(["positivas", "negativas"])

ax = plt.gca()
DecisionBoundaryDisplay.from_estimator(
    clasificador,
    X,
    plot_method = "contour",
    colors = "k",
    levels=[-1, 0, 1],
    alpha=0.5,
    linestyles=["--", "-", "--"],
    ax=ax
)

ax.scatter(
    clasificador.support_vectors_[:, 0],
    clasificador.support_vectors_[:, 1],
    s=100,
    linewidth=1,
    facecolors="none",
    edgecolors="k",
);

Show me the code

Sólo dos de las muestras son vectores de soporte.

Show me the code

scikit-learn proporciona una versión optimizada cuando el problema es linealmente separable:

clasificador = svm.LinearSVC()

Esta clase está optimizada para problemas lineales, pero no da tanta información sobre la solución como la clase más genérica SVC.

Escalado de los datos

SVM da mejores resultados si los datos están en la misma escala:

Escalado de los datos

Para ello, resulta muy útil utilizar alguna de las clases que proporciona scikit-learn como MinMaxScaler o StandardScaler

X = MinMaxScaler().fit_transform(X)

O mejor aún, definir un pipeline con la secuencia de pasos:

# Definimos la secuencia de pasos en el pipeline
pipeline = Pipeline([
    ("escalado", MinMaxScaler()),
    ("clasificador", svm.SVC(kernel="linear", C=1000)),
])

# Ajustamos a los datos
pipeline.fit(X, y)

# Hacemos predicciones
print(pipeline.predict([[10.0, 2]]))

Muestras solapadas

Muestras solapadas

Antes de pasar a ver qué es el kernel, vamos a analizar el caso en el que las muestras están solapadas, están en la región de la clase contraria.

Muestras solapadas

No vamos a entrar en el detalle de la demostración (Bishop 2006).

La cantidad (relacionado con la distancia) que esta vez debemos minimizar es:

\[ C \sum_{n=1}^N \xi_n+ \frac{1}{2} \| \theta \|^2 \]

  1. \(\xi_n = 1\) si \(x_n\) está sobre la recta.
  2. \(\xi_n = 0\) si \(x_n\) está sobre el margen o más allá.
  3. \(\xi_n < 1\) si el punto está entre el margen y la recta, lado correcto.
  4. \(\xi_n > 1\) si el punto está entre el margen y la recta, lado incorrecto.
  5. \(C\) es un parámetro de regularización.

Muestras solapadas

Esta vez en la solución tenemos vectores de soporte que pueden cumplir las condiciones 2, 3 ó 4.

Show me the code

clasificador = svm.SVC(kernel="linear", C=1000)
clasificador.fit(X, y);

En el código, el único cambio es que podemos especificar el valor de \(C\) que es un parámetro de regularización.

El truco del kernel

Problemas linealmente no separables

Observa el siguiente conjunto de datos:

Fíjate que cada muestra sólo tiene valor para una característica y la etiqueta de la clase.

Problemas linealmente no separables

Ahora, vamos a hacer un truco aumentando el número de características de cada muestra \((x) \rightarrow (x, x^2)\):

Problemas linealmente no separables

Ahora el problema sí que es linealmente separable:

Hemos ampliado el número de características en el conjunto de datos.

Problemas linealmente no separables

Vamos a ver un ejemplo más complejo:

Claramente no es linealmente separable.

Problemas linealmente no separables

Para cada punto \(p = (p_1,p_2)\) vamos a realizar la siguiente transformación:

\[ \phi: \mathbb{R^2} \rightarrow \mathbb{R^3} \\ (p_1, p_2) \rightarrow (p_1^2, p_2^2, \sqrt{2}p_1 p_2) \] Ahora sí que podemos separar las muestras con un hiperplano.

De nuevo la Lagrangiana

Por otro lado, esta es la lagrangiana que hemos minimizado:

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m x_n^T x_m + \sum_{n=1}^N \alpha_n \]

El punto importante es que aparecen términos del producto escalar de dos puntos del conjunto de entrenamiento \(x_n^T, x_m\), con:

\[ x_n, x_m \in \mathbb{R^D} \]

Donde \(D\) es la dimensión del espacio.

De nuevo la Lagrangiana

Quizás, la lagrangiana no se pueda minimizar en un espacio de dimensión \(D\), pero sí se puede minimizar en un espacio de dimensión superior:

\[ \phi: \mathbb{R^D} \rightarrow \mathbb{R^E} \\ x \in \mathbb{R^D} \rightarrow \phi(x) \in \mathbb{R^E} \]

Con \(E > D\).

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m \phi(x_n^T) \phi(x_m) + \sum_{n=1}^N \alpha_n \]

El truco del kernel

El punto importe es el producto de los vectores transformados:

\[ \phi(x_n^T) \phi(x_m) \]

Puede ocurrir que al transformar los vectores de partida lleguemos a un espacio con muchas más dimensiones que el original, y el producto de los vectores transformados sea impracticable (Ej: el kernel gaussiano transforma un vector de dimensión n a un espacio de infinitas dimensiones).

El truco del kernel

El truco consiste en elegir una transformación \(\phi(\cdot)\) de tal modo que cuando tenga que hacer el producto escalar \(\phi(x_n^T) \phi(x_m)\) no tenga que hacer las transformaciones \(\phi(\cdot)\) de cada vector porque sé como calcular ese producto sin tener que hacerlas.

Volvamos al ejemplo inicial:

\[ \phi: \mathbb{R^2} \rightarrow \mathbb{R^3} \\ x = (x_1, x_2) \rightarrow \phi(x) = (x_1^2, x_2^2, \sqrt{2}x_1 x_2) \\ x^{\prime} = (x_1^{\prime}, x_2^{\prime}) \rightarrow \phi(x^{\prime}) = (x_1^{\prime 2}, x_2^{\prime 2}, \sqrt{2}x_1^{\prime} x_2^{\prime}) \]

El truco del kernel

Multiplicamos escalarmente los vectores transformados:

\[ \phi(x) \phi(x^{\prime}) = (x_1^2, x_2^2, \sqrt{2}x_1 x_2) \cdot (x_1^{\prime 2}, x_2^{\prime 2}, \sqrt{2}x_1^{\prime} x_2^{\prime}) = \\ x_1^2 x_1^{\prime 2} + x_2^2 x_2^{\prime 2} + 2 x_1 x_1^{\prime} x_2 x_2^{\prime} = \\ [(x_1, x_2) \cdot (x_1^{\prime}, x_2^{\prime})]^2 = k(x, x^{\prime}) \]

El kernel \(k(x, x^{\prime})\) se calcula a partir de los vectores sin transformar, y el resultado es el mismo que el del producto escalar de los vectores transformados.

El truco del kernel

Luego:

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m \phi(x_n^T) \phi(x_m) + \sum_{n=1}^N \alpha_n \]

\[ L(\alpha_n) = -\frac{1}{2} \sum_{n=1}^N \sum_{m=1}^N \alpha_n \alpha_m t_n t_m k(x_n, x_m) + \sum_{n=1}^N \alpha_n \]

Lo complicado es encontrar los kernels.

El truco del kernel

La condición (fuerte) que debe cumplir el kernel es que debe ser igual al producto escalar de los vectores transformados.

Algunos kernels:

  • Lineal: \(k(x,x^{\prime}) = x^t x^{\prime}\)
  • Polinomial: \(k(x,x^{\prime}) = (\gamma x^t x^{\prime} + r)^d\)
  • Gaussiano: \(k(x,x^{\prime}) = exp(-\gamma \|x^t x^{\prime}\|^2\)
  • Sigmoide: \(k(x,x^{\prime}) = tanh(\gamma x^T x^{\prime} + r)\)

El truco del kernel

Resulta más sencillo construir nuevos kernels a partir de kernels conocidos usando las siguientes reglas:

  • \(k(x,x^{\prime}) = ck_1(x,x^{\prime})\)
  • \(k(x,x^{\prime}) = f(x)k_1(x,x^{\prime}) f(x^{\prime})\)
  • \(k(x,x^{\prime}) = k_1(x,x^{\prime}) + k_2(x,x^{\prime})\)
  • \(k(x,x^{\prime}) = k_1(x,x^{\prime}) k_2(x,x^{\prime})\)

Show me the code

Vamos a probar un kernel gaussiano:

El kernel gaussiano lleva el conjunto de datos a un espacio de dimensión infinita.

Show me the code

clasificador_no_lineal = svm.SVC(kernel="rbf", C=1000)
clasificador_no_lineal.fit(Xcir, ycir)

plt.scatter(Xcir[ycir==0][:,0], Xcir[ycir==0][:,1])
plt.scatter(Xcir[ycir==1][:,0], Xcir[ycir==1][:,1])
plt.legend(["positivas", "negativas"])
plt.xlim(-1.5, 1.5)
plt.ylim(-1.5, 1.5)
ax = plt.gca()
disp = DecisionBoundaryDisplay.from_estimator(
    clasificador_no_lineal,
    Xcir,
    plot_method = "contour",
    colors = "k",
    levels=[-1, 0, 1],
    alpha=0.5,
    linestyles=["--", "-", "--"],
    ax=ax
)

ax.scatter(
    clasificador_no_lineal.support_vectors_[:, 0],
    clasificador_no_lineal.support_vectors_[:, 1],
    s=100,
    linewidth=1,
    facecolors="none",
    edgecolors="k",
);

Creatividad

¿Se te ocurre alguna otra solución ad-hoc para solucionar el problema de clasificación de estos datos?

Aplicación

Aplicación a Howell

Vamos a aplicar SVM al caso de los datos de Howell. Vamos a utilizar, inicialmente un kernel lineal:

Aplicación a Howell

Ahora veamos los resultados con un kenel polinómico y otro gaussiano:

Aplicación a Howell

Veamos qué tal se comporta con los datos de prueba para el caso de un kernel lineal:

Precisión (accuracy):  0.8522727272727273

Aplicación a Howell

Veamos qué tal se comporta con los datos de prueba para el caso de un kernel polinómico:

Precisión (accuracy):  0.8409090909090909

Aplicación a Howell

Finalmente, veamos qué tal se comporta con los datos de prueba para el caso de un kernel gaussiano:

Precisión (accuracy):  0.8522727272727273

Aplicación a Howell

Si comparamos con la regresión logística, vemos que los resultados obtenidos son muy parecidos.

Resumen

Resumen

  • Las Máquinas de Soporte Vectorial fueron desarrolladas para resolver problemas de clasificación binaria.
  • El objetivo es encontrar el hiperplano que separa las muestras de las dos clases, y que tiene el máximo margen entre ellas.
  • El problema de separación por un hiperplano se puede extender a otras fronteras de separación introduciendo el truco del kernel.

Resumen

  • Las SVM funcionan muy bien cuando el número de muestras en nuestro conjunto de datos de unos cuantos miles, más allá, el algoritmo de entrenamiento puede ser muy lenta.
  • La contrapartida es que la clasificación de nuevas muestras es muy rápida.

Aprendizaje Automático (IR2130) - Óscar Belmonte Fernández