A decision tree has a wonderfully legible sales pitch:

ask one question
split the data
repeat

That is why trees are everywhere. They feel less like a black box than a neural net and less like algebra than a generalized linear model. The root node looks like an explanation.

But the root node is not just an explanation.

It is the winner of a contest.

For a CART-style classifier, the tree searches over candidate splits and chooses the one that most reduces node impurity.1 That works beautifully when the contest is fair. It gets strange when one feature gets one ticket and another feature gets a hundred.

The quiet bias is:

the tree compares each feature's best accident

The Small Crime Scene

Imagine three predictors:

signal          binary, genuinely predictive
binary noise    binary, independent of the label
many-cut noise  continuous, independent of the label

At a stump, the signal feature has one natural split. The binary-noise feature also has one. The continuous-noise feature can try many thresholds.

Even when the continuous feature is pure noise, its best threshold is the maximum of many random impurity reductions. The maximum of many accidents is not an average accident. It is a selected accident.

That selection step is where interpretability leaks.

Hothorn, Hornik, and Zeileis state the issue bluntly in their conditional inference tree paper: exhaustive-search tree algorithms have both overfitting and selection bias toward covariates with many possible splits or missing values.2 Pruning can shrink an overgrown tree, but it does not undo the biased choice of which variable was invited into the tree.2

Strobl, Boulesteix, Zeileis, and Hothorn made the same warning concrete for random forests and variable importance: when predictors differ in measurement scale or number of categories, the usual variable-importance measures can artificially prefer suboptimal predictors.3

This is not a moral failure of trees. It is a multiple-comparisons problem wearing a friendly shape.

The Lab

The browser lab below fits a single greedy classification stump and then repeats the same experiment many times. The data-generating process is simple:

one binary signal changes the class probability
one binary noise feature is independent of the label
one ordered categorical noise feature is independent of the label
one many-cut continuous noise feature is independent of the label

The split criterion is Gini impurity decrease. The holdout set is freshly generated from the same process, so a noise split that won the training contest has nowhere to hide.

Default settings:

samples              160
signal effect         22%
many-cut candidates  120
category levels       36
repeated samples     260

single fitted stump:  signal
training gain         0.0366
holdout gain          0.0120
holdout accuracy      57.7%

signal wins           73%
all noise wins        27%
many-cut noise wins   15%

The signal is real. The noise is also competitive.

Signal Many-cut noise Category noise Binary noise Training statistic

Deterministic browser experiment. Each repetition draws a new training sample, fits a one-split CART-style stump by exhaustive Gini-gain search, and evaluates the selected split on an independent holdout sample from the same data-generating process.

Try three moves.

First, lower Signal effect to 10%. In the default seed, the repeated simulation gives the signal only about 18% of stump wins; noise features win the rest. The single fitted stump may still say signal, but the repeated ledger tells you the procedure is unstable.

Second, raise Noise cut points. Under a pure-noise null, the expected best training gain rises as the number of candidate thresholds rises. That bottom left panel is the whole lesson in miniature: the split statistic is being optimized over a larger menu.

Third, raise Samples. The fake gains shrink. This is why the problem is most visible in small-to-medium data, wide tables, mixed feature types, and feature-importance workflows where people read the tree as a ranked list of causes.

Why A Forest Does Not Magically Fix It

A random forest changes many things at once:

bootstrap or subsampling
random feature subsets at each node
many high-variance trees averaged together
feature importance accumulated over many splits

It is excellent prediction machinery. But the default impurity importance is still built from split gains. Louppe and coauthors describe mean decrease impurity as the weighted impurity decrease accumulated over nodes where a variable is used.4 If a variable is selected too often because it had many candidate thresholds, that bias can flow into the importance score.

Strobl et al. separate two issues: biased variable selection inside individual trees and bootstrap-sampling effects.3 That matters because “just use permutation importance” is not a universal cleanup spell either. Permutation importance answers a prediction question under a chosen fitted model and data distribution. It is often safer than impurity importance for high-cardinality noise, but it can still be affected by correlated predictors, leakage, grouped features, and the model’s learned structure.

So the practical hierarchy is:

impurity importance: fast, inspectable, biased toward many split opportunities
permutation importance: closer to predictive reliance, needs a holdout contract
conditional inference: changes the split-selection test itself
domain audit: asks whether the feature was allowed to know the answer

The Repair Is To Separate Two Questions

Greedy CART asks a combined question:

which variable and which split give the biggest impurity drop?

Conditional inference trees separate it:

which variable is associated with the response?
given that variable, where should it split?

Hothorn, Hornik, and Zeileis build that separation through permutation-test machinery and stopping criteria based on multiple testing.2 The point is not that every project should swap algorithms immediately. The point is that the bias has a statistical shape, not merely a software shape.

Once you see it, the root split of a tree starts to look less like:

the most important feature is X

and more like:

among the candidate questions this algorithm allowed itself to ask,
X produced the largest in-sample impurity decrease

That sentence is less pretty. It is also much closer to the truth.

The Checklist I Use

Before interpreting tree features, I want to know:

How many candidate splits did each feature get?
Were high-cardinality categoricals encoded as ordered integers?
Was feature importance impurity-based, permutation-based, or conditional?
Was importance measured on training data, out-of-bag data, or a real holdout?
Do grouped or correlated features split credit across substitutes?
Could a feature be a proxy for leakage, sampling, time, or row identity?

The lab is deliberately only a stump. That is enough. If the first split can be biased before the tree grows, a forest of trees deserves an audit before it becomes a story about the world.

The tree did not lie.

It just got more lottery tickets.

  1. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone, Classification and Regression Trees, Wadsworth/Taylor & Francis, 1984. ↩

  2. Torsten Hothorn, Kurt Hornik, and Achim Zeileis, “Unbiased Recursive Partitioning: A Conditional Inference Framework”, Journal of Computational and Graphical Statistics 15(3):651-674, 2006. DOI: 10.1198/106186006X133933. ↩ ↩2 ↩3

  3. Carolin Strobl, Anne-Laure Boulesteix, Achim Zeileis, and Torsten Hothorn, “Bias in random forest variable importance measures: Illustrations, sources and a solution”, BMC Bioinformatics 8, article 25, 2007. DOI: 10.1186/1471-2105-8-25. ↩ ↩2

  4. Gilles Louppe, Louis Wehenkel, Antonio Sutera, and Pierre Geurts, “Understanding variable importances in forests of randomized trees”, NeurIPS 2013. ↩