Ao impulsionar, por que os alunos são "fracos"?

28

Veja também uma pergunta semelhante em stats.SE .

Ao impulsionar algoritmos como AdaBoost e LPBoost , sabe-se que os alunos "fracos" a serem combinados só precisam ter um desempenho melhor do que o acaso para serem úteis, da Wikipedia:

Os classificadores que ele usa podem ser fracos (ou seja, exibem uma taxa de erro substancial), mas desde que seu desempenho não seja aleatório (resultando em uma taxa de erro de 0,5 para classificação binária), eles melhorarão o modelo final. Mesmo classificadores com uma taxa de erro maior do que seria esperado de um classificador aleatório serão úteis, pois terão coeficientes negativos na combinação linear final de classificadores e, portanto, se comportarão como seus inversos.

  • Quais são os benefícios de usar alunos fracos em oposição a alunos fortes? (por exemplo, por que não impulsionar com métodos de aprendizado "fortes" - somos mais propensos a superajustar?)

  • Existe algum tipo de força "ideal" para os alunos fracos? E isso está relacionado ao número de alunos no conjunto?

Existe alguma teoria para fazer backup das respostas para essas perguntas?

tdc
fonte
Alunos fracos também evitar o excesso de ajuste aos dados de treinamento
Aman profunda Gautam

Respostas:

15

Portanto, impulsionar é um algoritmo de aprendizado, que pode gerar previsões de alta precisão usando como sub-rotina outro algoritmo, que por sua vez pode gerar hipóteses com eficiência apenas um pouco melhor (por um polinômio inverso) do que a suposição aleatória.

Sua principal vantagem é a velocidade.

Quando Schapire a apresentou em 1990, foi um avanço, pois mostrou que um aprendiz de tempo polinomial que gera hipóteses com erros ligeiramente menores que 1/2 pode ser transformado em um aprendiz de tempo polinomial que gera hipóteses com um erro arbitrariamente pequeno.

Portanto, a teoria para respaldar sua pergunta está em "A força da capacidade de aprender fraca" ( pdf ), onde ele basicamente mostrou que a aprendizagem "forte" e "fraca" são equivalentes.

E talvez a resposta da pergunta original seja: "não faz sentido construir aprendizes fortes quando você pode construir alunos fracos mais baratos".


Nos artigos relativamente recentes, há "Sobre a equivalência entre aprendizado fraco e separabilidade linear: novos relaxamentos e algoritmos de impulso eficientes" ( pdf ) que eu não entendo, mas que parecem relacionados e podem ser de interesse para pessoas mais instruídas :)

andreister
fonte
1
+1 boas referências. Então, talvez a resposta seja: "não faz sentido construir aprendizes fortes quando você pode construir alunos fracos mais baratos"?
tdc 17/02/12
sim, parece - eu atualizei a resposta! Além disso, se eu entendi corretamente, isso não depende da força de seus alunos fracos - eles apenas precisam ser "um pouco" melhores do que aleatórios.
andreister
1
Acho que o que vocês realmente querem dizer é: não faz sentido construir aprendizes fortes e caros quando habilidades semelhantes ou até melhores podem ser alcançadas simplesmente combinando muitos aprendizes fracos baratos . De fato, se a habilidade alcançado pelos alunos fortes era muito maior do que a habilidade alcançado pelos alunos fracos, bem, então eu podia ver totalmente o ponto na construção de alunos fortes ...
Antoine
9

Vou abordar o sobreajuste, que ainda não foi mencionado, com uma explicação mais intuitiva. Sua primeira pergunta foi:

Quais são os benefícios de usar alunos fracos em oposição a alunos fortes? (por exemplo, por que não impulsionar com métodos de aprendizado "fortes" - somos mais propensos a superajustar?)

As principais razões, no meu entendimento, são:

  • Velocidade , como coberto muito bem nas outras respostas;
  • Melhoria da precisão : se você já tem um aluno forte, os benefícios de impulsionar são menos relevantes;
  • Evite overfitting , como você adivinhou. Pense nisso desta maneira:

O que o aumento faz é combinar muitas hipóteses diferentes do espaço de hipóteses, para que possamos terminar com uma melhor hipótese final. O grande poder de impulsionar, portanto, vem da diversidade da hipótese combinada.

Se usarmos um aprendiz forte, essa diversidade tende a diminuir: após cada iteração, não haverá muitos erros (já que o modelo é complexo), o que não fará com que a mudança de impulso mude muito a nova hipótese. Com hipóteses muito semelhantes, o conjunto será muito semelhante a um único modelo complexo, que por sua vez tende a se ajustar demais!

Arthur Colombini Gusmão
fonte
4
Esta é a verdadeira resposta.
Matthew Drury
6

Para impulsionar, usamos alunos fracos principalmente porque eles são treinados mais rapidamente em comparação com alunos fortes. Pense nisso. Se eu usar a Rede Neural de várias camadas como aprendiz, preciso treinar muitas delas. Por outro lado, uma árvore de decisão pode ser muito mais rápida, então eu posso treinar muitas delas.

Digamos que eu use 100 alunos. Treino NN em 100 segundos e árvore de decisão em 10 segundos. Meu primeiro aumento com NN levará 100 * 100 segundos, enquanto o segundo aumento com árvore de decisão levará 100 * 10 segundos.

Dito isto, vi artigos, que usam alunos fortes para impulsionar. Mas naqueles problemas que aprendizes fortes eram rápidos na minha opinião.

Tentei treinar o MLP no conjunto de dados de detecção de intrusão KDD99 (4+ milhões) usando Weka. Demorou mais de 72 horas na minha máquina. Mas impulsionar (AdaBoostM1 com Decision Tree - Decision Stump) levou apenas 3 horas. Nesse problema, fica claro que não posso usar o reforço com um aprendiz forte, que é um aprendiz que leva muito tempo.

Atilla Ozgur
fonte
1
"Vi artigos que usam alunos fortes para impulsionar" - alguma referência?
tdc