Aula 11: Máquinas de Vetores de Suporte (SVM)
Supervised Learning
1 Revisão e Ruptura de Paradigma
1.1 A Tese do Curso e o Paradigma Probabilístico
Nas primeiras dez aulas deste curso, todo o edifício do aprendizado supervisionado foi estruturado em torno da seguinte tese epistemológica:
\[\text{Algoritmo Supervisionado} = \text{Distribuição Assumida} + \text{Verossimilhança} + \text{Regra de Decisão Bayesiana}\]
- Na Regressão Linear (Aulas 2 e 3), assumimos erros gaussianos aditivos \(y \mid \mathbf{x} \sim \mathcal{N}(\mathbf{w}^T \mathbf{x}, \sigma^2)\), o que conduziu aos Mínimos Quadrados Ordinários via Máxima Verossimilhança.
- Na Regressão Logística (Aula 6), modelamos a probabilidade a posteriori através da função logística \(p(y = 1 \mid \mathbf{x}) = \sigma(\mathbf{w}^T \mathbf{x})\), minimizando a entropia cruzada sobre a totalidade das \(N\) amostras.
- No Gradient Tree Boosting (Aula 10), realizamos descida de gradiente funcional para minimizar a deviance de Bernoulli, combinando centenas de árvores para aproximar o \(\log\)-odds populacional \(f^*(\mathbf{x}) = \frac{1}{2}\ln \frac{p(y=1\mid\mathbf{x})}{1 - p(y=1\mid\mathbf{x})}\).
Em todos esses métodos, existia uma premissa implícita: para classificar um novo ponto, é prudente estimar a função de probabilidade condicional \(p(y \mid \mathbf{x})\) em todas as regiões do espaço amostral.
1.2 A Ruptura de Vapnik: O Princípio de Conservação da Capacidade
Em 1995, Vladimir Vapnik e Corinna Cortes formularam uma proposta epistemológica radical que deu origem às Máquinas de Vetores de Suporte (Support Vector Machines — SVM):
O Princípio de Vapnik: “Ao resolver um problema de interesse prático, nunca resolva um problema mais geral como passo intermediário. Tente resolver o problema original diretamente, sem desperdiçar recursos na estimativa de grandezas desnecessárias.”
Se o objetivo é traçar uma fronteira discriminante entre duas classes de células tumorais (malignas vs. benignas), não precisamos saber se uma célula localizada no extremo do espaço tem \(99{,}9\%\) ou \(99{,}999\%\) de probabilidade de ser benigna. A única informação crítica reside na vizinhança imediata da fronteira de decisão.
Considere o caso linearmente separável: existem infinitos hiperplanos capazes de separar perfeitamente os dados com erro de treinamento igual a zero. Qual desses infinitos hiperplanos oferece a melhor garantia matemática de generalização para dados nunca vistos?
A resposta da Teoria do Aprendizado Estatístico (Vapnik-Chervonenkis) é inequívoca: o hiperplano que maximiza a distância ortogonal mínima até as amostras mais próximas de cada classe — o chamado hiperplano de margem máxima.
1.3 Roteiro da Aula
Nesta aula, desvendamos a teoria, a geometria e a implementação das SVMs através de cinco perguntas condutoras:
- O que é a margem geométrica canônica e por que sua maximização equivale a um problema quadrático convexo em \(\|\mathbf{w}\|^2\)?
- Como a dualidade de Lagrange e as condições KKT (Karush-Kuhn-Tucker) revelam a esparsidade dos vetores de suporte?
- Como a introdução de variáveis de folga \(\xi_i \ge 0\) (Soft Margin) conecta formalmente a SVM à minimização da perda Hinge regularizada?
- Como o Truque do Kernel (Kernel Trick) projeta dados não lineares em espaços de Hilbert de dimensão infinita operando apenas produtos internos locais?
- Como transformar os escores geométricos não calibrados da SVM em probabilidades estatisticamente rigorosas via Calibração de Platt (1999) e como estender o modelo para regressão (\(\varepsilon\)-SVR)?
1.4 Problema Motivador: Breast Cancer Wisconsin
Utilizamos como fio condutor o dataset Breast Cancer Wisconsin (\(N = 569\)), no qual o objetivo é diagnosticar se uma biópsia por aspiração com agulha fina corresponde a um nódulo mamário maligno (\(y = -1\)) ou benigno (\(y = +1\)).
Para permitir a intuição visual direta, selecionamos inicialmente os dois primeiros atributos padronizados: - \(x_1\): Raio Médio (mean radius); - \(x_2\): Textura Média (mean texture).
Abaixo, ilustramos os dados e contrastamos três hiperplanos arbitrários que separam o subconjunto local com o hiperplano ótimo de margem máxima:
1.5 Pausa 1: A Ruptura com a Verossimilhança
DicaPergunta aberta provocadora
Em uma aplicação de diagnóstico médico, a Regressão Logística estima que um novo paciente tem probabilidade estimada \(\hat{p} = 0{,}51\) de apresentar nódulo maligno, enquanto uma SVM Linear treinada no mesmo conjunto classifica o paciente como benigno com escore de margem \(f(\mathbf{x}) = +0{,}85\). Explique conceitualmente por que esses dois modelos lineares podem produzir decisões divergentes mesmo tendo acesso aos mesmos dados.
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Em conjuntos de dados linearmente separáveis, o algoritmo de Máxima Verossimilhança da Regressão Logística sem regularização converge para parâmetros finitos e atinge a margem máxima exata da SVM.
- □ A distância geométrica euclidiana de um ponto \(\mathbf{x}\) ao hiperplano \(\mathbf{w}^T \mathbf{x} + b = 0\) depende inversamente da norma euclidiana \(\|\mathbf{w}\|\).
- □ Ao contrário da Regressão Logística, na qual cada observação do dataset exerce influência sobre o gradiente da função de perda, a SVM de margem rígida depende estritamente das amostras que repousam sobre as margens.
- □ A teoria de VC (Vapnik-Chervonenkis) estabelece que a capacidade de generalização de um classificador linear de margem máxima depende exclusivamente da dimensionalidade \(d\) do espaço de entrada, e não da razão entre o diâmetro dos dados e a largura da margem.
2 Bloco 1: Margem Máxima e Problema Dual (Hard Margin)
2.1 A Geometria do Hiperplano Canônico
Seja um conjunto de treinamento \(D = \{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_N, y_N)\}\) com atributos \(\mathbf{x}_i \in \mathbb{R}^d\) e rótulos binários \(y_i \in \{-1, +1\}\).
Um hiperplano afim em \(\mathbb{R}^d\) é definido pelo conjunto de pontos que satisfazem:
\[\mathcal{H} = \{\mathbf{x} \in \mathbb{R}^d : \mathbf{w}^T \mathbf{x} + b = 0\}\]
onde \(\mathbf{w} \in \mathbb{R}^d\) é o vetor normal ortogonal à superfície do hiperplano e \(b \in \mathbb{R}\) é o termo de deslocamento (bias).
Para qualquer ponto \(\mathbf{x} \in \mathbb{R}^d\), sua projeção ortogonal sobre o hiperplano \(\mathcal{H}\) é dada por \(\mathbf{x}_0 = \mathbf{x} - d \frac{\mathbf{w}}{\|\mathbf{w}\|}\), onde \(d \in \mathbb{R}\) é a distância orientada com sinal. Como \(\mathbf{x}_0\) pertence a \(\mathcal{H}\):
\[\mathbf{w}^T \left(\mathbf{x} - d \frac{\mathbf{w}}{\|\mathbf{w}\|}\right) + b = 0 \implies \mathbf{w}^T \mathbf{x} - d \frac{\|\mathbf{w}\|^2}{\|\mathbf{w}\|} + b = 0\]
\[d(\mathbf{x}) = \frac{\mathbf{w}^T \mathbf{x} + b}{\|\mathbf{w}\|}\]
Multiplicando pelo rótulo da classe \(y \in \{-1, +1\}\), a distância euclidiana ortogonal perpendicular de uma amostra \((\mathbf{x}_i, y_i)\) ao hiperplano é:
\[d_i = \frac{y_i(\mathbf{w}^T \mathbf{x}_i + b)}{\|\mathbf{w}\|}\]
2.2 Fixação da Escala Canônica e o Problema Primal
Para eliminar a redundância de escala provocada por \(\kappa > 0\), impomos a convenção canônica: escalonamos os parâmetros \((\mathbf{w}, b)\) de modo que o ponto mais próximo do hiperplano tenha valor absoluto exatamente igual a 1:
\[\min_{i=1, \dots, N} y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1\]
Sob essa parametrização canônica: 1. Para todos os pontos da classe positiva (\(y_i = +1\)), temos \(\mathbf{w}^T \mathbf{x}_i + b \ge +1\). 2. Para todos os pontos da classe negativa (\(y_i = -1\)), temos \(\mathbf{w}^T \mathbf{x}_i + b \le -1\). 3. Logo, para qualquer amostra \(i = 1, \dots, N\): \[y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1\]
A distância do ponto mais próximo até o hiperplano é dada por \(\gamma_{\text{half}} = \frac{1}{\|\mathbf{w}\|}\).
Portanto, a margem geométrica total (a distância entre os dois hiperplanos de suporte paralelos \(\mathbf{w}^T \mathbf{x} + b = +1\) e \(\mathbf{w}^T \mathbf{x} + b = -1\)) é:
\[\gamma = \frac{2}{\|\mathbf{w}\|}\]
Maximizar a margem geométrica \(\frac{2}{\|\mathbf{w}\|}\) equivale estritamente a minimizar a sua recíproca quadrática \(\frac{1}{2}\|\mathbf{w}\|^2\). Chegamos assim ao Problema Primal da SVM de Margem Rígida (Hard Margin):
\[\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{sujeito a } y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1, \quad \forall i = 1, \dots, N\]
2.3 Geometria do Hiperplano e Margem Canônica
2.4 O Lagrangeano Primal e as Condições de Ponto de Sela
Para resolver o problema quadrático sob restrições de desigualdade, introduzimos os multiplicadores de Lagrange \(\alpha_i \ge 0\) para cada uma das \(N\) restrições \(y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 \ge 0\).
A função Lagrangeana primal \(\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})\) é formulada como:
\[\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2} \|\mathbf{w}\|^2 - \sum_{i=1}^N \alpha_i \big[ y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 \big]\]
com \(\alpha_i \ge 0\). De acordo com o teorema da dualidade de Lagrange, o ponto ótimo deve satisfazer as condições de estacionariedade em relação às variáveis primais \((\mathbf{w}, b)\):
Derivada em relação ao vetor de pesos \(\mathbf{w}\): \[\nabla_{\mathbf{w}} \mathcal{L} = \mathbf{w} - \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i = \mathbf{0} \implies \mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i\]
Propriedade Fundamental: O vetor de pesos ótimo \(\mathbf{w}\) é uma combinação linear direta dos vetores de entrada dos dados de treinamento.
Derivada em relação ao termo independente \(b\): \[\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^N \alpha_i y_i = 0 \implies \sum_{i=1}^N \alpha_i y_i = 0\]
Propriedade Fundamental: A soma ponderada dos multiplicadores de Lagrange multiplicados por seus respectivos rótulos de classe anula-se identicamente.
2.5 O Problema Dual de Wolfe
Substituindo as relações de estacionariedade de volta na função Lagrangeana primal \(\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})\):
\[\mathcal{L} = \frac{1}{2} \left(\sum_{i=1}^N \alpha_i y_i \mathbf{x}_i\right)^T \left(\sum_{j=1}^N \alpha_j y_j \mathbf{x}_j\right) - \sum_{i=1}^N \alpha_i y_i \left(\sum_{j=1}^N \alpha_j y_j \mathbf{x}_j\right)^T \mathbf{x}_i - b \underbrace{\sum_{i=1}^N \alpha_i y_i}_{= 0} + \sum_{i=1}^N \alpha_i\]
\[\mathcal{L} = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j - \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j + \sum_{i=1}^N \alpha_i\]
\[\mathcal{Q}(\boldsymbol{\alpha}) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle\]
Chegamos ao célebre Problema Dual de Wolfe:
\[\max_{\boldsymbol{\alpha}} \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle\]
\[\text{sujeito a } \alpha_i \ge 0, \quad \forall i = 1, \dots, N \quad \text{e} \quad \sum_{i=1}^N \alpha_i y_i = 0\]
Note que a dimensionalidade original \(d\) desapareceu completamente do problema de otimização: os vetores de dados \(\mathbf{x}_i\) e \(\mathbf{x}_j\) entram na formulação exclusivamente através de seus produtos internos euclidianos \(\langle \mathbf{x}_i, \mathbf{x}_j \rangle\).
2.6 As Condições KKT e a Esparsidade
Pelo Teorema de Karush-Kuhn-Tucker (KKT), as soluções ótimas primais \((\mathbf{w}^*, b^*)\) e duais \(\boldsymbol{\alpha}^*\) devem satisfazer simultaneamente a condição de folga complementar (complementary slackness):
\[\alpha_i^* \big[ y_i((\mathbf{w}^*)^T \mathbf{x}_i + b^*) - 1 \big] = 0, \quad \forall i = 1, \dots, N\]
Essa equação impõe uma dicotomia analítica estrita para cada observação \(i\):
Caso 1: \(\alpha_i^* = 0\).
Nesse caso, a restrição pode ser estritamente satisfeita como desigualdade: \(y_i(\mathbf{w}^T \mathbf{x}_i + b) > 1\). O ponto encontra-se além da margem canônica, bem no interior de seu próprio território. Ele não participa da somatória de \(\mathbf{w} = \sum \alpha_i y_i \mathbf{x}_i\) e não tem absolutamente nenhuma influência na fronteira de decisão.Caso 2: \(\alpha_i^* > 0\).
Para que o produto se anule quando \(\alpha_i^* > 0\), o segundo termo deve ser identicamente nulo: \[y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 = 0 \iff y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1\] O ponto repousa exatamente sobre uma das superfícies da margem canônica. Esses pontos privilegiados são denominados Vetores de Suporte (Support Vectors).
Para classificar um novo ponto \(\mathbf{x}_{\text{novo}}\), a função de decisão é computada como:
\[f(\mathbf{x}_{\text{novo}}) = \operatorname{sign}\left( \sum_{i \in \text{SV}} \alpha_i y_i \langle \mathbf{x}_i, \mathbf{x}_{\text{novo}} \rangle + b \right)\]
O cálculo do termo independente \(b\) é obtido avaliando qualquer vetor de suporte \(j \in \text{SV}\) (onde \(y_j (\mathbf{w}^T \mathbf{x}_j + b) = 1\)):
\[b = y_j - \sum_{i \in \text{SV}} \alpha_i y_i \langle \mathbf{x}_i, \mathbf{x}_j \rangle\]
Na prática numérica, calcula-se a média de \(b\) sobre todos os vetores de suporte para máxima estabilidade aritmética.
2.7 Pausa 2: Dualidade e Esparsidade dos Vetores de Suporte
DicaPergunta aberta provocadora
Imagine que após treinar uma SVM de margem rígida em um banco com \(N = 100.000\) transações financeiras, identificamos que exatamente 42 amostras são vetores de suporte (\(\alpha_i > 0\)). Se um operador acidentalmente deletar \(50.000\) observações do conjunto de treino que possuíam \(\alpha_i = 0\) e retreinar a SVM do zero nas \(50.000\) restantes, o que acontecerá com os parâmetros \((\mathbf{w}, b)\) do hiperplano final?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O vetor de pesos \(\mathbf{w}\) da SVM é expresso exclusivamente como uma combinação linear das amostras de treino que constituem vetores de suporte.
- □ No problema dual de Wolfe, a função objetivo depende da dimensão \(d\) do espaço de entrada unicamente através do custo computacional de calcular os produtos internos \(\langle \mathbf{x}_i, \mathbf{x}_j \rangle\).
- □ As condições KKT de folga complementar garantem que qualquer ponto com \(\alpha_i > 0\) possui distância ortogonal estritamente maior que \(1/\|\mathbf{w}\|\) em relação ao hiperplano separador.
- □ O valor do termo independente \(b\) é determinado unicamente pelo multiplicador de Lagrange \(\alpha_i\) de maior magnitude.
3 Bloco 2: Margem Suave (Soft Margin) e a Perda Hinge
3.1 Variáveis de Folga e Dados Não Separáveis
Na esmagadora maioria das aplicações reais (como no Breast Cancer Wisconsin), as classes não são linearmente separáveis. Há sobreposição estocástica entre distribuições tumorais benignas e malignas, além de possíveis ruídos de medição laboratorial. Se aplicássemos a SVM de margem rígida, o conjunto de restrições \(y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1\) seria inviável, e o algoritmo de otimização falharia sem encontrar solução.
Para superar esse impasse, Corinna Cortes e Vladimir Vapnik (1995) introduziram as variáveis de folga (slack variables) \(\xi_i \ge 0\) para cada observação \(i = 1, \dots, N\):
\[y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0\]
A variável de folga \(\xi_i\) mede a violação física da margem ideal: - \(\xi_i = 0\): O ponto está classificado corretamente e repousa sobre a margem ou além dela (caso ideal). - \(0 < \xi_i \le 1\): O ponto está classificado corretamente (\(y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 0\)), porém penetrou no interior da margem de segurança (violação de margem). - \(\xi_i > 1\): O ponto violou a margem e cruzou a fronteira de decisão, sendo classificado incorretamente pelo hiperplano.
3.2 O Problema Primal Soft Margin e o Hiperparâmetro \(C\)
Para equilibrar o desejo de maximizar a margem (minimizando \(\frac{1}{2}\|\mathbf{w}\|^2\)) com a necessidade de penalizar as violações de margem, formulamos o Problema Primal da SVM de Margem Suave:
\[\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i\]
\[\text{sujeito a } y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1 - \xi_i \quad \text{e} \quad \xi_i \ge 0, \quad \forall i = 1, \dots, N\]
O escalar \(C > 0\) é o hiperparâmetro de regularização: - \(C \to \infty\): As violações \(\xi_i\) são punidas infinitamente. O modelo recai na margem rígida (Hard Margin), com altíssima variância e sensibilidade extrema a ruídos. - \(C \to 0\): O modelo prioriza a minimização de \(\|\mathbf{w}\|^2\), tolerando margens largas e inúmeras violações \(\xi_i\), aumentando o viés estrutural.
3.3 O Dual com Restrições em Caixa (Box Constraints)
Introduzindo os multiplicadores \(\alpha_i \ge 0\) para a restrição \(1 - \xi_i - y_i(\mathbf{w}^T \mathbf{x}_i + b) \le 0\) e \(\mu_i \ge 0\) para a não negatividade \(-\xi_i \le 0\), a Lagrangeana primal é:
\[\mathcal{L}(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i \big[ y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i \big] - \sum_{i=1}^N \mu_i \xi_i\]
As condições de estacionariedade produzem: 1. \(\nabla_{\mathbf{w}} \mathcal{L} = \mathbf{0} \implies \mathbf{w} = \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i\) 2. \(\frac{\partial \mathcal{L}}{\partial b} = 0 \implies \sum_{i=1}^N \alpha_i y_i = 0\) 3. \(\frac{\partial \mathcal{L}}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \implies \alpha_i + \mu_i = C\)
Como \(\mu_i \ge 0\), temos necessariamente que \(\alpha_i \le C\). Combinando com \(\alpha_i \ge 0\), os multiplicadores ficam limitados a uma caixa compacta:
\[0 \le \alpha_i \le C\]
O Problema Dual Soft Margin é idêntico ao de margem rígida, exceto pelo teto \(C\) sobre cada \(\alpha_i\):
\[\max_{\boldsymbol{\alpha}} \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle\]
\[\text{sujeito a } 0 \le \alpha_i \le C, \quad \forall i=1, \dots, N \quad \text{e} \quad \sum_{i=1}^N \alpha_i y_i = 0\]
3.4 Impacto Empírico de \(C\) no Breast Cancer
3.5 A Equivalência com a Perda Hinge (Hinge Loss)
A formulação de margem suave possui uma conexão profunda com o arcabouço clássico de Minimização do Risco Empírico Regularizado.
Observe que as restrições primais impõem \(\xi_i \ge 0\) e \(\xi_i \ge 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b)\). Para minimizar a soma \(\sum \xi_i\), a escolha ótima de \(\xi_i\) em função de \(\mathbf{w}\) e \(b\) é exatamente o menor valor compatível com ambas as desigualdades:
\[\xi_i^* = \max\big(0, 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b)\big)\]
Substituindo \(\xi_i^*\) diretamente na função objetivo primal e dividindo toda a expressão pela constante \(C\), obtemos:
\[\min_{\mathbf{w}, b} \sum_{i=1}^N \max\big(0, 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b)\big) + \frac{1}{2C} \|\mathbf{w}\|^2\]
A função \(L_{\text{hinge}}(y, f(\mathbf{x})) = \max(0, 1 - y f(\mathbf{x}))\) é a célebre Perda Hinge (Perda em Dobradiça).
Isso revela a verdadeira natureza da SVM de margem suave: ela é analiticamente equivalente a minimizar a perda Hinge empírica somada a um termo de regularização Ridge (\(L_2\)) com coeficiente \(\lambda = \frac{1}{C}\).
3.6 Comparação de Funções de Perda
3.7 Pausa 3: Margem Suave, Perda Hinge e o Hiperparâmetro \(C\)
DicaPergunta aberta provocadora
Compare a curva da Perda Hinge com a curva da Perda Logística para \(z = y \cdot f(\mathbf{x}) \ge 2\). O que acontece com o gradiente de cada função nessa região e como esse comportamento matemático explica por que a SVM possui soluções esparsas enquanto a Regressão Logística é obrigada a manter coeficientes dependentes de todas as amostras?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Na formulação de margem suave, um ponto com variável de folga \(\xi_i = 0{,}6\) foi classificado incorretamente pela SVM.
- □ Configurar o hiperparâmetro \(C\) para um valor excessivamente elevado reduz a margem geométrica e eleva o risco de sobreajuste (overfitting).
- □ No problema dual com restrições em caixa, os vetores de suporte livres (aqueles com \(0 < \alpha_i < C\)) situam-se exatamente sobre a margem e possuem folga \(\xi_i = 0\).
- □ A perda Hinge é estritamente diferenciável em todo o seu domínio \(\mathbb{R}\), o que permite o uso de descida de gradiente clássica sem necessidade de subgradientes.
4 Bloco 3: O Truque do Kernel e Fronteiras Não-Lineares
4.1 A Limitação da Linearidade e Espaços de Alta Dimensão
Apesar do rigor de margem máxima, um hiperplano afim \(\mathbf{w}^T \mathbf{x} + b = 0\) é incapaz de separar conjuntos cujas classes formem anéis concêntricos, estruturas entrelaçadas (duas luas) ou a clássica operação lógica XOR.
A estratégia teórica consagrada consiste em projetar os vetores de entrada originais \(\mathbf{x} \in \mathbb{R}^d\) para um espaço de atributos de dimensionalidade muito mais alta (ou até infinita) \(\mathcal{H}\) através de uma transformação não linear determinística:
\[\phi: \mathbb{R}^d \to \mathcal{H}, \quad \mathbf{x} \mapsto \phi(\mathbf{x})\]
Pelo Teorema de Cover sobre a Separabilidade de Padrões (1965), um conjunto de dados não linearmente separável em baixa dimensão tem probabilidade substancialmente maior de tornar-se linearmente separável quando projetado não-linearmente em um espaço de dimensão superior.
Contudo, calcular explicitamente \(\phi(\mathbf{x})\) para cada ponto acarretaria custos computacionais proibitivos de memória e processamento. É aqui que entra a genialidade do Truque do Kernel.
4.2 O Truque do Kernel e o Teorema de Mercer
Relembremos a forma do Problema Dual de Wolfe da SVM:
\[\max_{\boldsymbol{\alpha}} \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}}\]
E a regra final de inferência de classificação:
\[f(\mathbf{x}) = \operatorname{sign}\left( \sum_{i \in \text{SV}} \alpha_i y_i \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle_{\mathcal{H}} + b \right)\]
Perceba o detalhe supremo: em nenhum momento precisamos das coordenadas isoladas de \(\phi(\mathbf{x})\)! O algoritmo exige estritamente a avaliação do produto interno entre pares de vetores no espaço transformado.
Se existir uma função computável diretamente no espaço original \(k(\mathbf{x}, \mathbf{z})\) tal que:
\[k(\mathbf{x}, \mathbf{z}) = \langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle_{\mathcal{H}}\]
podemos substituir todo \(\langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle\) diretamente por \(k(\mathbf{x}_i, \mathbf{x}_j)\) com custo computacional associado a \(\mathbb{R}^d\)!
Teorema de Mercer (1909): Uma função contínua e simétrica \(k(\mathbf{x}, \mathbf{z})\) admite uma representação como produto interno em algum espaço de Hilbert \(\mathcal{H}\) se, e somente se, a matriz de Gram correspondente \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\) for semidefinida positiva (PSD) para qualquer conjunto finito de pontos \(\{\mathbf{x}_1, \dots, \mathbf{x}_N\}\).
4.3 Catálogo de Kernels: Linear, Polinomial e RBF Gaussiano
Os três kernels mais celebrados no aprendizado estatístico são:
Kernel Linear: \[k_{\text{lin}}(\mathbf{x}, \mathbf{z}) = \mathbf{x}^T \mathbf{z} + c\] Recai no hiperplano linear padrão. Ideal quando \(d \gg N\) (ex.: bioinformática, genômica com microarrays, classificação de textos com TF-IDF).
Kernel Polinomial de Grau \(d_p\): \[k_{\text{poly}}(\mathbf{x}, \mathbf{z}) = (\gamma \mathbf{x}^T \mathbf{z} + r)^{d_p}\] Modela interações multivariadas entre atributos até a ordem \(d_p\).
Kernel RBF Gaussiano (Radial Basis Function): \[k_{\text{rbf}}(\mathbf{x}, \mathbf{z}) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{z}\|^2}{2\sigma^2}\right)\] onde \(\gamma = \frac{1}{2\sigma^2} > 0\) é o parâmetro de largura de banda (bandwidth).
4.4 O Kernel RBF e o Espaço de Dimensão Infinita
Por que o Kernel RBF Gaussiano é considerado uma das construções mais elegantes da matemática aplicada?
Considere o caso escalar simplificado com \(\gamma = 1/2\): \(k(x, z) = \exp(-\frac{1}{2}(x - z)^2)\). Expandindo o quadrado:
\[k(x, z) = \exp\left(-\frac{1}{2}x^2\right) \exp\left(-\frac{1}{2}z^2\right) \exp(xz)\]
Aplicando a expansão em série de potências de Taylor para a função exponencial \(\exp(u) = \sum_{k=0}^\infty \frac{u^k}{k!}\):
\[\exp(xz) = \sum_{k=0}^\infty \frac{(xz)^k}{k!} = \sum_{k=0}^\infty \left(\frac{x^k}{\sqrt{k!}}\right) \left(\frac{z^k}{\sqrt{k!}}\right)\]
Multiplicando pelos fatores gaussianos prévios:
\[k(x, z) = \sum_{k=0}^\infty \underbrace{\left( e^{-x^2/2} \frac{x^k}{\sqrt{k!}} \right)}_{\phi_k(x)} \underbrace{\left( e^{-z^2/2} \frac{z^k}{\sqrt{k!}} \right)}_{\phi_k(z)} = \langle \phi(x), \phi(z) \rangle_{\ell^2}\]
O vetor de mapeamento implícito induzido pelo kernel RBF é uma sequência com infinitos termos:
\[\phi(x) = e^{-x^2/2} \left[ 1, \, x, \, \frac{x^2}{\sqrt{2!}}, \, \frac{x^3}{\sqrt{3!}}, \, \dots, \, \frac{x^k}{\sqrt{k!}}, \, \dots \right]^T \in \ell^2\]
Portanto, ao ajustar uma SVM com Kernel RBF Gaussiano, estamos calculando o hiperplano de margem máxima em um espaço de Hilbert de dimensão infinita avaliando meramente uma função exponencial em fração de microssegundo!
4.5 Impacto do Hiperparâmetro \(\gamma\) no Breast Cancer
4.6 Pausa 4: O Truque do Kernel e a Geometria de Hilbert
DicaPergunta aberta provocadora
Um analista de dados afirma: “Já que o Kernel RBF projeta os dados em um espaço de dimensão infinita, qualquer conjunto de dados com \(N\) observações se tornará linearmente separável; logo, podemos dispensar as variáveis de folga \(\xi_i\) e usar sempre \(C \to \infty\).” Explique o erro conceitual dessa afirmação e descreva o que acontecerá com a fronteira de decisão se os dados contiverem rótulos com ruído.
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Para que uma função \(k(\mathbf{x}, \mathbf{z})\) seja um kernel válido pelo Teorema de Mercer, é estritamente necessário que os autovalores da matriz de Gram sejam todos estritamente negativos.
- □ No Kernel RBF Gaussiano \(k(\mathbf{x}, \mathbf{z}) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2)\), o valor do produto interno atinge seu máximo quando os vetores são idênticos (\(\mathbf{x} = \mathbf{z}\)), decaindo para zero conforme a distância euclidiana tende ao infinito.
- □ Aumentar excessivamente o hiperparâmetro \(\gamma\) da RBF força o modelo a criar ilhas de decisão isoladas em torno dos vetores de suporte individuais, provocando sobreajuste severo.
- □ Ao utilizar o Truque do Kernel com a RBF, o tempo computacional para avaliar a fronteira de decisão em um novo ponto de teste depende linearmente da dimensão infinita do espaço de Hilbert.
5 Bloco 4: Calibração de Platt e Support Vector Regression
5.1 O Escore da SVM e a Ausência de Probabilidades
A predição da SVM é governada pelo valor escalar de margem:
\[f(\mathbf{x}) = \sum_{i \in \text{SV}} \alpha_i y_i k(\mathbf{x}_i, \mathbf{x}) + b \in (-\infty, +\infty)\]
A decisão binária utiliza unicamente a regra \(\hat{y} = \operatorname{sign}(f(\mathbf{x}))\).
Entretanto, em aplicações clínicas críticas — como decidir se uma paciente deve ser submetida a uma biópsia invasiva sob risco cirúrgico —, o médico não quer apenas saber se \(f(\mathbf{x}) > 0\); ele precisa de uma estimativa calibrada da probabilidade a posteriori:
\[P(Y = +1 \mid \mathbf{x})\]
A SVM clássica não é um modelo probabilístico. O escore \(f(\mathbf{x})\) mede apenas a distância funcional assinada até o hiperplano. Como converter \(f(\mathbf{x})\) em probabilidade legítima sem perder as virtudes de margem da SVM?
5.2 Calibração de Platt (1999)
Em 1999, John Platt propôs um método elegante e hoje canônico: ajustar uma função logística paramétrica univariada diretamente sobre os escores \(f(\mathbf{x})\) produzidos pela SVM:
\[P(Y = +1 \mid \mathbf{x}) = \frac{1}{1 + \exp\big(A \cdot f(\mathbf{x}) + B\big)}\]
onde os parâmetros escalares \(A, B \in \mathbb{R}\) são determinados por Máxima Verossimilhança via entropia cruzada.
Cuidado Crítico com Vazamento (Data Leakage): Se ajustarmos os parâmetros \(A\) e \(B\) da sigmoide sobre os mesmos dados de treino utilizados para determinar \(\mathbf{w}\) e \(b\), as probabilidades serão absurdamente superconfiantes e mal calibradas, porque os escores de treino \(f(\mathbf{x}_i)\) já sofreram sobreajuste.
Por essa razão, Platt estipulou que os escores devem ser gerados via validação cruzada fora-da-amostra (out-of-fold cross-validation). É exatamente este procedimento que o
CalibratedClassifierCVdo scikit-learn executa.
5.3 Curva de Calibração: Escore vs. Probabilidade de Platt
5.4 Extensão para Regressão: Support Vector Regression (\(\varepsilon\)-SVR)
A genialidade do princípio de esparsidade por margem não se limita à classificação: ela estende-se naturalmente à regressão através da Support Vector Regression (\(\varepsilon\)-SVR) proposta por Vapnik (1995).
Na regressão linear clássica, o erro quadrático \((y - f(\mathbf{x}))^2\) penaliza qualquer resíduo infinitesimal. Na \(\varepsilon\)-SVR, introduzimos a função de perda \(\varepsilon\)-insensível (\(\varepsilon\)-insensitive loss):
\[L_\varepsilon(y, f(\mathbf{x})) = \max\big(0, |y - f(\mathbf{x})| - \varepsilon\big)\]
Essa perda cria um tubo de tolerância cilíndrico de raio \(\varepsilon\) ao redor da curva estimada: 1. Qualquer resíduo com \(|y_i - f(\mathbf{x}_i)| \le \varepsilon\) sofre custo estritamente zero. 2. Apenas os pontos que caem fora do tubo de tolerância exercem tração no modelo e recebem multiplicadores de Lagrange \(\alpha_i > 0\) ou \(\alpha_i^* > 0\).
Isso produz uma solução de regressão esparsa, que ignora o ruído de fundo contido no interior do tubo de tolerância.
5.5 O Tubo de Tolerância da SVR em Diagrama
5.6 Pausa 5: Calibração de Platt e o Tubo da SVR
DicaPergunta aberta provocadora
Na Support Vector Regression (\(\varepsilon\)-SVR), o cientista decide configurar o raio do tubo \(\varepsilon = 0\). O que acontece com a esparsidade da solução resultante? O modelo ainda desfrutará da propriedade de ignorar observações não informativas?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ No método de Platt Scaling, estimar a sigmoide diretamente sobre os escores calculados na base de treino sem validação cruzada out-of-fold produz probabilidades confiáveis e imunes a viés de sobreajuste.
- □ Na Support Vector Regression (\(\varepsilon\)-SVR), qualquer amostra de treino cujo erro absoluto \(|y_i - f(\mathbf{x}_i)|\) seja menor ou igual a \(\varepsilon\) possui multiplicadores de Lagrange nulos e não atua como vetor de suporte.
- □ O escore contínuo da SVM \(f(\mathbf{x})\) fornece nativamente uma probabilidade a posteriori calibrada de classe, tornando redundante qualquer calibração adicional.
- □ Na \(\varepsilon\)-SVR, aumentar o valor de \(\varepsilon\) reduz o número total de vetores de suporte do modelo, tornando a representação da função mais esparsa.
6 Fechamento da Aula
6.1 Retomando as Cinco Perguntas Centrais
Ao longo desta aula, transformamos a geometria dos hiperplanos em um arcabouço rigoroso de aprendizado estatístico. Sintetizamos as respostas às cinco perguntas fundacionais:
- Margem Máxima Canônica: A margem física é \(\frac{2}{\|\mathbf{w}\|}\) sob a escala canônica \(y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1\). Maximizar essa folga geométrica equivale a minimizar a energia quadrática \(\|\mathbf{w}\|^2/2\), resultando em um problema de otimização estritamente convexo imune a mínimos locais espúrios.
- Dualidade e Esparsidade: Pelo Teorema de Wolfe e condições KKT de folga complementar (\(\alpha_i [y_i f(\mathbf{x}_i) - 1] = 0\)), pontos que residem além da margem têm \(\alpha_i = 0\) e são completamente ignorados. A fronteira depende unicamente dos vetores de suporte (\(\alpha_i > 0\)).
- Margem Suave e Perda Hinge: A introdução de variáveis de folga \(\xi_i \ge 0\) penalizadas por \(C\) equivale à minimização da perda Hinge regularizada \(\max(0, 1 - y f(\mathbf{x})) + \lambda \|\mathbf{w}\|^2\). O patamar horizontal da Hinge para \(y f \ge 1\) garante a esparsidade exata de \(\boldsymbol{\alpha}\).
- O Truque do Kernel: Pelo Teorema de Mercer, produtos internos em espaços de Hilbert de dimensão infinita (RBF) são avaliados diretamente no espaço original via \(k(\mathbf{x}, \mathbf{z}) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2)\) com custo aritmético elementar.
- Calibração de Platt e SVR: Os escores determinísticos \(f(\mathbf{x})\) são calibrados probabilisticamente ajustando-se uma sigmoide sobre previsões out-of-fold. Na regressão (\(\varepsilon\)-SVR), o tubo de tolerância \(\varepsilon\)-insensível restaura a esparsidade ao zerar o custo de pequenas oscilações de ruído.
6.2 Quadro Comparativo de Algoritmos Supervisionados
| Propriedade | Regressão Logística | Gradient Boosting | SVM Linear | SVM Kernel RBF | SVR (\(\varepsilon\)-insensível) |
|---|---|---|---|---|---|
| Alvo Principal | Probabilidade \(p(y \mid \mathbf{x})\) | \(\log\)-odds populacional | Hiperplano de margem | Hiperplano em \(\mathcal{H}\) | Tubo esparso \(\varepsilon\) |
| Função de Perda | Entropia Cruzada | Deviance / Quadrática | Perda Hinge | Perda Hinge com Kernel | \(\varepsilon\)-insensível |
| Esparsidade | Nenhuma (\(\forall i\) pesa) | Nenhuma | Exata em dados | Exata em dados | Exata em dados |
| Capacidade Não Linear | Apenas via features | Muito alta (árvores) | Nenhuma (linear pura) | Infinita (Hilbert) | Infinita (Hilbert) |
| Calibração Nativa | Sim (direta na sigmoide) | Sim (na deviance) | Não (Platt Scaling) | Não (Platt Scaling) | N/A (regressão) |
| Escalonamento | Recomendável | Dispensável | Obrigatório! | Obrigatório! | Obrigatório! |
6.3 Ponte para a Aula 12: Do Kernel Fixo ao Deep Learning
Nesta aula, testemunhamos o poder quase mágico do Truque do Kernel: ao projetar dados em espaços de Hilbert de alta dimensão, fronteiras arbitrariamente complexas tornam-se hiperplanos lineares de margem máxima.
No entanto, o Truque do Kernel carrega uma limitação arquitetural profunda: o kernel \(k(\mathbf{x}, \mathbf{z})\) é escolhido e fixado a priori pelo engenheiro humano (seja ele polinomial ou gaussiano). O algoritmo projeta os dados em uma base fixa pré-definida e apenas otimiza pesos lineares \(\boldsymbol{\alpha}\) sobre essa representação estática.
O que aconteceria se, em vez de fixar manualmente a função de mapeamento \(\phi(\mathbf{x})\), construíssemos uma arquitetura computacional capaz de aprender as transformações não lineares ótimas a partir dos próprios dados de forma adaptativa e em múltiplas camadas hierárquicas?
Essa é a grande revolução que exploraremos na próxima aula:
\[\mathbf{x} \longrightarrow \mathbf{h}^{(1)} = \sigma(W_1 \mathbf{x} + \mathbf{b}_1) \longrightarrow \mathbf{h}^{(2)} = \sigma(W_2 \mathbf{h}^{(1)} + \mathbf{b}_2) \longrightarrow \dots \longrightarrow \hat{y}\]
Na Aula 12: Redes Neurais e Aprendizado de Representações, investigaremos como o algoritmo de Backpropagation (diferenciação automática reversa) permite treinar extratores hierárquicos de características profundas, inaugurando a era do Deep Learning.