Phase 02 - Lesson 05

Máquinas de vetores de suporte

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

Encontre a rua mais larga entre duas classes. Essa é a ideia toda.

Tipo: Construir Idioma: Python Pré-requisitos: Fase 1 (Lições 08 Otimização, 14 Normas e Distâncias, 18 Otimização Convexa) Tempo: ~90 minutos

Objetivos de aprendizagem

• Implementar um SVM linear do zero usando perda de dobradiça e gradiente descendente na formulação primária
• Explicar o princípio da margem máxima e identificar vetores de suporte a partir de um modelo treinado
• Compare kernels lineares, polinomiais e RBF e explique como o truque do kernel evita mapeamento explícito de alta dimensão
• Avaliar o tradeoff controlado pelo parâmetro C entre largura de margem e erros de classificação

O problema

Você tem duas classes de pontos de dados e precisa desenhar uma linha (ou hiperplano) separando-os. Infinitas linhas poderiam funcionar. Qual você deve escolher?

Aquele com maior margem. A margem é a distância entre o limite de decisão e os pontos de dados mais próximos de cada lado. Uma margem mais ampla significa que o classificador está mais confiante e generaliza melhor para dados não vistos.

Essa intuição leva ao Support Vector Machines, um dos algoritmos matematicamente mais elegantes em ML. Os SVMs eram o método de classificação dominante antes do aprendizado profundo e continuam sendo a melhor escolha para pequenos conjuntos de dados, dados de alta dimensão e problemas onde é necessário um modelo bem compreendido e com princípios, com garantias teóricas.

SVMs se conectam diretamente à Fase 1: a otimização é convexa (Lição 18), a margem é medida com normas (Lição 14) e o truque do kernel explora produtos escalares para lidar com limites não lineares sem nunca computar no espaço de alta dimensão.

O Conceito

O classificador de margem máxima

Dados dados linearmente separáveis ​​com rótulos y_i em {-1, +1} e vetores de características x_i, queremos um hiperplano w^T x + b = 0 que separe as classes.

A distância de um ponto x_i ao hiperplano é:

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

Para um ponto classificado corretamente: y_i * (w^T x_i + b) > 0. A margem é o dobro da distância do hiperplano ao ponto mais próximo em 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"]

O problema de otimização:

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

Equivalentemente (minimizar ||w||^2 é mais fácil de otimizar):

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

Este é um programa quadrático convexo. Possui uma solução global única. Os pontos de dados que ficam exatamente nos limites da margem (onde y_i * (w^T x_i + b) = 1) são os vetores de suporte. Eles são os únicos pontos que determinam o limite de decisão. Mova ou remova qualquer ponto sem vetor de suporte e o limite não será alterado.

Vetores de suporte: os poucos 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

A maioria dos pontos de treinamento são irrelevantes. Apenas os vetores de suporte importam. É por isso que os SVMs são eficientes em termos de memória no momento da previsão: você só precisa armazenar os vetores de suporte, não todo o conjunto de treinamento.

O número de vetores de suporte também fornece um limite para o erro de generalização. Menos vetores de suporte em relação ao tamanho do conjunto de dados significa melhor generalização.

Margem suave: tratamento de ruído com o parâmetro C

Os dados reais raramente são perfeitamente separáveis. Alguns pontos podem estar do lado errado do limite ou dentro da margem. A formulação de margem suave permite violações ao introduzir variáveis ​​de folga.

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

A variável de folga xi_i mede quanto o ponto i viola a margem. C controla a compensação:

C é a força de regularização, invertida. C grande = menos regularização. C pequeno = mais regularização.

Perda de dobradiça: a função de perda SVM

A margem suave SVM pode ser reescrita como uma otimização irrestrita:

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

O termo max(0, 1 - y_i * f(x_i)) é a perda de dobradiça. É zero quando o ponto está classificado corretamente e além da margem. É linear quando o ponto está dentro da margem ou classificado incorretamente.

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 com perda logística (regressão logística):

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

A perda de dobradiça produz soluções esparsas (apenas vetores de suporte têm contribuição diferente de zero). A perda logística usa todos os pontos de dados. Isso torna os SVMs mais eficientes em termos de memória no momento da previsão.

Treinando um SVM linear com descida do gradiente

Você pode treinar um SVM linear usando gradiente descendente na perda de dobradiça mais regularização L2, sem resolver o QP restrito:

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

Isso é chamado de formulação primal. Ele é executado em O(n * d) por época, onde n é o número de amostras e d é o número de recursos. Para dados grandes, esparsos e de alta dimensão (classificação de texto), isso é rápido.

A formulação dupla e o truque do kernel

