Adaptively Pruning Features for Boosted Decision Trees
This work addresses efficiency issues for practitioners using boosted decision trees in large-scale applications, though it is incremental as it builds on existing methods with specific improvements.
The paper tackles the high computational cost of training boosted decision trees on large-scale datasets by developing an efficient algorithm that computes exact greedy-optimal trees, outperforming the state-of-the-art Quick Boost method and achieving near-optimal performance close to derived lower bounds.
Boosted decision trees enjoy popularity in a variety of applications; however, for large-scale datasets, the cost of training a decision tree in each round can be prohibitively expensive. Inspired by ideas from the multi-arm bandit literature, we develop a highly efficient algorithm for computing exact greedy-optimal decision trees, outperforming the state-of-the-art Quick Boost method. We further develop a framework for deriving lower bounds on the problem that applies to a wide family of conceivable algorithms for the task (including our algorithm and Quick Boost), and we demonstrate empirically on a wide variety of data sets that our algorithm is near-optimal within this family of algorithms. We also derive a lower bound applicable to any algorithm solving the task, and we demonstrate that our algorithm empirically achieves performance close to this best-achievable lower bound.