Árvores e Ensembles

Objetivos de aprendizagem #

• O1. Explicar como uma árvore de decisão escolhe cada divisão.
• O2. Distinguir bagging de boosting quanto ao erro que cada um ataca.
• O3. Ajustar os hiperparâmetros de um modelo de boosting na ordem que importa.
• O4. Justificar por que boosting em dados tabulares continua competitivo com deep learning.

O problema: a fronteira que a reta não alcança #

Um sistema precisa detectar consumo anômalo de energia. A regra real, que ninguém escreveu porque ninguém a conhecia inteira, é esta:

• consumo muito alto fora do horário comercial é anomalia;
• consumo muito baixo também é — medidor quebrado, fraude por desvio;
• consumo intermediário, em qualquer horário, é normal.

Um modelo linear não consegue expressar isso. Nem com mais dados, nem com mais tempo de treino. A razão é estrutural: uma reta é monotônica em cada atributo — se "mais consumo" empurra para anomalia, ele empurra sempre, no mesmo sentido. E aqui os dois extremos são anomalia e o meio é normal.

Medimos. No dado do experimento da etapa 07, com o teto teórico em 0,9402 de AUC:

O modelo linear está em 0,4963 — acaso. Não é que ele vá mal; é que ele não tem como ir bem. Já uma árvore de profundidade 3, ou seja, três perguntas encadeadas, chega a 98% do teto.

De onde isto veio #

As árvores: Breiman fora da universidade #

O aperto. Leo Breiman deixou a academia em 1967 e passou treze anos como consultor, voltando a Berkeley só em 1980. Nesse período ele modelou coisas como padrões de tráfego em autoestradas, gargalos no sistema judiciário e o nível de ozônio do dia seguinte na bacia de Los Angeles. Três características em comum, e nenhuma delas aparece num seminário de estatística: variáveis de tipos misturados (número, categoria, ordem), dados faltando por razões banais, e o resultado tendo de ser explicado a quem não lê estatística — um juiz, um engenheiro de tráfego, um secretário municipal.

O que se fazia antes. Modelos paramétricos que exigiam que o consultor jurasse a forma da relação antes de olhar o dado, e que devolviam uma equação impossível de defender numa reunião com quem decide.

A virada. Um modelo que é a própria explicação: uma sequência de perguntas binárias sobre os atributos. A árvore não aproxima uma função e depois se explica — ela já é o organograma da decisão. E lida com tipo misto sem esforço, porque cada corte só precisa saber comparar dentro de um atributo.

A ideia reaproveitável. A restrição de quem vai usar o resultado é um requisito de projeto, não uma limitação a lamentar. CART tem a forma que tem porque nasceu na consultoria e não no seminário. Sempre que você escolher um modelo, a pergunta "quem vai precisar defender esta decisão, e para quem?" muda a resposta — e é uma pergunta técnica, não política.

O nome. Classification and Regression Trees (Breiman, Friedman, Olshen & Stone, Wadsworth, 1984). Em paralelo, na linha da inteligência artificial, Quinlan desenvolve o ID3 (Iterative Dichotomiser 3), herdeiro do CLS de Hunt (1966); conta-se que o gatilho foi um desafio de Donald Michie: decidir, só por atributos do tabuleiro, se um final de xadrez Rei-Torre contra Rei-Cavalo está perdido em número fixo de lances.

O boosting: uma pergunta que virou algoritmo #

Esta é a origem menos conhecida e a mais instrutiva do capítulo, porque ninguém estava procurando boosting.

Em 1988, Michael Kearns e Leslie Valiant fizeram uma pergunta teórica: um aprendiz que só acerta um pouco mais que o acaso pode ser transformado num aprendiz arbitrariamente bom? Era uma questão sobre limites do possível, não um pedido de algoritmo. Nas palavras de quem a respondeu, eles introduziram a noção de aprendizagem fraca e "left open the question of whether the notions of strong and weak learnability are equivalent".

