Aula 10: Gradient Boosting e Otimização Numérica no Espaço de Funções
Supervised Learning
1 Revisão e Introdução
1.1 Revisão Cuidadosa: O Que a Aula 9 Deixou Pronto
Na Aula 9, inauguramos a Parte 3 do curso analisando como a teoria estatística de agregação de modelos opera sobre a decomposição do Erro Quadrático Médio Esperado (\(\text{EMSE} = \text{Bias}^2 + \text{Var} + \sigma^2\), Aula 8). Desenvolvemos o algoritmo de Bagging (Bootstrap Aggregation) e sua extensão crucial, as Florestas Aleatórias (Random Forests, Breiman 2001).
O pilar teórico da Aula 9 estabeleceu que a média de \(B\) estimadores identicamente distribuídos \(T_1, \dots, T_B\), cada qual com variância \(\sigma^2\) e correlação positiva par-a-par \(\rho\), possui variância governada pela fórmula exata:
\[\text{Var}\left(\frac{1}{B}\sum_{b=1}^B T_b\right) = \rho \sigma^2 + \frac{1-\rho}{B}\sigma^2\]
Dessa formulação emergiram três conclusões estruturais inescapáveis: 1. Preservação Rígida do Viés: Pela linearidade da esperança, \(\mathbb{E}\left[\frac{1}{B}\sum_{b=1}^B T_b\right] = \mathbb{E}[T]\). O Bagging é incapaz de atenuar o erro estrutural de especificação de um modelo. Se o estimador base for excessivamente rígido (alto viés), o ensemble agregado continuará sofrendo de subajuste (underfitting). 2. Dependência de Modelos de Alta Capacidade: Para que o Bagging produza um preditor de alto desempenho, os modelos base precisam possuir baixo viés inicial. Por essa razão, alimentamos o Bagging com árvores CART profundas e não podadas (Aula 3), cuja capacidade não paramétrica elimina o viés, tolerando sua alta variância porque a agregação paralela a amortecerá. 3. O Gargalo da Correlação \(\rho\): Mesmo quando \(B \to \infty\), o termo \(\frac{1-\rho}{B}\sigma^2\) decai a zero, mas o piso \(\rho \sigma^2\) permanece inalterado. As Florestas Aleatórias contornam essa barreira sorteando um subconjunto aleatório de \(m \le p\) variáveis por nó, quebrando a correlação entre as árvores.
Contudo, essa estratégia deixa uma lacuna teórica fundamental: e se não dispusermos de estimadores de baixo viés? E se nossos modelos base forem deliberadamente simples, rápidos e de alto viés (weak learners), como cortes univariados simples (decision stumps)?
1.2 Ideia Central: Da Média Paralela à Adição Sequencial
A ideia central do Boosting é inverter completamente a arquitetura de ensemble: em vez de construir árvores profundas em paralelo e calcular sua média aritmética, construímos uma sequência acoplada de árvores rasas (weak learners), na qual cada novo modelo é treinado com a missão explícita de corrigir os erros cometidos pelo comitê acumulado até aquele ponto.
A representação final do modelo não é uma média simples, mas uma expansão aditiva de funções:
\[f_M(\mathbf{x}) = f_0(\mathbf{x}) + \sum_{m=1}^M \nu \cdot h_m(\mathbf{x})\]
onde \(f_0(\mathbf{x})\) é uma estimativa constante inicial, \(h_m(\mathbf{x})\) é uma árvore de regressão ajustada na iteração \(m\), e \(\nu \in (0, 1]\) é um fator de encolhimento (shrinkage).
O salto intelectual revolucionário, formalizado por Jerome Friedman (2001), foi provar que o ajuste de uma árvore aos “resíduos” de um modelo anterior nada mais é do que uma descida de gradiente mais íngreme (steepest descent) executada no espaço não paramétrico das funções. Em vez de atualizar parâmetros finitos em \(\mathbb{R}^d\), damos passos direcionais em direção ao mínimo da função de perda no espaço de Hilbert das hipóteses!
1.3 Roteiro da Aula
Para explorar com rigor matemático essa teoria e operacionalizá-la em algoritmos de ponta, estruturamos nossa investigação em cinco perguntas condutoras:
- Como o Boosting inverte formalmente os princípios estatísticos do Bagging, reduzindo sistematicamente o viés a partir de modelos fracos?
- Por que o algoritmo AdaBoost.M1 (Freund & Schapire, 1997) equivale a um Modelo Aditivo em Estágios (FSAM) minimizando a perda exponencial?
- Qual é a generalização geométrica de Friedman (2001) ao projetar o vetor gradiente do espaço de dados sobre o espaço de árvores de decisão?
- Como derivar os pseudo-resíduos e os valores ótimos nas folhas para perdas quadrática, absoluta, Huber e deviance logística?
- Como o hiperparâmetro de encolhimento (\(\nu\)) e a profundidade máxima das árvores (\(J\) nós terminais) controlam o sobreajuste e a ordem de interação entre atributos?
1.4 Problema Motivador: California Housing
Para tornar a necessidade do Boosting evidente antes de mergulharmos no formalismo analítico, retomamos o dataset California Housing (gvlassis/california_housing), com as mesmas 2.000 instâncias de treino e 1.000 instâncias de teste empregadas na Aula 9. Nosso objetivo é estimar a mediana do valor dos imóveis (MedHouseVal).
Acompanhemos a progressão empírica do erro quadrático médio de teste (\(\text{MSE}_{\text{test}}\)) em cinco estágios: 1. Preditor Constante Inicial (\(f_0\)): A média amostral de treino \(\bar{y} = 2{,}0123\) produz um erro de teste catastrófico de \(\text{MSE} = 1{,}3417\). 2. Decision Stump Isolado (\(J = 2\)): Uma única árvore podada na profundidade 1 (com apenas um corte binário baseado em MedInc) sofre de subajuste severo devido ao alto viés estrutural: \(\text{MSE}_{\text{test}} = 0{,}9984\). 3. Bagging de 100 Stumps: Se aplicarmos o algoritmo da Aula 9 sobre esses stumps, o erro de teste quase não se altera (\(\text{MSE} \approx 0{,}995\)), confirmando que a média paralela preserva o viés original (\(\mathbb{E}[\bar{T}] = \mathbb{E}[T]\)). 4. Gradient Boosting de 100 Stumps (\(\nu = 0{,}1\)): Ao conectar os mesmos 100 stumps sequencialmente via Gradient Boosting, onde cada stump aprende o resíduo do comitê acumulado, o erro despenca para \(\text{MSE}_{\text{test}} = 0{,}4709\) — uma redução superior a \(52\%\) no erro residual sem alterar a complexidade individual de nenhum nó! 5. Gradient Tree Boosting com \(J = 8\) (Profundidade 3, \(\nu = 0{,}1\)): Ao permitir que cada árvore capture interações de até 3ª ordem, o erro cai para \(\text{MSE}_{\text{test}} = 0{,}2793\), superando com folga o desempenho da Random Forest de 100 árvores completas da Aula 9 (\(\text{MSE}_{\text{test}} = 0{,}2897\)).
1.5 Pausa 1: A Inversão Filosófica
DicaPergunta aberta provocadora
Um cientista de dados propõe treinar um Gradient Tree Boosting utilizando árvores profundas e não podadas com \(J = 256\) nós terminais, exatamente como fez na Random Forest da Aula 9. Avalie o que ocorrerá com os resíduos das iterações subsequentes e com o erro de generalização no conjunto de teste.
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Pela decomposição analítica do EMSE, o Bagging reduz variância via média paralela de estimadores instáveis, enquanto o Boosting reduz viés ajustando modelos sequencialmente aos erros residuais.
- □ Como o Boosting adiciona novos estimadores que reduzem o erro de treinamento, aumentar indefinidamente o número de iterações \(M\) jamais causará sobreajuste (overfitting).
- □ Se os modelos base possuírem alto viés inicial (como decision stumps), a aplicação do Bagging resulta em ganho quase nulo devido à preservação da esperança \(\mathbb{E}[\bar{T}] = \mathbb{E}[T]\).
- □ Uma árvore de regressão com profundidade 1 (decision stump) é capaz de capturar interações não lineares entre pares de preditores quando combinada via Bagging.
2 Intuição — Descida de Gradiente no Espaço de Funções
2.1 A Imagem Mental: O Jogador de Golfe e os Resíduos
Considere a metáfora clássica do jogador de golfe que tenta colocar a bola no buraco situado a uma distância \(y\): 1. Na primeira tacada, o jogador utiliza uma régua simples e atinge a posição \(f_0\). Ele constata que a bola ainda está a uma distância residual \(r_1 = y - f_0\) do buraco. 2. Em vez de voltar ao ponto de partida e tentar uma tacada completamente independente (como faria o Bagging), ele caminha até a nova posição e desfere uma segunda tacada com o objetivo explícito de cobrir o resíduo \(r_1\). 3. Se a segunda tacada avançar \(h_1 \approx r_1\), a nova posição acumulada será \(f_1 = f_0 + h_1\), restando um resíduo bem menor \(r_2 = y - f_1\). 4. O processo repete-se sequencialmente: cada tacada \(h_m\) mira exatamente no resíduo remanescente \(r_m = y - f_{m-1}\).
Essa analogia intuitiva ilustra com clareza o caso em que a perda utilizada é a quadrática (\(L_2\)). Contudo, e se o nosso objetivo não for minimizar a distância quadrática, mas sim o valor absoluto da distância (\(L_1\)), a perda de Huber ou a deviance logística de uma classificação binária? É aqui que entra o salto de abstração da otimização numérica funcional.
2.2 O Mecanismo em Diagrama: Descida Funcional
No espaço vetorial \(\mathbb{R}^N\) formado pelas predições do modelo nas \(N\) observações de treinamento, o vetor \(\mathbf{f}_{m-1} = [f_{m-1}(\mathbf{x}_1), \dots, f_{m-1}(\mathbf{x}_N)]^T\) representa o estado atual do ensemble. O vetor gradiente negativo \(-\mathbf{g}_m = -\nabla_{\mathbf{f}} L \in \mathbb{R}^N\) aponta na direção de descida mais íngreme (steepest descent).
Contudo, não podemos simplesmente adotar \(-\mathbf{g}_m\) como nossa atualização direta, pois esse vetor é discreto e existe apenas nas coordenadas dos dados observados de treino; ele não fornece nenhuma regra para predizer novos pontos \(\mathbf{x} \notin \mathcal{D}\). A solução de Friedman consiste em projetar ortogonalmente o vetor gradiente irrestrito \(-\mathbf{g}_m\) sobre o espaço de funções parametrizadas por árvores de decisão \(\mathcal{H}_{\text{tree}}\), ajustando uma árvore \(h_m(\mathbf{x})\) por mínimos quadrados aos pseudo-resíduos.
2.3 Pausa 2: Descida de Gradiente no Espaço de Funções
DicaPergunta aberta provocadora
Por que não podemos simplesmente atualizar diretamente os valores das predições de treino fazendo \(f_m(\mathbf{x}_i) = f_{m-1}(\mathbf{x}_i) + \rho r_{im}\) para cada ponto observado \(i = 1, \dots, N\), dispensando completamente a indução da árvore de regressão?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O vetor \(-\mathbf{g}_m \in \mathbb{R}^N\) representa a direção de descida mais íngreme da função de perda avaliada no conjunto de treinamento.
- □ Atualizar diretamente as predições nos \(N\) pontos de treino sem ajustar um modelo base produz um preditor capaz de generalizar perfeitamente para novos dados de teste.
- □ Ajustar uma árvore de regressão aos pseudo-resíduos via mínimos quadrados corresponde formalmente à projeção ortogonal do gradiente não paramétrico sobre a classe de hipóteses de árvores.
- □ A partição induzida pela árvore permite que a direção do gradiente seja extrapolada e avaliada em qualquer ponto \(\mathbf{x} \in \mathbb{R}^p\) do domínio.
3 Bloco 1: Modelos Aditivos em Estágios e AdaBoost
3.1 Modelos Aditivos em Estágios Progressivos (FSAM)
A formulação geral de um modelo aditivo com funções de base parametrizadas é dada por:
\[f_M(\mathbf{x}) = \sum_{m=1}^M \beta_m h(\mathbf{x}; \gamma_m)\]
onde \(\beta_m\) são os multiplicadores escalares de expansão e \(h(\mathbf{x}; \gamma_m)\) são funções base elementares (como árvores CART simples, onde \(\gamma_m\) parametriza as variáveis de corte e os limiares de divisão).
O ajuste ótimo simultâneo de todos os \(M\) termos requer resolver:
\[\min_{\{\beta_m, \gamma_m\}_{m=1}^M} \sum_{i=1}^N L\left(y_i, \sum_{m=1}^M \beta_m h(\mathbf{x}_i; \gamma_m)\right)\]
Essa otimização global multivariada é intratável computacionalmente para funções de base não lineares como árvores de decisão. Para contornar esse obstáculo, emprega-se a heurística gulosa de Modelos Aditivos em Estágios Progressivos (Forward Stagewise Additive Modeling - FSAM): em cada iteração \(m\), congelamos todos os termos acumulados \(f_{m-1}(\mathbf{x})\) e otimizamos exclusivamente os parâmetros da nova função base:
\[(\beta_m, \gamma_m) = \arg\min_{\beta, \gamma} \sum_{i=1}^N L\big(y_i, f_{m-1}(\mathbf{x}_i) + \beta h(\mathbf{x}_i; \gamma)\big)\]
3.2 O Algoritmo AdaBoost.M1 (Freund & Schapire, 1997)
O algoritmo AdaBoost.M1 (Adaptive Boosting, Freund & Schapire, 1997) foi o primeiro algoritmo de boosting amplamente bem-sucedido na prática. Originalmente concebido sob a perspectiva da teoria de aprendizado computacional (PAC learning), seu objetivo era resolver uma questão teórica proposta por Valiant (1984) e Kearns & Valiant (1989): é possível combinar um conjunto de classificadores fracos (com acurácia apenas ligeiramente superior ao chute aleatório) para construir um classificador forte com acurácia arbitrariamente alta?
A mecânica operacional do AdaBoost.M1 para classificação binária (\(y_i \in \{-1, +1\}\)) opera em \(M\) iterações sequenciais com pesos adaptativos sobre as instâncias:
A intuição prática é imediata: se uma instância \(i\) for classificada corretamente por \(h_m\) (\(y_i h_m(\mathbf{x}_i) = +1\)), seu peso é multiplicado pelo fator atenuador \(e^{-\alpha_m} < 1\). Se for classificada incorretamente (\(y_i h_m(\mathbf{x}_i) = -1\)), seu peso é multiplicado pelo fator amplificador \(e^{+\alpha_m} > 1\). Assim, a cada rodada, o conjunto de dados é “deformado”, concentrando a probabilidade de amostragem nos exemplos mais difíceis e forçando o próximo classificador \(h_{m+1}\) a se especializar nas falhas do comitê.
3.3 Exemplo Ilustrativo: AdaBoost em Ação
Para consolidar a intuição de como os pesos adaptativos deformam o espaço amostral e forçam o algoritmo a corrigir seus próprios erros, analisamos o exemplo clássico de Freund & Schapire (1997) e Bishop (2006, PRML Fig. 14.1) com 10 observações bidimensionais pertencentes a duas classes (\(+1\) círculos azuis e \(-1\) quadrados laranjas).
Utilizamos como aprendizes fracos decision stumps (árvores de decisão com profundidade 1, capazes de traçar apenas uma reta horizontal ou vertical paralela aos eixos):
Iteração 1 (\(m=1\)):
Todos os 10 pontos iniciam com pesos idênticos \(w_i^{(1)} = 0{,}10\). O primeiro stump \(h_1\) traça uma linha vertical em \(x_1 \approx 0{,}33\). Ele acerta os 3 pontos azuis da esquerda e os 4 pontos laranjas do centro, mas erra os 3 pontos azuis da direita (destacados em vermelho pontilhado). Com taxa de erro ponderada \(\text{err}_1 = 0{,}30\), seu voto no comitê é \(\alpha_1 = \frac{1}{2}\ln(0{,}70 / 0{,}30) \approx 0{,}42\).Iteração 2 (\(m=2\)):
Os pesos são atualizados: os 3 pontos azuis errados têm seus pesos multiplicados por \(e^{+\alpha_1}\), tornando-se muito maiores visualmente no gráfico (\(w_i \approx 0{,}167\)). O segundo stump \(h_2\) é forçado a priorizar esses pontos de alto peso e traça uma linha vertical em \(x_1 \approx 0{,}68\), classificando corretamente os 3 pontos da direita, mas errando os 3 pontos da esquerda. Seu peso no comitê é \(\alpha_2 \approx 0{,}65\).Iteração 3 (\(m=3\)):
Agora os pontos azuis da esquerda acumulam maior peso e forçam o terceiro stump \(h_3\) a focar na separação remanescente, com \(\alpha_3 \approx 0{,}75\).Comitê Final \(H(\mathbf{x}) = \text{sign}\left(\sum_{m=1}^3 \alpha_m h_m(\mathbf{x})\right)\):
Ao combinar os votos ponderados dos 3 stumps unidimensionais simples, o comitê final forma uma fronteira composta não linear que isola perfeitamente os pontos laranjas centrais dos pontos azuis laterais, atingindo acurácia de 100% (zero erro de treinamento)!
3.4 AdaBoost como Otimização Gulosa sob Perda Exponencial
Durante anos após sua criação, o AdaBoost era visto pela comunidade como um algoritmo misterioso e quase heurístico. Esse cenário mudou com o trabalho seminal de Friedman, Hastie e Tibshirani (2000, ESL §10.2–10.4), que revelaram sua base estatística: o AdaBoost.M1 é analiticamente equivalente ao Forward Stagewise Additive Modeling (FSAM) sob a função de perda exponencial:
\[L(y, f(\mathbf{x})) = \exp\big(-y f(\mathbf{x})\big), \quad y \in \{-1, +1\}\]
No passo \(m\), já possuímos o comitê acumulado \(f_{m-1}(\mathbf{x})\) e queremos adicionar um novo termo \(\alpha h(\mathbf{x})\), com \(h(\mathbf{x}) \in \{-1, +1\}\) e \(\alpha > 0\):
\[\min_{\alpha, h} \sum_{i=1}^N \exp\Big( -y_i \big(f_{m-1}(\mathbf{x}_i) + \alpha h(\mathbf{x}_i)\big) \Big) = \sum_{i=1}^N \underbrace{\exp\big(-y_i f_{m-1}(\mathbf{x}_i)\big)}_{w_i^{(m)}} \exp\big(-\alpha y_i h(\mathbf{x}_i)\big)\]
O termo \(w_i^{(m)} \equiv \exp(-y_i f_{m-1}(\mathbf{x}_i))\) não depende do novo modelo: ele é simplesmente o peso acumulado da observação \(i\) até a iteração \(m\). Se o modelo atual acerta o exemplo com folga (\(y_i f_{m-1} > 0\)), seu peso decai para quase zero; se o modelo erra (\(y_i f_{m-1} < 0\)), seu peso cresce exponencialmente.
3.4.1 A Decomposição em Acertos e Erros
Como \(y_i, h(\mathbf{x}_i) \in \{-1, +1\}\), o produto \(y_i h(\mathbf{x}_i)\) só pode assumir dois valores: - Acerto (\(y_i = h(\mathbf{x}_i)\)): \(y_i h(\mathbf{x}_i) = +1 \implies \text{fator } e^{-\alpha}\). - Erro (\(y_i \neq h(\mathbf{x}_i)\)): \(y_i h(\mathbf{x}_i) = -1 \implies \text{fator } e^{+\alpha}\).
Podemos particionar a perda total diretamente entre os exemplos que o modelo acerta e os que ele erra:
\[\text{Perda}(\alpha, h) = e^{-\alpha} \sum_{y_i = h(\mathbf{x}_i)} w_i^{(m)} + e^{+\alpha} \sum_{y_i \neq h(\mathbf{x}_i)} w_i^{(m)}\]
Dividindo pela soma total dos pesos \(w_m = \sum_{i=1}^N w_i^{(m)}\) e definindo a taxa de erro ponderada \(\text{err}_m \equiv \frac{\sum_{\text{erros}} w_i^{(m)}}{w_m}\), a fração de acertos é naturalmente \((1 - \text{err}_m)\). A perda média resume-se à elegante combinação convexa:
\[\frac{\text{Perda}}{w_m} = (1 - \text{err}_m) e^{-\alpha} + \text{err}_m e^{+\alpha}\]
3.5 As Duas Decisões do AdaBoost em Forma Direta
A partir da perda média ponderada por \(w_m\), decorrem imediatamente as duas regras fundamentais do AdaBoost:
Quem deve ser o classificador base \(h_m\)?
Para qualquer \(\alpha > 0\), o custo unitário do erro (\(e^\alpha\)) é estritamente superior ao custo do acerto (\(e^{-\alpha}\)). Para minimizar a perda, o classificador \(h\) deve concentrar o máximo de peso possível nos acertos e o mínimo nos erros. Logo, \(h_m\) é o classificador que minimiza a taxa de erro ponderada: \[h_m(\mathbf{x}) = \arg\min_h \sum_{i=1}^N w_i^{(m)} \mathbb{I}(y_i \neq h(\mathbf{x}_i))\]Quanto deve valer o passo / voto \(\alpha_m\)?
Com \(h_m\) fixado, derivamos a perda em relação a \(\alpha\) para encontrar o ponto de mínimo (o equilíbrio ótimo entre o benefício dos acertos e o custo dos erros): \[\frac{\partial}{\partial \alpha} \Big[ (1 - \text{err}_m) e^{-\alpha} + \text{err}_m e^{+\alpha} \Big] = -(1 - \text{err}_m) e^{-\alpha} + \text{err}_m e^{+\alpha} = 0\] \[\implies \text{err}_m e^{+\alpha} = (1 - \text{err}_m) e^{-\alpha} \implies e^{2\alpha} = \frac{1 - \text{err}_m}{\text{err}_m}\] Aplicando o logaritmo natural em ambos os lados, surge a célebre fórmula do AdaBoost: \[\alpha_m = \frac{1}{2} \ln \left( \frac{1 - \text{err}_m}{\text{err}_m} \right)\]
Intuição dos Três Regimes de \(\alpha_m\): - Classificador excelente (\(\text{err}_m \to 0\)): \(\frac{1 - \text{err}}{\text{err}} \to \infty \implies \alpha_m \to +\infty\) (ganha peso altíssimo no comitê). - Classificador cara-ou-coroa (\(\text{err}_m = 0{,}5\)): \(\frac{0{,}5}{0{,}5} = 1 \implies \alpha_m = \frac{1}{2}\ln(1) = 0\) (não tem poder preditivo e é sumariamente ignorado). - Classificador pior que o acaso (\(\text{err}_m > 0{,}5\)): \(\alpha_m < 0\) (o comitê inverte automaticamente suas predições, transformando seus erros em acertos!).
3.6 Atualização de Pesos: A Mecânica Iterativa
Com o classificador base \(h_m(\mathbf{x})\) e seu respectivo coeficiente \(\alpha_m\) determinados, o comitê acumulado é atualizado adicionando a nova regra:
\[f_m(\mathbf{x}) = f_{m-1}(\mathbf{x}) + \alpha_m h_m(\mathbf{x})\]
Ao avaliar a definição analítica do peso da próxima iteração, \(w_i^{(m+1)} \equiv \exp(-y_i f_m(\mathbf{x}_i))\), obtemos diretamente a regra de recorrência do AdaBoost.M1:
\[w_i^{(m+1)} = \exp\Big(-y_i \big(f_{m-1}(\mathbf{x}_i) + \alpha_m h_m(\mathbf{x}_i)\big)\Big) = w_i^{(m)} \exp\big(-\alpha_m y_i h_m(\mathbf{x}_i)\big)\]
Essa atualização atua de forma assimétrica e adaptativa sobre cada instância individual: - Se a observação foi classificada corretamente (\(y_i h_m(\mathbf{x}_i) = +1\)):
O peso é multiplicado pelo fator atenuador \(e^{-\alpha_m} < 1\), aliviando a importância daquela amostra nas próximas rodadas. - Se a observação foi classificada incorretamente (\(y_i h_m(\mathbf{x}_i) = -1\)):
O peso é multiplicado pelo fator amplificador \(e^{+\alpha_m} > 1\), aumentando a pressão sobre os classificadores seguintes para corrigir esse erro.
3.7 Razão Erro/Acerto e a Conexão com Bayes e Logística
A agressividade dessa reponderação fica evidente quando comparamos a evolução relativa entre uma instância errada e uma instância correta:
\[\frac{w_{\text{erro}}^{(m+1)}}{w_{\text{acerto}}^{(m+1)}} = \frac{w_{\text{erro}}^{(m)} e^{+\alpha_m}}{w_{\text{acerto}}^{(m)} e^{-\alpha_m}} = \frac{w_{\text{erro}}^{(m)}}{w_{\text{acerto}}^{(m)}} \cdot e^{2\alpha_m}\]
Lembrando que \(e^{2\alpha_m} = \frac{1 - \text{err}_m}{\text{err}_m}\), obtemos a identidade fundamental:
\[\frac{w_{\text{erro}}^{(m+1)}}{w_{\text{acerto}}^{(m+1)}} = \frac{w_{\text{erro}}^{(m)}}{w_{\text{acerto}}^{(m)}} \cdot \left( \frac{1 - \text{err}_m}{\text{err}_m} \right)\]
Isso significa que, a cada iteração, as instâncias incorretas ganham uma vantagem multiplicativa exatamente igual à razão de chances (odds) do acerto sobre o erro \(\frac{1 - \text{err}_m}{\text{err}_m}\). Por exemplo: - Com taxa de erro \(\text{err}_m = 0{,}20\) (\(80\%\) de acerto), a razão salta por um fator de \(\frac{0{,}80}{0{,}20} = 4\). Cada erro passa a valer 4 vezes mais que cada acerto imediatamente na rodada seguinte! - Com taxa de erro \(\text{err}_m = 0{,}10\) (\(90\%\) de acerto), o salto multiplicativo relativo é de \(\frac{0{,}90}{0{,}10} = 9\times\)!
3.7.1 Conexão Teórica: Minimizador Populacional e Log-Odds
Por que a perda exponencial \(L(y, f) = e^{-yf}\) funciona como critério de classificação? Hastie, Tibshirani e Friedman (ESL §10.4) investigaram o comportamento do modelo no limite populacional. Buscamos a função \(f^*(\mathbf{x})\) que minimiza o risco esperado condicionado a \(\mathbf{X} = \mathbf{x}\):
\[f^*(\mathbf{x}) = \arg\min_{f(\mathbf{x})} \mathbb{E}_{Y \mid \mathbf{x}}\big[e^{-Y f(\mathbf{x})}\big] = \arg\min_{f(\mathbf{x})} \Big[ P(Y=1 \mid \mathbf{x}) e^{-f(\mathbf{x})} + P(Y=-1 \mid \mathbf{x}) e^{+f(\mathbf{x})} \Big]\]
Diferenciando em relação a \(f(\mathbf{x})\) e igualando a zero:
\[-P(Y=1 \mid \mathbf{x}) e^{-f(\mathbf{x})} + P(Y=-1 \mid \mathbf{x}) e^{+f(\mathbf{x})} = 0 \implies e^{2f(\mathbf{x})} = \frac{P(Y=1 \mid \mathbf{x})}{P(Y=-1 \mid \mathbf{x})}\]
Aplicando o logaritmo natural em ambos os lados:
\[f^*(\mathbf{x}) = \frac{1}{2} \ln \left( \frac{P(Y=1 \mid \mathbf{x})}{P(Y=-1 \mid \mathbf{x})} \right) = \frac{1}{2} \text{logit}\big(P(Y=1 \mid \mathbf{x})\big)\]
O resultado é extraordinário e unifica a teoria: 1. O AdaBoost está estimando nada menos que a metade da razão de chances logarítmica (log-odds) populacional, coincidindo perfeitamente com a quantidade modelada pela Regressão Logística (Aula 6)! 2. A regra de decisão final \(\text{sign}(f^*(\mathbf{x}))\) reproduz com exatidão a regra de decisão ótima de Bayes (Aula 2), atribuindo \(+1\) sempre que \(P(Y=1 \mid \mathbf{x}) > 0{,}5\).
3.8 O Calcanhar de Aquiles: Outliers e Rótulos Ruidosos
Apesar de sua elegância teórica e do vínculo com a fronteira de Bayes, a perda exponencial possui uma fraqueza severa na prática: sua extrema vulnerabilidade a dados ruidosos e outliers.
Considere uma observação com rótulo ruidoso ou com atributos atípicos que o modelo classifica com alta confiança errônea (margem negativa \(y_i f(\mathbf{x}_i) \ll 0\)): - Na Regressão Logística (perda deviance):
\(L_{\text{dev}}(y, f) = \ln(1 + e^{-yf}) \approx |yf|\). A penalidade cresce de forma estritamente linear quando o erro aumenta. - No AdaBoost (perda exponencial):
\(L_{\text{exp}}(y, f) = e^{-yf} = e^{|yf|}\). A penalidade cresce de forma puramente exponencial!
Se um único exemplo tiver margem \(y_i f(\mathbf{x}_i) = -10\) (por exemplo, um registro rotulado incorretamente ou ruído severo de sensor), seu peso acumulado salta para \(e^{10} \approx 22.026\). Como consequência direta: 1. O peso dessa anomalia domina a soma total dos pesos \(w_m\). 2. Os classificadores fracos subsequentes monopolizam toda a sua capacidade de particionamento tentando memorizar e acomodar esse ponto isolado. 3. A fronteira de decisão deforma-se dramaticamente com ilhas e reentrâncias espúrias, destruindo a acurácia de teste nos dados normais.
3.9 A Motivação do Gradient Tree Boosting (Friedman, 2001)
A patologia dos outliers no AdaBoost impôs uma pergunta fundamental à comunidade estatística na virada do milênio: como manter o princípio dos comitês aditivos sequenciais sem ficar prisioneiro da perda exponencial?
No AdaBoost, a escolha da perda exponencial não decorreu de uma necessidade empírica, mas sim de conveniência algébrica: sob \(e^{-yf}\), o subproblema de otimização em estágios (FSAM) admite soluções analíticas fechadas para o passo \(\alpha_m\) e para a regra de pesos recursiva.
Se tentássemos substituir a perda exponencial por funções de perda robustas a outliers — como a perda absoluta (\(L_1\)), a perda de Huber ou a deviance logística binomial —, o subproblema em estágios deixa de ter solução analítica fechada em relação aos parâmetros de uma árvore de decisão!
A resposta revolucionária foi apresentada por Jerome Friedman (2001) com a formulação do Gradient Tree Boosting: 1. Tratar o ajuste do modelo aditivo como um processo de otimização numérica no espaço de funções (o espaço \(\mathbb{R}^N\) das predições amostrais). 2. Em vez de deduzir regras analíticas de reponderação para cada perda, calcular diretamente o gradiente negativo da função de perda (os pseudo-resíduos). 3. Projetar esse vetor gradiente na classe de árvores de regressão via mínimos quadrados simples.
Esse salto conceitual liberta o boosting da perda exponencial e abre caminho para otimizar comitês sob qualquer critério diferenciável.
3.10 Pausa 3: FSAM e AdaBoost
DicaPergunta aberta provocadora
Em uma aplicação de detecção de fraudes com dados bancários altamente contaminados por registros fraudulentos atípicos, um cientista observa que o AdaBoost entra em sobreajuste severo após 25 iterações. Por que a formulação matemática da função de perda exponencial explica essa falha catastrófica perante outliers?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O algoritmo AdaBoost.M1 é analiticamente equivalente ao FSAM minimizando a função de perda exponencial \(L(y, f) = e^{-yf}\).
- □ Se um classificador base atingir exatamente \(50\%\) de taxa de erro ponderada (\(\text{err}_m = 0{,}50\)), seu multiplicador no ensemble será \(\alpha_m = 0\).
- □ Sob a perda exponencial, a penalidade atribuída a uma observação incorreta com margem negativa \(-yf = 5\) cresce de forma assintoticamente linear.
- □ A função que minimiza a esperança condicional da perda exponencial é a metade da razão de chances logarítmica (log-odds) populacional.
4 Bloco 2: Gradient Boosting e Pseudo-Resíduos Genéricos
4.1 A Formulação Geral de Jerome Friedman (2001)
Em seu artigo seminal “Greedy Function Approximation: A Gradient Boosting Machine” (2001), Jerome Friedman estabeleceu a estrutura matemática para treinar comitês aditivos sob qualquer função de perda diferenciável \(L(y, f(\mathbf{x}))\).
Considere a perda empírica acumulada no conjunto de treino:
\[L(\mathbf{f}) = \sum_{i=1}^N L(y_i, f(\mathbf{x}_i))\]
Se interpretarmos o vetor de predições \(\mathbf{f} = [f(\mathbf{x}_1), \dots, f(\mathbf{x}_N)]^T \in \mathbb{R}^N\) como um parâmetro em um espaço de \(N\) dimensões, o método da descida de gradiente mais íngreme prescreve a atualização:
\[\mathbf{f}_m = \mathbf{f}_{m-1} - \rho_m \mathbf{g}_m\]
onde \(\mathbf{g}_m \in \mathbb{R}^N\) é o vetor gradiente avaliado no modelo anterior \(\mathbf{f}_{m-1}\), cujos componentes são:
\[g_{im} = \left[\frac{\partial L(y_i, f(\mathbf{x}_i))}{\partial f(\mathbf{x}_i)}\right]_{f(\mathbf{x}) = f_{m-1}(\mathbf{x})}\]
Definimos o pseudo-resíduo \(r_{im}\) como o oposto do gradiente:
\[r_{im} \equiv -g_{im} = -\left[\frac{\partial L(y_i, f(\mathbf{x}_i))}{\partial f(\mathbf{x}_i)}\right]_{f(\mathbf{x}) = f_{m-1}(\mathbf{x})}\]
4.2 Dedução de Pseudo-Resíduos para Perdas Clássicas
A beleza do arcabouço de Friedman reside em sua universalidade. Vejamos a dedução dos pseudo-resíduos para as quatro principais perdas estatísticas:
4.2.1 1. Perda Quadrática (\(L_2\) — Regressão Gaussiana)
\[L(y, f) = \frac{1}{2}(y - f)^2 \implies r_{im} = -\left[-(y_i - f)\right] = y_i - f_{m-1}(\mathbf{x}_i)\] O pseudo-resíduo é rigorosamente o resíduo algébrico tradicional.
4.2.2 2. Perda Absoluta (\(L_1\) / Laplace — Regressão Robusta à Mediana)
\[L(y, f) = |y - f| \implies r_{im} = -\left[-\text{sign}(y_i - f)\right] = \text{sign}\big(y_i - f_{m-1}(\mathbf{x}_i)\big)\] O pseudo-resíduo fornece apenas a direção do desvio (\(\pm 1\)), eliminando completamente o impacto da magnitude do erro. Um ponto com erro \(+10^6\) atrai o modelo com a mesma intensidade que um ponto com erro \(+0{,}01\).
4.2.3 3. Perda de Huber (Regressão Suave e Robusta)
Combina a suavidade analítica de \(L_2\) para pequenos erros com a robustez de \(L_1\) nas caudas, mediada por um limiar \(\delta\): \[L_\delta(y, f) = \begin{cases} \frac{1}{2}(y - f)^2, & \text{se } |y - f| \le \delta \\ \delta |y - f| - \frac{1}{2}\delta^2, & \text{se } |y - f| > \delta \end{cases}\] \[r_{im} = \begin{cases} y_i - f_{m-1}(\mathbf{x}_i), & \text{se } |y_i - f_{m-1}(\mathbf{x}_i)| \le \delta \\ \delta \cdot \text{sign}\big(y_i - f_{m-1}(\mathbf{x}_i)\big), & \text{se } |y_i - f_{m-1}(\mathbf{x}_i)| > \delta \end{cases}\]
4.2.4 4. Deviance Binomial (Regressão Logística — Classificação \(y \in \{0, 1\}\))
Com \(p(\mathbf{x}) = \sigma(f(\mathbf{x})) = \frac{1}{1 + e^{-f(\mathbf{x})}}\) e perda de entropia cruzada binária (Aula 6): \[L(y, f) = - \big[ y \ln p + (1 - y) \ln (1 - p) \big]\] \[r_{im} = -\left[ \frac{\partial L}{\partial f} \right] = y_i - p_{m-1}(\mathbf{x}_i)\] O pseudo-resíduo da classificação binária é a diferença entre o rótulo real binário (\(0\) ou \(1\)) e a probabilidade estimada corrente!
4.3 O Algoritmo Gradient Tree Boosting (Alg. 10.3 do ESL)
Apresentamos formalmente o algoritmo canônico de Gradient Tree Boosting para Regressão (Friedman, 2001; Hastie et al., ESL Algoritmo 10.3):
4.4 Pausa 4: Pseudo-Resíduos e Busca Linear nas Folhas
DicaPergunta aberta provocadora
Ao modelar uma variável financeira com caudas pesadíssimas e valores atípicos de milhões de dólares, um engenheiro substitui a perda quadrática \(L_2\) pela perda absoluta \(L_1\). Como essa mudança altera o pseudo-resíduo de treinamento e o cálculo do valor constante ótimo \(\gamma_{jm}\) que atualiza cada folha da árvore?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Para a função de perda quadrática clássica \(L_2\), o pseudo-resíduo é analiticamente idêntico ao resíduo comum \(r_{im} = y_i - f_{m-1}(\mathbf{x}_i)\).
- □ Sob a perda de valor absoluto \(L_1\), o pseudo-resíduo independe da magnitude escalar do erro, fornecendo unicamente a direção \(\text{sign}(y_i - f_{m-1}(\mathbf{x}_i))\).
- □ O valor ótimo \(\gamma_{jm}\) que atualiza cada folha terminal sob a perda absoluta \(L_1\) é dado pela média aritmética dos resíduos das instâncias alocadas àquela folha.
- □ A perda de Huber realiza uma transição suave entre o comportamento quadrático para erros pequenos (\(|e| \le \delta\)) e o comportamento linear para erros atípicos (\(|e| > \delta\)).
5 Bloco 3: Regularização, Arquitetura de Árvores e Interpretação
5.1 Regularização por Encolhimento
No Algoritmo 10.3, a etapa de atualização do comitê incorpora um parâmetro escalar \(\nu \in (0, 1]\) conhecido como taxa de aprendizado ou fator de encolhimento (shrinkage):
\[f_m(\mathbf{x}) = f_{m-1}(\mathbf{x}) + \nu \sum_{j=1}^{J_m} \gamma_{jm} \mathbb{I}(\mathbf{x} \in R_{jm})\]
Quando \(\nu = 1{,}0\), o algoritmo realiza passos completos no espaço de funções. Friedman (2001) demonstrou teoricamente e empiricamente que dar passos completos quase sempre conduz a um sobreajuste rápido, especialmente em problemas com ruído amostral.
A introdução de \(\nu < 0{,}1\) atua como uma regularização implícita por penalidade \(L_2\). Ao atenuar o passo de cada árvore individual: 1. Impede-se que as primeiras árvores dominem toda a representação da função alvo. 2. Forçam-se as árvores subsequentes a buscarem correções residuais em direções ortogonais e variáveis secundárias. 3. Cria-se um tradeoff fundamental entre \(\nu\) e \(M\): reduzir \(\nu\) por um fator 10 exige multiplicar o número de árvores \(M\) por aproximadamente 10 vezes. Contudo, o mínimo do erro de teste obtido com \(\nu\) pequeno é sistematicamente inferior ao obtido com \(\nu = 1{,}0\).
5.2 Arquitetura de Árvores e Controle da Ordem de Interação
Um dos aspectos teóricos mais elegantes do Gradient Tree Boosting diz respeito à parametrização do tamanho de cada árvore constituinte, determinado pelo número de nós terminais \(J\).
Hastie, Tibshirani e Friedman (ESL §10.11) demonstraram um teorema estrutural fundamental:
As implicações práticas dessa propriedade são diretas: 1. \(J = 2\) (Decision Stumps / Profundidade 1): Cada árvore divide exatamente uma variável \(x_k\). A expansão aditiva resultante tem a forma: \[f(\mathbf{x}) = \sum_{k=1}^p f_k(x_k)\] Trata-se de um Modelo Aditivo Generalizado (GAM) puro! Não há nenhum termo cruzado \(x_j x_k\). Os efeitos marginais de cada variável operam de forma puramente aditiva e são completamente interpretáveis. 2. \(J = 3\) (Profundidade 2): Permite interações bivariadas de 2ª ordem (\(f_{jk}(x_j, x_k)\)). 3. \(J = 4\) a \(8\) (Profundidade 2 a 3): Permite interações de 3ª a 7ª ordem. Na esmagadora maioria dos problemas empíricos tabulares, a natureza dos dados é dominada por efeitos principais e interações de baixa ordem. Árvores com \(4 \le J \le 8\) são suficientes para capturar praticamente todo o sinal relevante sem abrir as portas para variância desnecessária.
5.3 Interpretabilidade: Importância de Atributos e PDP
Apesar de ser um comitê complexo de centenas de árvores, o Gradient Tree Boosting preserva ferramentas sólidas de interpretabilidade estatística propostas por Friedman (2001):
5.3.1 1. Importância Relativa de Variáveis
Para uma única árvore \(T\), a importância de uma variável \(x_k\) é a soma da melhoria na impureza quadrática em todos os nós internos \(t\) onde \(x_k\) foi selecionada para a divisão:
\[I_k^2(T) = \sum_{t=1}^{J-1} \hat{i}_t^2 \cdot \mathbb{I}(v(t) = k)\]
onde \(v(t)\) é a variável de corte no nó \(t\) e \(\hat{i}_t^2\) é o ganho quadrático. No Gradient Boosting com \(M\) árvores, a métrica é calculada pela média sobre todo o comitê:
\[I_k^2 = \frac{1}{M} \sum_{m=1}^M I_k^2(T_m)\]
5.3.2 2. Gráficos de Dependência Parcial (Partial Dependence Plots - PDP)
O PDP permite isolar visualmente o efeito marginal de um subconjunto restrito de variáveis preditoras \(X_S\) (por exemplo, 1 ou 2 variáveis) sobre a função estimada \(f(\mathbf{x})\), integrando numericamente sobre a distribuição empírica das demais variáveis complementares \(X_C\):
\[\bar{f}_S(\mathbf{x}_S) = \frac{1}{N} \sum_{i=1}^N f(\mathbf{x}_S, \mathbf{x}_{i, C})\]
5.4 Pausa 5: Regularização, Arquitetura e Interpretação
DicaPergunta aberta provocadora
Um analista ajusta um modelo Gradient Tree Boosting com \(\nu = 1{,}0\) e descobre que \(M = 30\) árvores atingem o menor erro de validação. Ele então decide reduzir \(\nu\) para \(\nu = 0{,}02\), mantendo fixas exatamente as mesmas 30 árvores. O que acontecerá com o desempenho do modelo e como ele deve reconfigurar \(M\) para usufruir dos benefícios do encolhimento?
DicaJulgamento de V ou F
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O hiperparâmetro de encolhimento \(\nu \in (0, 1]\) amortece o passo de cada árvore, funcionando como um análogo funcional da regularização \(L_2\).
- □ Reduzir \(\nu\) para valores próximos a zero permite que o ensemble atinja o mesmo erro de treino com um número \(M\) significativamente menor de árvores.
- □ Uma árvore com \(J = 2\) nós terminais (decision stump) restringe o ensemble final a um Modelo Aditivo Generalizado sem qualquer interação entre variáveis.
- □ Os Gráficos de Dependência Parcial (PDP) isolam o efeito marginal de uma variável fixando todas as outras variáveis exatamente em suas médias amostrais.
6 Fechamento
6.1 Retomando as 5 Perguntas da Aula
Como o Boosting inverte formalmente os princípios estatísticos do Bagging?
O Bagging reduz a variância de modelos complexos e instáveis (árvores profundas de baixo viés) através de média aritmética paralela. O Boosting reduz o viés de modelos simples e rígidos (decision stumps de alto viés) através de adições sequenciais onde cada nova árvore mira nos resíduos remanescentes.Por que o AdaBoost equivale a um modelo aditivo com perda exponencial?
Demonstramos algebricamente que no Forward Stagewise Additive Modeling com \(L(y, f) = e^{-yf}\), a ponderação das instâncias emerge da fatoração \(w_i = e^{-y_i f_{m-1}}\), o classificador base minimiza o erro de classificação ponderado, e a derivada em relação a \(\beta\) conduz diretamente à constante analítica \(\alpha_m = \frac{1}{2}\ln((1-\text{err}_m)/\text{err}_m)\).Qual é o salto de generalização de Friedman (2001) no espaço de funções?
Friedman provou que ajustar árvores sobre resíduos equivale a realizar descida de gradiente mais íngreme (steepest descent) no espaço vetorial \(\mathbb{R}^N\), onde o pseudo-resíduo é o gradiente negativo \(-\frac{\partial L}{\partial f_i}\), e a indução da árvore de regressão por mínimos quadrados atua como uma projeção ortogonal desse gradiente sobre a classe de hipóteses.Como derivar os pseudo-resíduos para perdas gerais?
Para \(L_2\), o pseudo-resíduo é o resíduo comum \(y_i - f_{m-1}\). Para \(L_1\), é a direção \(\text{sign}(y_i - f_{m-1})\) com atualização de folha pela mediana. Para Huber, combina ambos com truncamento em \(\delta\). Para a deviance binomial, é a diferença entre rótulo e probabilidade \(y_i - p_{m-1}\).Como o encolhimento \(\nu\) e a profundidade \(J\) governam o modelo?
O encolhimento \(\nu \le 0{,}1\) atua como regularização \(L_2\) implícita, prevenindo sobreajuste ao custo de exigir maiores \(M\). O número de folhas \(J\) controla estritamente a ordem máxima de interação (\(K \le J - 1\)), com \(J=2\) produzindo modelos aditivos puros e \(J \in [4, 8]\) capturando interações ricas com baixo risco de sobreajuste.
6.2 Tabela Comparativa Completa: Bagging vs. Boosting
A tabela abaixo sintetiza formalmente os contrastes operacionais e estatísticos entre os dois grandes paradigmas de ensembles da Parte 3 do curso:
| Dimensão Teórica / Prática | Bagging e Random Forests (Aula 9) | Gradient Tree Boosting (Aula 10) |
|---|---|---|
| Alvo Primário do Erro | Redução de Variância (\(\text{Var}\)) | Redução de Viés (\(\text{Bias}^2\)) |
| Complexidade dos Learners Base | Alta (árvores profundas, não podadas) | Baixa a moderada (\(J \in [4, 8]\) nós terminais) |
| Mecanismo de Agregação | Média aritmética paralela independente | Expansão aditiva sequencial acoplada |
| Comportamento quando \(B, M \to \infty\) | Estabiliza no patamar \(\rho \sigma^2\) (não sobreajusta) | Risco de sobreajuste (exige early stopping) |
| Paralelização Computacional | Trivial e perfeita em todas as árvores | Inerentemente sequencial entre iterações |
| Sensibilidade a Outliers e Ruído | Muito robusto (amortece ruído pela média) | Sensível sob \(L_2\) e AdaBoost; robusto sob Huber/\(L_1\) |
| Papel do Aprendizado Estocástico | Subamostragem de atributos (\(m \le p\)) por nó | Subamostragem de dados (\(\eta\)) e shrinkage (\(\nu\)) |
6.3 O Que Fica em Aberto e Próximos Passos
Embora o Gradient Tree Boosting de Friedman tenha revolucionado a modelagem preditiva em dados tabulares, a computação dos cortes de árvores via aproximação de primeira ordem (gradiente puro) apresenta limitações computacionais e analíticas quando lidamos com perdas complexas e bases massivas.
Esse desafio deu origem aos frameworks modernos que dominam competições de Machine Learning: - XGBoost (Chen & Guestrin, 2016): Incorpora uma aproximação de Taylor de 2ª ordem (usando gradiente e Hessiana da perda simultaneamente), adiciona regularização explícita nos pesos das folhas (\(L_1\) e \(L_2\)) e paraleliza a busca por histogramas de corte. - LightGBM (Ke et al., 2017): Introduz amostragem unilateral baseada em gradiente (GOSS) e crescimento folha por folha (leaf-wise). - CatBoost (Prokhorenkova et al., 2018): Resolve vazamentos de dados com ordered boosting para tratamento nativo de variáveis categóricas.
6.4 Ponte para a Aula 11: Máquinas de Vetores de Suporte (SVM)
Nas Aulas 9 e 10, atacamos a não linearidade e a complexidade por meio de comitês massivos: ou combinamos centenas de hiperplanos ortogonais em paralelo para amortecer a variância (Bagging), ou alinhamos dezenas de árvores no espaço de funções para perseguir o gradiente da perda (Boosting).
Na Aula 11, mudaremos radicalmente de perspectiva matemática. Em vez de construir comitês com milhares de regras por partes, investigaremos as Máquinas de Vetores de Suporte (Support Vector Machines - SVM). Retornaremos à geometria pura da teoria de separação ótimo de Vapnik (1995): 1. Como encontrar o hiperplano único que maximiza a margem geométrica de separação entre classes? 2. Como a dualidade de Lagrange e as condições KKT provam que a decisão depende unicamente de um subconjunto parcimonioso de dados: os vetores de suporte? 3. Como o truque do kernel (kernel trick) viabiliza o mapeamento implícito para espaços de Hilbert de dimensão infinita sem nenhum custo de maldição da dimensionalidade?