1 Wb2wn0u7hmx7bdjtt0yza.png

Viene con una descripción detallada gratuita sobre SVM

En esta historia, implementaremos el algoritmo de aprendizaje automático de vectores de soporte en su forma general de margen suave y kernelizada. Comenzaremos brindando una breve descripción general de SVM y sus ecuaciones de entrenamiento e inferencia, y luego las traduciremos a código para desarrollar el modelo SVM. Luego, ampliamos nuestra implementación para manejar escenarios multiclase y concluimos probando nuestro modelo usando Sci-kit Learn.

Así, al final de esta historia:

  • Obtendrá una perspectiva clara de varios conceptos importantes de SVM.
  • Podrá implementar, con verdadera comprensión, el modelo SVM desde cero para los casos binarios y multiclase.
Noche estrellada de Van Gogh con un eje de simetría y estrellas: generada por el autor usando DALLE 2

Tabla de contenidos

· Breve descripción
SVM de margen duro
SVM de margen suave
SVM de margen suave del kernel
· Implementación
Importaciones Básicas
Definición de kernels e hiperparámetros SVM
Definir el método de predicción
Definir el método de predicción
Probar la implementación
Generalización del ajuste a multiclase
Generalización de predicción a multiclase
Probar la implementación

SVM de margen duro

El objetivo en SVM es ajustar el hiperplano que alcanzaría el margen máximo (distancia desde los puntos más cercanos en las dos clases). Se puede demostrar, y es intuitivo, que dicho hiperplano (A) tiene mejores propiedades de generalización y es más robusto al ruido que un hiperplano que no maximiza el margen (B).

Figura por Ennepetaler86 en Wikimedia. CC BY-SA 3.0 no adaptado.

Para lograr esto, SVM encuentra el hiperplano. W. y b resolviendo el siguiente problema de optimización:

Se intenta encontrar Wb que maximiza la distancia al punto más cercano y clasifica todo correctamente (como en la restricción donde y toma ±1). Se puede demostrar que esto es equivalente al siguiente problema de optimización:

Para lo cual se puede escribir el equivalente doble problema de optimizacion

La solución a esto produce un multiplicador de Lagrange para cada punto del conjunto de datos que suponemos tiene tamaño. metro: (αα₂, …, α_N). La función objetivo es claramente cuadrática en α y las restricciones son lineales, lo que significa que esto se puede resolver fácilmente con programación cuadrática. Una vez encontrada la solución, se deduce de la derivación del dual que:

(xₛ,yₛ) es cualquier punto con α>0

Observe que sólo los puntos con α>0 definir el hiperplano (contribuir a la suma). Estos se llaman vectores de soporte.

Y por lo tanto, la ecuación de predicción, que cuando se le da un nuevo ejemplo X, devuelve su predicción y=±1 es:

Implica conectar y luego hacer alguna simplificación algebraica.

Esta forma básica de SVM se llama SVM de margen duro porque el problema de optimización que resuelve (como se definió anteriormente) exige que todos los puntos del entrenamiento se clasifiquen correctamente. En escenarios prácticos, puede haber algún ruido que impida o limite la existencia de un hiperplano que separe perfectamente los datos, en cuyo caso el problema de optimización arrojaría una solución nula o deficiente.

SVM de margen suave

Ajustar por margen suave SVM por Mangat et al. en Puerta de la investigación. CC BY-SA 4.0 Internacional

Para generalizar el SVM de margen duro, el SVM de margen suave adapta el problema de optimización introduciendo una constante C (hiperparámetro dado por el usuario) que controla qué tan «duro» debe ser. En particular, modifica el problema de optimización primal para que quede como sigue:

modificaciones en azul

lo que permite que cada punto cometa alguna violación ϵₙ (por ejemplo, estar en el lado equivocado del hiperplano) pero aún apunta a reducirlos en general ponderando su suma en la función objetivo por C. Se vuelve equivalente a un margen estricto cuando C se acerca al infinito ( generalmente antes de que lo haga). Mientras tanto, una C más pequeña permitiría más violaciones (a cambio de un margen más amplio; es decir, menores wᵗw).

Sorprendentemente, se puede demostrar que el problema dual equivalente sólo cambia al restringir α para que cada punto sea ≤C.

Dado que se permiten violaciones, los vectores de soporte (puntos con α>0) ya no están todos al borde del margen. Se puede demostrar que cualquier vector de soporte que haya cometido una violación tendrá α=C y que los vectores sin soporte (α=0) no puede cometer violaciones. Llamamos vectores de apoyo que potencialmente cometieron violaciones (α=C) “vectores de soporte sin margen” y otros puros (que no han cometido violaciones; se encuentran en el borde) “vectores de soporte de margen” (0<α).

