Special Invited Paper-Additive logistic regression: A statistical view of boosting

Abstract

Boosting is one of the most important recent developments in\nclassification methodology. Boosting works by sequentially applying a\nclassification algorithm to reweighted versions of the training data and then\ntaking a weighted majority vote of the sequence of classifiers thus produced.\nFor many classification algorithms, this simple strategy results in dramatic\nimprovements in performance. We show that this seemingly mysterious phenomenon\ncan be understood in terms of well-known statistical principles, namely\nadditive modeling and maximum likelihood. For the two-class problem, boosting\ncan be viewed as an approximation to additive modeling on the logistic scale\nusing maximum Bernoulli likelihood as a criterion. We develop more direct\napproximations and show that they exhibit nearly identical results to boosting.\nDirect multiclass generalizations based on multinomial likelihood are derived\nthat exhibit performance comparable to other recently proposed multiclass\ngeneralizations of boosting in most situations, and far superior in some. We\nsuggest a minor modification to boosting that can reduce computation, often by\nfactors of 10 to 50. Finally, we apply these insights to produce an alternative\nformulation of boosting decision trees. This approach, based on best-first\ntruncated tree induction, often leads to better performance, and can provide\ninterpretable descriptions of the aggregate decision rule. It is also much\nfaster computationally, making it more suitable to large-scale data mining\napplications.