Random Forest

VIÉS E VARIÂNCIA Decompondo o erro de um modelo

O erro esperado de qualquer modelo pode ser dividido, matematicamente, em três componentes:

\[\text{Err}(x) = \underbrace{\left(E[\hat f(x)] - f(x)\right)^2}_{\text{Viés}^2} + \underbrace{E\left[\left(\hat f(x) - E[\hat f(x)]\right)^2\right]}_{\text{Variância}} + \underbrace{\sigma_e^2}_{\text{Ruído}}\]

• Viés²: o quão longe a predição média do algoritmo (sobre todos os possíveis conjuntos de treino de mesmo tamanho) está do valor correto.
• Variância: o quanto a predição do algoritmo oscila em torno dessa média quando o conjunto de treino muda.
• Ruído: limite inferior do erro esperado de qualquer algoritmo — não pode ser reduzido pelo modelo.

VIÉS E VARIÂNCIA Viés vs. variância, visualmente

VIÉS E VARIÂNCIA Erro vs. complexidade do modelo

MODELOS MÚLTIPLOS Combinar modelos para predizer melhor

INTUIÇÃO A ideia central: treinar muitas árvores e agregar

• Random Forest treina um grande número \(B\) de árvores, cada uma em uma versão ligeiramente diferente dos dados e considerando apenas um subconjunto aleatório de variáveis em cada divisão.
• Classificação: a predição final é a votação majoritária entre as \(B\) árvores.
• Regressão: a predição final é a média das predições das \(B\) árvores.
• Cada árvore individual do Random Forest é, em geral, cultivada sem poda (profunda) — a estabilidade não vem de árvores individuais mais simples, mas da agregação de muitas árvores complexas e diferentes.

INTUIÇÃO O fluxo completo, em um diagrama

%%{init: {"htmlLabels": false, "flowchart": {"htmlLabels": false, "curve": "basis"}, "themeVariables": {"fontSize": "22px"}}}%%
flowchart LR
    D["Dados de treino"] --> S1["Amostra bootstrap 1"]
    D --> S2["Amostra bootstrap 2"]
    D --> S3["Amostra bootstrap B"]
    S1 --> T1["Árvore 1"]
    S2 --> T2["Árvore 2"]
    S3 --> T3["Árvore B"]
    T1 --> AG["Agregação<br/>(votação ou média)"]
    T2 --> AG
    T3 --> AG
    AG --> P["Predição final"]
    style AG fill:#1B4F7A,color:#ffffff,stroke:#1B4F7A
    style P fill:#12283F,color:#ffffff,stroke:#12283F

BOOTSTRAP E BAGGING Amostragem bootstrap

• Uma amostra bootstrap sorteia \(n\) observações com reposição a partir da base de treino original (também de tamanho \(n\)) — algumas observações aparecem repetidas; outras não são sorteadas nenhuma vez.
• A probabilidade de uma observação específica não ser sorteada em uma amostra bootstrap é \(\left(1 - \frac{1}{n}\right)^n\), que converge para \(\frac{1}{e} \approx 36{,}8\%\) quando \(n\) é grande.
• Essas observações deixadas de fora em cada amostra são chamadas out-of-bag (OOB).

BOOTSTRAP E BAGGING A proporção out-of-bag, calculada de verdade

A simulação confirma a matemática: mesmo com bases grandes, cerca de um terço dos dados de treino fica de fora de cada amostra bootstrap específica.

BOOTSTRAP E BAGGING Bagging: bootstrap + agregação

BOOTSTRAP E BAGGING Bagging, formalmente

Considere uma amostra de treinamento \(L = \{(x_i, y_i)\}_{i=1}^{N}\) e um preditor \(\hat d_n(x)\) construído a partir de \(L\).

