class: center, middle, title-slide .title[ # AdaBoost ] .subtitle[ ## (Adaptive Boosting) ] .author[ ### Jaime Utria ] .institute[ ### Departamento de Estatística - UFF ] --- <!-- macro comandos matemáticos Latex --> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ TeX: { Macros: { vet: ["{\\mathbf #1}",1], prodint: ["\\langle #1, #2 \\rangle",2], posto: ["{\\mathrm{posto} (#1)}",1], tr: ["{\\mathrm{tr} (#1)}",1] } } }); </script> ## Boosting: Ideia Geral - Treinar preditores sequencialmente, cada um tentanto corrigir os erros de seu predecessor. - A ideia é treinar uma sequência de preditores fracos, `\(\hat f_1, \ldots, \hat f_B\)`, e logo combiná-los em um preditor final, `\(\hat f_{boost}\)`, forte. --- .center[ <img src="data:image/png;base64,#07_09.png" width="60%" /> Fonte: Raschka e Mirjalili. ] --- ## *Boosting* - *Boosting* refere-se a um algoritmo geral que pode ser aplicado ao treinamento de vários modelos, por exemplo, árvores de decisão, SVM, etc. - O objetivo desse tipo de algoritmos é reduzir o viés e a variância em modelos para aprendizado supervisionado. - Em *Bagging*, as `\(B\)` árvores são geradas independentemente por meio de *bootstrap*, com cada elemento do conjunto de dados de treinamento tendo a mesma probabilidade de ser selecionado em cada réplica *bootstrap*. - Já no *Boosting*, as `\(B\)` árvores são geradas **sequencialmente** a partir do conjunto treinamento, com probabilidade de seleção diferentes atribuídas aos seus elementos. - Elementos mal classificados em uma árvore recebem pesos maiores para seleção na árvore subsequente (obtida do mesmo conjunto de treino). --- ## AdaBoost `\(\mathcal{L} = \{(\mathbf{x}_i,y_i): \mathbf{x}_i \in \mathbb{R}^p, y_i\in \{1,-1\}: i =1, \ldots, n\}\)`. - Inicializamos o vetor de pesos `\(\mathbf{w}^{(1)}\)` com pesos uniformes, tal que `\(\displaystyle\sum_{i=1}^n w_i^{(1)} = 1\)`. - Para cada `\(b=1, \ldots, B-1\)`, fazemos o seguinte: - Treinar um classificador fraco ponderado: `\(\hat{f}_b(\mathbf{x},\mathbf{y},\mathbf{w}^{(b)}) = \hat{f}_b(\mathbf{x})\)`. - Predizer os rótulos: `\(\hat{\mathbf{y}}^{(b)} = [\hat{f}_b(\mathbf{x}_1), \ldots, \hat{f}_b(\mathbf{x}_n)]^\top\)`. - Calcular a taxa de erro ponderado: `\(\varepsilon^{(b)} = \mathbf{w}^\top I(\hat{\mathbf{y}}^{(b)} \neq \mathbf{y}).\)` - Calcular o coeficiente: `\(\alpha_b = \frac{1}{2} \ln\left(\frac{1-\varepsilon^{(b)}}{\varepsilon^{(b)}}\right)\)` - Atualizar os pesos `\(\mathbf{w}^{(b+1)} = \mathbf{w}^{(b)} \exp(-\alpha_b \hat{\mathbf{y}}^{(b)}\mathbf{y})\)` - Normalizar os pesos para somar 1: `\(\frac{\mathbf{w}^{(b+1)}}{\sum_{i=1}^n w_i^{(b+1)}}.\)` - Preditor forte final: `\(\hat{f}_{boost}(\mathbf{x}) = \mathrm{sgn}(\sum_{b=1}^B \alpha_b \hat{f}_b(\mathbf{x}))\)` --- ## AdaBoost em árvores de classificação: Ideias principais 1. No contexto de árvores de classificação os classificadores fracos são árvores com um nó raiz e duas folhas, chamados de **tocos** (*stumps*), ou seja, criamos uma floresta de tocos. 2. Alguns tocos têm mais a dizer (maior contribuição) na classificação final que outros. 3. Cada toco é construído levando em consideração os erros do anterior. --- ## Diabetes (**Toy**) ``` ## Rows: 10 ## Columns: 8 ## $ Pregnancies <int> 6, 6, 0, 4, 4, 9, 3, 12, 14, 5 ## $ Glucose <int> 105, 111, 124, 132, 85, 145, 162, 140, 100, 1… ## $ BloodPressure <int> 70, 64, 56, 86, 58, 80, 52, 82, 78, 82 ## $ SkinThickness <int> 32, 39, 13, 31, 22, 46, 38, 43, 25, 26 ## $ BMI <dbl> 30.8, 34.2, 21.8, 28.0, 27.8, 37.9, 37.2, 39.… ## $ DiabetesPedigreeFunction <dbl> 0.122, 0.260, 0.452, 0.419, 0.306, 0.637, 0.6… ## $ Age <int> 37, 24, 21, 63, 28, 40, 24, 58, 46, 58 ## $ Outcome <fct> 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 ``` --- ``` r library(rpart) library(rpart.plot) # Toco 1 ctrl <- rpart.control(maxdepth = 1, minsplit = 10) set.seed(12345) rpart1 <- rpart(Outcome ~., data = diabetes_toy, control = ctrl) predictions1 <- predict(rpart1,diabetes_toy,type = "class") table(predictions1,diabetes_toy$Outcome) ``` ``` ## ## predictions1 0 1 ## 0 5 1 ## 1 0 4 ``` --- O primeiro toco é criado de acordo com aquela divisão que tenha o maior ganho de informação e usando todos os indivíduos com o mesmo peso: 0,10. .center[ <!-- --> ] --- ## Atualizamos os pesos para criar o segundo toco ``` r pesos1 <- rep(0.1,10) erros1 <- predictions1 != diabetes_toy$Outcome erros1_pond <- sum(pesos1*erros1) if(erros1_pond == 0){erros1_pond = erros1_pond + 0.001} alpha1 <- 0.5*log((1-erros1_pond)/erros1_pond) erros1_num = NULL for (i in 1:10) { erros1_num[i] <- ifelse(erros1[i] == FALSE,-1,1) } pesos2 <- pesos1*exp(alpha1*erros1_num) # normalizamos os pesos pesos2 <- pesos2/sum(pesos2) ``` --- ``` r # pesos atualizados pesos2 ``` ``` ## [1] 0.05555556 0.05555556 0.05555556 0.05555556 0.05555556 0.05555556 ## [7] 0.05555556 0.05555556 0.50000000 0.05555556 ``` ``` r # contribuição do toco 1 alpha1 ``` ``` ## [1] 1.098612 ``` --- ``` ## X1 X2 X3 X4 X5 X6 X7 Y pesos1 pesos2 ## 228 6 105 70 32 30.8 0.122 37 0 0.1 0.05555556 ## 80 6 111 64 39 34.2 0.260 24 0 0.1 0.05555556 ## 322 0 124 56 13 21.8 0.452 21 0 0.1 0.05555556 ## 333 4 132 86 31 28.0 0.419 63 0 0.1 0.05555556 ## 336 4 85 58 22 27.8 0.306 28 0 0.1 0.05555556 ## 459 9 145 80 46 37.9 0.637 40 1 0.1 0.05555556 ## 153 3 162 52 38 37.2 0.652 24 1 0.1 0.05555556 ## 255 12 140 82 43 39.2 0.528 58 1 0.1 0.05555556 ## 204 14 100 78 25 36.6 0.412 46 1 0.1 0.50000000 ## 267 5 144 82 26 32.0 0.452 58 1 0.1 0.05555556 ``` --- ``` r # Toco 2 ctrl <- rpart.control(maxdepth = 1, minsplit = 10) index_toco2 <- sample(1:10,10,replace = TRUE,prob = pesos2) diabetes_toy_2 <- diabetes_toy[index_toco2,] set.seed(12345) rpart2 <- rpart(Outcome ~., data = diabetes_toy_2, control = ctrl) predictions2 <- predict(rpart2,diabetes_toy_2,type = "class") table(predictions2,diabetes_toy_2$Outcome) ``` ``` ## ## predictions2 0 1 ## 0 3 0 ## 1 0 7 ``` --- O segundo toco é criado é criado de acordo com aquela divisão que tenha o maior ganho de informação e dando mais "atenção" aquelas observações mal classificadas pelo toco 1. .center[ <!-- --> ] --- ``` r erros2 <- predictions2 != diabetes_toy_2$Outcome erros2_pond <- sum(pesos2*erros2) if(erros2_pond == 0){erros2_pond = erros2_pond + 0.001} alpha2 <- 0.5*log((1-erros2_pond)/erros2_pond) # contribuição do toco 2 alpha2 ``` ``` ## [1] 3.453377 ``` --- Suponha agora que queremos classificar uma mulher com `\(\mathbf{x}\)` =`[Glucose = 138, Pregnancies = 4]` - Temos que o primeiro preditor (toco 1), classifica como 1: Diabetes(1). - Temos que o segundo preditor (toco 2), classifica como -1: Normal(0). `\(\hat{f}_{boost}(\mathbf{x}) = \mathrm{sgn}(\alpha_1 \times 1 + \alpha_2 \times -1) = \mathrm{sgn}(\alpha_1 - \alpha_2) = -1\)` pois `\(\alpha_2 > \alpha_1\)`. Portanto, a paciente será classificada como normal. - No caso de dois tocos, fazemos a classificação de acordo aquele que temo maior `\(\alpha\)`. - Quando temos mais tocos, fazemos a classificação de acordo aqueles que tenham a maior contribuição total: soma dos `\(\alpha\)`'s. --- ## Diabetes (completo) ``` r ## Separação treino/teste set.seed(12345) index_train <- caret::createDataPartition(y = diabetes$Outcome, p = 0.7, list = FALSE) training <- diabetes[index_train,] testing <- diabetes[-index_train,] ## Treinamento library(adabag) library(rpart) library(rpart.plot) ctrl <- rpart.control(maxdepth = 1) set.seed(12345) diabetes_boost <- boosting(Outcome ~., data = training, boos = TRUE, mfinal = 20, control = ctrl) ``` --- ## Primeiras 4 árvores (tocos) .center[ <!-- --> ] --- ``` r predictions <- predict.boosting(diabetes_boost,testing) predictions$confusion ``` ``` ## Observed Class ## Predicted Class 0 1 ## 0 99 23 ## 1 7 30 ``` ``` r predictions$error ``` ``` ## [1] 0.1886792 ```