We consider the problem of learning decision rules for prediction with feature budget constraint. In particular, we are interested in pruning an ensemble of decision trees to reduce expected feature cost while maintaining high prediction accuracy for any test example. We propose a novel 0-1 integer program formulation for ensemble pruning. Our pruning formulation is general - it takes any ensemble of decision trees as input. By explicitly accounting for feature-sharing across trees together with accuracy cost trade-off, our method is able to significantly reduce feature cost by pruning subtrees that introduce more loss in terms of feature cost than benefit in terms of prediction accuracy gain. Theoretically, we prove that a linear programming relaxation produces the exact solution of the original integer program. This allows us to use efficient convex optimization tools to obtain an optimally pruned ensemble for any given budget. Empirically, we see that our pruning algorithm significantly improves the performance of the state of the art ensemble method BudgetRF.
Generally, pruning is not considered when constructing random forests as overfitting is avoided by constructing an ensemble of trees. The ensemble approach is a strong approach to avoiding overfitting, however test-time budget constraint problems require consideration of both cost and accuracy. Kulkarni and Sinha @cite_14 provide a survey of methods to prune random forests in order to reduce ensemble size. However, these methods do not explicitly account for feature costs.
@cite_14
2112716550
Random Forest is an ensemble supervised machine learning technique. Based on bagging and random feature selection, number of decision trees (base classifiers) is generated and majority voting is taken for classification. For effective learning and classification of Random Forest, there is need for reducing number of trees (Pruning) in Random Forest. We have presented here systematic survey of pruning efforts of Random Forest classifier along with the required theoretical background. Most of the work for pruning takes static approach while recently dynamic pruning is being targeted. We have also generated a Comparison Chart by taking relevant parameters. There is research scope for analyzing behavior of Random forest, generating accurate and diverse base decision trees, truly dynamic pruning algorithm for Random Forest classifier, and generating optimal subset of Random forest.