Se puede demostrar que la ecuación de inferencia no cambia:

Sin embargo, ahora (xₛ,yₛ) ahora debe ser un vector de soporte que no haya cometido violaciones porque la ecuación supone que está en el borde del margen (anteriormente, se podía usar cualquier vector de soporte).

SVM de margen suave del kernel

Soft Margin SVM extiende el Hard Margin SVM para manejar el ruido, pero frecuentemente, los datos no son separables por un hiperplano debido a factores más allá del ruido, como ser naturalmente no lineales. Soft Margin SVM se puede utilizar en casos como estos, pero entonces la solución óptima probablemente implicará un hiperplano que permita muchos más errores de los que es tolerable en la realidad.

Figura por Aprendizaje automático en Wikimedia. CC BY-SA 4.0 Internacional

Kernel Soft Margin SVM generaliza Soft Margin SVM para abordar situaciones en las que los datos son naturalmente no lineales. Por ejemplo, en el ejemplo que se muestra a la izquierda no hay ningún hiperplano lineal que Soft Margin SVM pueda encontrar, independientemente de la configuración de C, que separaría decentemente los datos.

Sin embargo, es posible mapear cada punto. X en el conjunto de datos a una dimensión superior a través de alguna función de transformación z=Φ(x) para hacer que los datos sean más lineales (o perfectamente lineales) en el nuevo espacio de dimensiones superiores. Esto equivale a reemplazar X con z en el dual para obtener:

En realidad, especialmente cuando Φ se transforma en un espacio de muy altas dimensiones, computando z puede llevar mucho tiempo. Esto se resuelve con el truco del kernel que reemplaza el zz con un equivalente cálculo de una función matemática (llamada función kernel) y que es mucho más rápida (por ejemplo, una simplificación algebraica de zz). Por ejemplo, aquí hay algunas funciones populares del kernel (cada una de las cuales corresponde a alguna transformación). Φ a un espacio dimensional superior):

El grado del polinomio (Q) y RBF γ son hiperparámetros (decididos por el usuario)

Con esto, el problema de optimización dual queda:

e intuitivamente, la ecuación de inferencia se convierte (después de manipulación algebraica):

Una derivación completa de todas las ecuaciones anteriores suponiendo que tienes la antecedentes matemáticos puede ser encontrado aquí.

Foto por Scott Graham en desempaquetar

Para la implementación usaremos

Importaciones Básicas

Comenzamos importando algunas bibliotecas básicas:

import numpy as np                  # for basic operations over arrays
from scipy.spatial import distance # to compute the Gaussian kernel
import cvxopt # to solve the dual opt. problem
import copy # to copy numpy arrays

Definición de kernels e hiperparámetros SVM

Comenzamos definiendo los tres núcleos usando sus respectivas funciones.

El grado del polinomio (Q) y RBF γ son hiperparámetros (decididos por el usuario)
class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ.T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ, γ=10: np.exp(-γ*distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}

Para mantener la coherencia con otros núcleos, el núcleo lineal requiere un hiperparámetro adicional inútil. Como es obvio, kernel_funs toma una cadena para el kernel y devuelve la función del kernel correspondiente.

Ahora sigamos definiendo el constructor:

class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ.T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ, γ=10: np.exp(-γ*distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}

def __init__(self, kernel='rbf', C=1, k=2):
# set the hyperparameters
self.kernel_str = kernel
self.kernel = SVM.kernel_funs[kernel]
self.C = C # regularization parameter
self.k = k # kernel parameter

# training data and support vectors (set later)
self.X, y = None, None
self.αs = None

# for multi-class classification (set later)
self.multiclass = False
self.clfs = []

El SVM tiene tres hiperparámetros principales, el kernel (almacenamos la cadena dada y la función del kernel correspondiente), el parámetro de regularización C y el hiperparámetro del kernel (que se pasará a la función del kernel); representa Q para el núcleo polinómico y γ para el núcleo RBF.

Definir el método de ajuste

Para ampliar esta clase con fit y predict funciones en celdas separadas, definiremos la siguiente función y la usaremos como decorador más adelante:

SVMClass = lambda func: setattr(SVM, func.__name__, func) or func

Recuerde que ajustar el SVM corresponde a encontrar el vector de soporte. α para cada punto resolviendo el problema de optimización dual:

