Timezone: »

 
Poster
Pruning Random Forests for Prediction on a Budget
Feng Nan · Joseph Wang · Venkatesh Saligrama

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #150
in Wednesday Posters »

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.

Keywords: Combinatorial Optimization · (Other) Classification · (Other) Machine Learning Topics

Author Information

Feng Nan (Boston University)
Joseph Wang (Boston University)
Venkatesh Saligrama (Boston University)

More from the Same Authors