Phase 02 - Lesson 05

Máquinas de vectores de soporte

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Encuentra la calle más ancha entre dos clases. Esa es toda la idea.

Tipo: Construcción Idioma: Python Requisitos previos: Fase 1 (Lecciones 08 Optimización, 14 Normas y distancias, 18 Optimización convexa) Tiempo: ~90 minutos

Objetivos de aprendizaje

• Implementar un SVM lineal desde cero usando pérdida de bisagra y descenso de gradiente en la formulación primaria
• Explicar el principio de margen máximo e identificar vectores de soporte a partir de un modelo entrenado.
• Comparar núcleos lineales, polinomiales y RBF y explicar cómo el truco del núcleo evita el mapeo explícito de alta dimensión.
• Evaluar la compensación controlada por el parámetro C entre el ancho del margen y los errores de clasificación.

El problema

Tiene dos clases de puntos de datos y necesita dibujar una línea (o hiperplano) que los separe. Podrían funcionar infinitas líneas. ¿Cuál deberías elegir?

El que tiene mayor margen. El margen es la distancia entre el límite de decisión y los puntos de datos más cercanos en cada lado. Un margen más amplio significa que el clasificador tiene más confianza y generaliza mejor los datos invisibles.

Esta intuición conduce a Support Vector Machines, uno de los algoritmos matemáticamente más elegantes de ML. Las SVM eran el método de clasificación dominante antes del aprendizaje profundo y siguen siendo la mejor opción para conjuntos de datos pequeños, datos de alta dimensión y problemas en los que se necesita un modelo bien comprendido y basado en principios con garantías teóricas.

Las SVM se conectan directamente a la Fase 1: la optimización es convexa (Lección 18), el margen se mide con normas (Lección 14) y el truco del núcleo explota los productos escalares para manejar límites no lineales sin siquiera calcular en el espacio de alta dimensión.

El concepto

El clasificador de margen máximo

Dados datos linealmente separables con etiquetas y_i en {-1, +1} y vectores de características x_i, queremos un hiperplano w^T x + b = 0 que separe las clases.

La distancia desde un punto x_i al hiperplano es:

distance = |w^T x_i + b| / ||w||

Para un punto correctamente clasificado: y_i * (w^T x_i + b) > 0. El margen es el doble de la distancia desde el hiperplano hasta el punto más cercano a cada lado.

graph LR
    subgraph Margin
        direction TB
        A["w^T x + b = +1"] ~~~ B["w^T x + b = 0"] ~~~ C["w^T x + b = -1"]
    end
    D["+ class points"] --> A
    E["- class points"] --> C
    B --- F["Decision boundary"]

El problema de optimización:

maximize    2 / ||w||     (the margin width)
subject to  y_i * (w^T x_i + b) >= 1  for all i

De manera equivalente (minimizar ||w||^2 es más fácil de optimizar):

minimize    (1/2) ||w||^2
subject to  y_i * (w^T x_i + b) >= 1  for all i

Este es un programa cuadrático convexo. Tiene una solución global única. Los puntos de datos que se encuentran exactamente en los límites del margen (donde y_i * (w^T x_i + b) = 1) son los vectores de soporte. Son los únicos puntos que determinan el límite de decisión. Mueva o elimine cualquier punto que no sea un vector de soporte y el límite no cambiará.

Vectores de soporte: los pocos críticos

graph TD
    subgraph Classification
        SV1["Support Vector (+ class)<br>y(w'x+b) = 1"] --- DB["Decision Boundary<br>w'x+b = 0"]
        DB --- SV2["Support Vector (- class)<br>y(w'x+b) = 1"]
    end
    O1["Other + points<br>(do not affect boundary)"] -.-> SV1
    O2["Other - points<br>(do not affect boundary)"] -.-> SV2

La mayoría de los puntos de entrenamiento son irrelevantes. Sólo importan los vectores de soporte. Es por eso que las SVM son eficientes en cuanto a memoria en el momento de la predicción: solo necesita almacenar los vectores de soporte, no todo el conjunto de entrenamiento.

El número de vectores de soporte también da un límite al error de generalización. Menos vectores de soporte en relación con el tamaño del conjunto de datos significa una mejor generalización.