Dejar α ser un vector de columna variable α₂ … α_N)ᵗ y sea y un vector de columna constante para las etiquetas (y y₂ … y_N)ᵗ y deja k ser una matriz constante donde k[n,m] calcula el kernel en (xₙ, xₘ). Recuerde las siguientes equivalencias basadas en índices para el producto escalar, el producto exterior y la forma cuadrática, respectivamente:

poder escribir el problema de optimización dual en forma matricial de la siguiente manera:

Sabiendo que este es un programa cuadrático como insinuamos anteriormente, podemos leer Programación cuadrática en la documentación de CVXOPT:

De CVXOPT Documentación. Licencia pública general GNU

Los corchetes te indican que puedes llamar a esto con (Pq) solo o (P,q,G,h) o (P, q, G, h, A, b) y así sucesivamente (todo lo que no se proporcione se establecerá con un valor predeterminado como 1).

Para conocer los valores de (P, q, G, h, A, b) En nuestro caso, hacemos la siguiente comparación:

Hagamos la comparación más fácil reescribiendo el primero de la siguiente manera:

Observe que cambiamos el máximo a mínimo multiplicando la función por -1

Ahora es obvio que (tenga en cuenta que 0≤α es equivalente a -α≤0):

Con esto, podemos escribir la siguiente función de ajuste:

@SVMClass
def fit(self, X, y, eval_train=False):
# if more than two unique labels, call the multiclass version
if len(np.unique(y)) > 2:
self.multiclass = True
return self.multi_fit(X, y, eval_train)

# if labels given in {0,1} change it to {-1,1}
if set(np.unique(y)) == {0, 1}: y[y == 0] = -1

# ensure y is a Nx1 column vector (needed by CVXOPT)
self.y = y.reshape(-1, 1).astype(np.double) # Has to be a column vector
self.X = X
N = X.shape[0] # Number of points

# compute the kernel over all possible pairs of (x, x') in the data
# by Numpy's vectorization this yields the matrix K
self.K = self.kernel(X, X, self.k)

### Set up optimization parameters
# For 1/2 x^T P x + q^T x
P = cvxopt.matrix(self.y @ self.y.T * self.K)
q = cvxopt.matrix(-np.ones((N, 1)))

# For Ax = b
A = cvxopt.matrix(self.y.T)
b = cvxopt.matrix(np.zeros(1))

# For Gx <= h
G = cvxopt.matrix(np.vstack((-np.identity(N),
np.identity(N))))
h = cvxopt.matrix(np.vstack((np.zeros((N,1)),
np.ones((N,1)) * self.C)))

# Solve
cvxopt.solvers.options['show_progress'] = False
sol = cvxopt.solvers.qp(P, q, G, h, A, b)
self.αs = np.array(sol["x"]) # our solution

# a Boolean array that flags points which are support vectors
self.is_sv = ((self.αs-1e-3 > 0)&(self.αs <= self.C)).squeeze()
# an index of some margin support vector
self.margin_sv = np.argmax((0 < self.αs-1e-3)&(self.αs < self.C-1e-3))

if eval_train:
print(f"Finished training with accuracy{self.evaluate(X, y)}")

Nos aseguramos de que se trata de un problema binario y que las etiquetas binarias estén configuradas como lo supone SVM (±1) y que y es un vector columna con dimensiones (norte,1). Luego resolvemos el problema de optimización para encontrar α₂ … α_N)ᵗ.

Usamos α₂ … α_N)ᵗ para obtener una matriz de banderas que sea 1 en cualquier índice correspondiente a un vector de soporte para que luego podamos aplicar la ecuación de predicción sumando solo los vectores de soporte y un índice para un vector de soporte de margen para (xₛ,yₛ). Tenga en cuenta que en las comprobaciones asumimos que los vectores que no son de soporte pueden no tener a=0 exactamente, si es α≤1e-3 entonces esto es aproximadamente cero (sabemos que los resultados de CVXOPT pueden no ser, en última instancia, precisos). Del mismo modo, suponemos que los vectores de soporte sin margen pueden no tener α=C exactamente.

Definir el método de predicción

Recuerde que la ecuación de predicción es:

@SVMClass
def predict(self, X_t):
if self.multiclass: return self.multi_predict(X_t)
# compute (xₛ, yₛ)
xₛ, yₛ = self.X[self.margin_sv, np.newaxis], self.y[self.margin_sv]
# find support vectors
αs, y, X= self.αs[self.is_sv], self.y[self.is_sv], self.X[self.is_sv]
# compute the second term
b = yₛ - np.sum(αs * y * self.kernel(X, xₛ, self.k), axis=0)
# compute the score
score = np.sum(αs * y * self.kernel(X, X_t, self.k), axis=0) + b
return np.sign(score).astype(int), score

