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

Double Descent in Gradient Boosting Decision Trees via Split-Candidate Scaling
Aug 4, 2026Ryuichi KanohDouble Descent Gradient-Boosted Decision Trees
1The University of Electro-Communications · 2National Institute of Informatics
Learned Look-Ahead Splitting Rule for CART
Sep 14, 2026Andrew Gao, Tianlin Liu, Ruichen Han +1Decision Tree Learning Classification
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
Adaptive Multi-Branching for Shallow Decision Tree Induction
Aug 29, 2026Hanul Park, Jeonghoon Choi, Juseong Kim +2Decision Tree Learning Tabular ML
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

Aug 4, 2026J/K move · Enter open · S save

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

Ryuichi Kanoh

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

Double Descent Gradient-Boosted Decision Trees

Open paper AskPDF arXiv

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.

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