O nome do problema vem de um lugar que vale registrar: a pergunta "was termed the hypothesis boosting problem", e a referência que Schapire dá para isso é um manuscrito não publicado, de Kearns sozinho, chamado "Thoughts on hypothesis boosting". O termo que hoje nomeia uma família inteira de algoritmos nasceu num texto que nunca saiu em periódico.

Em 1990, Robert Schapire respondeu que sim, e a prova era construtiva. A construção era o método. AdaBoost, com Freund, vem em seguida.

A ideia reaproveitável. Uma pergunta bem-posta sobre limites vira algoritmo. Quando você consegue formular precisamente "isto é possível?", a resposta afirmativa frequentemente já contém o como. Vale mais aprender isso do que decorar o AdaBoost.

Repare no relógio. Em quase todo o resto deste livro, a distância entre a ideia e o procedimento utilizável é de décadas: 1943→1958 no capítulo III.1, 1927→1970 no II.7, 1931→1974 no 0.2. No boosting são sete anos — pergunta em 1988, resposta em 1990, algoritmo em 1995.

A diferença não é a época nem o computador. É que aqui o aperto já estava formulado como uma pergunta formal precisa. Quando a pergunta é vaga, a espera é longa; quando é exata, a resposta traz o método junto. Isso é uma dica prática sobre como gastar o seu tempo: afiar a pergunta costuma render mais que procurar a solução.

E a ponte com o capítulo II.4 #

Bagging (bootstrap aggregating, Breiman, 1996) vem do mesmo diagnóstico que produziu o LASSO no capítulo II.4: instabilidade. Breiman classificou métodos entre estáveis e instáveis, e a árvore é o caso extremo de instável — mude poucos exemplos e a árvore inteira muda.

Do lado "instabilidade é defeito, encolha os coeficientes" saiu a regularização. Do lado "instabilidade é insumo" saiu o bagging: se o modelo varia muito com o dado, então perturbe de propósito e tire a média. Random Forests (2001) é a mesma frase dita de novo, com uma perturbação a mais. O mesmo diagnóstico, dois métodos, dois capítulos.

Procedência das afirmações desta seção:

Números deste capítulo. Todos saem de ml-zero/etapa-07/rodar.py, com seed fixa. Rodar duas vezes dá o mesmo resultado (Princípio II).

⚠ Honestidade sobre o experimento. O dado foi construído com uma regra que é literalmente uma árvore pequena — uma interação e uma quebra. Árvores têm vantagem estrutural aqui por construção, e seria desonesto apresentar isso como descoberta. O experimento serve para tornar visível por que a vantagem existe, não para provar que ela sempre existe. A evidência de que dado tabular real tende a ter essa forma está em Grinsztajn et al. (2022), adiante.

Fundamentos: como a árvore escolhe cada corte #

Uma árvore de decisão é uma sequência de perguntas binárias. A única decisão real é: qual pergunta fazer em cada nó?

O procedimento é guloso e local. Em cada nó, para cada atributo, para cada corte possível, mede-se quanto o corte reduz a impureza — e escolhe-se o melhor. Depois repete-se nos dois filhos, sem nunca reconsiderar o corte anterior.

A impureza mais usada em classificação é o Gini:

onde $p$ é a proporção da classe positiva no nó. A intuição vale mais que a fórmula: é a chance de você errar se chutasse a classe sorteando pela distribuição do próprio nó. Zero quando o nó é puro (só uma classe); máximo em $p=0,5$ (moeda honesta).

O ganho de um corte é a impureza do pai menos a média ponderada da impureza dos filhos:

Três consequências que explicam quase todo comportamento de árvore:

1. O corte é local e definitivo. A árvore nunca desfaz uma decisão anterior. Por isso ela é rápida e por isso ela às vezes erra feio: um corte ruim no topo compromete tudo abaixo.
2. Escala não importa. Multiplicar um atributo por mil não muda a ordem dos valores, e o corte depende só da ordem. É por isso que árvores dispensam normalização — ao contrário de tudo que usa distância ou gradiente (cap. I.6 e 06).
3. Atributos inúteis são ignorados de graça. Se nenhum corte de um atributo dá ganho, ele simplesmente não aparece na árvore. Guarde este ponto: ele volta no fim do capítulo.