Eso es todo. También podemos implementar un evaluate método para calcular la precisión (usado en el ajuste anterior).

@SVMClass
def evaluate(self, X,y):
outputs, _ = self.predict(X)
accuracy = np.sum(outputs == y) / len(y)
return round(accuracy, 2)

Probar la implementación

from sklearn.datasets import make_classification
import numpy as np

# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=2500, n_features=5,
n_redundant=0, n_informative=5,
n_classes=2, class_sep=0.3)

# Test Implemented SVM
svm = SVM(kernel='rbf', k=1)
svm.fit(X, y, eval_train=True)

y_pred, _ = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape[0]}") #0.9108

# Test with Scikit
from sklearn.svm import SVC
clf = SVC(kernel='rbf', C=1, gamma=1)
clf.fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape[0]}") #0.9108

Puede cambiar el conjunto de datos y el hiperparámetro para asegurarse aún más de que sean iguales. Lo ideal sería hacerlo comparando funciones de decisión en lugar de precisión.

Generalización del ajuste a multiclase

@SVMClass
def multi_fit(self, X, y, eval_train=False):
self.k = len(np.unique(y)) # number of classes
# for each pair of classes
for i in range(self.k):
# get the data for the pair
Xs, Ys = X, copy.copy(y)
# change the labels to -1 and 1
Ys[Ys!=i], Ys[Ys==i] = -1, +1
# fit the classifier
clf = SVM(kernel=self.kernel_str, C=self.C, k=self.k)
clf.fit(Xs, Ys)
# save the classifier
self.clfs.append(clf)
if eval_train:
print(f"Finished training with accuracy {self.evaluate(X, y)}")

Para generalizar el modelo a multiclase, más k clases. Entrenamos un clasificador SVM binario para cada clase presente donde hacemos un bucle en cada clase y volvemos a etiquetar los puntos que le pertenecen en +1 y los puntos de todas las demás clases en -1.

El resultado del entrenamiento es k clasificadores cuando se dan k clases donde el con El clasificador fue entrenado en los datos con el con la clase está etiquetada como +1 y todas las demás están etiquetadas como -1.

Generalización de predicción a multiclase

Luego, para realizar la predicción en un nuevo ejemplo, elegimos la clase para la cual el clasificador correspondiente tiene más confianza (tiene la puntuación más alta)

@SVMClass
def multi_predict(self, X):
# get the predictions from all classifiers
N = X.shape[0]
preds = np.zeros((N, self.k))
for i, clf in enumerate(self.clfs):
_, preds[:, i] = clf.predict(X)

# get the argmax and the corresponding score
return np.argmax(preds, axis=1), np.max(preds, axis=1)

Probar la implementación

from sklearn.datasets import make_classification
import numpy as np

# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=500, n_features=2,
n_redundant=0, n_informative=2,
n_classes=4, n_clusters_per_class=1,
class_sep=0.3)

# Test SVM
svm = SVM(kernel='rbf', k=4)
svm.fit(X, y, eval_train=True)

y_pred = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape[0]}") # 0.65

# Test with Scikit
from sklearn.multiclass import OneVsRestClassifier
from sklearn.svm import SVC

clf = OneVsRestClassifier(SVC(kernel='rbf', C=1, gamma=4)).fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape[0]}") # 0.65

Trazar las regiones de decisión para cada uno de ellos conduce al siguiente gráfico:

Figura del autor

Tenga en cuenta que, aunque SVM de Sci-kit Learn admite OVR de forma predeterminada (sin una llamada explícita como se muestra arriba), potencialmente también tiene optimizaciones adicionales específicas para SVM.

Código completo


import numpy as np # for basic operations over arrays
from scipy.spatial import distance # to compute the Gaussian kernel
import cvxopt # to solve the dual optimization problem
import copy # to copy numpy arrays

class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ .T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ , γ=10: np.exp(-γ * distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}

def __init__(self, kernel='rbf', C=1, k=2):
# set the hyperparameters
self.kernel_str = kernel
self.kernel = SVM.kernel_funs[kernel]
self.C = C # regularization parameter
self.k = k # kernel parameter

# training data and support vectors
self.X, y = None, None
self.αs = None

# for multi-class classification
self.multiclass = False
self.clfs = []

# This is useless here (only for notebook)
SVMClass = lambda func: setattr(SVM, func.__name__, func) or func

