Boosting (aprendizado de máquina) - Boosting (machine learning)

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

No aprendizado de máquina , o boosting é um meta-algoritmo de conjunto para reduzir principalmente o preconceito e também a variação no aprendizado supervisionado , além de uma família de algoritmos de aprendizado de máquina que converte alunos fracos em fortes. O reforço é baseado na pergunta feita por Kearns e Valiant (1988, 1989): "Um conjunto de alunos fracos pode criar um único aluno forte?" Um aluno fraco é definido como um classificador apenas ligeiramente correlacionado com a classificação verdadeira (pode rotular exemplos melhor do que adivinhação aleatória). Em contraste, um aluno forte é um classificador arbitrariamente bem correlacionado com a classificação verdadeira.

A resposta afirmativa de Robert Schapire em um artigo de 1990 à questão de Kearns e Valiant teve ramificações significativas em aprendizado de máquina e estatística , principalmente levando ao desenvolvimento de boosting.

Quando introduzido pela primeira vez, o problema de reforço de hipóteses simplesmente se referia ao processo de transformar um aluno fraco em um aluno forte. "Informalmente, [o aumento da hipótese] problema pergunta se um algoritmo de aprendizagem eficiente [...] que produz uma hipótese cujo desempenho é apenas ligeiramente melhor do que adivinhação aleatória [ou seja, um aluno fraco] implica a existência de um algoritmo eficiente que produz uma hipótese de precisão [ou seja, um bom aluno]. " Algoritmos que alcançam o boost de hipótese rapidamente tornaram-se simplesmente conhecidos como "boosting". O arco de Freund e Schapire (Adapt [at] ive Resampling and Combining), como uma técnica geral, é mais ou menos sinônimo de boosting.

Algoritmos de impulso

Embora o boosting não seja restrito por algoritmos, a maioria dos algoritmos de boosting consiste em aprender iterativamente classificadores fracos em relação a uma distribuição e adicioná-los a um classificador forte final. Quando eles são adicionados, eles são ponderados de uma forma que está relacionada à precisão dos alunos fracos. Depois que um aluno fraco é adicionado, as ponderações dos dados são reajustadas, conhecido como " reponderação ". Os dados de entrada classificados incorretamente ganham um peso maior e os exemplos que são classificados corretamente perdem peso. Assim, os futuros alunos fracos concentram-se mais nos exemplos que os alunos fracos anteriores classificaram incorretamente.

Uma ilustração que apresenta a intuição por trás do algoritmo de boosting, consistindo nos alunos paralelos e no conjunto de dados ponderado.

Existem muitos algoritmos de impulso. Os originais, propostos por Robert Schapire (uma formulação de porta de maioria recursiva ) e Yoav Freund (aumento por maioria), não eram adaptativos e não podiam tirar vantagem total dos alunos fracos. Schapire e Freund desenvolveram AdaBoost , um algoritmo de aumento adaptativo que ganhou o prestigioso Prêmio Gödel .

Apenas algoritmos que são algoritmos de impulso comprováveis ​​na formulação de aprendizado provavelmente aproximadamente correta podem ser chamados com precisão de algoritmos de impulso . Outros algoritmos que são semelhantes em espírito aos algoritmos de impulso são às vezes chamados de "algoritmos de alavancagem", embora também sejam chamados incorretamente de algoritmos de impulso.

A principal variação entre muitos algoritmos de boosting é seu método de ponderar pontos de dados de treinamento e hipóteses . AdaBoost é muito popular e o mais significativo historicamente, pois foi o primeiro algoritmo que se adaptou aos alunos fracos. Muitas vezes, é a base para a cobertura introdutória do incentivo em cursos universitários de aprendizado de máquina. Existem muitos algoritmos mais recentes, como LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost e outros. Muitos algoritmos de boosting se encaixam na estrutura AnyBoost, que mostra que o boosting executa a descida de gradiente em um espaço de função usando uma função de custo convexa .

Categorização de objetos em visão computacional

