En esta práctica vamos a implementar una versión simplificada del algoritmo SMO basada en estas notas. El algoritmo SMO original (Platt, 1998) utiliza una heurística algo compleja para seleccionar las alphas con respecto a las cuales optimizar. La versión que vamos a implementar simplifica el proceso de elección de las alphas, a costa de una convergencia más lenta. Una vez implementado, compararemos los resultados de nuestro algoritmo con los obtenidos usando a clase SVC del paquete sklearn.svm.
Finalmente, utilizaremos la implementación de sklearn para resolver problemas sencillos de clasificación en dos dimensiones y visualizar fácilmente la frontera de decisión y el margen.
Todo el código que tienes que desarrollar lo debes incluir en el fichero svm.py, en los lugares indicados.
La fecha tope para la entrega es el **21/12/2017 a las 23:59**. Se debe subir a la plataforma moodle un único fichero comprimido con el siguiente contenido:
Lo primero que vamos a hacer es implementar las funciones que calculan los kernels. En el fichero svm.py, completa el código de las funciones linear_kernel, poly_kernel y rbf_kernel. Luego ejecuta las celdas siguientes, que comparan los resultados de estas funciones con funciones equivalentes de sklearn.
In [1]:
# Imports
import numpy as np
import svm as svm
from sklearn.metrics.pairwise import polynomial_kernel
from sklearn.metrics.pairwise import rbf_kernel
In [2]:
# Datos de prueba:
n = 10
m = 8
d = 4
x = np.random.randn(n, d)
y = np.random.randn(m, d)
print (x.shape)
print (y.shape)
In [3]:
# Con tu implementación:
K = svm.linear_kernel(x, y)
print ("El array K deberia tener dimensiones: (%d, %d)" % (n, m))
print ("A ti te sale un array con dimensiones:", K.shape)
# Con la implementación de sklearn:
K_ = polynomial_kernel(x, y, degree=1, gamma=1, coef0=1)
# Diferencia entre tu kernel y el de sklearn (deberia salir practicamente 0):
maxdif = np.max(np.abs(K - K_))
print ("Maxima diferencia entre tu implementacion y la de sklearn:", maxdif)
In [4]:
# Con tu implementación:
K = svm.poly_kernel(x, y, deg=2, b=1)
print ("El array K deberia tener dimensiones: (%d, %d)" % (n, m))
print ("A ti te sale un array con dimensiones:", K.shape)
# Con la implementación de sklearn:
K_ = polynomial_kernel(x, y, degree=2, gamma=1, coef0=1)
# Diferencia entre tu kernel y el de sklearn (deberia salir practicamente 0):
maxdif = np.max(np.abs(K - K_))
print ("Maxima diferencia entre tu implementacion y la de sklearn:", maxdif)
In [5]:
s = 1.0
# Con tu implementación:
K = svm.rbf_kernel(x, y, sigma=s)
print ("El array K deberia tener dimensiones: (%d, %d)" % (n, m))
print ("A ti te sale un array con dimensiones:", K.shape)
# Con la implementación de sklearn:
K_ = rbf_kernel(x, y, gamma=1/(2*s**2))
# Diferencia entre tu kernel y el de sklearn (deberia salir practicamente 0):
maxdif = np.max(np.abs(K - K_))
print ("Maxima diferencia entre tu implementacion y la de sklearn:", maxdif)
In [6]:
# Datos de prueba (problema XOR):
x = np.array([[-1, -1], [1, 1], [1, -1], [-1, 1]])
y = np.array([1, 1, -1, -1])
# Alphas y b:
alpha = np.array([0.125, 0.125, 0.125, 0.125])
b = 0
# Clasificador, introducimos la solucion a mano:
svc = svm.SVM(C=1000, kernel="poly", sigma=1, deg=2, b=1)
svc.init_model(alpha, b, x, y)
# Clasificamos los puntos x:
y_ = svc.evaluate_model(x)
# Las predicciones deben ser exactamente iguales que las clases:
print ("Predicciones (deberian ser [1, 1, -1, -1]):", y_)
In [7]:
# Prueba con los datos del XOR:
x = np.array([[-1, -1], [1, 1], [1, -1], [-1, 1]])
y = np.array([1, 1, -1, -1])
# Clasificador que entrenamos para resolver el problema:
svc = svm.SVM(C=1000, kernel="poly", sigma=1, deg=2, b=1)
svc.simple_smo(x, y, maxiter = 100, verb=True)
# Imprimimos los alphas y el bias (deberian ser alpha_i = 0.125, b = 0):
print ("alpha =", svc.alpha)
print ("b =", svc.b)
# Clasificamos los puntos x (las predicciones deberian ser iguales a las clases reales):
y_ = svc.evaluate_model(x)
print ("Predicciones =", y_)
La siguiente prueba genera un problema al azar y lo resuelve con tu método y con sklearn. Ambas soluciones deberían ser parecidas, aunque la tuya será mucho más lenta. Prueba con los diferentes tipos de kernels para comprobar tu implementación.
In [9]:
# Prueba con otros problemas y comparacion con sklearn:
from sklearn.svm import SVC
# Generacion de los datos:
n = 20
X = np.random.rand(n,2)
y = 2.0*(X[:,0] > X[:,1]) -1
# Uso de SVC:
clf = SVC(C=10.0, kernel='rbf', degree=2.0, coef0=1.0, gamma=0.5)
clf.fit(X, y)
print ("Resultados con sklearn:")
print (" -- Num. vectores de soporte =", clf.dual_coef_.shape[1])
print (" -- Bias b =", clf.intercept_[0])
# Uso de tu algoritmo:
svc = svm.SVM(C=10, kernel="rbf", sigma=1.0, deg=2.0, b=1.0)
svc.simple_smo(X, y, maxiter = 500, tol=1.e-15, verb=True, print_every=10)
print ("Resultados con tu algoritmo:")
print (" -- Num. vectores de soporte =", svc.num_sv)
print (" -- Bias b =", svc.b)
# Comparacion entre las alphas:
a1 = clf.dual_coef_
a2 = (svc.alpha * y)[svc.is_sv]
# Maxima diferencia entre tus alphas y las de sklearn:
maxdif = np.max(np.abs(np.sort(a1) - np.sort(a2)))
print ("Maxima diferencia entre tus alphas y las de sklearn:", maxdif)
Finalmente vamos a utilizar la implementación de sklearn para resolver problemas sencillos de clasificación en dos dimensiones. El objetivo es entender cómo funcionan los distintos tipos de kernel (polinómico y RBF) con problemas que se pueden visualizar fácilmente.
Para implementar los modelos utilizaremos la clase SVC del paquete sklearn.svm.
Primero importamos algunos módulos adicionales, establecemos el modo inline para las gráficas de matplotlib e inicializamos la semilla del generador de números aleatorios. El módulo p4_utils contiene funciones para generar datos en 2D y visualizar los modelos.
In [3]:
from p4_utils import *
import matplotlib.pyplot as plt
from sklearn.svm import SVC
%matplotlib inline
np.random.seed(19)
La siguiente celda realiza las siguientes acciones:
Crea un problema con dos conjuntos de datos (entrenamiento y test) de 50 puntos cada uno, y dos clases (+1 y -1). La frontera que separa las clases es lineal.
Entrena un clasificador SVC para separar las dos clases, con un kernel lineal.
Imprime los vectores de soporte, las alphas y el bias.
Obtiene la tasa de acierto en training y en test.
Y finalmente dibuja el modelo sobre los datos de entrenamiento y test. La línea negra es la frontera de separación, mientras que las líneas azul y roja representan los márgenes para las clases azul y roja respectivamente. Sobre la gráfica de entrenamiento muestra además los vectores de soporte.
In [11]:
# Creación del problema, datos de entrenamiento y test:
np.random.seed(300)
n = 50
model = 'rbf'
ymargin = -0.5
x, y = createDataSet(n, model, ymargin)
xtest, ytest = createDataSet(n, model, ymargin)
# Construcción del clasificador:
clf = SVC(C=100, kernel='rbf', degree=1.0, coef0=1.0, gamma=100)
clf.fit(x, y)
# Vectores de soporte:
print("Vectores de soporte: %d" % (len(clf.support_)))
for i in clf.support_:
print(" [%f, %f] c = %d" % (x[i,0], x[i,1], y[i]))
# Coeficientes a_i y b:
print("Coeficientes a_i:")
print (" ", clf.dual_coef_)
print("Coeficiente b:")
print (" ", clf.intercept_[0])
# Calculo del acierto en los conjuntos de entrenamiento y test:
score_train = clf.score(x, y)
print("Score train = %f" % (score_train))
score_test = clf.score(xtest, ytest)
print("Score test = %f" % (score_test))
# Gráficas:
plt.figure(figsize=(12,6))
plt.subplot(121)
plotModel(x[:,0],x[:,1],y,clf,"Training, score = %f" % (score_train))
for i in clf.support_:
if y[i] == -1:
plt.plot(x[i,0],x[i,1],'ro',ms=10)
else:
plt.plot(x[i,0],x[i,1],'bo',ms=10)
plt.subplot(122)
plotModel(xtest[:,0],xtest[:,1],ytest,clf,"Test, score = %f" % (score_test))
(1) Escribe la ecuación de la frontera de decisión para este problema como combinación lineal de las funciones de kernel sobre cada uno de los vectores de soporte. Ten en cuenta que los coeficientes $a_{i}$ son el producto de la clase del punto y su multiplicador de Lagrange correspondiente: $a_{i} = \alpha_{i} t_{i}$. Por este motivo encontramos valores negativos.<br><br> La expresión que se nos pide sería la siguiente:
$$\sum_{i = 0}^{n} a_i k(x_i, \vec{x}) + b $$(2) Con el conjunto de datos anterior, prueba a entrenar el clasificador con un parámetro C igual a 0.01. ¿Se siguen clasificando bien todos los patrones? ¿Qué ocurre con el margen? ¿Qué pasa si bajas aún más el valor de C hasta 0.001? ¿Qué pasa con el margen si aumentamos mucho el parámetro C? Razona tus respuestas.
Realizamos experimetos con los siguientes parámetros:
| C | Nº vec soporte | Training score | Test score |
|---|---|---|---|
| 0.00001 | 46 | 0.54 | 0.56 |
| 0.001 | 46 | 0.56 | 0.56 |
| 0.01 | 38 | 0.98 | 1.0 |
| 10 | 3 | 1.0 | 1.0 |
| 1000 | 3 | 1.0 | 1.0 |
Como se puede ver en la tabla, parámetros de C extremos (tanto mínimos como máximos) experimentan un límite en los resultados. A partir de C = 10 y hacía valores mayores, el nº de vectores se estabiliza a 3 dando porcentajes de acierto tanto en test como resultado del 100%. Además, observando los límites, vemos como el margen se estabiliza hasta el que parece ser su valor mínimo y optimo.
Por otro lado, en parámetros de C cada vez mas bajos, (0.001 o 0.0001) el número de vectores se dispara a 46, dando porcentajes de acierto cada vez peores hasta un 0.54 que pareciera ser su mínimo. El margen en este caso se hacía cada vez más amplio hasta estacionarse.
(3) Genera un nuevo conjunto de datos manteniendo el modelo lineal pero cambiando el parámetro ymargin a -0.5. Como ves ahora el problema ya no es linealmente separable. Prueba a resolverlo con el clasificador inicial (con C=10) y luego prueba otros valores de C. ¿Qué ocurre con valores altos de C? ¿Y con valores bajos? ¿Qué ocurre con los vectores de soporte?
Se han realizado los siguientes experimentos:
| C | Nº vec soporte | Training score | Test score |
|---|---|---|---|
| 0.00001 | 46 | 0.76 | 0.80 |
| 0.01 | 46 | 0.76 | 0.80 |
| 1 | 22 | 0.82 | 0.90 |
| 10 | 19 | 0.84 | 0.90 |
| 1000 | 19 | 0.84 | 0.90 |
AL igual que se han visto en el punto anterior, tanto como para valores altos como para valores bajos se alcanza un límite en el cual el número de vectores y las tasas de acierto se estacionan.
Las diferencias principales respecto al problema lineal son que, por un lado las tasas de acierto no son tan amplias (0.9 como máximo en test y 0.84 en training) debido a la complejidad de alcanzar solución y que los márgenes no están tan centrados respecto al punto de origen.
(4) Haz pruebas utilizando un kernel gausiano y variando los parámetros C y gamma. Comenta los resultados.
Se han realizado los siguientes experimentos:
| C | gamma | Nº vec soporte | Training score | Test score |
|---|---|---|---|---|
| 1 | 0.1 | 29 | 0.86 | 0.92 |
| 100 | 0.1 | 17 | 0.90 | 0.88 |
| 1000 | 0.1 | 19 | 0.92 | 0.92 |
| 1 | 0.01 | 42 | 0.80 | 0.82 |
| 100 | 0.01 | 17 | 0.84 | 0.92 |
| 1000 | 0.01 | 16 | 0.88 | 0.92 |
| 1000 | 1 | 19 | 0.96 | 0.86 |
| 1000 | 100 | 19 | 1.0 | 0.58 |
Como conclusión podemos desarrollar que al igual que en casos anteriores, el parámetro C influye siendo peor cuanto más bajo sea. Como dato interesante de estos resultados, ver como domina el parámetro sigma del kernel gaussiano. Según vemos, un valor gamma igual a 1 parece que ofrece la mejor solución. También vemos que si disparamos este valor, el algoritmo sufre de sobreaprendizaje dando una tasa del 100% en training pero una pobre tasa del 56% en test.