Four Ways to Grow a Classifier and Why One of Them Cannot Learn

Cagri Temel

cs.LGSep 16, 2026

Four Ways to Grow a Classifier and Why One of Them Cannot Learn

Authors: Cagri Temel

Organizations: Hezarfen LLC Seattle, WA, USA

Abstract

Constructive classifiers add structure while they train: a level to a tree, a unit to a hidden layer, a split at a leaf. This paper asks what each of four such growth decisions buys, measured under one protocol on 24 datasets, and gives an exact diagnosis and fix for the one that buys nothing. The diagnosis concerns the natural way to deepen a soft decision tree: turn every leaf into a gate whose two children inherit the parent's class distribution, so the function is unchanged. I prove that this leaves the gradient of every new gate identically zero and with the gate at 1/2, gives the two children identical gradients, so under this construction the added level can never learn. That predicts where it costs: nothing on two-class problems, where two leaves already suffice and a great deal where more classes need more leaves. Measured, the cost is -0.2 points over 13 binary datasets and 40.2 points over 7 multi-class ones, and it tracks the number of classes (Spearman 0.64), not the number of features (0.03). The fix is any perturbation of the children. Neither its size nor its direction matters: a residual-directed initialisation changes accuracy by +0.20 points against noise. The other three decisions each buy one thing. Fitting a new hidden unit to the residual before installing it buys a smaller network but not a more accurate one. Splitting one leaf at a time buys sparsity; it lost accuracy until I found that the split started its two children identical and untrained, the same defect in another place; with the children inheriting the parent and the symmetry broken, per-leaf growth comes within 2.3 points of a complete tree using 23% of its splits. Requiring statistical significance before a node gets a more expressive split buys nothing. Every number comes from the measurement scripts.

Figures & tables

Growth	Iris	Wine	Digits
Exactly function-preserving ( $\varepsilon=0$ )	0.762 $\pm$ 0.103	0.786 $\pm$ 0.145	0.369 $\pm$ 0.035
Perturbed, $\varepsilon=0.05$	0.942 $\pm$ 0.041	0.979 $\pm$ 0.020	0.917 $\pm$ 0.034
Perturbed, $\varepsilon=0.2$ (the default)	0.942 $\pm$ 0.044	0.979 $\pm$ 0.020	0.921 $\pm$ 0.027
Perturbed, $\varepsilon=0.5$	0.938 $\pm$ 0.050	0.983 $\pm$ 0.018	0.916 $\pm$ 0.026
Same depth, trained from scratch	0.958 $\pm$ 0.032	0.978 $\pm$ 0.016	0.925 $\pm$ 0.029

Table 1: Depth-four soft decision tree grown one level at a time, as a function of the perturbation applied to new child distributions. The tree trained from scratch has the same depth, epoch budget and settings; only the growth operation differs. Mean and standard deviation over three seeds of stratified five-fold cross-validation.

Dataset	$n$	$p$	$K$	$\varepsilon=0$	$\varepsilon=0.2$	from scratch	cost	$p$
banknote	1372	4	2	0.985 $\pm$ 0.007	0.985 $\pm$ 0.007	1.000 $\pm$ 0.000	+1.5	1.000
blood - transfusion	748	4	2	0.785 $\pm$ 0.019	0.788 $\pm$ 0.025	0.799 $\pm$ 0.025	+1.4	0.506
climate - crashes	540	18	2	0.955 $\pm$ 0.014	0.952 $\pm$ 0.018	0.932 $\pm$ 0.018	-2.3	0.324
diabetes	768	8	2	0.769 $\pm$ 0.028	0.770 $\pm$ 0.029	0.731 $\pm$ 0.033	-3.8	0.535
ilpd	583	10	2	0.711 $\pm$ 0.019	0.704 $\pm$ 0.030	0.699 $\pm$ 0.042	-1.2	0.588
kc1	2109	21	2	0.855 $\pm$ 0.007	0.857 $\pm$ 0.011	0.854 $\pm$ 0.012	-0.1	0.214

Table 2: The same comparison on twenty OpenML CC-18 datasets, sorted by number of classes. cost is the accuracy of the tree trained from scratch minus the exactly function-preserving one, in points;

p

is the combined

5\times 2

F

test of

\varepsilon=0

against

\varepsilon=0.2

