On the Insufficiency of the Large Margins Theory in Explaining Boosting and Ensemble Performance

• Activity Number: 236
• Type: Contributed
• Date/Time: Monday, August 1, 2011 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Waldyn Martinez Cid*+ and J. Brian Gray
• Companies: University of Alabama and University of Alabama
• Keywords: AdaBoost ; arc-gv ; generalization error ; linear programming

Abstract

AdaBoost (Freund and Schapire 1997) and other ensemble methods combine a set of weak classifiers through weighted voting to produce a strong classifier. Schapire, Freund, Bartlett, and Lee (1998) developed a bound on the generalization error of a combined classifier based on the margins of the training data, the sample size, and the complexity of the weak classifiers. From this bound, they and others (see, e.g., Reyzin and Schapire 2006) have concluded that higher margins should lead to lower generalization error, everything else being equal (sometimes referred to as the "large margins theory"). In this article, we introduce a linear programming (LP) method that increases or maintains all of the margins of an AdaBoost (or any other ensemble) solution using the same set of weak classifiers, yet the resulting combined classifier has similar or worse test set performance than AdaBoost, indicating that the large margins theory is insufficient to explain the performance of AdaBoost.