Towards Better Decision Forests: Forest Alternating Optimization

Miguel Á. Carreira-Perpiñán, Magzhan Gabidolla, Arman ZharmagambetovCVPR 2023 · OpenReview

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.

Visualization of the "islands" phenomenon: FAO's error surface compared to Ground Truth and Gradient Boosting.

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 cpuact dataset, 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

Abstract

Decision forests are among the most accurate models in machine learning. This is remarkable given that the way they are trained is highly heuristic: neither the individual trees nor the overall forest optimize any well-defined loss. While diversity mechanisms such as bagging or boosting have been until now critical in the success of forests, we think that a better optimization should lead to better forests—ideally eliminating any need for an ensembling heuristic. However, unlike for most other models, such as neural networks, optimizing forests or trees is not easy, because they define a non-differentiable function. We show, for the first time, that it is possible to learn a forest by optimizing a desirable loss and regularization jointly over all its trees and parameters. Our algorithm, Forest Alternating Optimization, is based on defining a forest as a parametric model with a fixed number of trees and structure (rather than adding trees indefinitely as in bagging or boosting). It then iteratively updates each tree in alternation so that the objective function decreases monotonically. The algorithm is so effective at optimizing that it easily overfits, but this can be corrected by averaging. The result is a forest that consistently exceeds the accuracy of the state-of-the-art while using fewer, smaller trees.
BibTeX
@inproceedings{carreiraperpinan2023towards,
  author = {Miguel Á. Carreira-Perpiñán and Magzhan Gabidolla and Arman Zharmagambetov},
  title = {{Towards Better Decision Forests: Forest Alternating Optimization}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2023},
  url = {https://openreview.net/forum?id=HVGeE6m4tg},
}
Figure