@SVMClass
def fit(self, X, y, eval_train=False):
if len(np.unique(y)) > 2:
self.multiclass = True
return self.multi_fit(X, y, eval_train)

# relabel if needed
if set(np.unique(y)) == {0, 1}: y[y == 0] = -1
# ensure y has dimensions Nx1
self.y = y.reshape(-1, 1).astype(np.double) # Has to be a column vector
self.X = X
N = X.shape[0]

# compute the kernel over all possible pairs of (x, x') in the data
self.K = self.kernel(X, X, self.k)

# For 1/2 x^T P x + q^T x
P = cvxopt.matrix(self.y @ self.y.T * self.K)
q = cvxopt.matrix(-np.ones((N, 1)))

# For Ax = b
A = cvxopt.matrix(self.y.T)
b = cvxopt.matrix(np.zeros(1))

# For Gx <= h
G = cvxopt.matrix(np.vstack((-np.identity(N),
np.identity(N))))
h = cvxopt.matrix(np.vstack((np.zeros((N,1)),
np.ones((N,1)) * self.C)))

# Solve
cvxopt.solvers.options['show_progress'] = False
sol = cvxopt.solvers.qp(P, q, G, h, A, b)
self.αs = np.array(sol["x"])

# Maps into support vectors
self.is_sv = ((self.αs > 1e-3) & (self.αs <= self.C)).squeeze()
self.margin_sv = np.argmax((1e-3 < self.αs) & (self.αs < self.C - 1e-3))

if eval_train:
print(f"Finished training with accuracy {self.evaluate(X, y)}")

@SVMClass
def multi_fit(self, X, y, eval_train=False):
self.k = len(np.unique(y)) # number of classes
# for each pair of classes
for i in range(self.k):
# get the data for the pair
Xs, Ys = X, copy.copy(y)
# change the labels to -1 and 1
Ys[Ys!=i], Ys[Ys==i] = -1, +1
# fit the classifier
clf = SVM(kernel=self.kernel_str, C=self.C, k=self.k)
clf.fit(Xs, Ys)
# save the classifier
self.clfs.append(clf)
if eval_train:
print(f"Finished training with accuracy {self.evaluate(X, y)}")

@SVMClass
def predict(self, X_t):
if self.multiclass: return self.multi_predict(X_t)
xₛ, yₛ = self.X[self.margin_sv, np.newaxis], self.y[self.margin_sv]
αs, y, X= self.αs[self.is_sv], self.y[self.is_sv], self.X[self.is_sv]

b = yₛ - np.sum(αs * y * self.kernel(X, xₛ, self.k), axis=0)
score = np.sum(αs * y * self.kernel(X, X_t, self.k), axis=0) + b
return np.sign(score).astype(int), score

@SVMClass
def multi_predict(self, X):
# get the predictions from all classifiers
preds = np.zeros((X.shape[0], self.k))
for i, clf in enumerate(self.clfs):
_, preds[:, i] = clf.predict(X)

# get the argmax and the corresponding score
return np.argmax(preds, axis=1)

@SVMClass
def evaluate(self, X,y):
outputs, _ = self.predict(X)
accuracy = np.sum(outputs == y) / len(y)
return round(accuracy, 2)

from sklearn.datasets import make_classification
import numpy as np

# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=500, n_features=2,
n_redundant=0, n_informative=2, n_classes=4,
n_clusters_per_class=1, class_sep=0.3)

# Test SVM
svm = SVM(kernel='rbf', k=4)
svm.fit(X, y, eval_train=True)

y_pred = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape[0]}")

# Test with Scikit
from sklearn.multiclass import OneVsRestClassifier
from sklearn.svm import SVC

clf = OneVsRestClassifier(SVC(kernel='rbf', C=1, gamma=4)).fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape[0]}")

Foto por Nathan van Egmond en desempaquetar

En resumen, implementamos el algoritmo de aprendizaje de la máquina de vectores de soporte (SVM), cubriendo su forma general de margen suave y kernelizada. Proporcionamos una descripción general de SVM, desarrollamos el modelo en código, lo ampliamos para escenarios multiclase y validamos nuestra implementación utilizando Sci-kit Learn.

Espero que lo que has aprendido de esta historia te resulte útil para tu trabajo. Hasta la próxima, hasta la próxima.

Recursos:

El código es en su mayoría adaptaciones del presente aquí (Licencia MIT):
Persson, Aladino. “SVM desde cero: aprendizaje automático Python (máquina vectorial de soporte)).” YouTube.