Boosting é um método de aprendizado ensemble em machine learning que combina um conjunto de modelos menos precisos, chamados de aprendizes fracos, para criar um único modelo altamente preciso, conhecido como aprendiz forte. Diferentemente de métodos ensemble paralelos, como o bagging, os algoritmos de boosting constroem os modelos sequencialmente. Cada novo modelo na sequência é treinado para corrigir os erros cometidos pelos seus predecessores. Esse processo iterativo melhora a precisão geral, principalmente ao reduzir o viés. Boosting é uma técnica popular e eficaz usada em aprendizado supervisionado, tanto para tarefas de classificação quanto de regressão.
A base teórica do boosting surgiu de uma questão proposta por Kearns e Valiant em 1988 e 1989: seria possível criar um único aprendiz forte a partir de um conjunto de aprendizes fracos? Um aprendiz fraco é definido como um classificador que tem um desempenho apenas um pouco melhor do que a adivinhação aleatória, enquanto um aprendiz forte é altamente correlacionado com a classificação verdadeira. A resposta afirmativa de Robert Schapire em um artigo de 1990 levou ao desenvolvimento dos primeiros algoritmos práticos de boosting. Posteriormente, Freund e Schapire desenvolveram o AdaBoost, que continua sendo um exemplo fundamental da técnica.
Mecanismo Central
Embora não haja uma restrição algorítmica rígida, a maioria dos algoritmos de boosting funciona de forma iterativa, aprendendo aprendizes fracos em relação a uma distribuição de pesos sobre os dados de treinamento e adicionando-os a um classificador final forte. Ao serem adicionados, esses aprendizes fracos são ponderados de acordo com sua precisão. Após a inclusão de cada aprendiz fraco, os pesos dos dados são reajustados: exemplos classificados incorretamente ganham mais peso, enquanto os classificados corretamente perdem peso. Esse processo, conhecido como reponderação, força os aprendizes fracos subsequentes a se concentrarem nos exemplos mais difíceis que foram errôneamente classificados pelos modelos anteriores.
Esse foco sequencial em exemplos difíceis é o que distingue o boosting de outros métodos ensemble. O mecanismo de reponderação garante que cada novo modelo na sequência aborde os erros residuais do conjunto combinado. Ao longo de várias rodadas, o ensemble reduz progressivamente seu viés de treinamento, frequentemente alcançando alta precisão mesmo quando os aprendizes fracos individuais são apenas marginalmente melhores que a chance aleatória.
Desenvolvimento Histórico
Existem muitos algoritmos de boosting. Os originais, propostos por Robert Schapire (através de uma formulação de portão majoritário recursivo) e Yoav Freund (com o método boost by majority), não eram adaptativos e não conseguiam aproveitar totalmente o potencial dos aprendizes fracos. Schapire e Freund então desenvolveram o AdaBoost, um algoritmo adaptativo que conquistou o prestigioso Prêmio Gödel. O AdaBoost foi o primeiro algoritmo capaz de se adaptar aos aprendizes fracos, o que o tornou historicamente significativo e a base para a introdução do boosting em cursos universitários de machine learning.
Somente algoritmos que podem ser formalmente comprovados como métodos de boosting dentro da estrutura de aprendizado provavelmente aproximadamente correto (PAC) podem ser chamados com precisão de algoritmos de boosting. Outros algoritmos com espírito semelhante são, por vezes, chamados de algoritmos de alavancagem, embora também sejam frequentemente (e incorretamente) rotulados como boosting. A principal variação entre muitos algoritmos de boosting está no método de ponderação dos pontos de dados e das hipóteses.
Principais Algoritmos
O AdaBoost continua sendo o algoritmo mais significativo historicamente, mas muitos outros foram desenvolvidos desde então. Entre eles estão o LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost e CatBoost. Muitos desses algoritmos se enquadram na estrutura do AnyBoost, que demonstra que o boosting realiza uma descida de gradiente em um espaço de funções utilizando uma função de custo convexa.
Implementações modernas, como o xgboost e o CatBoost, tornaram-se amplamente utilizadas na indústria e em competições de machine learning devido à sua escalabilidade e desempenho. Esses algoritmos incorporam técnicas de regularização, utilizam aprendizes fracos baseados em árvores de decisão eficientes e oferecem otimizações específicas para dados esparsos e características categóricas. Eles são comumente aplicados em diversos domínios, desde finanças até saúde, frequentemente superando outros métodos em dados tabulares.
Categorização de Objetos em Visão Computacional
Dado um conjunto de imagens contendo vários objetos conhecidos no mundo, um classificador pode ser aprendido a partir delas para classificar automaticamente os objetos em novas imagens. Classificadores simples baseados em uma única característica visual do objeto tendem a ter um desempenho fraco. O uso de métodos de boosting para a categorização de objetos é uma maneira de unificar esses classificadores fracos de forma especial, aumentando a capacidade geral de categorização.
O Problema da Categorização de Objetos
A categorização de objetos é uma tarefa típica de Artificial intelligence e visão computacional que envolve determinar se uma imagem contém uma categoria específica de objeto. A ideia está intimamente relacionada ao reconhecimento e à detecção de objetos. A categorização baseada na aparência tipicamente envolve a extração de características, o aprendizado de um classificador e a aplicação desse classificador a novos exemplos. Há muitas maneiras de representar uma categoria de objeto, desde a análise de forma até modelos de saco de palavras ou descritores locais, como o SIFT. Exemplos de classificadores supervisionados incluem o classificador ingênuo de Bayes, máquinas de vetores de suporte, misturas de gaussianas e redes neurais. No entanto, pesquisas mostraram que categorias de objetos e suas localizações em imagens também podem ser descobertas de forma não supervisionada.
O Estado da Arte na Categorização de Objetos
O reconhecimento de categorias de objetos em imagens é um problema desafiador em visão computacional, especialmente quando o número de categorias é grande. Isso se deve à alta variabilidade intraclasse e à necessidade de generalização diante das variações de objetos dentro da mesma categoria. Objetos de uma mesma categoria podem parecer muito diferentes entre si. Até mesmo o mesmo objeto pode parecer distinto sob diferentes pontos de vista, escalas e condições de iluminação. A desordem de fundo e a oclusão parcial também adicionam dificuldades ao reconhecimento. Enquanto os seres humanos são capazes de reconhecer milhares de tipos de objetos, a maioria dos sistemas de reconhecimento existentes é treinada para reconhecer apenas alguns, como rostos humanos, carros ou objetos simples. A pesquisa tem sido muito ativa em lidar com um número maior de categorias e permitir a adição incremental de novas categorias. Embora o problema geral permaneça em aberto, vários detectores de múltiplas categorias (para centenas ou milhares de categorias) foram desenvolvidos, em parte através do compartilhamento de características e do uso de boosting.
Boosting para Categorização Binária
O AdaBoost pode ser usado para a detecção de rostos como um exemplo de categorização binária, onde as duas categorias são rostos e não-rostos (fundo). O algoritmo geral funciona da seguinte forma: primeiro, um grande conjunto de características simples é formado. Em seguida, os pesos dos exemplos de treinamento são inicializados. Para cada uma das T rodadas, os pesos são normalizados. Um classificador fraco é então treinado usando uma única característica do conjunto disponível, e seu erro de treinamento é avaliado. O classificador com o menor erro é escolhido, e os pesos dos exemplos de treinamento são atualizados: o peso aumenta se o exemplo foi classificado incorretamente e diminui se foi classificado corretamente. Finalmente, o classificador forte é formado pela combinação linear dos T classificadores fracos, onde cada classificador recebe um coeficiente maior se seu erro de treinamento foi menor. Após o boosting, um classificador construído a partir de 200 características pode alcançar uma taxa de detecção de 95% com uma taxa de falsos positivos de 10⁻⁵.
Outra aplicação do boosting para categorização binária é um sistema que detecta pedestres usando padrões de movimento e aparência. Este trabalho foi o primeiro a combinar informações de movimento e aparência como características para detectar uma pessoa em movimento. Ele adota uma abordagem semelhante à estrutura de detecção de objetos Viola-Jones.
Boosting para Categorização Multi-classe
Em comparação com a categorização binária, a categorização multi-classe envolve atribuir uma imagem a uma de várias categorias possíveis de objetos. Métodos de boosting para problemas multi-classe geralmente estendem as abordagens binárias através de estratégias como decomposição um-vs-todos ou um-vs-um, ou modificando diretamente o algoritmo de boosting para lidar com múltiplas classes. Esses métodos permitiram que sistemas de detecção de objetos reconhecessem centenas ou milhares de categorias, embora com um custo computacional aumentado e maior complexidade.
Aplicações e Impacto
O boosting tem sido aplicado em muitos domínios além da visão computacional. Em contextos de Deep learning, as ideias do boosting influenciaram técnicas de ensemble e otimização baseada em gradiente. No processamento de linguagem natural, o boosting é usado para classificação de texto e análise de sentimentos. Em finanças, é utilizado para pontuação de crédito e detecção de fraudes. Em bioinformática, o boosting auxilia na classificação de expressão gênica e na predição de função de proteínas. A capacidade do método de combinar modelos simples em preditores altamente precisos o tornou uma ferramenta essencial tanto na pesquisa acadêmica quanto na prática industrial.
Significância Teórica
A significância teórica do boosting reside na demonstração de que a aprendibilidade fraca implica a aprendibilidade forte. Esse resultado, comprovado por Schapire em 1990, respondeu à questão levantada por Kearns e Valiant e estabeleceu uma base formal para a compreensão do poder dos métodos ensemble. A estrutura de aprendizado provavelmente aproximadamente correto (PAC) fornece garantias formais para os algoritmos de boosting, assegurando que, com um número suficiente de aprendizes fracos, o ensemble pode atingir um erro arbitrariamente baixo na distribuição de treinamento. Essa base teórica distingue o boosting de muitos outros métodos ensemble heurísticos e inspirou uma extensa pesquisa sobre as condições sob as quais o boosting é bem-sucedido.
Limitações e Considerações
O boosting não está isento de limitações. Ele pode ser sensível a dados ruidosos e outliers, pois o mecanismo de reponderação pode fazer com que o ensemble se ajuste excessivamente a exemplos rotulados incorretamente. A natureza sequencial do boosting também o torna menos adequado para paralelização do que o bagging, embora implementações modernas tenham introduzido aproximações para acelerar o treinamento. Além disso, a escolha do aprendiz fraco e o número de rodadas podem afetar significativamente o desempenho, exigindo um ajuste cuidadoso dos hiperparâmetros. Apesar desses desafios, o boosting continua sendo uma das técnicas mais eficazes e amplamente utilizadas em aprendizado supervisionado.