Smaller, more accurate regression forests using tree alternating optimization

Arman Zharmagambetov, Miguel Á. Carreira-PerpiñánICML 2020 · OpenReview

Introduction

Regression forests, built on ensemble approaches like bagging or boosting, have long been recognized as a leading off-the-shelf method for regression tasks. However, most popular models—such as Random Forests and Gradient Boosting—rely on the traditional CART algorithm to build their individual trees.

CART is a "greedy" algorithm: it makes the best possible split at the current node and never looks back. While fast, this approach is mathematically suboptimal. It often leads to massive forests with thousands of deep, complex trees to compensate for the poor quality of individual learners. Optimizing a tree structure globally is notoriously difficult, as it is an NP-hard problem that does not work well with standard gradient descent due to discrete tree splits.

This paper introduces a method to build regression forests that are both more accurate and significantly smaller than industry standards. By replacing the traditional greedy tree-growing approach with a global optimization strategy called Tree Alternating Optimization (TAO), the authors produce forests of "oblique" trees that achieve state-of-the-art results with a fraction of the parameters.

The Tree Alternating Optimization (TAO) Framework

The core contribution of this research is the adaptation of TAO for regression. Unlike CART, which grows a tree from the top down, TAO starts with a fixed tree structure and optimizes its parameters iteratively.

Key technical components include:

  • The Alternating Strategy: TAO updates nodes in a way that allows for parallelization. It identifies sets of "non-descendant" nodes (nodes that aren't on the same path) and updates them simultaneously.
  • Node-wise Optimization:
    • Decision Nodes: These are transformed into a weighted 0/1 loss binary classification problem. The algorithm finds the best hyperplane split (an "oblique" split) to send data points to the child node that minimizes downstream error.
  • Leaf Nodes: These are treated as local regression problems. The authors tested both constant leaves (predicting a single value) and linear leaves (fitting a linear model to the data reaching that leaf).
  • Sparsity and Pruning: By applying $L_1$ regularization during optimization, the algorithm naturally "prunes" the tree. If a node or a feature doesn't contribute significantly to reducing the error, its weights are driven to zero, effectively removing it.
  • Ensembling: These optimized trees are then combined using bagging (training multiple trees on random subsets of data) to create the final forest.

Key Insights and Experimental Results

The authors evaluated their approach on a diverse set of benchmarks, ranging from standard machine learning datasets (Abalone, Ailerons) to large-scale tasks (YearPredictionMSD, SARCOS) and high-dimensional image transformations.

Optimization Over Greed

The most significant takeaway is that even a single tree optimized with TAO can often outperform an entire forest of 100+ CART-based trees. This demonstrates that the bottleneck in current forest models isn't the ensemble method itself, but the weakness of the underlying greedy trees. Furthermore, traditional trees use "axis-aligned" splits, whereas TAO uses oblique splits (hyperplanes) that can evaluate combinations of features. This allows the tree to capture correlations that axis-aligned trees can only approximate with many more nodes.

Superior Accuracy and Model Compression

TAO forests consistently achieved the lowest test error across all datasets. In some cases, like the SARCOS and CT slice datasets, the error was nearly half that of the next best competitor (XGBoost or Random Forest).

Performance comparison on standard regression benchmarks

Because TAO trees are shallower and the forests require fewer of them, the resulting models have orders of magnitude fewer parameters and lower inference latency. For example, on the Abalone dataset, a 100-tree Random Forest requires roughly 230k parameters. A TAO-l (linear leaf) forest with just 30 trees achieved better accuracy with only 8k parameters. This massive reduction in FLOPs makes TAO models highly ideal for deployment on edge devices.

High-Dimensional Success

For complex regression tasks, using linear models in the leaves (TAO-l) proved to be a game-changer. It allows the forest to represent a piecewise linear function, which is far more efficient for modeling continuous physical processes than the "staircase" function produced by constant leaves.

Visual comparison of predictions on the MNIST rotation task

This was particularly evident in custom MNIST-based regression tasks, where the model had to predict an entire transformed image (up to 784 output dimensions). TAO-l forests were the only models able to produce clear, recognizable rotated digits, while other methods produced blurry or distorted outputs.

Limitations and Future Work

While inference is exceptionally fast, training a TAO forest is more computationally expensive than training a standard Random Forest. Its training time is comparable to Gradient Boosting but slower than the "fire and forget" speed of CART. The authors note that their Python implementation is not yet fully optimized, and a more efficient C++ implementation would likely narrow this training time gap.

Additionally, while depth and the number of trees are the primary hyperparameters, the $L_1$ penalty and the number of optimization iterations also play roles in the final model's performance, requiring careful tuning. Future directions include exploring TAO with boosting (sequential training) rather than just bagging, which could push predictive accuracy even further.

Summary updated

Abstract

Regression forests, based on ensemble approaches such as bagging or boosting, have long been recognized as the leading off-the-shelf method for regression. However, forests rely on a greedy top-dow...
BibTeX
@inproceedings{zharmagambetov2020smaller,
  author = {Arman Zharmagambetov and Miguel Á. Carreira-Perpiñán},
  title = {{Smaller, more accurate regression forests using tree alternating optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=WKKxxgv46Vj},
}
Figure