Machine Learning 101 — SVM (Support Vector Machines)
Las Support Vector Machines (SVM) son un algoritmo de aprendizaje supervisado utilizado para resolver problemas de clasificación y regresión. SVM funciona dividiendo el espacio de características en dos regiones: una región para cada clase en un problema de clasificación binaria o una región para la predicción de una variable continua en un problema de regresión. En este artículo, explicaremos cómo funciona el algoritmo SVM para machine learning.
Este algoritmo es bastante más desafiante que los anteriores en cuanto a la matemática y los conceptos involucrados.
El objetivo de SVM es encontrar el hiperplano que mejor separe las diferentes clases en el espacio de características. Un hiperplano es una frontera que separa los datos en dos regiones en función de sus características. En un problema de clasificación binaria, el hiperplano debe separar las dos clases, mientras que en un problema de regresión, el hiperplano debe predecir el valor de la variable continua en función de las características.
El algoritmo SVM encuentra el hiperplano óptimo al maximizar la distancia entre el hiperplano y los puntos de datos más cercanos a él. Estos puntos de datos más cercanos se llaman vectores de soporte, de ahí el nombre Support Vector Machines. La distancia entre el hiperplano y los vectores de soporte se llama margen(Lineas enteras de la imagen).
Nos ponemos matemáticos =(
Este hiperplano que mencionamos es aquel que tiene el mayor margen posible entre las dos clases, y se puede expresar matemáticamente mediante la siguiente ecuación:
w^T x + b = 0
Donde w es un vector normal al hiperplano, b es un término de sesgo (bias), x es un vector de características de una muestra de datos y ^T representa la transposición del vector w
En este punto tenemos muchos términos matemáticos que debemos tener incorporados para poder avanzar, te invito a que los repases.
Para encontrar el hiperplano óptimo(el de mayor margen posible entre las dos clases), el SVM utiliza la técnica de optimización convexa de maximización del margen.
El margen es la distancia perpendicular desde el hiperplano a los vectores de soporte más cercanos de ambas clases, y se puede expresar matemáticamente mediante la siguiente ecuación:
margen = (w^T x_+ + b) / ||w|| — (w^T x_- + b) / ||w||
Donde x_+ y x_- son vectores de características de los vectores de soporte más cercanos de las clases positiva y negativa, respectivamente. ||w|| representa la norma Euclidiana del vector w.
El objetivo de la optimización convexa es maximizar el margen, lo que equivale a minimizar la norma de w manteniendo la restricción de que todos los datos estén correctamente clasificados. Es decir, se busca minimizar la siguiente función objetivo:
min ||w||² / 2
Restringido a:
y_i (w^T x_i + b) >= 1
Donde y_i es la etiqueta de clase de la muestra de datos x_i (1 para la clase positiva y -1 para la clase negativa).
Esta función objetivo se puede resolver mediante la técnica de Lagrange, que introduce multiplicadores de Lagrange para transformar el problema de minimización con restricciones en un problema de maximización sin restricciones. La solución final se expresa como una combinación lineal de las muestras de datos y sus multiplicadores de Lagrange:
w = sum_i alpha_i y_i x_i
Donde alpha_i es el multiplicador de Lagrange asociado a la muestra de datos x_i.
Implementando SVM
A continuación les comparto la clase con la implementación del algoritmo, si bien el algoritmo fue conceptualmente desafiante su implementación es de las mas sencillas
import numpy as np
class SVM:
def __init__(self, learning_rate=0.001, lambda_param=0.01, n_iters=1000):
self.lr = learning_rate
self.lambda_param = lambda_param
self.n_iters = n_iters
self.w = None
self.b = None
def fit(self, X, y):
y_ = np.where(y <= 0, -1, 1)
n_samples, n_features = X.shape
self.w = np.zeros(n_features)
self.b = 0
# Descenso del gradiente
for _ in range(self.n_iters):
for idx, x_i in enumerate(X):
condition = y_[idx] * (np.dot(x_i, self.w) - self.b) >= 1
if (condition):
self.w -= self.lr * \
(2 * self.lambda_param * self.w) # Primer update
else:
self.w -= self.lr * \
(2 * self.lambda_param * self.w -
np.dot(x_i, y_[idx])) # Segundo update
self.b -= self.lr * y_[idx]
def predict(self, X):
linear_output = np.dot(X, self.w) - self.b
return np.sign(linear_output)
La función de ajuste (fit) toma un conjunto de datos de entrada X y sus etiquetas de clase y entrena el modelo SVM.
La función de predicción (predict) toma un conjunto de datos X y devuelve las predicciones de clase para cada muestra de datos.
En la función de ajuste, se transforman las etiquetas de clase y a través de la función np.where() se asignan valores de -1 y 1 a las clases. Se inicializa el vector de pesos (w) y el sesgo (b) a cero y luego se realiza un ciclo de entrenamiento en la matriz de datos X. Se realiza un ciclo interno sobre cada muestra de datos en X y se evalúa una condición para actualizar los pesos y el sesgo.
Si la condición de margen es mayor o igual a 1, se actualiza solo el vector de pesos (w) utilizando la ecuación del primer update en la función de costo. De lo contrario, se actualizan tanto el vector de pesos (w) como el sesgo (b) utilizando la ecuación del segundo update en la función de costo.
Estos pasos anteriores de ajuste de parámetros es lo que conocemos como descenso del gradiente.
La función de predicción simplemente realiza una multiplicación matricial de los datos de entrada (X) y el vector de pesos (w), y luego se le resta el sesgo (b) para obtener la salida lineal. Luego se aplica una función signo para obtener las predicciones de clase binarias (-1 o 1).
Por ultimo dejo una clase para poder probar este algoritmo y ver el resultado final con un set de datos.
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from svm import SVM
X, y = datasets.make_blobs(n_samples=50, n_features=2,
centers=2, cluster_std=1.05, random_state=40)
y = np.where(y == 0, -1, 1)
clf = SVM()
clf.fit(X, y)
print(clf.w, clf.b)
def visualize_svm():
def get_hyperplane_value(x, w, b, offset):
return (-w[0] * x + b + offset) / w[1]
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
plt.scatter(X[:, 0], X[:, 1], marker="o", c=y)
x0_1 = np.amin(X[:, 0])
x0_2 = np.amax(X[:, 0])
x1_1 = get_hyperplane_value(x0_1, clf.w, clf.b, 0)
x1_2 = get_hyperplane_value(x0_2, clf.w, clf.b, 0)
x1_1_m = get_hyperplane_value(x0_1, clf.w, clf.b, -1)
x1_2_m = get_hyperplane_value(x0_2, clf.w, clf.b, -1)
x1_1_p = get_hyperplane_value(x0_1, clf.w, clf.b, 1)
x1_2_p = get_hyperplane_value(x0_2, clf.w, clf.b, 1)
ax.plot([x0_1, x0_2], [x1_1, x1_2], "y--")
ax.plot([x0_1, x0_2], [x1_1_m, x1_2_m], "k")
ax.plot([x0_1, x0_2], [x1_1_p, x1_2_p], "k")
x1_min = np.amin(X[:, 1])
x1_max = np.amax(X[:, 1])
ax.set_ylim([x1_min - 3, x1_max + 3])
plt.show()
visualize_svm()
Podes ver este código y el de los otros artículos en este repositorio.