Optimal Weak to Strong Learning

The field of boosting has been started from a classic question in learning theory asking whether classifiers that are just slightly better than random guessing can be used to create a classifier with arbitrarily high accuracy when given enough training data. This question was initially asked by Kearns and Valiant [15, 16] and ignited the line of research that eventually lead to the development of AdaBoost [7], the prototype boosting algorithm to date. AdaBoost carefully combines the predictions of several inaccurate classifiers trained with a focus on different parts of the training data to come up with a voting classifier that performs well everywhere. We quantify the performance of an inaccurate learner by its advantage over random guessing. Said loosely, a -weak learner will correctly classify new data points with probability at least 1/2+. In contrast, given 0 <, < 1 and enough training data a strong learner outputs with probability 1 over the choice of the training data and possible random choices of the algorithm a hypothesis that correctly classifies new data points with probability at least 1 .