Pruning Random Forests for Prediction on a Budget
This addresses the need for efficient prediction in resource-limited settings, offering a practical solution for domains like mobile or embedded systems.
The paper tackles the problem of resource-constrained prediction by pruning random forests to optimize feature cost and accuracy, proposing a novel 0-1 integer programming approach with a scalable primal-dual algorithm that outperforms existing state-of-the-art methods.
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.