Real Boosting a la Carte with an Application to Boosting Oblique Decision Trees

Claudia Henry, Richard Nock, Frank Nielsen

In the past ten years, boosting has become a major field of machine learning and classification. This paper brings contributions to its theory and algorithms. We first unify a well-known top-down decision tree induction algorithm due to Kearns and Mansour, and discrete AdaBoost, as two versions of a same higher-level boosting algorithm. It may be used as the basic building block to devise simple provable boosting algorithms for complex classifiers. We provide one example: the first boosting algorithm for Oblique Decision Trees, an algorithm which turns out to be simpler, faster and significantly more accurate than previous approaches.