Dadas imagens contendo vários objetos conhecidos no mundo, um classificador pode ser aprendido com elas para classificar automaticamente os objetos em imagens futuras. Classificadores simples construídos com base em algum recurso de imagem do objeto tendem a ser fracos no desempenho de categorização. Usar métodos de boosting para categorização de objetos é uma maneira de unificar os classificadores fracos de uma maneira especial para aumentar a capacidade geral de categorização.

Problema de categorização de objetos

A categorização de objetos é uma tarefa típica de visão computacional que envolve determinar se uma imagem contém ou não alguma categoria específica de objeto. A ideia está intimamente relacionada com reconhecimento, identificação e detecção. A categorização de objetos baseada em aparência normalmente contém extração de recursos , aprendizagem de um classificador e aplicação do classificador a novos exemplos. Existem muitas maneiras de representar uma categoria de objetos, por exemplo, de análise de forma , modelos de saco de palavras ou descritores locais, como SIFT , etc. Exemplos de classificadores supervisionados são classificadores Naive Bayes , máquinas de vetores de suporte , misturas de gaussianas e redes neurais . No entanto, a pesquisa mostrou que as categorias de objetos e suas localizações nas imagens também podem ser descobertas de maneira não supervisionada .

Status quo para categorização de objetos

O reconhecimento de categorias de objetos em imagens é um problema desafiador na visão computacional , especialmente quando o número de categorias é grande. Isso se deve à alta variabilidade intraclasse e à necessidade de generalização entre variações de objetos dentro da mesma categoria. Os objetos dentro de uma categoria podem ter uma aparência bem diferente. Até mesmo o mesmo objeto pode parecer diferente sob diferentes pontos de vista, escala e iluminação . A desordem de fundo e a oclusão parcial também dificultam o reconhecimento. Os humanos são capazes de reconhecer milhares de tipos de objetos, enquanto a maioria dos sistemas de reconhecimento de objetos existentes são treinados para reconhecer apenas alguns, por exemplo , rostos humanos , carros , objetos simples, etc. A pesquisa tem sido muito ativa em lidar com mais categorias e permitir incremental acréscimos de novas categorias e, embora o problema geral permaneça sem solução, vários detectores de objetos multicategorias (para até centenas ou milhares de categorias) foram desenvolvidos. Um meio é por recurso partilha e reforço.

Impulsionando a categorização binária

AdaBoost pode ser usado para detecção de rosto como um exemplo de categorização binária . As duas categorias são faces versus fundo. O algoritmo geral é o seguinte:

1. Forme um grande conjunto de recursos simples
2. Inicializar pesos para imagens de treinamento
3. Para rodadas T
   1. Normalizar os pesos
   2. Para os recursos disponíveis do conjunto, treine um classificador usando um único recurso e avalie o erro de treinamento
   3. Escolha o classificador com o menor erro
   4. Atualize os pesos das imagens de treinamento: aumente se classificado incorretamente por este classificador, diminua se estiver correto
4. Forme o classificador final forte como a combinação linear dos classificadores T (coeficiente maior se o erro de treinamento for pequeno)

Após o boost, um classificador construído a partir de 200 recursos poderia render uma taxa de detecção de 95% sob uma taxa de falsos positivos . ${\ displaystyle 10 ^ {- 5}}$

Outra aplicação de boosting para categorização binária é um sistema que detecta pedestres usando padrões de movimento e aparência. Este trabalho é o primeiro a combinar informações de movimento e informações de aparência como recursos para detectar uma pessoa caminhando. Ele adota uma abordagem semelhante à estrutura de detecção de objetos Viola-Jones .

Impulsionando a categorização multiclasse

Comparada com a categorização binária, a categorização multiclasse procura recursos comuns que podem ser compartilhados entre as categorias ao mesmo tempo. Eles se transformam em recursos mais genéricos, semelhantes a arestas . Durante o aprendizado, os detectores de cada categoria podem ser treinados em conjunto. Em comparação com o treinamento separadamente, ele generaliza melhor, precisa de menos dados de treinamento e requer menos recursos para atingir o mesmo desempenho.