O dual Lagrangiano do problema SVM (da Fase 1, Lição 18, condições KKT) é:

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

O dual envolve apenas produtos escalares x_i . x_j entre pontos de dados. Este é o insight principal. Substitua cada produto escalar por uma função de kernel K(x_i, x_j) e o SVM pode aprender limites não lineares sem nunca calcular a transformação explicitamente.

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)

O kernel RBF mapeia dados em um espaço de dimensão infinita. Os pontos próximos no espaço de entrada têm valor de kernel próximo a 1. Os pontos distantes têm valor de kernel próximo a 0. Ele pode aprender qualquer limite de decisão suave.

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

O truque do kernel calcula o produto escalar no espaço de alta dimensão sem nunca ir até lá. Para o kernel polinomial de grau d em dimensões D, o espaço de recursos explícito tem dimensões O(D^d). Mas K(x, z) é calculado em tempo O(D).

SVM para regressão (SVR)

A regressão vetorial de suporte ajusta um tubo de largura épsilon ao redor dos dados. Os pontos dentro do tubo têm perda zero. Os pontos fora do tubo são penalizados linearmente.

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

O parâmetro épsilon controla a largura do tubo. Tubo mais largo = menos vetores de suporte = ajuste mais suave. Tubo mais estreito = mais vetores de suporte = ajuste mais apertado.

Por que os SVMs perderam para o aprendizado profundo (e quando ainda vencem)

Os SVMs dominaram o ML desde o final da década de 1990 até o início da década de 2010. O aprendizado profundo os superou por vários motivos:

SVMs ainda vencem nestas situações:

• Pequenos conjuntos de dados (centenas a milhares de amostras)
• Dados esparsos de alta dimensão (texto com recursos TF-IDF)
• Quando você precisa de garantias matemáticas (limites de margem)
• Quando o tempo de treinamento deve ser mínimo (linear SVM é muito rápido)
• Classificação binária com estrutura de margem clara
• Detecção de anomalias (uma classe SVM)

Construa

Etapa 1: Perda de dobradiça e gradiente

A fundação. Calcule a perda de dobradiça para um lote e seu 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

Etapa 2: Linear SVM via descida do gradiente

Treine minimizando a perda regularizada de dobradiça. Não é necessário nenhum solucionador 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]

Etapa 3: Funções do kernel

Implemente kernels lineares, polinomiais e 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))

Etapa 4: Margem e identificação do vetor de suporte

Após o treinamento, identifique quais pontos são vetores de suporte e calcule a largura da margem.

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

Veja code/svm.py para a implementação completa com todas as demonstrações.

Use-o

Com 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: sempre escale seus recursos antes de treinar um SVM. SVMs são sensíveis às magnitudes dos recursos porque a margem depende de ||w||, e os recursos não dimensionados distorcem a geometria.

Para grandes conjuntos de dados, use LinearSVC (formulação primária, O(n) por época) em vez de SVC (formulação dupla, O(n^2) a O(n^3)):

from sklearn.svm import LinearSVC

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

Exercícios

1. Gere um conjunto de dados 2D linearmente separável. Treine seu LinearSVM e identifique os vetores de suporte. Verifique se os vetores de suporte são os pontos mais próximos do limite de decisão.

2. Varie C de 0,001 a 1000 em um conjunto de dados ruidoso. Trace o limite de decisão para cada valor C. Observe a transição de margem ampla (underfitting) para margem estreita (overfitting).

3. Crie um conjunto de dados onde os limites das classes sejam circulares (não lineares). Mostre que um SVM linear falha. Calcule a matriz do kernel RBF e mostre que as classes se tornam separáveis ​​no espaço de recursos induzido pelo kernel.

4. Compare a perda de dobradiça com a perda logística no mesmo conjunto de dados. Treine uma regressão linear SVM e logística. Conte quantos pontos de treinamento contribuem para o limite de decisão de cada modelo (vetores de suporte versus todos os pontos).

5. Implementar SVR (perda insensível ao épsilon). Ajuste-o para y = sin(x) + ruído. Trace o tubo épsilon em torno das previsões e destaque os vetores de suporte (pontos fora do tubo).

Termos-chave

Leitura Adicional

• Vapnik: The Nature of Statistical Learning Theory (1995) - o texto fundamental sobre SVMs e aprendizagem estatística
• Cortes & Vapnik: Redes de vetores de suporte (1995) - o artigo SVM original
• Platt: Sequential Minimal Optimization (1998) - o algoritmo SMO que tornou o treinamento SVM prático
• scikit-learn SVM documentação - guia prático com detalhes de implementação
• LIBSVM: uma biblioteca para máquinas de vetores de suporte - a biblioteca C++ por trás da maioria das implementações SVM