Dataset	$K$	random	residual	residual $+$ gate	from scratch	$p$
Iris	3	0.942 $\pm$ 0.044	0.927 $\pm$ 0.048	0.940 $\pm$ 0.044	0.958 $\pm$ 0.032	0.118
Wine	3	0.979 $\pm$ 0.020	0.981 $\pm$ 0.018	0.981 $\pm$ 0.018	0.978 $\pm$ 0.016	0.395
Cancer	2	0.971 $\pm$ 0.013	0.971 $\pm$ 0.013	0.971 $\pm$ 0.013	0.970 $\pm$ 0.012	0.045
Digits	10	0.921 $\pm$ 0.027	0.929 $\pm$ 0.014	0.930 $\pm$ 0.015	0.925 $\pm$ 0.029	0.702
banknote	2	0.985 $\pm$ 0.007	0.985 $\pm$ 0.007	0.985 $\pm$ 0.007	1.000 $\pm$ 0.000	1.000
blood - transfusion	2	0.788 $\pm$ 0.025	0.786 $\pm$ 0.025	0.790 $\pm$ 0.023	0.799 $\pm$ 0.025	0.595

Table 3: Symmetry broken by random noise, along the residual direction, and along the residual with the gate pointed at the samples pulling right. Depth four, 150 epochs, three seeds of five-fold cross-validation;

p

is the

5\times 2

F

test of the last of these against random noise.

Dataset	New unit	Accuracy	Hidden units	$5\times 2$ cv $F$
Iris	random	0.936 $\pm$ 0.046	17.2 $\pm$ 2.4
	residual	0.956 $\pm$ 0.037	6.9 $\pm$ 1.5	$F=3.00$ , $p=0.1185$
Wine	random	0.985 $\pm$ 0.015	6.3 $\pm$ 2.2
	residual	0.985 $\pm$ 0.015	4.3 $\pm$ 0.5	$F=0.81$ , $p=0.6383$
Digits	random	0.949 $\pm$ 0.013	7.5 $\pm$ 0.6
	residual	0.928 $\pm$ 0.015	5.7 $\pm$ 0.5	$F=8.20$ , $p=0.0157$

Table 4: GAL network, 150 epochs, three seeds of five-fold cross validation. The

F

column tests the two accuracies against each other.

Dataset	$K$	all data	90%	untrained	noise	residual	splits	$p$
		complete, 63 splits		per-leaf
Digits	10	0.967 $\pm$ 0.010	0.965 $\pm$ 0.011	0.703 $\pm$ 0.153	0.920 $\pm$ 0.015	0.927 $\pm$ 0.015	10.5	0.106
vehicle	4	0.800 $\pm$ 0.022	0.796 $\pm$ 0.019	0.710 $\pm$ 0.044	0.792 $\pm$ 0.027	0.780 $\pm$ 0.027	16.1	0.016
segment	7	0.961 $\pm$ 0.006	0.958 $\pm$ 0.008	0.948 $\pm$ 0.014	0.950 $\pm$ 0.011	0.952 $\pm$ 0.008	21.9	0.523
satimage	6	0.896 $\pm$ 0.011	0.897 $\pm$ 0.008	0.870 $\pm$ 0.013	0.878 $\pm$ 0.012	0.878 $\pm$ 0.011	9.4	0.754
optdigits	10	0.970 $\pm$ 0.004	0.973 $\pm$ 0.004	0.839 $\pm$ 0.090	0.936 $\pm$ 0.013	0.938 $\pm$ 0.010	11.3	0.283

Table 5: Per-leaf growth, depth at most six, 180 epochs. untrained is the previous behaviour; noise and residual inherit the parent and break the symmetry. splits is the mean number of splits of the residual variant;

p

tests residual with the gate against untrained.

Dataset	$K$	all data	90%	split budget	full budget	$p$
		from scratch		grown
Digits	10	0.925 $\pm$ 0.029	0.929 $\pm$ 0.030	0.921 $\pm$ 0.027	0.921 $\pm$ 0.028	0.274
vehicle	4	0.798 $\pm$ 0.031	0.756 $\pm$ 0.031	0.777 $\pm$ 0.030	0.790 $\pm$ 0.033	0.600
segment	7	0.948 $\pm$ 0.014	0.947 $\pm$ 0.012	0.931 $\pm$ 0.013	0.946 $\pm$ 0.009	0.648
satimage	6	0.880 $\pm$ 0.011	0.883 $\pm$ 0.010	0.883 $\pm$ 0.010	0.881 $\pm$ 0.010	0.584
optdigits	10	0.937 $\pm$ 0.024	0.946 $\pm$ 0.010	0.941 $\pm$ 0.011	0.941 $\pm$ 0.011	0.757

Table 6: Depth four, 150 epochs. split budget divides the epochs across growth rounds, which is the default; full budget gives every round all of them.

p

tests full against split.

Dataset	Selection rule	Accuracy	Nodes
Breast Cancer	highest accuracy	0.971 $\pm$ 0.020	4.7 $\pm$ 1.8
	significance	0.958 $\pm$ 0.016	7.0 $\pm$ 1.9