Margen suave: manejo del ruido con el parámetro C

Los datos reales rara vez son perfectamente separables. Algunos puntos pueden estar en el lado equivocado del límite o dentro del margen. La formulación de margen suave permite violaciones al introducir variables de holgura.

minimize    (1/2) ||w||^2 + C * sum(xi_i)
subject to  y_i * (w^T x_i + b) >= 1 - xi_i
            xi_i >= 0  for all i

La variable de holgura xi_i mide cuánto punto i viola el margen. C controla la compensación:

C es la fuerza de regularización, invertida. C grande = menos regularización. C pequeña = más regularización.

Pérdida de bisagra: la función de pérdida SVM

El margen suave SVM se puede reescribir como una optimización sin restricciones:

minimize    (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b)))

El término max(0, 1 - y_i * f(x_i)) es la pérdida de bisagra. Es cero cuando el punto está correctamente clasificado y más allá del margen. Es lineal cuando el punto está dentro del margen o mal clasificado.

Hinge loss for a single point:

loss
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

Zero loss when y*f(x) >= 1 (correctly classified, outside margin).
Linear penalty when y*f(x) < 1.

Compare con la pérdida logística (regresión logística):

Hinge:     max(0, 1 - y*f(x))          Hard cutoff at margin
Logistic:  log(1 + exp(-y*f(x)))        Smooth, never exactly zero

La pérdida de bisagra produce soluciones escasas (solo los vectores de soporte tienen una contribución distinta de cero). La pérdida logística utiliza todos los puntos de datos. Esto hace que las SVM sean más eficientes en cuanto a memoria en el momento de la predicción.

Entrenando un SVM lineal con descenso de gradiente

Puedes entrenar un SVM lineal usando el descenso de gradiente en la pérdida de bisagra más la regularización L2, sin resolver el QP restringido:

L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b)))

Gradient with respect to w:
  If y_i * (w^T x_i + b) >= 1:  dL/dw = lambda * w
  If y_i * (w^T x_i + b) < 1:   dL/dw = lambda * w - y_i * x_i

Gradient with respect to b:
  If y_i * (w^T x_i + b) >= 1:  dL/db = 0
  If y_i * (w^T x_i + b) < 1:   dL/db = -y_i

A esto se le llama formulación primaria. Se ejecuta en O (n * d) por época, donde n es el número de muestras y d es el número de características. Para datos grandes, escasos y de alta dimensión (clasificación de texto), esto es rápido.

La formulación dual y el truco del núcleo

El dual lagrangiano del problema SVM (de la Fase 1, Lección 18, condiciones KKT) es:

maximize    sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j))
subject to  0 <= alpha_i <= C
            sum(alpha_i * y_i) = 0

El dual solo involucra productos escalares x_i . x_j entre puntos de datos. Esta es la idea clave. Reemplace cada producto escalar con una función del núcleo K(x_i, x_j) y SVM puede aprender límites no lineales sin siquiera calcular la transentrenamiento explícitamente.

Linear kernel:      K(x, z) = x . z
Polynomial kernel:  K(x, z) = (x . z + c)^d
RBF (Gaussian):     K(x, z) = exp(-gamma * ||x - z||^2)

El núcleo RBF asigna datos a un espacio de dimensión infinita. Los puntos que están cerca en el espacio de entrada tienen un valor central cercano a 1. Los puntos que están muy separados tienen un valor central cercano a 0. Puede aprender cualquier límite de decisión fluido.

graph LR
    subgraph "Input Space (not separable)"
        A["Data points in 2D<br>circular boundary"]
    end
    subgraph "Feature Space (separable)"
        B["Data points in higher dim<br>linear boundary"]
    end
    A -->|"Kernel trick<br>K(x,z) = phi(x).phi(z)"| B

El truco del kernel calcula el producto escalar en el espacio de alta dimensión sin siquiera llegar allí. Para el núcleo polinómico de grado d en D dimensiones, el espacio de características explícito tiene dimensiones O(D^d). Pero K(x, z) se calcula en tiempo O(D).

SVM para regresión (SVR)

La regresión de vectores de soporte ajusta un tubo de ancho épsilon alrededor de los datos. Los puntos dentro del tubo tienen pérdida cero. Los puntos fuera del tubo se penalizan linealmente.