O fluxo principal do algoritmo é semelhante ao caso binário. A diferença é que uma medida do erro de treinamento conjunto deve ser definida com antecedência. Durante cada iteração, o algoritmo escolhe um classificador de um único recurso (recursos que podem ser compartilhados por mais categorias devem ser encorajados). Isso pode ser feito convertendo a classificação multiclasse em binária (um conjunto de categorias versus o resto) ou introduzindo um erro de penalidade das categorias que não têm o recurso do classificador.

No artigo "Compartilhando recursos visuais para detecção de objetos multiclasse e multivista", A. Torralba et al. usou o GentleBoost para impulsionar e mostrou que quando os dados de treinamento são limitados, aprender por meio de recursos de compartilhamento faz um trabalho muito melhor do que nenhum compartilhamento, dadas as mesmas rodadas de incentivo. Além disso, para um determinado nível de desempenho, o número total de recursos necessários (e, portanto, o custo de tempo de execução do classificador) para os detectores de compartilhamento de recursos, é observado para escalar aproximadamente logaritmicamente com o número de classes, ou seja, mais lento do que o crescimento linear em o caso de não compartilhamento. Resultados semelhantes são mostrados no artigo "Aprendizagem incremental de detectores de objetos usando um alfabeto de forma visual", mas os autores usaram AdaBoost para impulsionar.

Algoritmos de aumento convexo vs. não convexo

Os algoritmos de reforço podem ser baseados em algoritmos de otimização convexos ou não convexos. Algoritmos convexos, como AdaBoost e LogitBoost , podem ser "derrotados" por ruído aleatório de forma que eles não possam aprender combinações básicas e fáceis de aprender de hipóteses fracas. Essa limitação foi apontada por Long & Servedio em 2008. No entanto, em 2009, vários autores demonstraram que algoritmos de otimização baseados em otimização não convexa, como BrownBoost , podem aprender com conjuntos de dados ruidosos e podem aprender especificamente o classificador subjacente do Long– Conjunto de dados Servedio.

Veja também

Implementações

• Scikit-learn , uma biblioteca de aprendizado de máquina de código aberto para python
• Orange , um pacote de software de mineração de dados gratuito, módulo Orange.ensemble
• Weka é um conjunto de ferramentas de aprendizado de máquina que oferece implementações variadas de algoritmos de impulso, como AdaBoost e LogitBoost
• O pacote R GBM (Generalized Boosted Regression Models) implementa extensões para o algoritmo AdaBoost de Freund e Schapire e a máquina de aumento de gradiente de Friedman.
• jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter e árvores de decisão alternadas
• Pacote R adabag : Aplica Multiclass AdaBoost.M1, AdaBoost-SAMME e Bagging
• Pacote R xgboost : Uma implementação de aumento de gradiente para modelos lineares e baseados em árvore.

Notas

Referências

Leitura adicional

• Yoav Freund e Robert E. Schapire (1997); A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting , Journal of Computer and System Sciences, 55 (1): 119-139
• Robert E. Schapire e Yoram Singer (1999); Algoritmos de impulso aprimorados usando preditores com classificação de confiança , aprendizado de máquina, 37 (3): 297-336

links externos

• Robert E. Schapire (2003); The Boosting Approach to Machine Learning: An Overview , MSRI (Mathematical Sciences Research Institute) Workshop on Nonlinear Estimation and Classification
• Zhou Zhi-Hua (2014) Boosting 25 years , CCL 2014 Keynote.
• Zhou, Zhihua (2008). "Explicação da margem do algoritmo de impulso" (PDF) . In: Proceedings of the 21st Annual Conference on Learning Theory (COLT'08) : 479–490.
• Zhou, Zhihua (2013). “Na dúvida sobre a margem de explicação do boosting” (PDF) . Inteligência Artificial . 203 : 1-18. arXiv : 1009,3613 . doi : 10.1016 / j.artint.2013.07.002 . S2CID  2828847 .