Introduction
Decision forests, such as Random Forests and Gradient Boosting, are staples of modern machine learning. However, their training remains largely heuristic. Unlike neural networks, which optimize a global loss function via backpropagation, forests are typically built using greedy recursive partitioning (e.g., CART) and ensembling techniques like bagging or boosting. This paper introduces Forest Alternating Optimization (FAO), a novel framework that treats a forest as a single parametric model and jointly optimizes all its trees and parameters to minimize a global loss function.
The Problem with Heuristic Forests
Traditional training methods suffer from two main drawbacks. First, they lack global optimization; individual trees and the forest as a whole do not optimize a well-defined global loss, relying instead on local proxies like node purity. Second, this leads to parameter inefficiency. To improve accuracy, practitioners often add more nodes or trees, resulting in bloated models. Because forests are non-differentiable, standard gradient-based optimization cannot be applied directly.
Forest Alternating Optimization (FAO)
FAO addresses these issues by starting with a fixed forest structure and iteratively updating it. The algorithm alternates between two main steps:
- Alternating over Trees: One tree is updated at a time while others are fixed. The target tree is optimized to fit the residuals using Tree Alternating Optimization (TAO), which ensures a monotonic decrease in loss.
- Alternating over All Leaves: With decision nodes fixed, leaf labels across all trees are treated as coefficients in a regularized linear regression problem, allowing for a simultaneous global update of all predictions.
The "Islands" Phenomenon and Overfitting
FAO is remarkably effective at minimizing training error, but this power comes with a risk of overfitting. The authors identify the "islands" phenomenon: because forests are piecewise constant, an aggressive optimizer can create small regions of high error ("islands") far from the training data. This nonsmoothness is the price of high flexibility and locality.
To mitigate this, the authors propose Averaged FAO (FAO-avg), which averages predictions from multiple FAO forests trained with different initializations. This step restores the generalization performance lost to the optimizer's aggressiveness.
Key Results
Evaluation on benchmarks like MNIST, CIFAR-100, and various regression tasks shows that FAO-avg consistently outperforms state-of-the-art libraries like XGBoost and LightGBM.
- Superior Accuracy: On MNIST, FAO reached ~1.3% error using raw pixels, rivaling multi-layer perceptrons and significantly exceeding traditional forest methods.
- Compactness: FAO achieves superior accuracy with significantly smaller models. For instance, on the
cpuactdataset, an FAO model with 30 trees outperformed a 60-tree Gradient Boosting model. - Efficiency: Despite the complex optimization, the process is highly parallelizable and can train a high-performing MNIST forest in minutes on a standard processor.
Conclusion
FAO represents a shift in decision forest training from heuristic induction to global optimization. By viewing forests as parametric models, FAO produces more compact and accurate predictors. Future work will focus on direct regularization techniques to prevent the "islands" phenomenon without requiring an averaging step, potentially leading to even more efficient and robust models.
Summary updated