Máquinas de Vetores de Suporte

A SVM (Cortes & Vapnik, 1995) coroou a era do aprendizado estatístico: um classificador derivado de um princípio geométrico limpo — maximizar a margem — com teoria rigorosa por trás, e um truque que permite a um método linear traçar fronteiras extremamente não lineares. Antes do deep learning, as SVMs eram o estado da arte em quase toda parte; elas continuam excelentes em problemas de porte pequeno a médio e de alta dimensão.

Margem máxima

Muitos hiperplanos separam duas classes separáveis; qual é o melhor? A resposta de Vapnik: aquele mais distante dos pontos mais próximos de ambas as classes — a "rua" mais larga. Uma margem larga significa que pequenas perturbações dos dados não invertem as previsões: melhor generalização, comprovadamente.

Para o hiperplano \(w^\top x + b = 0\), escalone \(w, b\) de modo que os pontos mais próximos satisfaçam \(\lvert w^\top x + b \rvert = 1\) (as linhas tracejadas). A largura da rua é \(2 / \lVert w \rVert\), então maximizar a margem = minimizar \(\lVert w \rVert\):

\[ \min_{w, b} \; \frac{1}{2} \lVert w \rVert^2 \quad \text{sujeito a} \quad y_i (w^\top x_i + b) \geq 1 \;\; \forall i \qquad (y_i \in \{-1, +1\}) \]

Um programa quadrático convexo — um único ótimo global. Os pontos circulados que tocam as linhas tracejadas são os vetores de suporte: só eles determinam a solução. Mova ou remova qualquer outro ponto e nada muda — o modelo comprime o conjunto de dados aos seus casos-limite críticos.

Margem suave: tolerando a imperfeição

Dados reais não são separáveis. Introduza a folga \(\xi_i \geq 0\) (o quanto o ponto \(i\) viola sua margem) e cobre por ela:

\[ \min_{w, b, \xi} \; \frac{1}{2}\lVert w \rVert^2 + C \sum_{i=1}^{n} \xi_i \quad \text{sujeito a} \quad y_i (w^\top x_i + b) \geq 1 - \xi_i \]

O \(C\) é o botão de viés–variância, e funciona como o C da regressão logística (ambos são regularização inversa):

\(C\) grande: violações são caras → margem estreita e estrita → risco de sobreajuste;
\(C\) pequeno: violações são baratas → margem larga e tolerante → fronteira mais suave e simples.

Equivalentemente: a SVM minimiza a hinge loss \(\max(0,\, 1 - y_i(w^\top x_i + b))\) mais uma penalidade L2 — o mesmo template "perda + regularização" do Ridge, com uma perda que ignora pontos confortavelmente além da margem.

O kernel trick

A forma dual da otimização depende dos dados apenas por meio de produtos internos \(x_i^\top x_j\), e a previsão também:

\[ f(x) = \operatorname{sign}\Big( \sum_{i \in \text{SV}} \alpha_i y_i \, \langle x_i, x \rangle + b \Big) \]

Então: mapeie os dados para um espaço de dimensão mais alta \(\phi(x)\) onde eles se tornam linearmente separáveis — mas nunca calcule \(\phi\) explicitamente. Basta substituir todo produto interno por uma função de kernel

\[ K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle, \]

calculada diretamente no espaço original. Maquinaria linear, fronteira não linear, sem custo exponencial.

Kernel	\(K(x, x')\)	Notas
linear	\(x^\top x'\)	baseline; melhor para dados esparsos de alta dimensão (texto)
polinomial	\((\gamma\, x^\top x' + r)^p\)	interações de atributos até o grau \(p\)
RBF (gaussiano)	\(\exp(-\gamma \lVert x - x' \rVert^2)\)	padrão; espaço implícito de dimensão infinita

Para o RBF, o \(\gamma\) define o raio de influência de cada vetor de suporte: \(\gamma\) grande → ilhas apertadas em torno dos pontos (sobreajuste); \(\gamma\) pequeno → influência ampla e suave (subajuste). O \(C\) e o \(\gamma\) são ajustados juntos em uma grade logarítmica (GridSearchCV). O painel direito da figura mostra o RBF traçando uma fronteira circular que nenhum hiperplano conseguiria — no espaço implícito, os círculos são linearmente separáveis.

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

svm = make_pipeline(StandardScaler(),                    # SVMs são baseadas em distância
                    SVC(kernel='rbf', C=1.0, gamma='scale'))
svm.fit(X_train, y_train)

O treino, em essência

Os solvers otimizam o dual (ex.: SMO — Sequential Minimal Optimization, Platt 1998 — que otimiza iterativamente pares de \(\alpha_i\)). Um esboço em pseudocódigo da ideia:

inicialize todos os α_i = 0
repita até as condições KKT valerem (dentro da tolerância):
    escolha um par (α_i, α_j) que viole as condições      # escolha heurística
    otimize o objetivo sobre esse par analiticamente       # forma fechada para 2 variáveis
    limite a 0 ≤ α ≤ C, atualize b
os pontos que terminam com α_i > 0 são os vetores de suporte

A complexidade é aproximadamente \(O(n^2)\)–\(O(n^3)\) em amostras — a razão de as SVMs brilharem em \(n \sim 10^3\)–\(10^5\) mas cederem ao gradient boosting e às redes neurais em milhões de linhas. (Para kernels lineares, LinearSVC/SGDClassifier escalam muito mais.)

Perfil prático


Pontos fortes	generalização por margem máxima; flexibilidade de kernels; eficaz quando atributos ≫ amostras; a solução depende apenas dos vetores de suporte
Fraquezas	escala mal com n; dois hiperparâmetros acoplados (C, γ); sem probabilidades nativas (o escalonamento de Platt é um ajuste posterior); requer escalonamento
Recorra a ela quando	conjuntos pequenos/médios, dados de alta dimensão, fronteiras não lineares sem deep learning

Material de aula

Notebooks da aula (em português)

Notebooks práticos usados em sala:

Aula 17 — Support Vector Machines: abrir no Colab
Aula 18 — SVM Pseudocódigo (implementação do zero): abrir no Colab

Vídeos

SVM — Support Vector Machines: Fundamentos e prática — em português
16. Learning: Support Vector Machines — MIT OpenCourseWare, Patrick Winston