Boosting is a machine learning meta-algorithm for performing supervised learning. Boosting is based on the question posed by Kearns^[1]: 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. As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ... A meta-algorithm is an algorithm that can be usefully considered to have other significant algorithms, not just elementary operations and simple control structures, as its constituents; also an algorithm that has subordinate algorithms as variable and replaceable parameters. ... Supervised learning is a machine learning technique for creating a function from training data. ...

The affirmative answer to Kearns question has significant ramifications in machine learning and statistics. As a broad subfield of artificial intelligence, machine learning is concerned with the design and development of algorithms and techniques that allow computers to learn. At a general level, there are two types of learning: inductive, and deductive. ... A graph of a normal bell curve showing statistics used in educational assessment and comparing various grading methods. ...

Boosting Algorithms

While boosting is not algorithmically constrained, most boosting algorithms follow a template. Typically boosting occurs in iterations, by incrementally adding weak learners to a final strong learner. At every iteration, a weak learner learns the training data with respect to a distribution. The weak learner is then added to the final strong learner. This is typically done by weighting the weak learner in some manner, which is typically related to the weak learner's accuracy. After the weak learner is added to the final strong learner, the data is reweighted: examples that are misclassified gain weight and examples that are classified correctly lose weight (some boosting algorithms will actually decrease the weight of repeatedly misclassified examples, e.g. boost by majority and BrownBoost). Thus, future weak learners will focus more on the examples that previous weak learners misclassified. BrownBoost is a boosting algorithm that is robust to noisy datasets. ...

There are many boosting algorithms. The original algorithms proposed by Rob Schapire (a recursive majority gate formulation ^[2]) and Yoav Freund (boost by majority ^[3]) were not adaptive and could not take full advantage of the weak learners. Yoav Freund is a researcher and professor at the University of California, San Diego who mainly works on machine learning, probability theory and related fields and applications. ...

Some algorithms refer to themselves as "boosting algorithms," and these algorithms can be quite effective. However, in the probably approximately correct learning (PAC) model, only provable boosting algorithms should adopt the title "boosting." Algorithms that are similar to boosting in spirit, but not provably PAC-boosters, are sometimes called "leveraging algorithms." These can be quite effective machine learning algorithms ^[4]. Probably approximately correct learning (PAC learning) is a framework of learning that was proposed by Leslie Valiant in his paper A theory of the learnable. ...

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^[5], which shows that boosting performs gradient descent in function space using a convex cost function. AdaBoost, short for Adaptive Boosting, was formulated by Yoav Freund and Robert Schapire. ... Linear Programming Boosting (LPBoost) is a supervised classifier from the Boosting family of classifiers. ... BrownBoost is a boosting algorithm that is robust to noisy datasets. ... Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. ... In mathematics, a function space is a set of functions of a given kind from a set X to a set Y. It is called a space because in many applications, it is a topological space or a vector space or both. ... Look up convex in Wiktionary, the free dictionary. ...

References

• 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. http://www.cse.ucsd.edu/~yfreund/papers/adaboost.pdf
• Robert E. Schapire and Yoram Singer. Improved Boosting Algorithms Using Confidence-Rated Predictors. Machine Learning, 37(3):297--336, 1999. http://citeseer.ist.psu.edu/schapire99improved.html

See also

• AdaBoost
• LPBoost
• Bootstrap aggregating
• BrownBoost
• Alternating decision tree

• logistic regression
• maximum entropy methods
• neural networks
• support vector machines

AdaBoost, short for Adaptive Boosting, was formulated by Yoav Freund and Robert Schapire. ... Linear Programming Boosting (LPBoost) is a supervised classifier from the Boosting family of classifiers. ... Bootstrap aggregating (bagging) is a meta-algorithm to improve classification and regression models in terms of stability and classification accuracy. ... BrownBoost is a boosting algorithm that is robust to noisy datasets. ... An Alternating Decision Tree (ADTree) is a machine learning method for classification. ... Logistic regression is a statistical regression model for Bernoulli-distributed dependent variables. ... The principle of maximum entropy is a method for analyzing the available information in order to determine a unique epistemic probability distribution. ... // See also Artificial neural network. ... Support vector machines (SVMs) are a set of related supervised learning methods used for classification and regression. ...

External links

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