Digits	highest accuracy	0.599 $\pm$ 0.036	12.2 $\pm$ 1.0
	significance	0.596 $\pm$ 0.055	13.7 $\pm$ 1.4

Table 7: Omnivariate tree of maximum depth three. Three seeds of five-fold cross validation.

Decision Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

Aug 4, 2026

Double Descent in Gradient Boosting Decision Trees via Split-Candidate Scaling

Double descent is commonly studied by scaling an explicit capacity parameter, such as neural-network width. For gradient boosting decision trees (GBDTs), however, an analogous single-axis capacity parameter has not been established. We propose the number of split candidates as an operational capacity parameter for GBDTs. Holding other training controls fixed, increasing the split-candidate budget refines the feature-quantization grid and expands the dictionary of root-to-leaf paths from which boosting selects its updates. To analyze this expansion, we construct an empirical tree-kernel diagnostic that summarizes how candidate-induced paths group the training examples. A regime in which the empirical kernel rank grows toward the sample size and very small positive eigenvalues emerge exposes noise-sensitive directions; in this regime, test error peaks before decreasing again at larger split-candidate budgets. This perspective predicts that deeper trees should reach the regime with fewer split candidates, larger training sets should require finer grids, and label noise should make the peak more pronounced. Experiments support these predictions and show test-error peaks at intermediate split-candidate budgets across XGBoost, LightGBM, and CatBoost, whereas a random-forest control improves monotonically under the same split-candidate sweep. Taken together, our analysis and experiments support split-candidate scaling as a single-axis capacity intervention for studying GBDTs and suggest that the observed double descent arises from an interaction between candidate-induced geometry and boosting dynamics.

Ryuichi Kanoh

1The University of Electro-Communications · 2National Institute of Informatics

Double Descent Gradient-Boosted Decision Trees

Ask PDF

Sep 14, 2026

Learned Look-Ahead Splitting Rule for CART

Classification and regression trees are typically constructed using a greedy splitting rule that maximizes the immediate reduction in prediction error at each node. Although this strategy is computationally efficient, it can miss splits that yield small short-term gains but create substantial downstream improvements after further partitioning. We propose a look-ahead tree-building method that evaluates each candidate split by the prediction error reduction achieved after growing a conventional CART subtree below that split. Because the full look-ahead procedure can be computationally expensive, we also describe a smart look-ahead algorithm that learns downstream split values using node-level features. The proposed framework preserves the interpretability of recursive partitioning while improving split selection in hierarchical or interaction-driven settings. We conduct a simulation study comparing conventional, full look-ahead, and smart look-ahead methods under several settings and apply the proposed methods to analyze two real data examples demonstrating the merit of the new methods.

Andrew Gao, Tianlin Liu, Ruichen Han +1

Thomas Jefferson High School for Science and Technology, Alexandria, VA 22312, USA · Lynbrook High School, San Jose, CA 95129, USA · Department of Biomedical Data Science, Stanford University, Stanford, CA 94305, USA

Decision Tree Learning Classification

Ask PDF

Aug 29, 2026

Adaptive Multi-Branching for Shallow Decision Tree Induction

Decision trees are attractive for tabular prediction tasks because each prediction follows an interpretable sequence of feature-threshold tests. Under a strict maximum-depth budget, however, conventional binary trees can be under-expressive, since each internal node makes only a single threshold decision. We study shallow-depth tree induction, where the goal is to improve accuracy while keeping root-to-leaf paths short. We propose the Multi-Branch Neural Decision Tree with Adaptive Pruning (MBNDT), a single axis-aligned tree trained end-to-end with differentiable multi-way splits. Each internal node learns ordered thresholds over a selected feature and a branch mask that adapts its effective arity, and the trained model is converted to a deterministic single-path tree for inference. Across 21 OpenML binary-classification benchmarks, MBNDT achieves the best average rank and mean balanced accuracy among depth-constrained single-tree baselines; a controlled ablation isolates multi-way splitting as the source of the gain. These gains come with an explicit trade-off: MBNDT realizes more leaves than the other single-tree baselines, making it best suited when accuracy under short, bounded decision paths is prioritized over minimal global tree size.

Hanul Park, Jeonghoon Choi, Juseong Kim +2

Department of Information Convergence Engineering, Pusan National University, Busan, Rep. of Korea · School of Computer Science and Engineering, Pusan National University, Busan, Rep. of Korea

Decision Tree Learning Tabular ML Interpretable ML

Ask PDF

Abstract

Decision Tree Learning

Explore similar work

Double Descent in Gradient Boosting Decision Trees via Split-Candidate Scaling

Learned Look-Ahead Splitting Rule for CART

Adaptive Multi-Branching for Shallow Decision Tree Induction