Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Quickly Boosting Decision Trees - Pruning Underachieving Features Early

Ron Appel, Thomas Fuchs, Piotr Dollár, and Pietro Perona

Abstract

Boosted decision trees are among the most popular learning techniques in use today. While exhibiting fast speeds at test time, relatively slow training renders them impractical for applications with real-time learning requirements. We propose a principled approach to overcome this drawback. We prove a bound on the error of a decision stump given its preliminary error on a subset of the training data; the bound may be used to prune unpromising features early in the training process. We propose a fast training algorithm that exploits this bound, yielding speedups of an order of magnitude at no cost in the final performance of the classifier. Our method is not a new variant of Boosting; rather, it is used in conjunction with existing Boosting algorithms and other sampling methods to achieve even greater speedups.

Details

Publication typeInproceedings
Published inICML
PublisherInternational Conference on Machine Learning
> Publications > Quickly Boosting Decision Trees - Pruning Underachieving Features Early