Adaptive Forests For Classification

AI summary

Overview

• Research area: Machine learning, specifically tree-based ensemble methods and optimization-based predictive modeling (mixed integer optimization applied to classification).
• Technical level: Advanced. The paper assumes familiarity with CART, Random Forests, gradient boosting, ROC/AUC evaluation, and Mixed Integer Optimization (MIO) formulations, and it presents optimization problems in mathematical notation.
• Scope in one sentence: The paper proposes Adaptive Forests (AF), a classification method that replaces the equal weighting of CART trees used by Random Forests and XGBoost with input-dependent, unequal weights learned through policy trees and refined by mixed integer optimization.

What This Paper Is About

Random Forests builds many independent CART trees on random data and feature subsets and combines their predictions by averaging or majority vote; XGBoost builds trees sequentially. Both aggregate trees with equal weights, and prior "weighted random forest" variants assign each tree a single constant weight that does not change from one input to another. This paper asks whether prediction accuracy can be improved by assigning each tree a different weight depending on the specific input being classified, and it builds a framework that learns those weights with optimization.

Key Contributions

1. The Adaptive Forests model. AF combines (a) m independent CART base learners trained on randomly sampled data instances and feature subsets with (b) an Optimal Policy Tree that routes each input to a leaf carrying a weight vector from a finite candidate set, so the final prediction uses weights tailored to that input.
2. A dynamic weight-refinement mechanism. Beyond the Optimal Predictive-Policy Trees (OP2T) framework of Bertsimas and Peroni (2024), which is limited to a finite set of predefined weights, AF uses Mixed Integer Optimization to iteratively generate and select new weight candidates, adding exploration and exploitation constraints and capping how many new weights enter the candidate set.
3. A configuration framework for OPT training. The paper lays out multiple choices for the reward matrix (hard, soft, threshold-soft, Euclidean distance, KL divergence, negative cross-entropy), for which input features to give OPT (original features, optionally augmented with base-learner predicted probabilities), and for which portion of data_opt to use (all, non-deterministic only, deterministic-and-correct removed, deterministic-and-incorrect removed).
4. An empirical study against strong baselines. AF is compared with Random Forests, XGBoost, and a weighted random forest (wRF) across real-world datasets, with results reported on binary and multi-class classification using CART depths of 10 and 100.

Main Findings

• AF leads on average AUC for binary classification at CART depth 10. Averaged over the 14 binary datasets in Table 2, AF reaches 0.8256, versus 0.7888 for Random Forests, 0.8077 for XGBoost, and 0.7978 for wRF.
• AF leads on average AUC for binary classification at CART depth 100. Averaged over the same 14 datasets in Table 3, AF reaches 0.8179, versus 0.7838 for Random Forests, 0.8087 for XGBoost, and 0.7919 for wRF.
• AF records the most dataset-level wins in both binary tables. At depth 10 the win counts are AF 6, wRF 4, Random Forests 3, XGBoost 2. At depth 100 the win counts are AF 6, XGBoost 4, wRF 3, Random Forests 2.
• AF is described as robustly strong, not uniformly best. The paper reports that AF is one of the two top-performing models in AUC for binary classification in 10 out of 14 instances and in OvR AUC for multi-class classification in 5 out of 7 instances. Individual datasets where AF does not lead include diabetes-bin-500 (AF 0.8299 vs Random Forests 0.8474 and XGBoost 0.8624 at depth 10), haberman-survival (AF 0.6840 vs wRF 0.7188 at depth 10), and indian-liver-patient (AF 0.7585 vs XGBoost 0.7711 and wRF 0.7733 at depth 10).
• AF uses far fewer trees. AF caps the number of underlying CARTs at 50 for binary classification and 100 for multi-class classification, compared with the 1000 trees considered for the competing methods.
• Substituting OCT for CART did not help. The paper states that the same experiments were run with Optimal Classification Trees instead of CART as the base learner, and no significant improvements were observed, so results are reported exclusively with CART.
• The multi-class result tables are referenced but not shown in the available text. The paper refers to Tables 4 and 5 for multi-class computational performance with depths 10 and 100, but the provided content is truncated after Table 3, so the multi-class per-dataset numbers and averages are not available in this excerpt.
• Dataset scale in the binary experiments. The 14 binary datasets in Tables 2 and 3 range from n = 74 (echocardiogram, p = 12) to n = 1000 (statlog-german-credit, p = 25), with feature counts from p = 4 (haberman-survival) to p = 45 (spectf-heart). The abstract states AF was tested on 20+ real-world datasets in total.

Methodology in Plain English

