Logo de Pablo MadariagaPablo MadariagaData ScientistAgendar reunión

Capítulo 3

Support Vector Machines

3.1 Hiperplanos de Separación

Un SVM busca el hiperplano óptimo que separa dos clases con el máximo margen:

f(x)=w⊤x+bf(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b

Clasificamos como +1+1 si f(x)>0f(\mathbf{x}) > 0, −1-1 si no. El margen es la distancia mínima del hiperplano a cualquier punto de entrenamiento.

3.2 Formulación Primal

Queremos maximizar el margen 2/∥w∥2 / \|\mathbf{w}\|, equivalente a minimizar:

min⁡w,b12∥w∥2sujeto a yi(w⊤xi+b)≥1\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{sujeto a } y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1

Para datos no separables, introducimos variables de holgura ξi\xi_i:

min⁡w,b12∥w∥2+C∑i=1nξis.a. yi(w⊤xi+b)≥1−ξi\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \quad \text{s.a. } y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 - \xi_i

CC controla el trade-off entre margen y error de clasificación.

3.3 Formulación Dual y Kernels

El problema dual introduce multiplicadores de Lagrange αi\alpha_i:

max⁡α∑i=1nαi−12∑i,jαiαjyiyjxi⊤xj\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j

Con el kernel trick, reemplazamos el producto punto por una función kernel:

max⁡α∑i=1nαi−12∑i,jαiαjyiyjk(xi,xj)\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j k(\mathbf{x}_i, \mathbf{x}_j)

Lineal

k(xi,xj)=xi⊤xjk(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^\top \mathbf{x}_j

Polinomial

k(xi,xj)=(xi⊤xj+c)dk(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^\top \mathbf{x}_j + c)^d

RBF (Gaussiano)

k(xi,xj)=exp⁡(−γ∥xi−xj∥2)k(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)

3.4 Visualización Interactiva

El SVM encuentra el hiperplano con margen máximo. Ajusta C para ver el efecto en los vectores de soporte.

⌘/Alt + clic = clase -1
Vectores soporte: 0Margen: 0.500Puntos: 20

3.5 Implementación

Sklearn implementa SMO (optimización de secuencia mínima) para resolver el dual eficientemente:

python
from sklearn.svm import SVC
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score

X, y = make_classification(n_samples=500, n_features=10,
                           n_informative=5, random_state=42)

for kernel in ['linear', 'rbf', 'poly']:
    model = SVC(kernel=kernel, C=1.0, gamma='scale')
    scores = cross_val_score(model, X, y, cv=5)
    print(f"{kernel}: {scores.mean():.3f} (±{scores.std():.3f})")

3.6 Una SVM desde Cero (Dual)

python
import numpy as np
from scipy.optimize import minimize

class SimpleSVM:
    def fit(self, X, y, C=1.0):
        n = X.shape[0]
        K = X @ X.T  # kernel lineal
        y2 = np.outer(y, y)

        def loss(alpha):
            return 0.5 * (alpha * y2 * K).sum() - alpha.sum()

        bounds = [(0, C) for _ in range(n)]
        constraints = {'type': 'eq', 'fun': lambda a: a @ y}
        alpha0 = np.zeros(n)
        res = minimize(loss, alpha0, bounds=bounds,
                       constraints=constraints)
        self.alpha = res.x
        sv = self.alpha > 1e-6
        self.w = (self.alpha[sv, None] * y[sv, None] * X[sv]).sum(0)
        self.b = np.mean(y[sv] - X[sv] @ self.w)
        return self

    def predict(self, X): return np.sign(X @ self.w + self.b)

3.7 Support Vectors

Los puntos con αi>0\alpha_i > 0 son los vectores de soporte — los únicos que determinan el hiperplano. Puntos fuera del margen tienen αi=0\alpha_i = 0. Esto hace que SVM sea esparso: eficiente en inferencia.

python
# Cuántos vectores de soporte?
model = SVC(kernel='rbf', C=1.0)
model.fit(X, y)
print(f"Support vectors: {len(model.support_vectors_)} / {len(X)}")

# Los pesos duales (alpha) para kernel RBF
print(f"Alpha no-cero: {(model.dual_coef_ != 0).sum()}")