Uma breve introdução ao AdaBoost
Neste artigo, trago um pouco sobre um algoritmo de aprendizado de máquina muito poderoso e aplicado em diversos problemas: o AdaBoost.
Boosting
O AdaBoost (termo advindo de Adaptive Boosting) é talvez a implementação mais conhecida da técnica Boosting. Essa abordagem consiste em combinar diferentes classificadores “simples” (denominados weak learners) de forma sequencial e adaptativa. Isto é, o processo de treinamento do weak learner t influencia diretamente no treinamento do weak learner t + 1.
O princípio por trás da técnica Boosting consiste em direcionar o weak learner subsequente às amostras que o weak learner atual não foi capaz de predizer corretamente no treinamento. Dessa forma, cada weak learner tenta se especializar nos erros do seu antecessor. Veja um exemplo visual:
Na imagem, temos um problema de duas classes onde o AdaBoost é aplicado com 3 weak learners (gráficos 1, 2 e 3). Em cada figura, perceba que o weak learner reforça as amostras preditas incorretamente pelo antecessor (representadas pelos círculos e triângulos maiores). No passo 4 da figura, temos o modelo final gerado pelo AdaBoost que combina as fronteiras de decisão de cada weak learner.
Explicação do algoritmo
Agora que temos uma intuição do funcionamento do AdaBoost, vamos partir para os detalhes do algoritmo:
Repassando os pontos importantes, passo-a-passo:
- 1. Cada amostra xᵢ possui um peso associado wᵢ que representa a probabilidade da i-ésima amostra ser sorteada. Inicialmente, todos os pesos são inicializados com o mesmo valor;
- 2. São treinados M weak learners (árvores de decisão, neste caso) em sequência (no loop for);
- 2.a. Gera-se um conjunto de dados a partir do sorteio (com reposição) das amostras do conjunto de dados original, sendo wᵢ a probabilidade da amostra xᵢ ser sorteada. Treina-se o m-ésimo classificador com esse conjunto;
- 2.b. Calcula-se a soma das amostras classificadas incorretamente pelo m-ésimo classificador, ponderada e normalizada pelos pesos wᵢ;
- 2.c. Calcula-se o fator de importância alfa do m-ésimo classificador a partir do erro;
- 2.d. Os pesos de cada amostra são atualizados para o próximo weak learner. Note que as amostras classificadas incorretamente receberão um valor w maior do que aquelas em que o weak learner acertou. Importante destacar também que a soma de todos os pesos deve ser igual a 1;
- 3. A predição final do ensemble será o resultado de uma função sinal {-1, 1}, gerada a partir da soma ponderada entre as predições de cada classificador e seu respectivo fator de importância alfa.
A princípio, o algoritmo pode parecer complexo. Mas, na realidade, a grande “sacada” está na manipulação dos pesos. Quando um weak learner não consegue classificar uma amostra corretamente, o peso dessa amostra é aumentado para que ela tenha mais chances de ser incluída no sorteio do classificador seguinte.
Note também que a proposta original do AdaBoost aborda problemas de classificação binária. Posteriormente, o algoritmo SAMME (Stagewise Additive Modelling) foi introduzido para solucionar problemas multiclasse.
Exemplo com scikit-learn
A scikit-learn fornece uma implementação do AdaBoost por meio da classe AdaboostClassifier. Veja o código abaixo:
Nesse exemplo, implementamos um AdaBoost para classificar o famoso dataset Iris, que possui amostras de três classes diferentes. Nosso ensemble é composto de 50 weak learners e executado pelo algoritmo SAMME.
A scikit-learn implementa, por padrão, o algoritmo SAMME independentemente do problema, seja com duas ou mais classes. Em um próximo artigo, vou trazer os detalhes específicos do SAMME, mas adianto que ele também suporta os casos de classificação binária.
Visualizando a região de decisão do AdaBoost para o exemplo acima, obtemos o gráfico:
Interessante mencionar que o AdaBoost consegue delimitar um fronteira de decisão não-linear com robustez. Se usássemos uma única árvore de decisão para o problema, ela estaria mais suscetível a overfit.
Usando outros tipos de weak learners
Embora a proposta do AdaBoost original utilize árvores de decisão como weak learners, é possível configurar um parâmetro base_estimator ao instanciar um objeto AdaBoostClassifier. Para que um classificador possa ser usado como weak learner no AdaBoost, é requerido que tal classificador possua uma propriedade sample_weight , que armazena os pesos das amostras.
Uma lista dos algoritmos da scikit-learn que implementam sample_weight :
- AdaBoostClassifier
- BaggingClassifier
- BernoulliNB
- CalibratedClassifierCV
- CategoricalNB
- ComplementNB
- DecisionTreeClassifier
- DummyClassifier
- ExtraTreeClassifier
- ExtraTreesClassifier
- GaussianNB
- GradientBoostingClassifier
- HistGradientBoostingClassifier
- LinearSVC
- LogisticRegression
- LogisticRegressionCV
- MultiOutputClassifier
- MultinomialNB
- NuSVC
- Perceptron
- RandomForestClassifier
- RidgeClassifier
- RidgeClassifierCV
- SGDClassifier
- SVC
- StackingClassifier
- VotingClassifier
Por hoje, é só! No próximo artigo, trarei uma implementação do algoritmo SAMME sem o uso da scikit-learn, com mais detalhes do que acontece “por debaixo dos panos”. Não esqueça de comentar!
