Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers

By Abraham J. Wyner, Justin Bleich, David Mease. 2015

311 citations recorded by the source corpus.

There is a large literature explaining why AdaBoost is a successful classifier. The literature on AdaBoost focuses on classifier margins and boosting's interpretation as the optimization of an exponential likelihood function. These existing explanations, however, have been pointed out to be incomplete. A random forest is another popular ensemble method for which there is substantially less explanation in the literature. We introduce a novel perspective on AdaBoost and random forests that proposes that the two algorithms work for similar reasons. While both classifiers achieve similar predictive accuracy, random forests cannot be conceived as a direct optimization procedure. Rather, random forests is a self-averaging, interpolating algorithm which creates what we denote as a "spikey-smooth" classifier, and we view AdaBoost in the same light. We conjecture that both AdaBoost and random forests succeed because of this mechanism. We provide a number of examples and some theoretical justification to support this explanation. In the process, we question the conventional wisdom that suggests that boosting algorithms for classification require regularization or early stopping and should be limited to low complexity classes of learners, such as decision stumps. We conclude that boosting should be used like random forests: with large decision trees and without direct regularization or early stopping.

Subfields: Artificial Intelligence, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

Citations in the corpus

Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, neutral): “AdaBoost and Random Forests have recently been investigated in the interpolation regime by [41] for classiﬁcation.”
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, background): “Another line of research focuses on the generalization error of algorithms that fit the data perfectly (referred to as interpolating) [29, 10, 8, 20, 9, 25, 5, 7, 14, 21].”
InSDN: A Novel SDN Intrusion Dataset (2020, methodology): “Specifically, we employed three tree-based algorithms: a single Decision Tree (DT) [78], Random Forest (RF) [79], and Adaptive Boosting (AdaBoost) [80] learner.”
A Comparison of Undersampling, Oversampling, and SMOTE Methods for Dealing with Imbalanced Classification in Educational Data Mining (2023, background): “Both algorithms fall under the ensemble learning family and are successful in their application [42,43].”
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate (2018, methodology): “[51] proposed a thought-provoking explanation for the performance of AdaBoost and random forests in the interpolation regime, based on ideas related to “self-averaging” and localization.”
Under review as a conference paper at ICLR 2020 many domain adaptation methods (2019, background): “As noticed in the literature Wyner et al. (2017); Gomes et al. (2017), the random forests tend not to propagate severe overfitting error even with a large number of trees.”