1. Construa uma amostra bootstrap \(L^* = \{(x_i^*, y_i^*)\}_{i=1}^{N}\), sorteando com reposição a partir de \(L\).
2. Compute o preditor \(\hat d_n^*(x)\) com o mesmo procedimento de \(\hat d_n(x)\), mas usando \(L^*\).
3. Repita \(K\) vezes. Em regressão, o preditor via bagging é a média \(\hat d_{n;B}(x) \approx \frac{1}{K}\sum_{k=1}^{K} \hat d^{*}_{n;(k)}(x)\).
4. Em classificação, com \(N_j = \#\{k : \hat d^{*}_{n;(k)}(x) = j\}\) votos para a classe \(j\), o classificador via bagging é \(\hat d_{n;B}(x) = \arg\max_j N_j\).

BOOTSTRAP E BAGGING Bagging em ação

Cada linha vermelha é a fronteira de um classificador simples treinado em uma amostra bootstrap diferente (os pontos em cinza ficaram de fora daquela amostra). Individualmente, as fronteiras variam muito; a agregação delas (linha azul, no último painel) é bem mais estável.

SELEÇÃO ALEATÓRIA DE VARIÁVEIS O “random” do Random Forest

• Em cada divisão de cada árvore, o Random Forest considera apenas um subconjunto aleatório de \(m\) variáveis (não todas as \(p\) disponíveis) como candidatas para aquele split.
• Um novo subconjunto de \(m\) variáveis é sorteado a cada divisão, não uma vez por árvore — a aleatoriedade acontece em todos os níveis da árvore.
• Sem essa restrição (ou seja, no bagging simples), se uma variável for muito mais forte que as demais, praticamente todas as árvores a escolheriam no primeiro split — as árvores ficariam parecidas, e agregar árvores parecidas ajuda pouco.
• Em resumo: Random Forest = bagging de árvores de decisão + randomização de variáveis.

ALGORITMO Random Forest, passo a passo

Para \(b = 1, \dots, B\) (ao final, obtém-se o conjunto de árvores \(\{T_b\}_{1}^{B}\)):

1. Obtenha uma amostra bootstrap \(Z^*\) de tamanho \(N\) a partir do conjunto de treinamento.
2. Cresça uma árvore de decisão \(T_b\) a partir de \(Z^*\), repetindo recursivamente, para cada nó, até que o tamanho mínimo do nó \(n_{\min}\) seja alcançado:
   1. Selecione \(m\) variáveis aleatoriamente dentre as \(p\) variáveis.
   2. Escolha a melhor variável (e ponto de corte) para a divisão dentre as \(m\).
   3. Divida o nó em dois nós filhos.

ALGORITMO Do conjunto de árvores à predição

• Regressão: \(\hat f_{rf}^{B}(x) = \frac{1}{B}\sum_{b=1}^{B} T_b(x)\).
• Classificação: sendo \(\hat C_b(x)\) a classe predita pela \(b\)-ésima árvore, \(\hat C_{rf}^{B}(x) = \text{voto majoritário}\,\{\hat C_b(x)\}_{1}^{B}\).

SELEÇÃO ALEATÓRIA DE VARIÁVEIS Escolhendo m

• Os valores padrão (\(\sqrt{p}\) para classificação, \(p/3\) para regressão) são pontos de partida razoáveis, não regras ótimas — assim como o \(k\) do k-NN e o cp da árvore, \(m\) é um hiperparâmetro a ser ajustado.
• Valores pequenos de \(m\) aumentam a diversidade entre árvores, mas cada árvore individual fica, em geral, um pouco pior.
• Com \(m = p\), o Random Forest volta a ser simplesmente bagging de árvores.

REDUÇÃO DE VARIÂNCIA Por que a agregação funciona?

Para \(B\) árvores identicamente distribuídas, cada uma com variância \(\sigma^2\), e correlação \(\rho\) entre pares de árvores, a variância da predição agregada (a média) é:

\[\text{Var}\left(\frac{1}{B}\sum_{b=1}^{B} T_b\right) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2\]

• Se \(\rho = 0\) (árvores independentes), a variância cai para \(\sigma^2/B\) — tende a zero conforme \(B\) cresce.
• Se \(\rho = 1\) (árvores idênticas), a variância permanece \(\sigma^2\), não importa quantas árvores sejam adicionadas.
• A seleção aleatória de variáveis existe precisamente para reduzir \(\rho\) — é o que torna o “mais árvores” do Random Forest, de fato, eficaz.

REDUÇÃO DE VARIÂNCIA A fórmula, calculada e plotada

Com \(\rho = 1\) (linha mais escura), adicionar árvores não ajuda em nada — a curva é uma reta horizontal. Quanto menor \(\rho\), mais a variância despenca conforme \(B\) cresce.

OOB E IMPORTÂNCIA DE VARIÁVEIS O erro out-of-bag

OOB E IMPORTÂNCIA DE VARIÁVEIS Convergência do erro OOB

O erro OOB cai rapidamente e depois se estabiliza — sinal de que aumentar ntree além de certo ponto tem retorno cada vez menor.

OOB E IMPORTÂNCIA DE VARIÁVEIS Importância por impureza do nó

• Método mais simples: calcula-se, em média sobre todas as árvores, o quanto as partições geradas por uma variável reduziram a impureza dos nós.
  • Regressão: soma residual dos quadrados.
  • Classificação: índice de Gini.
• Cuidado: é inclinado a preferir variáveis com mais categorias (ou mais pontos de corte possíveis).

OOB E IMPORTÂNCIA DE VARIÁVEIS Importância por permutação

OOB E IMPORTÂNCIA DE VARIÁVEIS As duas medidas, no modelo da aula

x3 foi construída sem nenhuma relação com a classe — e as duas medidas revelam exatamente isso: um Random Forest não apenas prevê bem, como também aponta quais variáveis realmente carregam sinal.

HIPERPARÂMETROS E AJUSTE Principais hiperparâmetros

• ntree (número de árvores): mais árvores tendem a estabilizar o erro OOB, sem risco adicional de overfitting — o custo é apenas computacional.
• mtry (número de variáveis candidatas por divisão): controla diretamente a correlação \(\rho\) entre árvores — o hiperparâmetro mais importante para ajustar.
• nodesize (tamanho mínimo do nó): padrão 1 em classificação e 5 em regressão — as árvores individuais são cultivadas profundas, diferente da árvore isolada da aula anterior, que dependia de poda para não sofrer overfitting.

COMPARAÇÃO E USO PRÁTICO A fronteira de decisão do Random Forest

Comparada à fronteira em degraus grandes de uma única árvore (aula anterior), a fronteira do Random Forest é mais irregular em pequena escala — resultado de médias sobre muitas árvores levemente diferentes — mas ainda claramente composta por segmentos paralelos aos eixos.

COMPARAÇÃO E USO PRÁTICO Vantagens e limitações

Referências

• BREIMAN, L. Random Forests. Machine Learning, 45(1), 5–32, 2001.
• BREIMAN, L. Bagging predictors. Machine Learning, 24(2), 123–140, 1996.
• FACELI, K. et al. Inteligência Artificial: uma abordagem de aprendizado de máquina. LTC, 2011.
• HASTIE, T.; TIBSHIRANI, R.; FRIEDMAN, J. The Elements of Statistical Learning. 2. ed. Springer, 2009.
• JAMES, G.; WITTEN, D.; HASTIE, T.; TIBSHIRANI, R. An Introduction to Statistical Learning. 2. ed. Springer, 2021.
• Notas de aula do curso Mineração de Dados em Biologia Molecular, ministrado por André C. P. L. F. de Carvalho.