minimize    (1/2) ||w||^2 + C * sum(xi_i + xi_i*)
subject to  y_i - (w^T x_i + b) <= epsilon + xi_i
            (w^T x_i + b) - y_i <= epsilon + xi_i*
            xi_i, xi_i* >= 0

El parámetro épsilon controla el ancho del tubo. Tubo más ancho = menos vectores de soporte = ajuste más suave. Tubo más estrecho = más vectores de soporte = ajuste más ajustado.

Por qué las SVM perdieron ante el aprendizaje profundo (y cuándo siguen ganando)

Las SVM dominaron el ML desde finales de los 90 hasta principios de los 2010. El aprendizaje profundo los superó por varias razones:

Las SVM siguen ganando en estas situaciones:

• Pequeños conjuntos de datos (de cientos a miles de muestras)
• Datos dispersos de alta dimensión (texto con características TF-IDF)
• Cuando necesitas garantías matemáticas (límites de margen)
• Cuando el tiempo de entrenamiento debe ser mínimo (lineal SVM es muy rápido)
• Clasificación binaria con estructura de márgenes clara.
• Detección de anomalías (una clase SVM)

Constrúyelo

Paso 1: pérdida de bisagra y gradiente

La fundación. Calcule la pérdida de bisagra para un lote y su gradiente.

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n

Paso 2: Lineal SVM mediante descenso de gradiente

Entrene minimizando la pérdida regularizada de bisagras. No se necesita solucionador de QP.

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]

Paso 3: Funciones del kernel

Implemente núcleos lineales, polinomiales y RBF.

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))

Paso 4: Identificación de márgenes y vectores de soporte

Después del entrenamiento, identifique qué puntos son vectores de soporte y calcule el ancho del margen.

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors

Consulte code/svm.py para ver la implementación completa con todas las demostraciones.

Úsalo

Con scikit-learn:

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
print(f"Support vectors: {clf['svm'].n_support_}")

Importante: siempre escale sus rasgos antes de entrenar un SVM. Las SVM son sensibles a las magnitudes de las características porque el margen depende de ||w|| y las características sin escala distorsionan la geometría.

Para conjuntos de datos grandes, utilice LinearSVC (formulación primaria, O(n) por época) en lugar de SVC (formulación dual, O(n^2) a O(n^3)):

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])

Ejercicios

1. Genere un conjunto de datos 2D linealmente separable. Entrene su LinearSVM e identifique los vectores de soporte. Verifique que los vectores de soporte sean los puntos más cercanos al límite de decisión.

2. Varíe C de 0,001 a 1000 en un conjunto de datos ruidoso. Trazar el límite de decisión para cada valor de C. Observe la transición de un margen amplio (subajuste) a un margen estrecho (sobreajuste).

3. Cree un conjunto de datos donde los límites de clase sean circulares (no lineales). Demuestre que un SVM lineal falla. Calcule la matriz del núcleo RBF y demuestre que las clases se vuelven separables en el espacio de características inducidas por el núcleo.

4. Compare la pérdida de bisagra con la pérdida logística en el mismo conjunto de datos. Entrene una regresión lineal SVM y logística. Cuente cuántos puntos de entrenamiento contribuyen al límite de decisión de cada modelo (vectores de soporte frente a todos los puntos).

5. Implementar SVR (pérdida insensible a épsilon). Ajústelo a y = sin(x) + ruido. Trace el tubo épsilon alrededor de las predicciones y resalte los vectores de soporte (puntos fuera del tubo).

Términos clave

Lectura adicional

• Vapnik: La naturaleza de la teoría del aprendizaje estadístico (1995) - el texto fundamental sobre SVM y el aprendizaje estadístico
• Cortés y Vapnik: Redes de vectores de soporte (1995) - el artículo original SVM
• Platt: Sequential Minimal Optimization (1998) - el algoritmo SMO que hizo práctico el entrenamiento SVM
• scikit-learn SVM documentación - guía práctica con detalles de implementación
• LIBSVM: una biblioteca para máquinas de vectores de soporte: la biblioteca de C++ detrás de la mayoría de las implementaciones de SVM