ABSTRACT
The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners. Intuitively, a weak learner is just slightly better than randomguess, while a strong learner is very close to perfect performance. The birth of boosting algorithms originated from the answer to an interesting theoretical question posed byKearns and Valiant [1989]. That is, whether two complexity classes, weakly learnable and strongly learnable problems, are equal. This question is of fundamental importance, since if the answer is positive, anyweak learner is potentially able to be boosted to a strong learner, particularly if we note that in real practice it is generally very easy to obtain weak learners but difficult to get strong learners. Schapire [1990] proved that the answer is positive, and the proof is a construction, i.e., boosting.
