  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.
