10.10 Boosting
“Boosting” is a general method for improving the performance of any learning algorithm. In theory, boosting can be used to significantly reduce the error of any “weak” learning algorithm that consistently generates classifiers which need only be a little bit better than random guessing. (Freund and Schapire 1996, 1)
10.10.1 Teorema do júri de Condorcet
(Condorcet 1785) apresenta o teorema do júri de Condorcet, um marco nos problemas relativos aos sistemas de votação. Ele pode ser aplicado em uma ampla variedade de campos, como ciências sociais e aprendizado de máquina. O teorema pode ser expresso em termos de uma variável dicotômica assumindo os valores 1 e 0, e é considerado razoável atribuir uma classificação correta ou incorreta. Se um decisor – por exemplo um juiz ou classificador – atribui corretamente os 1 com probabilidade \(\theta\) maior que 1/2, o teorema afirma que mais decisores aumentam a probabilidade de atribuições corretas. Com \(\theta\) menor que 1/2, mais decisores diminuem a probabilidade de atribuições corretas, e para \(\theta = 1/2\) o número de decisores é indiferente. Adaptado de (Berg 1996), o teorema é formalmente descrito como segue.
Teorema 10.1 (Teorema de Condorcet) Seja (\(X_1, \ldots, X_n\)) \(n\) variáveis aleatórias binárias independentes tais que \(Pr(X_i = 1) = \theta > 1/2\) e \(P_n = Pr(\sum X_i > n/2)\). Então (a) \(P_n > \theta\) e (b) \(P_n\) é monotonamente crescente em \(n\) e \(P_n \longrightarrow 1\) quando \(n \longrightarrow \infty\). Se \(\theta < 1/2\), então \(P_n < \theta\) e \(P_n \longrightarrow 0\) com \(n \longrightarrow \infty\). Finalmente, quando \(\theta = 1/2\), então \(P_n = 1/2\) para todo \(n\).*
Exemplo 10.28 Se \(n = 3\) e \(\theta=0.6\) então \(P_{3}\) – a probabilidade de pelos menos dois de três decisores atribuírem corretamente os 1 – é dada por \[P_{3} = 0.6 \times 0.6 \times 0.6 + 0.6 \times 0.6 \times 0.4 + 0.6 \times 0.4 \times 0.6 + 0.4 \times 0.6 \times 0.6 = 0.648 > 0.6.\]
Exemplo 10.29 Se \(n = 3\) e \(\theta=0.3\), então \[P_{3} = 0.3^3 + 3 \times 0.3^2 \times 0.7 = 0.216 < 0.3.\]
Exemplo 10.30 Se \(n = 3\) e \(\theta=0.5\), então \[P_{3} = 0.5^3 + 3 \times 0.5^3 = 0.5.\]
10.10.2 Bagging
(Breiman 1996a) apresenta o bagging, acrônimo de “bootstrap aggregating”. É um método para gerar várias versões de um preditor e usá-las para obter um preditor agregado. A agregação pondera sobre as versões ao prever um resultado numérico e faz uma votação múltipla ao prever uma classe, o que remete ao teorema do júri de Condorcet. As múltiplas versões são formadas fazendo réplicas de bootstrap do conjunto de aprendizagem e usando-as como novos conjuntos de aprendizagem. Os passos do bagging são os seguintes:
Pegue \(b\) amostras obtidas do conjunto de dados original.
Construa uma árvore de decisão para cada uma das \(b\) amostras.
Faça a média das previsões de cada árvore para chegar ao modelo final.
A implementação pode ser realizada através da biblioteca ipred (Peters and Hothorn 2021).
Exemplo 10.31 Classificando espécies de lírio via bagging.
# amostra de treino: 60%
set.seed(1); itrain <- sort(sample(1:nrow(iris), floor(.6*nrow(iris))))
train <- iris[itrain,]
test <- iris[-itrain,]
# modelo
fit <- ipred::bagging(Species ~ ., data = train,
nbagg = 200, coob = TRUE,
control = rpart::rpart.control(minsplit = 4, cp = 0.01))
fit##
## Bagging classification trees with 200 bootstrap replications
##
## Call: bagging.data.frame(formula = Species ~ ., data = train, nbagg = 200,
## coob = TRUE, control = rpart::rpart.control(minsplit = 4,
## cp = 0.01))
##
## Out-of-bag estimate of misclassification error: 0.0444# predição
pred <- predict(fit, test)
# matriz de confusão e outras medidas
(cm <- table(pred, test[,5]))##
## pred setosa versicolor virginica
## setosa 18 0 0
## versicolor 0 23 1
## virginica 0 1 17## Confusion Matrix and Statistics
##
##
## pred setosa versicolor virginica
## setosa 18 0 0
## versicolor 0 23 1
## virginica 0 1 17
##
## Overall Statistics
##
## Accuracy : 0.9667
## 95% CI : (0.8847, 0.9959)
## No Information Rate : 0.4
## P-Value [Acc > NIR] : < 2.2e-16
##
## Kappa : 0.9495
##
## Mcnemar's Test P-Value : NA
##
## Statistics by Class:
##
## Class: setosa Class: versicolor Class: virginica
## Sensitivity 1.0 0.9583 0.9444
## Specificity 1.0 0.9722 0.9762
## Pos Pred Value 1.0 0.9583 0.9444
## Neg Pred Value 1.0 0.9722 0.9762
## Prevalence 0.3 0.4000 0.3000
## Detection Rate 0.3 0.3833 0.2833
## Detection Prevalence 0.3 0.4000 0.3000
## Balanced Accuracy 1.0 0.9653 0.9603O argumento coob = TRUE é utilizado para obter o erro out-of-bag (OOB) estimado. O erro out-of-bag utiliza as amostras que não entraram em cada uma das \(b\) sub amostras. Quanto às especificações na função rpart.control:
minsplit = 3: Obriga o modelo a exigir 3 observações em um nó para dividir.
cp = 0.01. Parâmetro de complexidade. Ao defini-lo como 0.01, exige-se que o modelo seja capaz de melhorar o ajuste geral em pelo menos 0.01 para realizar uma divisão.
Por fim pode-se calcular a importância das variáveis.
library(caret)
# calcula a importência das variáveis (pode levar alguns minutos)
VI <- data.frame(var = names(iris[,-5]), imp = varImp(fit))
# ordena a importância de forma decrescente
VI_ord <- VI[order(VI$Overall, decreasing = TRUE),]
# barplot horizontal
barplot(VI_ord$Overall,
names.arg = rownames(VI_ord),
horiz = TRUE,
las = 2,
col = 'steelblue',
xlab = 'Importância da variável')
10.10.3 AdaBoost
(Schapire and Freund 1995), (Freund and Schapire 1996) e (Freund and Schapire 1997) propõem o AdaBoost, que (Breiman 1996b) indica por arcing, acrônimo para “adaptively resample and combine”.
10.10.3.1 JOUSBoost
10.10.3.2 fastAdaboost
10.10.4 XGBoost
eXtreme Gradient Boosting
Exercício 10.10 Ler e tentar implementar as seguintes documentações:
(a) https://xgboost.readthedocs.io/en/latest/
(b) https://xgboost.readthedocs.io/en/latest/R-package/index.html