Regression Trees Know Calculus

Nathan Wycoff

Introduction

While regression trees are traditionally viewed as "chunky," piecewise-constant models with zero gradients almost everywhere, recent research demonstrates that their internal structure actually encodes rich derivative information. By extracting these "hidden" gradients, researchers can enable tree-based models to utilize sophisticated calculus-based tools—such as Integrated Gradients for interpretability and Active Subspaces for dimension reduction. Surprisingly, these tree-based gradient methods often outperform neural networks and Gaussian processes in both speed and scalability.

The Problem: The Differentiability Gap

Regression trees, along with ensemble methods like Random Forests and XGBoost, are the workhorses of modern data science. They are highly favored for their ability to handle non-linearities, interaction effects, and sharp discontinuities with ease. However, because standard versions use constant values in their leaves, they are technically non-differentiable.

This creates a significant gap in the machine learning toolkit. Many powerful techniques in machine learning and uncertainty quantification (UQ) rely on gradients (slopes) to explain model behavior or reduce dimensionality. Until now, utilizing these "calculus-based" tools usually required switching to more complex, inherently differentiable models like neural networks. This paper tackles a fundamental question: Can we extract meaningful gradients directly from a standard, constant-leaf regression tree?

Methods: The Tree-Based Gradient Estimator (TBGE)

To bridge this gap, the authors introduce the Tree-Based Gradient Estimator (TBGE). The core logic is elegantly simple and relies on the inherent structure of the tree:

  1. Local Finite Differences: At any given split in a tree, the model compares a "left" mean and a "right" mean. The difference between these means, divided by the width of the node, serves as a proxy for a partial derivative along that specific feature axis.
  2. Path Aggregation: As an observation traverses from the root of the tree to a specific leaf, it encounters splits on different variables. By aggregating these local estimates, the model builds a full gradient vector for any point in the feature space.
Evolution of gradient estimates at varying tree depths compared to the true vector field.

Once gradients are available, they can be applied to major integro-differential frameworks:

  • Tree-Based Integrated Gradients (TBIG): A local interpretability method that explains a prediction by integrating the gradient along a path from a reference point.
  • Tree-Based Active Subspaces (TBAS): A global sensitivity analysis tool that uses the covariance of gradients to find the most important "directions" (linear combinations of features) in the data.

Key Insights and Experimental Results

The authors validated these methods across diverse benchmarks, including UCI Regression datasets, MNIST, a large-scale medical dataset (NHEFS), and synthetic algebraic functions.

  • Trees "Know" More Than They Show: Even though a tree's output is flat within a leaf, the decision to split and the difference in child means contain an implicit, highly accurate estimate of the underlying function's slope.
  • Efficiency over Complexity: Unlike neural networks that require backpropagation, or Gaussian Processes (GPs) that scale poorly with large datasets, TBGE can be computed in a single pass through the tree. In experiments, the tree-based method was orders of magnitude faster than GPs for large samples, occupying the "Pareto front" of accuracy versus execution time.
  • Active-Subspace Rotation: Using the estimated Active Subspace to "rotate" the input data before fitting a downstream tree significantly improves predictive accuracy. "Active-subspace Rotated Trees" (TBAS) consistently matched or beat standard trees and PCA-rotated trees, showing statistically significant improvements on datasets like kin40k.
  • Interpretability: When applied to MNIST, Integrated Gradient visualizations successfully highlighted specific pixel intersections (e.g., the crossing of an "8") as the key features distinguishing digits, providing a more intuitive explanation than standard feature importance metrics.

Limitations and Future Work

While promising, the approach has theoretical and practical boundaries:

  • Slow Convergence: Theoretically, the gradient estimates converge at a rate of $O_P(1/\log N)$. This relatively slow rate means highly precise gradients require very large datasets and deep trees.
  • Greedy Splitting: Current theoretical proofs assume splits are made somewhat independently of the response variable. Proving convergence for real-world, greedy trees (like CART) remains a challenging area for future research.
  • Classification Challenges: While highly effective for regression, preliminary results on classification tasks were less promising, suggesting that translating probabilities to gradients in trees requires specialized handling.

Ultimately, this research proves that we do not have to abandon the robustness of tree-based models to enjoy the benefits of calculus-based machine learning tools. By simply looking at the splits, regression trees can reveal the hidden slopes of the data they model.

Summary updated

Abstract

Regression trees have emerged as a preeminent tool for solving real-world regression problems due to their ability to deal with nonlinearities, interaction effects and sharp discontinuities. In this article, we rather study regression trees applied to well-behaved, differentiable functions, and determine the relationship between node parameters and the local gradient of the function being approximated. We find a simple estimate of the gradient which can be efficiently computed using quantities exposed by popular tree learning libraries. This allows tools developed in the context of differentiable algorithms, like neural nets and Gaussian processes, to be deployed to tree-based models. To demonstrate this, we study measures of model sensitivity defined in terms of integro-differential quantities and demonstrate how to compute them for regression trees using the proposed gradient estimates. Quantitative and qualitative numerical experiments reveal the capability of gradients estimated by regression trees to improve predictive analysis, solve tasks in uncertainty quantification, and provide interpretation of model behavior.
BibTeX
@inproceedings{wycoff2025regression,
  author = {Nathan Wycoff},
  title = {{Regression Trees Know Calculus}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=wFXvD83mhb},
}
Figure