1. Split the data four ways. Twenty percent of the data is held out as data_test and used only for final evaluation. From the remaining 80%, 15% goes to data_val for choosing the best configuration; the rest is split 60:40 into data_single (for training CARTs) and data_opt (for training the policy tree). In fractional terms, data_single is 0.8 × 0.85 × 0.6, data_opt is 0.8 × 0.85 × 0.4, data_val is 0.8 × 0.15, and data_test is 0.2.
2. Train many CARTs. Each base learner is trained on randomly sampled data instances and feature subsets, the same way Random Forests generates its trees. Each tree outputs a probability distribution over the K classes.
3. Initialize a pool of weight candidates. A set W = {w_1, ..., w_T} of valid weight vectors (nonnegative, summing to 1 across the m learners) is initialized using methods described in the paper's Appendix A.
4. Reinterpret weighting as a prescription problem. For every input and every candidate weight vector, compute a reward that measures how well that weight vector would do. The paper offers several reward definitions — hard reward (1 if the weighted vote is correct), soft reward (the weighted probability assigned to the true class), threshold-soft, Euclidean distance to the true one-hot vector, KL divergence, and negative cross-entropy. Rewards are computable directly, so no counterfactual estimation is needed, unlike typical prescriptive-tree settings.
5. Learn a policy tree that assigns weights. Using the Optimal Policy Trees machinery, build a tree that segments the feature space and assigns each leaf a weight vector chosen to maximize total reward, with the tree depth capped, each leaf required to contain at least c_min samples, and a penalty lambda <= 0 controlling the number of splits.
6. Improve the candidate weight pool with optimization. At each iteration, solve a mixed integer program to find a new weight vector that minimizes weighted-classification error on data_opt (binary case) or maximizes the number of correctly classified instances (multi-class case). Additional constraints force the new weight to be at least min_gap away from every existing candidate (exploration) while staying within max_gap of at least one previously selected weight (exploitation, restricted to the historical set hist_W).
7. Keep the pool small. A separate mixed integer program selects at most k of the newly generated candidates, assigning one weight per leaf of the current policy tree, to control overfitting and runtime.
8. Iterate and select. Repeat weight generation and policy-tree training until convergence or a maximum of 10 iterations. In the first iteration, data_val is used to pick the best configuration for OPT training.
9. Evaluate once on the held-out set. Final performance is reported on data_test using AUC for binary classification and One-vs-Rest AUC for multi-class, where OvR AUC is defined as (1/K) times the sum over classes of AUC(class k versus not class k).

Why This Matters

• It challenges a default assumption in ensemble learning. Almost all prior weighted-forest work uses constant tree weights; AF demonstrates that letting weights vary with the input is empirically worthwhile, which reframes ensembling as a policy-learning problem rather than a fixed aggregation rule.
• It joins two previously separate optimization toolkits. The work demonstrates that prescriptive policy trees (OP2T/OPT) and mixed integer optimization for weight generation can be combined into a single pipeline, and it reports that the MIO refinement step extends performance beyond what the finite OP2T weight set alone achieves.
• It targets efficiency as well as accuracy. Getting better average AUC while using at most 50 CARTs (binary) or 100 CARTs (multi-class) instead of up to 1000 trees is directly relevant to deployment where training or inference cost matters.

Real-world applications implied by the datasets and framing in the paper:

• Clinical decision support. The motivating example is a panel of specialists whose opinions should be weighted differently per patient; the experiments include breast-cancer, breast-cancer-prognostic, echocardiogram, spect-heart, spectf-heart, haberman-survival, and the Boston Medical Center (BMC) Diabetes Dataset.
• Risk scoring and credit decisions. The statlog-german-credit dataset (n = 1000, p = 25) is a credit-approval benchmark where instance-specific weighting could matter.
• Medical screening and diagnostics. blood-transfusion (n = 748), indian-liver-patient (n = 583), and wdbc (n = 569) are all screening-style tasks.
• Interpretable model selection in regulated settings. Because the weighting rule is a tree, users can inspect how and when particular base learners are favored, which the paper stresses as an advantage over opaque aggregation.

Industry relevance: teams already running Random Forests or XGBoost in production could adopt AF as a drop-in ensemble layer on top of their existing CART base learners, gaining accuracy with fewer trees, while retaining a readable structure describing which models are trusted for which kinds of inputs.

Future Directions

1. Extending AF to regression. The paper is framed around binary and multi-class classification, and the reward definitions and MIO formulations given are classification-specific; OWRF (Chen et al. 2024) is described as primarily a regression method, suggesting regression is an open extension.
2. Reducing the cost of the iterative MIO loop. New weight candidates are generated by solving mixed integer programs with nonconvex quadratic exploration constraints and a candidate-selection program; the paper caps iterations at 10 and caps how many new weights enter the pool, leaving room for faster or more scalable solvers.
3. Automating configuration selection. The paper reports that no single configuration (reward type, feature set, subset of data_opt) consistently wins across datasets, and that validation-based selection is the most effective available strategy. A principled or learned way to pick configurations would remove a manual search step.
4. Base-learner and weight-set alternatives. Substituting Optimal Classification Trees for CART produced no significant improvement, and the weight candidates currently live on the probability simplex. The paper leaves open whether other base learners, other weight parameterizations, or different exploration/exploitation constraints (min_gap, max_gap) yield further gains.

Target Audience

This paper is most useful to machine learning researchers and practitioners working on ensembles, interpretable tree models, or optimization-based learning who are comfortable reading mixed integer optimization formulations. It will also benefit applied statisticians and data scientists in domains such as healthcare analytics and credit risk who need strong tabular classification performance and want to see how a weighting policy can be inspected. Readers looking for an introductory treatment of decision trees or boosting will find it too advanced without background in CART and MIO.

Authors’ abstract

Random Forests (RF) and Extreme Gradient Boosting (XGBoost) are two of the most widely used and highly performing classification and regression models. They aggregate equally weighted CART trees, generated randomly in RF or sequentially in XGBoost. In this paper, we propose Adaptive Forests (AF), a novel approach that adaptively selects the weights of the underlying CART models. AF combines (a) the Optimal Predictive-Policy Trees (OP2T) framework to prescribe tailored, input-dependent unequal weights to trees and (b) Mixed Integer Optimization (MIO) to refine weight candidates dynamically, enhancing overall performance. We demonstrate that AF consistently outperforms RF, XGBoost, and other weighted RF in binary and multi-class classification problems over 20+ real-world datasets.