Boosting

De la Viquipèdia, l'enciclopèdia lliure
Una il·lustració que presenta la intuïció que hi ha darrere de l'algorisme de reforç, que consisteix en els aprenents paral·lels i el conjunt de dades ponderades.

En l'aprenentatge automàtic, el boosting (reforç) és un metaalgoritme de conjunt per reduir principalment el biaix, i també la variància[1] en l'aprenentatge supervisat, i una família d'algorismes d'aprenentatge automàtic que converteixen els aprenents febles en forts.[2] El reforç es basa en la pregunta plantejada per Kearns i Valiant (1988, 1989):[3][4] "Pot un conjunt d'aprenents febles crear un sol aprenent fort?" Un alumne feble es defineix com un classificador que només està lleugerament correlacionat amb la classificació veritable (pot etiquetar exemples millor que endevinar aleatòriament). En canvi, un aprenent fort és un classificador que està ben correlacionat arbitràriament amb la veritable classificació.

La resposta afirmativa de Robert Schapire en un article de 1990 [5] a la pregunta de Kearns i Valiant ha tingut ramificacions significatives en l'aprenentatge automàtic i les estadístiques, sobretot conduint al desenvolupament del reforç.[6]

Classificació en cinc classes. El classificador generat per reforç només es classifica en dues classes.

Quan es va introduir per primera vegada, el problema de reforç d'hipòtesis es referia simplement al procés de convertir un aprenent feble en un aprenent fort. "Informalment, [el problema de reforç d'hipòtesis] es pregunta si un algorisme d'aprenentatge eficient […] que produeix una hipòtesi el rendiment de la qual és només lleugerament millor que l'endevinació aleatòria [és a dir, un aprenent feble] implica l'existència d'un algorisme eficient que produeix una hipòtesi d'arbitrària. precisió [és a dir, un aprenent fort]".[7] Els algorismes que aconsegueixen l'augment d'hipòtesis ràpidament es van conèixer simplement com a "boosting". L'arc de Freund i Schapire (Adapt[at]ive Resampling and Combining),[8] com a tècnica general, és més o menys sinònim de boosting.[9]

La principal variació entre molts algorismes de reforç és el seu mètode per ponderar els punts de dades d'entrenament i les hipòtesis. AdaBoost és molt popular i el més significatiu històricament, ja que va ser el primer algorisme que es va poder adaptar als aprenents febles. Sovint és la base de la cobertura introductòria de l'impuls en els cursos universitaris d'aprenentatge automàtic.[10] Hi ha molts algorismes més recents com LPBoost, TotalBoost, BrownBoost, xgboost, MadaBoost, LogitBoost i altres. Molts algorismes de reforç s'ajusten al marc AnyBoost,[11] que mostra que l'impuls realitza un descens de gradient en un espai de funcions utilitzant una funció de cost convexa.

Referències[modifica]

  1. ↑ Leo Breiman. «BIAS, VARIANCE, AND ARCING CLASSIFIERS». TECHNICAL REPORT, 1996. Arxivat de l'original el 2015-01-19. [Consulta: 19 gener 2015].
  2. ↑ Zhou Zhi-Hua. Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC, 2012, p. 23. ISBN 978-1439830031. 
  3. ↑ Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
  4. ↑ Michael Kearns. Cryptographic limitations on learning Boolean formulae and finite automata. 21. ACM, 1989, p. 433–444. DOI 10.1145/73007.73049. ISBN 978-0897913072. 
  5. ↑ Schapire, Robert E. «Còpia arxivada». Machine Learning, 5, 2, 1990, pàg. 197–227. Arxivat de l'original el 2012-10-10. DOI: 10.1007/bf00116037 [Consulta: 23 agost 2012].
  6. ↑ Leo Breiman Ann. Stat., 26, 3, 1998, pàg. 801–849. DOI: 10.1214/aos/1024691079 [Consulta: free]. «Schapire (1990) proved that boosting is possible. (Page 823)»
  7. ↑ Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
  8. ↑ Yoav Freund and 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
  9. ↑ Leo Breiman (1998); Arcing Classifier (with Discussion and a Rejoinder by the Author), Annals of Statistics, vol. 26, no. 3, pp. 801-849: "The concept of weak learning was introduced by Kearns and Valiant (1988, 1989), who left open the question of whether weak and strong learnability are equivalent. The question was termed the boosting problem since [a solution must] boost the low accuracy of a weak learner to the high accuracy of a strong learner. Schapire (1990) proved that boosting is possible. A boosting algorithm is a method that takes a weak learner and converts it into a strong learner. Freund and Schapire (1997) proved that an algorithm similar to arc-fs is boosting.
  10. ↑ Emer, Eric. «Boosting (AdaBoost algorithm)». MIT. Arxivat de l'original el 2022-10-09. [Consulta: 10 octubre 2018].
  11. ↑ Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean (2000); Boosting Algorithms as Gradient Descent, in S. A. Solla, T. K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pp. 512-518, MIT Press
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Boosting&oldid=32310844»