Pruning Random Forests for Prediction on a Budget

2016/06/16 by Joseph Wang, Nan, Feng, Venkatesh Saligrama +2 · 2 citations
Computer Science · #Advanced Image and Video Retrieval Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #Multimodal Machine Learning Applications

paper · pdf · doi:10.48550/arxiv.1606.05060

openalex publication_date 2016/06/16 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We propose to prune a random forest (RF) for resource-constrained prediction. We first construct a RF and then prune it to optimize expected feature cost & accuracy. We pose pruning RFs as a novel 0-1 integer program with linear constraints that encourages feature re-use. We establish total unimodularity of the constraint set to prove that the corresponding LP relaxation solves the original integer program. We then exploit connections to combinatorial optimization and develop an efficient primal-dual algorithm, scalable to large datasets. In contrast to our bottom-up approach, which benefits from good RF initialization, conventional methods are top-down acquiring features based on their utility value and is generally intractable, requiring heuristics. Empirically, our pruning algorithm outperforms existing state-of-the-art resource-constrained algorithms.

Citations

• An analysis of approximations for maximizing submodular set functions—I

Cited by

• Boosted Trees on a Diet: Compact Models for Resource-Constrained Devices
• Stochastic Encodings for Active Feature Acquisition

Related

• Feature-Budgeted Random Forest
• Improving the Accuracy-Memory Trade-Off of Random Forests Via Leaf-Refinement
• Optimally Pruning Decision Tree Ensembles With Feature Cost
• On Extreme Pruning of Random Forest Ensembles for Real-time Predictive Applications
• Exploiting random projections and sparsity with random forests and gradient boosting methods -- Application to multi-label and multi-output learning, random forest model compression and leveraging input sparsity