Some Theoretical Aspects of Boosting in the Presence of Noisy Data

Abstract

This is a survey of some theoretical results on boosting obtained from an analogous treatment of some regression and classification boosting algorithms. Some related papers include [J99] and [J00a,b,c,d], which is a set of (mutually overlapping) papers concerning the assumption of weak hypotheses, behavior of generalization error in the large time limit and during the process of boosting, comparison to the optimal Bayes error in noisy situations, overfitting, and regularization. 1. Introduction Boosting is a method of sequential linear combination of functions in a base hypothesis space. At each time / step t, the linear combination incorporates one more term to optimize an objective function. Examples include AdaBoost [FS97] for classification and Matching Pursuit [MZ93] for regression. `The most basic theoretical property of AdaBoost concerns its ability to reduce training error' [S99]. The training error decreases exponentially fast, subject to an assumption of `weak ba...