Boosting is a machine learning meta-algorithm for performing supervised learning. Boosting is based on the question posed by KearnsMichael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988] : can a set of weak learners create a single strong learner ? A weak learner is defined to be a classifier which is only slightly correlated with the true classification. In contrast, a strong learner is a classifier that is arbitrarily well-correlated with the true classification.

The affirmative answer to Kearns' question has significant ramifications in machine learning and statistics.

Boosting algorithms

While boosting is not algorithmically constrained, most boosting algorithms consist of iteratively learning weak classifiers with respect to a distribution and adding them to a final strong classifier. When they are added, they are typically weighted in some way that is usually related to the weak learner's accuracy. After a weak learner is added, the data is reweighted: examples that are misclassified gain weight and examples that are classified correctly lose weight (some boosting algorithms actually decrease the weight of repeatedly misclassified examples, e.g., boost by majority and BrownBoost). Thus, future weak learners focus more on the examples that previous weak learners misclassified.

There are many boosting algorithms. The original ones, proposed by Robert Schapire (a recursive majority gate formulation Rob Schapire. Strength of Weak Learnability. Journal of Machine Learning Vol. 5, pages 197-227. 1990] ) and Yoav Freund (boost by majority Yoav Freund. Boosting a weak learning algorithm by majority. Proceedings of the Third Annual Workshop on Computational Learning Theory. 1990] ) were not adaptive and could not take full advantage of the weak learners.

Only algorithms that are provable boosting algorithms in the probably approximately correct learning formulation are boosting algorithms. Other algorithms that are similar in spirit to boosting algorithms are sometimes called "leveraging algorithms", although they are also sometimes incorrectly called boosting algorithms.Nir Krause and Yoram Singer. Leveraging the margin more carefully. In Proceedings of the International Conference on Machine Learning (ICML), 2004.]

Examples of boosting algorithms

The main variation between many boosting algorithms is their method of weighting training data points and hypotheses. AdaBoost is very popular and perhaps the most significant historically as it was the first algorithm that could adapt to the weak learners. However, there are many more recent algorithms such as LPBoost, TotalBoost, BrownBoost,MadaBoost, LogitBoost, and others. Many boosting algorithms fit into the AnyBoost framework,Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In S.A. Solla, T.K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pages 512--518. MIT Press, 2000] which shows that boosting performs gradient descent in function space using a convex cost function.

See also




* Yoav Freund and Robert E. Schapire A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119--139, 1997.
* Robert E. Schapire and Yoram Singer. Improved Boosting Algorithms Using Confidence-Rated Predictors. Machine Learning, 37(3):297--336, 1999.

External links

* [ The boosting approach to machine learning: An overview]
* [ The strength of weak learnability]
* [ An up-to-date collection of papers on boosting]

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • boosting — index cumulative (intensifying), promotion (encouragement) Burton s Legal Thesaurus. William C. Burton. 2006 …   Law dictionary

  • Boosting — Klassifizierung in fünf Klassen. Der durch Boosting erzeugte Klassifikator klassifiziert nur in zwei Klassen, sozusagen binär. Boosting (engl. „Verstärken“) ist ein Algorithmus der automatischen Klassifizierung, der mehrere schlechte… …   Deutsch Wikipedia

  • Boosting — Le boosting est un domaine de l apprentissage automatique (branche de l intelligence artificielle). C est un principe qui regroupe de nombreux algorithmes qui s appuient sur des ensembles de classifieurs binaires : le boosting optimise leurs …   Wikipédia en Français

  • Boosting — Boost Boost (b[=oo]st), v. t. [imp. & p. p. {Boosted}; p. pr. & vb. n. {Boosting}.] [Cf. {Boast}, v. i.] To lift or push from behind (one who is endeavoring to climb); to push up; hence, to assist in overcoming obstacles, or in making advancement …   The Collaborative International Dictionary of English

  • boosting — See start boosting …   Dictionary of automotive terms

  • Boosting (disambiguation) — Boosting may refer to:* Boosting, a machine learning meta algorithm * Boosted fission weapon * A slang term for stealing, usually shoplifting * Boosting (video game), cheating to obtain progress or increase ranks in a video game, especially… …   Wikipedia

  • Boosting methods for object categorization — Given images containing various known objects in the world, a classifier can be learned from them to automatically categorize the objects in future images. Simple classifiers built based on some image feature of the object tend to be weak in… …   Wikipedia

  • Boosting (Sport) — Als Boosting bezeichnet man eine Methode der unerlaubten Leistungssteigerung im Sport, bei der ein Sportler sich selbst Schmerzen zufügt, um durch den Adrenalinschub mehr leisten zu können. Damit ist es dem Doping vergleichbar. Allgemeines Das… …   Deutsch Wikipedia

  • boosting — n. use of one drug to rais blood levels as to intensify the activity of another drug (Medicine) buːst n. push, shove; raising, lift; incentive, encouragement v. raise; push; urge …   English contemporary dictionary

  • boosting ratio — Смотри коэффициент форсирования …   Энциклопедический словарь по металлургии

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”