# Feature-Budgeted Random Forest

arXiv: https://arxiv.org/abs/1502.05925 · HTML: https://mlsanity.com/paper/1502.05925/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2015.

## Built on by (most cited first, 6 of 6)

- [A Survey on Active Feature Acquisition Strategies](https://mlsanity.com/paper/2502.11067/) (2025)
- [Stochastic Encodings for Active Feature Acquisition](https://mlsanity.com/paper/2508.01957/) (2025)
- [Spatial State-Action Features for General Games](https://mlsanity.com/paper/2201.06401/) (2022)
- [Fast Classification with Sequential Feature Selection in Test Phase](https://mlsanity.com/paper/2306.14347/) (2023)
- [NOCTA: Non-Greedy Objective Cost-Tradeoff Acquisition for Longitudinal Data](https://mlsanity.com/paper/2507.12412/) (2025)
- [MetaSieve: Faster Relational Deep Learning through SQL-Based Metapath Selection](https://mlsanity.com/paper/2608.25903/) (2026)

## Abstract (arXiv)

We seek decision rules for prediction-time cost reduction, where complete data is available for training, but during prediction-time, each feature can only be acquired for an additional cost. We propose a novel random forest algorithm to minimize prediction error for a user-specified it average feature acquisition budget. While random forests yield strong generalization performance, they do not explicitly account for feature costs and furthermore require low correlation among trees, which amplifies costs. Our random forest grows trees with low acquisition cost and high strength based on greedy minimax cost-weighted-impurity splits. Theoretically, we establish near-optimal acquisition cost guarantees for our algorithm. Empirically, on a number of benchmark datasets we demonstrate superior accuracy-cost curves against state-of-the-art prediction-time algorithms.