ABSTRACT
AdaBoost [9, 10] is one of the most influential ensemble methods. It took birth from the answer to an interesting question posed by Kearns and Valiant in 1988. That is, whether two complexity classes, weakly learnable and strongly learnable problems, are equal. If the answer to the question is positive, a weak learner that performs just slightly better than random guess can be “boosted” into an arbitrarily accurate strong learner. Obviously, such a question is of great importance to machine learning. Schapire [21] found that the answer to the question is “yes,” and gave a proof by construction, which is the first boosting algorithm. An important practical deficiency of this algorithm is the requirement that the error bound of the base learners be known ahead of time, which is usually unknown in practice. Freund and Schapire [9] then proposed an adaptive boosting algorithm, named AdaBoost, which does not require those unavailable information. It is evident that AdaBoost was born with theoretical significance, which has given rise to abundant research on theoretical aspects of ensemble methods in communities of machine learning and statistics. It is worth mentioning that for their AdaBoost paper [9], Schapire and Freund won the Godel Prize, which is one of the most prestigious awards in theoretical computer science, in the year 2003.
