Skip to yearly menu bar Skip to main content


Pruning Random Forests for Prediction on a Budget

Feng Nan · Joseph Wang · Venkatesh Saligrama

Area 5+6+7+8 #150

Keywords: [ (Other) Machine Learning Topics ] [ (Other) Classification ] [ Combinatorial Optimization ]


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.

Live content is unavailable. Log in and register to view live content