Teaching Linear-Leaf Trees the Teacher's Slopes

A piecewise linear regression tree splits the input space into boxes, as an ordinary decision tree does, and then fits a small linear equation inside each box instead of a single constant. When such a tree is distilled from a neural network (trained to imitate the network's outputs), every existing method gives the student only the teacher's predicted values. But a linear leaf $y = w^\top x + b$ has a slope, $w$, and the teacher has a slope too: its input gradient, available from one backward pass. This proposal distills the gradient as well as the value. Each leaf's weight vector is pulled toward the teacher's local gradient. The tree also splits wherever the teacher's gradients disagree within a box, because that disagreement is exactly what a single linear leaf cannot represent.

This matters because interpretable tabular models are now routinely extracted from neural or ensemble teachers, and point-wise imitation leaves the student unconstrained between training points. Adding gradients costs almost nothing here. The gradient term changes only a handful of additive running sums that fast linear-tree learners already maintain. It gives the leaves a regularizer centred on the teacher's local slope, replacing the usual pull toward zero. It also gives the splitter a cheap signal for where to cut. The central claim is that at a fixed budget of teacher queries and a fixed leaf count, gradient-augmented distillation yields linear-leaf trees that match the teacher more closely off the training points, and need fewer leaves to do so, than value-only distillation.

What already exists and what is missing

Two lines of work already distill into linear-leaf trees, and both match values only. Toward Interpretable Deep Reinforcement Learning with Linear Model U-Trees grows a linear-leaf tree online by imitating a deep Q-network's action values, using greedy variance-based splits. Cracking the Black Box: Distilling Deep Sports Analytics fits linear model trees to a deep network's smooth value predictions on millions of sports events and reports correlation above 0.99 with the teacher. These papers motivate the proposal: teacher outputs are good targets for linear leaves. They also leave its central lever unused, because neither uses the teacher's derivatives.

Two further papers supply the method but only for neural students. Sobolev Training for Neural Networks trains networks to match teacher input gradients as well as outputs. On Styblinski-Tang, a model trained this way on 20 points beat a standard model trained on 100 points. Locally Linear Region Knowledge Distillation shows that point-wise distillation lets students drift between training points, and repairs this by querying the teacher along interpolations between points. We reuse its interpolation idea as a baseline and its shape-discrepancy idea as a metric.

The tree-induction papers supply the machinery we modify, all trained on raw labels. CLARITree uses lookahead split search with rank-one Cholesky updates of the leaf Gram matrix, the matrix of feature cross-products $\sum_i x_i x_i^\top$. Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach evaluates splits from precomputed additive statistics and uses Elastic Net leaves.

The dynamic-programming paper also constrains the design. It found that single-variable leaves often generalize better than full multiple-regression leaves, because full leaves overfit noise. Our gradient term is aimed at this failure: it regularizes toward something informative rather than toward zero.

Distilling a Neural Network Into a Soft Decision Tree and Born-Again Tree Ensembles distill into trees whose leaves are constant, so they have no slope to supervise.

Core Claim

Consider a leaf holding points $x_i$, $i = 1, \dots, n$. Let $t_i$ be the teacher's prediction at $x_i$, let $g_i = \nabla_x f_{\text{teacher}}(x_i)$ be its gradient there, and let $\mu \ge 0$ weight the gradient term. The leaf objective is

$$ L(w,b) = \sum_{i=1}^n (t_i - w^\top x_i - b)^2 + \mu \sum_{i=1}^n \lVert w - g_i \rVert^2 = \sum_i (t_i - w^\top x_i - b)^2 + \mu n \lVert w - \bar g \rVert^2 + \mu \sum_i \lVert g_i - \bar g \rVert^2 , $$

where $\bar g$ is the mean teacher gradient in the leaf.

The second form makes two things visible. First, the optimal $w$ solves a ridge regression centred at $\bar g$ instead of at zero, so the teacher's slope acts as a local prior. Second, the last term does not depend on $w$ at all. It measures only how much the teacher's slope varies inside the box, and no leaf fit can reduce it; only a split can. Summed over the children of a candidate split, it is a split criterion computable in $O(k)$ per candidate from the running sums $\sum g_i$ and $\sum \lVert g_i \rVert^2$, where $k$ is the number of features. By comparison, CLARITree's lookahead costs $O(k^4)$.

The claim has three parts, each testable:

  • gradient-centred leaves reduce off-sample fidelity error at equal leaf count;
  • gradient-heterogeneity splits recover most of the benefit of full lookahead at a fraction of the cost;
  • the benefit is largest in the low-data regime, in line with the Sobolev result.

Research Program

We will build the objective into two learners.

The first is a greedy linear-tree learner in the style of CLARITree, operating on continuous features. The engineering wrinkle is that the shift $\mu n I$ grows as points move between siblings. That breaks the pure rank-one Cholesky update. We handle it by maintaining an eigendecomposition of the centred Gram matrix under rank-one updates, which permits solves at any shift in $O(k^2)$. As a fallback, we use a two-stage search: first screen split candidates by the heterogeneity term, then solve exactly only for the top candidates. Whether this preserves CLARITree's speed is itself a result we will report.

The second is the dynamic-programming learner. Its precomputed-statistics design absorbs the new sums directly.

We will then study three things.

  • Tuning $\mu$. We will examine whether $\mu$ can be set once, as a ratio against the target scale, rather than tuned per dataset. This bears on the hyperparameter sensitivity that Gradient Boosting with Piece-Wise Linear Regression Trees flags for linear leaves.
  • Where the teacher is queried. Options are training points, interpolations between training points, or both.
  • Which teachers qualify. Teachers must be differentiable, such as multilayer perceptrons or GBDT-PL (gradient boosting with linear-leaf trees). Ordinary constant-leaf boosted ensembles have zero gradient almost everywhere. For them we test smoothed finite differences, and we treat failure there as an honest scope limit.

Baselines

The naive reference point is a linear-leaf tree trained directly on ground-truth labels with no teacher at all, using CLARITree and SRT-L with their own Elastic Net tuning. This tells us whether distillation helps at all. The research file indicates that it did in the sports setting of Cracking the Black Box.

The strongest existing competitor is value-only distillation into the same learner. This is CLARITree fitted to teacher predictions, the natural modern version of the value-imitation recipe in Linear Model U-Trees. It is the strongest because it shares everything with our method except the gradient term. The research file reports no fidelity or accuracy number for CLARITree on California Housing, only speed: over 100x faster than optimal solvers, finishing in seconds where they failed after 64 hours. We will therefore produce this baseline ourselves.

For the reinforcement-learning setting, the published reference is Linear Model U-Trees scoring 103.32 in Flappy Bird against the teacher DQN's 123.42 Linear Model U-Trees. Our control experiments use the lower-dimensional Cart Pole and Mountain Car environments from that paper. The file gives no score numbers for those, so there we compare against our own rerun of value-only distillation.

A second strong competitor is value-only distillation on a set augmented with teacher queries along interpolations between training points, following Locally Linear Region Knowledge Distillation.

Two ablations isolate the key ingredient. The first uses ridge leaves centred at zero, with the same tuned strength, so it has the same regularization form but no teacher slope. The second uses gradient-centred leaves but ordinary variance splits, which separates the leaf effect from the split effect.

All methods get the same data splits, the same teacher, and the same maximum leaf count. Each gets an equal hyperparameter search budget of 30 configurations with 5-fold validation. They also get an equal teacher-evaluation budget: one gradient counts as one backward pass for neural teachers, and as $k$ extra queries under finite differences.

Beating the value-only baseline means lower held-out fidelity error at every leaf count on the accuracy-versus-leaves curve, with non-overlapping intervals across 10 seeds, on a majority of datasets.

Why not just…?

Why not just query the teacher at many more points and distill values only? This is the real threat. With a cheap tabular teacher, dense value queries might approximate the same information as gradients. The matched-query-budget comparison against interpolation-augmented distillation settles it. If dense values match gradients at equal cost, we will report that gradients offer convenience and nothing more.

Our reason to expect a gap is twofold. Sampling far from the data manifold probes regions where the teacher is unreliable, while gradients are measured only at real points. And the Sobolev results show derivatives acting as extra data at small sample sizes.

Why not just tune the Elastic Net penalty harder? The zero-centred ridge ablation addresses this directly. If a well-tuned pull toward zero matches a pull toward $\bar g$, the teacher's slope carries no information beyond shrinkage. The dynamic-programming paper's finding that full linear leaves overfit suggests zero-centred shrinkage throws away real slope; the ablation tests that.

Why not just use CLARITree's lookahead for better splits? Lookahead costs $O(k^4)$ in the number of features. We compare lookahead splits, gradient-heterogeneity splits, and both together on fidelity and wall-clock time. The heterogeneity split succeeds if it gets most of the lookahead gain at greedy cost, especially on the wider datasets.

Proposed Experiments

We use three groups of benchmarks.

  • Synthetic surfaces. Ackley, Rosenbrock and Styblinski-Tang, from the Sobolev paper, where the true gradients are known.
  • Tabular regression. California Housing, Seoul Bike and Individual Household Electric Power, the last subsampled for tractability. Teachers are MLPs and GBDT-PL.
  • Control. Cart Pole and Mountain Car Q-function distillation, as in Linear Model U-Trees.

Metrics are:

  • fidelity RMSE to the teacher at held-out points and at interpolated points, the latter as an analogue of the shape-discrepancy metric in Locally Linear Region Knowledge Distillation;
  • cosine agreement between leaf weights and teacher gradients;
  • task RMSE against ground truth;
  • extrapolation error on target ranges held out beyond the training range;
  • episode return for the control tasks, where the Linear Model U-Trees paper warns that fidelity and task success can diverge.

The decisive checks are four.

  • Low-data regime. Training-set size is swept from 1% to 100%. If the gradient advantage does not grow as data shrinks, the Sobolev mechanism is not what is operating.
  • Synthetic surfaces. Using the true gradient in place of the teacher's separates teacher error from method error.
  • Matched-budget dense sampling. As described under Why not just…?, this is the comparison that could falsify the practical value of the whole idea.
  • Leaf count. We compare the leaf count needed to reach the teacher's fidelity at 0.99 correlation, the level the sports paper reports for value-only trees, against the leaf count value-only CLARITree needs.