Métodos baseados em árvores
Laboratório de Estatística e Geoinformação - LEG/UFPR
Nesta seção, vamos descrever os métodos baseados em árvores no contexto de regressão e classificação. Estes envolvem estratificação ou segmentação do espaço de predição em regiões mais homogêneas, segundo a resposta. Tais abordagens apresentam algumas qualidades, por exemplo:
Podem ser aplicadas em problemas de regressão/classificação (com dados assimétricos, esparsos etc.);
Não precisa de variáveis dummy para lidar com preditores qualitativos;
Lidam bem com dados faltantes;
Implicitamente, realizam seleção de variáveis;
São simples e úteis para interpretação, pois não temos equações (a árvore é o próprio modelo), tornando-o atrativo, especialmente, para não estatísticos;
Entretanto, são mais simples do que deveriam. Por esse motivo, em termos de predição, não são competitivos com outras abordagens de aprendizado supervisionado.
Como o algoritmo funciona?
Algoritmo: a construção da árvore de decisão é composta por dois passos:
Dividimos o espaço dos preditores \(X_1, X_2, \dots, X_p\) em \(J\) regiões distintas, \(R_1,R_2,\dots, R_J\);
A predição de qualquer observação pertencente à região \(R_j\) será a resposta média \(\bar y_j\).
Exemplo 1: Suponha que no Passo 1 obtemos duas regiões, \(R_1\) e \(R_2\), tq:
\[\begin{eqnarray} R_1 &=& \{\mathbf{X} = (x_1,x_2) \ | \ x_1 < 4.5\} \nonumber\\[0.7cm] R_2 &=& \{\mathbf{X} = (x_1,x_2)\ |\ X_1 \geq 4.5\}\nonumber \end{eqnarray}\]
Supondo que a resposta média de \(R_1\) seja \(\bar y_1 = 3\) e de \(R_2\) seja \(\bar y_2 = 7\). Com a chegada de uma nova observação \(\mathbf{x}_k = (x_1,x_2)\), caso \(x_1 \in R_1\) atribuiremos o valor de 3 para \(y_k\), caso contrário, o valor de 7.
Exemplo 2: Agora, suponha que no Passo 1 obtivemos três regiões, \(R_1\), \(R_2\) e \(R_3\), tq:
Em teoria, \(R_1, \dots, R_J\) podem apresentar qualquer forma. Todavia, escolhe-se dividir o espaço dos preditores em retângulos por simplicidade e facilidade de interpretação. Dessa forma, o objetivo será encontrar \(R_1,\dots, R_J\) que minimizem a \[ SQRes = \sum_{j=1}^{J}\sum_{i \in R_j} (y_i - \hat y_{R_j})^2, \] em que \(\hat y_{R_j}\) é a resposta média das observações de treino, dentro do \(j\)-ésimo retângulo.
Divisão binária recursiva
Infelizmente, considerar toda possível partição do espaço em \(J\) retângulos é computacionalmente inviável. Por esta razão, utilizamos a abordagem da divisão binária recursiva (top-down approach).
Algoritmo
Para todo \(X_1,\dots,X_p\) e os possíveis valores do ponto de corte, \(s\), calculamos a \(SQRes\);
Em seguida, selecionamos \(X_j\) e o ponto de corte tal que a árvore resulte na menor \(SQRes\).
Por exemplo, dada as regiões
\[ R_1(j,s) = \{X|X_j<s\} \ \ \textrm{e} \ \ \ R_2(j,s) = \{X|X_j\geq s\}. \]
Procuramos o valor de \(j\) e \(s\) que minimize a equação \[ SQRes = \sum_{i:x_i\in R_1(j,s)}(y_i - \hat y_{R_1})^2 + \sum_{i:x_i\in R_2(j,s)}(y_i - \hat y_{R_2})^2. \]
Repetimos o processo, agora somente com a partição dos dados, e paramos quando algum critério seja alcançado (p. ex., até que nenhuma região tenha mais de 5 observações).
Por que partições binárias? Em vez de dividir cada nó em apenas dois grupos, poderíamos considerar múltiplas divisões. O problema é que essa abordagem fragmenta os dados rapidamente, deixando-os insuficientes para os próximos níveis. Além disso, o algoritmo tem maior dificuldade em aprender quando se tem mais de duas categorias de resposta.
Podando a árvore
É sabido que árvores muito grandes podem superajustar os dados de treinamento. Para resolver esse problema, nós a “podamos”. Dessa forma, com menos regiões, tem-se menor variabilidade, além de uma melhor interpretação dos resultados. O objetivo então será, a partir de uma grande árvore \(T_0\), reduzi-la até se obter uma subárvore ótima. Para tanto, utilizamos o critério cost complexity pruning, também conhecido como weakest link pruning (veja Ripley, 1996 ou Breiman et al., 1984). O processo é semelhante ao Lasso, pois também penalizamos o modelo pela sua complexidade. Mas, se antes buscávamos \(\beta's\) pequenos para evitar o superajuste, agora procuramos pelo menor número de regiões. De maneira específica, penalizamos a \(SQRes\) através do tamanho da árvore, da seguinte forma: \[\begin{eqnarray} SQRes_\lambda &=& SQRes + \lambda \times \left(\textrm{# Terminal nodes}\right)\nonumber\\[0.3cm] &=& \sum_{m=1}^{|T|} \sum_{i:x_i\in R_m}(y_i - \hat y_{R_m})^2 + \lambda|T|,\nonumber \end{eqnarray}\]
em que \(\lambda\) é o complexity parameter e \(|T|\) indica o número de terminal nodes da árvore \(T\). Na prática, encontramos as melhores subárvores, em função de \(\lambda\) (\(T_\lambda\)), e em seguida, utilizamos validação cruzada (por exemplo, 5 ou 10-fold) para escolher o \(\hat \lambda\).
Valores faltantes nos preditores
Suponha que nossos dados contenham observações faltantes em algumas (ou todas) variáveis. Descartar tais informações, além de esgotar rapidamente o conjunto de treinamento, perderíamos insights importantes sobre o fenômeno. Por exemplo, na figura abaixo, à esquerda nota-se que a distribuição dos dados de \(V348\) muda ao considerarmos os dados observados e não observados de \(V324\). No caso da variável \(V531\) (à direita) isso já não ocorre.
Como solução, já estudamos alguns processos de imputação dos dados faltantes. Entretanto, para modelos baseados em árvores de decisão, existem duas abordagens mais convenientes. A primeira é aplicável para preditores categóricos: simplesmente criamos uma categoria denominada \(“NA”\). Deste modo, podemos descobrir padrões atípicos entre os dados faltantes. A segunda, é a construção de variáveis de substituição (surrogate variables), da seguinte forma:
Inicialmente, construímos uma regra de separação, excluindo os dados faltantes;
Escolhido o melhor preditor e o ponto de divisão, avaliamos - dentre os demais preditores - qual(is) melhor “imita(m)” a divisão alcançada no passo 1;
Assim, chegando novos dados, caso não haja informação sobre o preditor, utilizamos às variáveis auxiliares do passo 2.
Esse processo explora a correlação das variáveis, na tentativa de minimizar o efeito dos dados faltantes. É importante constatar que essas não são as únicas opções.
Árvores de classificação
A árvore de classificação é muito similar à árvore de regressão, exceto pelo fato da resposta ser qualitativa. Vimos anteriormente que a predição para uma nova observação é dada pela resposta média das observações de treinamento. Agora, a predição se baseará na proporção de observação em cada classe. Continuaremos utilizando a divisão binária recursiva para o crescimento da árvore, mas alternativamente à \(SQRes\) recorreremos à outras métricas. Uma delas é a taxa de classificação incorreta (p. ex., uma observação pertence à classe \(A\) e foi classificada como \(B\)), que é apresentada da forma: \[ E = 1- \underset{\mathbf{k}}{max}\left(\hat p_{mk}\right), \] em que \(\hat p_{mk}\) representa a proporção de dados de treinamento na região \(m\) que pertencem à classe \(k\). Entretanto, essa quantidade não é sensível o suficiente para podar uma árvore adequadamente. Na prática, outras medidas são preferidas, como o Gini index: \[ G = \sum_{k=1}^{K} \hat p_{mk} \left(1 - \hat p_{mk}\right), \] que é uma medida de variância total nas \(K\) classes. Esse índice apresenta menor valor quando os \(\hat p_{mk}\)’s são próximos de 0 ou 1. Por isso é referenciado como uma medida de pureza do nó (valores pequenos indicam que o nó contém predominantemente observações de uma classe). Outra medida útil é a cross-entropy: \[ D = - \sum_{k=1}^{K} \hat p_{mk} log \left(\hat p_{mk}\right). \]
Desde que \(0 \leq \hat p_{mk} \leq 1\), temos que \(0 \leq -\hat p_{mk} log \left(\hat p_{mk}\right)\). Assim, cross-entropy apresentará valores próximos de zero se os \(\hat p_{mk}\)’s são próximos de 0 ou 1. De fato, ambos os índices são bastante similares numericamente. Quando o interesse é avaliar a qualidade de uma partição em específico, o Gini index e cross-entropy são os mais indicados, por serem mais sensíveis à pureza do nó. Mas se o objetivo é apenas a precisão da árvore final, recomenda-se a taxa de classificação incorreta.
Ensembles
Como vimos, os modelos baseados em árvores apresentam muitas qualidades. Entretanto, em muitos casos, não se mostram competitivos em termos de predição, quando comparado com outros algoritmos supervisionados. Um dos motivos está na sua instabilidade devida à natureza hierárquica do processo: o efeito de um erro na divisão superior é propagado em todas as demais. Assim, pequenas mudanças nos dados pode alterar drasticamente a regra de decisão (e sua interpretação). Além disso, caso a região em estudo não seja retangular, as árvores não farão o melhor trabalho. Na figura abaixo, apresentamos um exemplo comparando regressão linear simples com árvores de decisão. Nota-se que, mesmo aumentando a complexidade da árvore (aumentando as partições), não é possível imitar a regra obtida pelo modelo linear.
Para combater esses e outros problemas, desenvolveu-se os métodos chamados de Ensembles, que combinam - de diferentes formas - várias árvores, aumentando consideravelmente seu poder preditivo (evidentemente, às custas da interpretabilidade). Abaixo, estudaremos três deles: Bagging, Random Forests e Boosting.
1) Bagging
Como já vimos, o método de Bootstrap é uma poderosa ferramenta para reamostragem. Ele é utilizado especialmente nas situações em que é difícil (ou mesmo impossível) calcular diretamente o desvio-padrão da quantidade de interesse. Agora, vamos estudar sua utilidade em um contexto completamente diferente: no aumento da acurácia dos métodos de árvores de decisão. Para entender esse processo, relembre que dado um conjunto de \(n\) observações i.i.d. \(Z_1, \dots, Z_n\), cada uma com variância \(\sigma^2\), a variância de \(\bar Z\) será \(\sigma^2/n\). A ideia do bagging (Bootstrap aggregation) baseia-se nesse conceito, aumentamos a precisão final ao utilizar a média das predições (várias árvores, neste caso). Fazemos isso gerando repetidas amostras através do Bootstrap. O processo completo é descrito em seguida.
Algoritmo
Gerar \(B\) conjuntos de observações (bootstrapped).
Treinar o modelo, a fim de obter a predição no ponto \(x\);
Calcular a média das predições, que chamamos de bagging: \[ \hat h_{bag}(x) = \frac{1}{B}\sum_{b=1}^{B} \hat h^{b} (x), \] em que \(\hat h^{b} (x)\) é o modelo de árvore, construído com a \(b\)-ésima amostra bootstrap.
Essa abordagem se aplica à àrvore de regressão. Já para classificação, registra-se a classe predita pelas \(B\) árvores, e escolhe-se pela maioria dos votos. Na figura abaixo, temos a ilustração desse processo. Inicialmente, geramos \(B\) amostras bootstrap dos dados de treinamento. Em seguida, para cada conjunto de dados, obtemos um classificador. Assim, ao chegar uma nova observação, a predição será baseada na combinação dos classificadores.
É possível demonstrar (veja James, G. et al., 2014) que cada amostra bootstrap utiliza em torno de 2/3 das observações. Os 1/3 restantes são chamados de observações out-of-bag (OOB). Como esta parcela não participou do treinamento do modelo, podemos utilizá-la para estimar o erro de predição (em vez de aplicar validação cruzada).
2) Random Forests
Como vimos, o Bagging é uma técnica para reduzir a variabilidade da função de predição. Nele ajustamos vários modelos considerando diferentes amostras bootstrap (identicamente distribuídas, i.d.). Com essa abordagem, espera-se que o viés das árvores permaneça, i.e., a média das \(B\) predições seja igual à de uma em específico, e a variabilidade diminua. Por esse motivo que o utilizamos em procedimentos com baixo vício e elevada variabilidade, como em árvores de decisão. Mas note que as amostras bootstrap não são i.i.d, portanto temos que: \[ Var(\hat h_{bag}) = \rho\sigma^2 + \frac{1-\rho}{B}{\sigma^2}. \]
Em que \(\rho\) é a correlação entre as árvores (devido a correlação das amostras). Assim, conforme \(B\) aumenta, o segundo termo da equação desaparece, mas o primeiro permanece. Por isso, se diz que a correlação entre as árvores (herdada do bootstrap) é um limitante para o Bagging. Por exemplo, suponha que exista um preditor muito forte nos dados de treinamento, combinado a outros moderadamente relevantes, com o bagging, a maioria (ou todas) as bagged trees utilizarão essa variável influente. Consequentemente, todas serão muito semelhantes entre si. A ideia do Random Forests é minimizar essa deficiência. Fazemos isso selecionando aleatoriamente, em cada divisão, \(m < p\) variáveis de entrada (quando \(m = p\), voltamos ao bagging). I.e., se impõe que diferentes preditores sejam escolhidos em cada árvore (decorrelating the trees). Na figura abaixo, temos a ilustração desse processo.
Tipicamente, utilizamos \(m \approx \sqrt{p}\) (mas esse deve ser um parâmetro de tuning). Considerar um valor pequeno para \(m\), geralmente é útil em situações com muitos preditores correlacionados. Entretanto, deve-se ter cautela quando muitos preditores são irrelevantes, pois com \(m\) pequeno a chance de uma variável importante ser selecionada em cada árvore se reduz consideravelmente, comprometendo o desempenho do modelo.
3) Boosting
Boosting é outra alternativa para melhorar o desempenho das árvores de decisão. Assim como Bagging, ele é uma abordagem geral, na qual pode ser aplicado à diversos métodos de aprendizado estatístico. Relembre que em Bagging, criamos múltiplas cópias dos dados originais (através de bootstrap), ajustando em cada partição uma árvore diferente. Notadamente, cada árvore era construída de maneira independente, i.e., o desempenho da primeira não influenciava na construção da segunda, e assim por diante. Boosting funciona de maneira similar, exceto pelo fato de que as árvores agora crescem sequencialmente: a informação da árvore anterior é utilizada para construção da próxima. O princípio básico do Boosting é propor um modelo básico (weak learner) e o aprimorar (ou “ensinar”) em cada iteração. O processo consiste em filtrar os resultados corretos, e concentrar-se naqueles que o modelo não soube lidar. Em outras palavras, desenvolver os pontos fracos do algoritmo. A figura abaixo ilustra essa situação: com o primeiro conjunto de dados, encontramos o modelo inicial, e a partir daí, os novos modelos são construídos de acordo com os erros dos anteriores.
Em Estatística, quando analisamos o ajuste de um modelo, geralmente recorremos aos resíduos para avaliar sua qualidade, verificar homocedasticidade, encontrar pontos atípicos etc. Isso ocorre pois toda informação não especificada no modelo (ou não captada por ele) será incorporada ao resíduo. A ideia do boosting é exatamente essa, em cada etapa propor um novo modelo (somando-o ao antigo), baseando-se nos resíduos. Para ilustrar esse processo, considere que estamos interessados em explicar \(Y\) através da função \(h(x)\), ou seja: \[\begin{eqnarray} \label{eq1} Y = h(x) + \textrm{resíduo} \end{eqnarray}\] Se o \(\textrm{resíduo}\) não for um ruído branco (mas algo relacionado com \(Y\)), podemos obter novas informações, além daquelas obtidas com o primeiro modelo, da seguinte forma: \[\begin{eqnarray} \label{eq2} \textrm{resíduo} = g(x) + \textrm{resíduo2} \end{eqnarray}\] Note que \(g(x)\) representa uma função não contemplada em \(h(x)\), que ajuda a explicar \(Y\). Podendo ser, inclusive, uma função que corrige possíveis erros de \(h(x)\). Combinando (\ref{eq1}) e (\ref{eq2}) \[\begin{eqnarray} Y = h(x) + g(x) + \textrm{resíduo2} \nonumber \end{eqnarray}\]
Pode-se dizer que \(h(x)\) foi atualizada com uma parte do \(\textrm{resíduo}\), ou seja \[ h(x)^{(2)} = h(x)^{(1)} + g(x) \]
O primeiro método boosting de grande sucesso foi o Adaptive Boosting ou AdaBoost. Nesse caso, os weak learners, são árvores de decisão com uma separação apenas (chamada de decision stumps). O algoritmo trabalha colocando mais peso nas instâncias difíceis de classificar, gerando novos modelos para tais situações. Nesse caso, as previsões são feitas por maioria dos votos em cada modelo, ponderada pela sua precisão individual.
Exemplo simulado
Vamos ilustrar esse processo desenvolvendo o método desde o início. É digno de nota, que esta é apenas uma aplicação, e o algoritmo AdaBoost é mais complexo e eficiente do que o apresentado. Considere o exemplo simulado, obtido a partir da função: \[\begin{eqnarray} f(x) &=& \beta_0 + \beta_1 * x + \beta_2 * sin\left(\frac{x}{10}\right)\nonumber\\[6pt] &=& 10 +0,05* x + 2 * sin\left(\frac{x}{10}\right)\nonumber \end{eqnarray}\]
#-----------------------------------------------------------------------
# Gerando dados.
# Retorna um rúido normal padrão.
epsilon <- function(x, ...) {
rnorm(n = length(x), mean = 0, ...)
}
# Retorna os valores determinados pelo modelo.
eta <- function(x, beta = c(10, 0.05, 2)) {
beta[1] + beta[2] * x + beta[3] * sin(x/10)
}
# Simulando do modelo.
set.seed(567)
da <- data.frame(x = sort(runif(200, 0, 100)))
da$y <- eta(da$x) + epsilon(da$x, sd = 1)
# Exibindo os dados.
plot(y ~ x, data = da)
curve(eta, add = TRUE, col = "dodgerblue3", lwd = 3)
O método de Árvores de decisão pode ser entendido como uma função degrau, dada na forma: \[ f(x) = \begin{cases} y_1, & x_0 < x \leq x_1 \\ y_2, & x_1 < x \leq x_2 \\ \vdots & \ \ \ \ \ \ \ \ \ \vdots \\ y_p, & x_{p-1} < x \leq x_p. \end{cases} \]
Vamos considerar a versão com \(p = 2\). Dessa forma, a função retornará o valor \(y_1\) para valores \(x < s\) e \(y_2\) para valores de \(x\geq s\), em que \(s\) é o ponto de corte no domínio. Nosso primeiro modelo (weak learner) está apresentado abaixo, em azul.
#-----------------------------------------------------------------------
# A função h(x) será uma função degrau.
# Modelo inicial com predito sendo a média das observações.
m0 <- lm(y ~ 1, data = da)
plot(y ~ x, data = da)
lines(da$x, fitted(m0), type = "solid",col = "dodgerblue3", lwd = 3)
O processo consiste em analisar o resíduo decorrente do modelo anterior e somar novas árvores, suprindo tais deficiências. Na figura abaixo temos 12 iterações desse processo, em cada uma com partições diferentes.
# Função degrau. Retorna ajustado e resíduo.
h <- function(beta, y, x) {
dico <- ifelse(x < beta, 0, 1)
fit <- ave(y, dico, FUN = mean)
list(dico = dico, fit = fit, res = y - fit)
}
# Função custo.
loss <- function(beta, y, x) {
fit <- h(beta, y, x)$fit
sum((y - fit)^2)
}
# Verifica o comportamento da função.
# bseq <- seq(0, 100, 1)
# lseq <- sapply(bseq, FUN = loss, y = da$y, x = da$x)
# plot(lseq ~ bseq, type = "o")
# Usando a optim().
# optim(par = c(50),
# fn = loss,
# y = da$y,
# x = da$x)$par
#-----------------------------------------------------------------------
# O algorítmo.
# Cria uma lista para armazenar os artefatos produzidos.
n <- nrow(da)
k <- 12
resul <- replicate(k,
data.frame(fit = numeric(n),
res = numeric(n)),
simplify = FALSE)
# Inicia a lista com resultados do primeiro ajuste.
resul[[1]]$fit <- fitted(m0)
resul[[1]]$res <- residuals(m0)
bval <- c(NA, numeric(k - 1))
# Executa o gradiente boosting.
for (i in 2:k) {
# Encontra o beta minimizando a função perda.
beta <- optimize(f = loss,
y = resul[[i - 1]]$res,
x = da$x,
interval = c(0, 100))$minimum
# Exibe o progresso.
cat(i, "\t", beta, "\n")
bval[i] <- beta
# Extrai valores ajustados e resíduos.
hfit <- h(beta,
y = resul[[i - 1]]$res,
x = da$x)
# Atualiza os valores ajustados e resíduos.
resul[[i]]$fit <- resul[[i - 1]]$fit + hfit$fit
resul[[i]]$res <- da$y - resul[[i]]$fit
}
#-----------------------------------------------------------------------
# Exibe os resultados.
# Lista replicando a mesma fórmula.
form <- replicate(k, y ~ x)
names(form) <- 1:k
xyplot.list(form,
data = da,
type = "n",
as.table = TRUE) +
layer({
i <- which.packet()
fit <- resul[[i]]$fit
panel.points(x = x,
y = y,
col = "gray")
panel.lines(da$x,
fit,
col = "dodgerblue3",
lwd = 3)
panel.abline(v = bval[i], lty = 2)
})
Nota-se que, em cada iteração, os resíduos vão se relacionando cada vez menos com \(x\). Ou seja, o modelo vai aprendendo em cada etapa.
# Converte lista em tabela.
names(resul) <- as.character(1:k)
result <- plyr::ldply(resul, .id = "k")
result$k <- factor(result$k, levels = 1:k)
result$x <- da$x
# O comportamento dos resíduos com o acréscimo de funções.
xyplot(res ~ x | k,
data = result,
type = c("n", "smooth"),
span = 0.3,
as.table = TRUE) +
layer(panel.points(x = x, y = y,
col = "black")) +
layer(panel.abline(h = 0, lty = 2, lwd=2, col = "red"))
Veja que o algoritmo aprende lentamente. Do modelo atual, ajusta-se o seguinte, de acordo com seus os erros. Nesse caso, cada uma dessas árvores podem ser bastante simples, determinada pelo parâmetro \(d\). Assim, de pouco a pouco, vai-se aumentando a complexidade, adicionando novas árvores em regiões nas quais o algoritmo anterior não se saiu bem. Os parâmetros de tuning nesse método são:
B (número de árvores): por utilizarmos os resíduos na construção das árvores, um valor muito grande para esse parâmetro pode superajustar o modelo. O mesmo não acontece com o Bagging e Random Forests. Selecionamos o valor de \(B\) através da validação cruzada;
\(\alpha\) (taxa de aprendizagem): tipicamente, utilizamos os valores 0,01 ou 0,001, mas a escolha correta dependerá do problema. Valores muito pequenos exigirá o aumento de \(B\), a fim de alcançar um bom desempenho;
d (número de divisões em cada árvore): esse parâmetro controla a complexidade de cada árvore. Na prática, \(d=1\) funciona bem (neste caso, teremos apenas uma partição). Dessa forma, ajustaremos um modelo aditivo, uma vez que cada termo envolverá apenas uma variável. De maneira geral, o parâmetro \(d\) controla o grau de interação entre as variáveis envolvidas nas partições.
No \(R\), o pacoteAlgoritmo:
Inicie com \(\hat h(x) = 0\) e \(r_i = y_i\), para todo \(i\) dos dados de treino;
- Para \(b = 1,2,\dots, B\), repita:
Ajuste a árvore \(\hat h^b\) com \(d\) divisões (\(d+1\) terminal nodes) para os dados de treino \((X,r)\);
Atualize \(\hat h\) adicionando uma nova versão à árvore anterior: \[ \hat h(x) \leftarrow \hat h(x) + \alpha \hat h^b(x).\]
Atualize os resíduos, \[ r_i \leftarrow r_i - \alpha \hat h^b(x_i)\]
O modelo de saída fica então, \[\hat h(x) = \sum_{b=1}^{B} \alpha \hat h^b(x).\]
gbm (gradient boosted models) lida com uma variedade de problemas de regressão e classificação. Não vamos entrar em detalhes sobre Boosting para árvore de classificação. Em linhas gerais, em cada passo, as observações recebem pesos diferentes, dependendo da classificação realizada pela árvore anterior. Na figura abaixo, ilustramos esse processo com três iterações. Note que as observações classificadas incorretamente ganharam mais importância, para que as próximas árvores se atentem para esse fato. O aluno interessado pode encontrar mais detalhes sobre o assunto no livro Elements of Statistical Learning, capítulo 10.