Uma árvore sozinha tem variância alta #

Árvore profunda decora. Isso já era esperado do capítulo 0.2 — mais capacidade, mais variância. O que o capítulo 0.2 não mostrou é quanto.

Medindo a variância da predição, Var[f̂(x)], sobre 5 reamostragens bootstrap do treino:

Seis vezes menos. Treine a mesma árvore profunda em amostras ligeiramente diferentes do mesmo fenômeno e ela produz previsões visivelmente diferentes para o mesmo cliente. A floresta, não.

É essa instabilidade, e não a falta de acerto, que os ensembles atacam primeiro.

Bagging e boosting atacam erros diferentes #

Aqui está a ideia que organiza o capítulo inteiro, e a que mais rende em entrevista e em projeto:

Bagging: a média de modelos descorrelacionados #

Treine 25 árvores, cada uma numa reamostragem com reposição, e tire a média. Cada árvore individual é pior que a árvore única treinada em tudo — viu menos dados úteis. A média delas é melhor.

Isso é contraintuitivo até você ligar à decomposição: a média de $B$ estimadores independentes com variância ${\sigma }^2$ tem variância ${\sigma }^2/B$. O viés não muda — a média de modelos igualmente enviesados é igualmente enviesada. Bagging não deixa o modelo mais esperto; deixa-o mais estável.

E há um segundo truque, esse de Breiman (2001, ✓): sortear um subconjunto de atributos em cada nó. Sem isso, as árvores ficam parecidas demais (todas escolhem o mesmo atributo forte no topo) e a média melhora pouco. Estimadores só se cancelam se forem descorrelacionados — e a subamostragem força a descorrelação.

Boosting: cada árvore corrige o erro da anterior #

Comece com uma previsão constante. Calcule o resíduo — o quanto cada exemplo ficou errado. Ajuste uma árvore rasa a esse resíduo. Some uma fração dela à previsão. Recalcule o resíduo. Repita.

Cada árvore é deliberadamente fraca: profundidade 3, no experimento. Sozinha, ela vale 0,9201 de AUC. Cinquenta delas, somadas com passo 0,2, chegam a 0,9392 — 99,9% do teto teórico. É viés atacado por acumulação de correções, não por capacidade individual.

A taxa de aprendizado η encolhe cada contribuição. Passo pequeno com muitas árvores generaliza melhor que passo grande com poucas — o mesmo fenômeno que o capítulo II.4 trata como regularização.

A ordem de ajuste que economiza tempo #

Boosting tem muitos hiperparâmetros e eles interagem. Ajustá-los na ordem errada custa dias. A ordem que funciona:

O erro caro é começar pelo item 4 — mexer em regularização com profundidade errada é otimizar a decoração de uma casa cuja planta está errada.

E use early stopping desde o começo: em vez de escolher o número de árvores por busca, treine muitas e pare quando a validação parar de melhorar. É o hiperparâmetro que se ajusta sozinho.

Fundamentos científicos: por que árvores ainda ganham em tabular #

A afirmação "gradient boosting continua sendo a resposta padrão para dados tabulares" é forte, e neste livro ela não vale por repetição — vale por medição de terceiros, verificada.

Grinsztajn, Oyallon & Varoquaux (2022) (arXiv:2207.08815, ✓) montaram um benchmark de 45 datasets tabulares de domínios variados, comparando modelos de árvore com métodos de deep learning padrão e específicos para tabular, sob buscas extensas de hiperparâmetros. O resultado: modelos baseados em árvore permanecem no estado da arte em dados de porte médio (~10 mil exemplos) — e isso sem sequer contabilizar a vantagem de velocidade.

O mais útil do trabalho não é o placar, é o diagnóstico. Eles identificam três características do dado tabular que explicam a diferença:

1. Atributos não informativos. Bases tabulares reais vêm cheias de colunas irrelevantes. Árvores as ignoram de graça — nenhum corte, nenhum ganho, nenhuma presença. Redes precisam aprender a zerá-las, e nem sempre conseguem.
2. Funções irregulares. A relação entre atributo e alvo tem quebras, patamares e interações abruptas. Redes têm viés a favor de funções suaves; árvores não têm viés nenhum a favor de suavidade.
3. Orientação dos eixos. Em dados tabulares cada coluna tem significado próprio, e árvores cortam ao longo dos eixos — o que casa com a estrutura. Redes são invariantes a rotação, uma propriedade que ajuda em imagem e atrapalha aqui.

Repare que o experimento deste capítulo foi construído com exatamente as características 1 e 2 — três atributos de puro ruído e uma fronteira com quebra e interação. Ele ilustra o mecanismo que o paper mede. As duas coisas são diferentes, e confundi-las seria vender ilustração como evidência.

Cláusula de expiração. Escrevo em 2026 que gradient boosting é a escolha padrão para tabular de porte médio, sustentado por Grinsztajn et al. (2022). Esta é a afirmação com maior chance de envelhecer neste livro: há trabalho ativo em arquiteturas tabulares e em modelos de fundação para tabular. O gatilho de revisão é claro: um benchmark independente, com o mesmo rigor de busca de hiperparâmetros, mostrando vantagem consistente de um método não-árvore em dados de porte médio. Acompanhamento no placar de expiração.

Mão na massa #

A etapa 07 do ml-zero implementa os três modelos em ~250 linhas de biblioteca padrão — sem NumPy, sem scikit-learn:

1. Arvore — CART com Gini para classificação e erro quadrático para regressão (é a segunda que o boosting usa);
2. Floresta — bagging com subamostragem de atributos por nó;
3. Boosting — árvores sequenciais sobre o resíduo, com perda logística e taxa de aprendizado;
4. auc — pelo método dos postos, com empates tratados;
5. rodar.py — o experimento inteiro, que produz a tabela deste capítulo.

Três lições do capítulo estão escritas como testes que falham se deixarem de ser verdade: bagging corta a variância pela metade ou mais; a reta não alcança a fronteira irregular; e ninguém passa do teto de Bayes — passar indicaria vazamento (cap. I.3).

Notebook pronto para executar — arvores_ensembles.ipynb · abrir no Colab

Os quatro modelos treinados no mesmo dado, com a AUC de cada um. A última célula aumenta o ruído e mostra a vantagem do ensemble encolher — ela é propriedade do terreno, não uma constante.

Na sua máquina: pip install notebook e jupyter notebook, ou abra a pasta no VS Code. O notebook não precisa do repositório clonado — se você estiver no Colab, ele baixa sozinho os arquivos de que precisa. Como rodar a trilha inteira: ml-zero.

Assista #

Síntese — o que levar #

• Árvore corta por ganho de impureza, de forma gulosa e local. Dispensa normalização e ignora atributo inútil de graça.
• Uma árvore profunda tem variância alta: no experimento, 6× a da floresta.
• Bagging ataca variância (paralelo, árvores fortes, satura); boosting ataca viés (sequencial, árvores fracas, pode overfitar).
• Ordem de ajuste do boosting: profundidade → (taxa + nº de árvores, juntos) → subamostragem → regularização. Com early stopping desde o começo.
• Em tabular de porte médio, árvores continuam no estado da arte (Grinsztajn et al., 2022) — por três mecanismos, não por magia: atributos inúteis, funções irregulares e orientação dos eixos.
• E a afirmação tem prazo. O gatilho de revisão está escrito.

Verificação #

1. Explique, sem usar a palavra "variância", por que a média de 25 árvores é melhor que a melhor árvore isolada.
2. Você aumenta o número de árvores de um modelo e a validação piora. Isso é bagging ou boosting? Como você sabe?
3. Um colega diz que normalizou os atributos e a floresta melhorou. Que explicações são possíveis?