AdaBoost

Natureza	Algoritmo , metaheurísticas

AdaBoost (ou adaptativa aumentar ) é, na inteligência artificial e aprendizagem de máquina , um aumento meta-algoritmo introduzido por Yoav Freund e Robert Schapire . Ele pode ser usado em conjunto com muitos outros tipos de algoritmos de aprendizagem para melhorar o desempenho. As saídas dos outros algoritmos (chamados de classificadores fracos ) são combinadas em uma soma ponderada que representa a saída final do classificador impulsionado . AdaBoost é adaptativo no sentido de que classificadores fracos subsequentes são ajustados em favor de amostras classificadas incorretamente pelos classificadores anteriores.

AdaBoost é notavelmente sensível a dados ruidosos ou mal correlacionados. No entanto, em alguns problemas, pode ser menos sujeito a overfitting do que outros algoritmos. Os subclassificadores usados podem ser fracos, desde que tenham um desempenho pelo menos um pouco melhor do que um classificador aleatório, caso em que pode haver evidências de que o modelo final converge para um classificador forte.

Todos os algoritmos de aprendizagem tendem a corresponder a alguns tipos de problemas mais do que outros e, normalmente, têm muitos parâmetros e configurações diferentes que precisam ser ajustados para atingir o desempenho ideal em um conjunto de aprendizagem. AdaBoost (com árvores de decisão como pastas de trabalho fracas) é freqüentemente referido como a melhor pasta de trabalho pronta para uso.

Princípio

Adaboost depende da seleção iterativa do classificador fraco com base em uma distribuição de exemplos de treinamento. Cada exemplo é ponderado de acordo com sua dificuldade com o classificador atual. Este é um exemplo do método de pesos multiplicativos ( método de atualização de pesos multiplicativos ).

Descrição

Let Ser um conjunto de observações. Observe-os: onde estão as características do indivíduo e a variável a prever. $(x_ {1}, y_ {1}), \ ldots, (x_ {m}, y_ {m})$ $x_ {i} \ em X,$ $eu$ $\, y_ {i} \ in Y = \ {- 1, + 1 \}$

Inicializamos o peso associado a , $eu$ ${\ displaystyle D_ {t} (i) = {\ frac {1} {m}}, i = 1, \ ldots, m.}$

Para : $t = 1, \ ldots, T$

Encontre a função que minimiza o erro de classificação com base nos pesos . Ou seja, o que verifica o seguinte programa de minimização: $h_ {t}: X \ a \ {- 1, + 1 \}$ $\ epsilon _ {t}$ $D _ {{t}}$ $h_t$

$h_ {t} = \ arg \ min _ {h \ in {\ mathcal {H}}} \ sum _ {i = 1} ^ {m} D_ {t} (i) [y_ {i} \ neq h ( XI})]$

$\ epsilon _ {t} = \ sum _ {i = 1} ^ {m} D_ {t} (i) [y_ {i} \ neq h (x_ {i})]$ é o erro do modelo.

Se a função for selecionada, caso contrário, o algoritmo para $\ epsilon _ {min, t} <0,5$
Em seguida, calculamos a etapa do gradiente :, com $\ alpha _ {t} \ in \ mathbf {R}$ $\ alpha _ {t} = {\ frac {1} {2}} {\ textrm {ln}} {\ frac {1- \ epsilon _ {t}} {\ epsilon _ {t}}}$
Em seguida, atualizamos o peso dos exemplos:

$D_ {t + 1} (i) = {\ frac {D_ {t} (i) \, e ^ {- \ alpha _ {t} y_ {i} h_ {t} (x_ {i})}} { Z_ {t}}}$
com um fator de normalização igual a $Z _ {{t}}$ $2 {\ sqrt {\ epsilon _ {t} (1- \ epsilon _ {t})}}$

Quando o algoritmo para na iteração , o classificador resultante do processo de seleção é: $M$

${\ displaystyle H (x) = {\ textrm {sign}} \ left (\ sum _ {t = 1} ^ {M} \ alpha _ {t} h_ {t} (x) \ right)}$

Variantes

Variantes foram introduzidas e as mudanças se relacionam principalmente à maneira como os pesos são atualizados. Entre essas variantes, Gentle AdaBoost e Real Adaboost são freqüentemente usados. Outro exemplo é o RankBoost .

História

Este foi um dos primeiros métodos totalmente funcionais para implementar o princípio de impulso. Os autores receberam o prestigioso Prêmio Gödel em 2003 por sua descoberta.

Notas e referências

( Freund e Schapire 1997 )
Sanjeev Arora , Elad Hazan e Satyen Kale, “ O Método de Atualização de Pesos Multiplicativos: um Meta Algoritmo e Aplicações ” .
“ O método de atualização de pesos multiplicativos ” , na Universidade de Washington .
Página oficial do Prêmio Gödel 2003

Bibliografia

(pt) Yoav Freund e Robert Schapire , “ Uma generalização da teoria da decisão da aprendizagem on-line e uma aplicação para impulsionar ” , Journal of Computer and System Sciences , vol. 55, n o 1,1997, p. 119-139 ( ler online )

links externos

Boosting.org , um site sobre incentivos em geral
Uma breve introdução ao Boosting Introdução ao Adaboost por Freund e Schapire em 1999