Sparse Decision Trees (GOSDT)

At the end of the last section, we hinted at a big problem with decision trees: instability. A small change in the data can change the root split, and that one choice changes everything below it. Another problem is that CART creates trees using a “top down” approach and then applies pruning. An early mistake in the tree propagates to every branch below it. In attempt to subvert these problems, we ensemble predictions from many trees using random forests and boosted trees, but we lose the interpretability.

Tree Instability

Click students to remove them from the training set. Watch the root split change — even one or two removals can produce a completely different tree structure.

Training set — 24 of 24 students

Click any student to remove them from training.

Predict grade in XAI

Root split: Listens to music when doing HW

This fragility is inherent to greedy top-down splitting. The first split shapes everything below. Random forests average over many such trees to reduce variance, but the ensemble then loses the single readable path.

Theoretically, if random forests and gradient boosted trees exist with higher accuracy and stability, then there must exist an optimal decision tree that combines the best decisions from all of the trees in an ensemble.

But how would we find the optimal decision tree? The number of possible combinations is HUGE!

Generalized and Scalable Optimal Sparse Decision Trees (GOSDT) tackles this challenge by searching for a tree that performs well as a whole while paying for complexity.

ℹ

The optimization target

A simplified objective is:

$R(T) + \lambda H_T$

$R(T)$ is prediction error, $H_T$ is the number of leaves, and $\lambda$ is the price of complexity. A new leaf must reduce enough error to justify itself.

Accuracy Is Only Half the Objective

GOSDT searches across candidate trees and charges for leaves. Move the complexity penalty to decide how much accuracy you are willing to trade for a tree someone can hold in their head.

Leaf penaltyλ = 0.040

Candidate	Errors	Leaves	error + λ(leaves)
stump	18%	2	0.260
small tree ← selected	9%	4	0.250
medium tree	5%	7	0.330
large tree	3%	12	0.510

The word optimal refers to the stated objective and search space. Change the penalty or the available binary features and the optimal tree can change.

The search space is enormous. GOSDT uses bounds and equivalent feature representations to discard families of trees that cannot beat the best solution found so far. That is what makes a global optimization approach practical on nontrivial binary-feature problems. In the original paper, 10 Analytical Bounds are proposed to reduce the search space.

Feature preparation matters. Continuous values are usually converted into candidate thresholds such as age ≥ 50 or debt ratio ≥ 40%. The algorithm optimizes over the choices you give it. A missing threshold cannot appear in the final tree.

GOSDT Bounding Strategies

GOSDT eliminates families of candidate trees using bounds — if no tree in a family can beat the best solution found so far, the entire family is removed from the search. Explore how each bound works.

R_bestsofar — best error found so far0.18b(tree) — lower bound on this tree's error0.14

Comparing values

R_bestsofar (0.18) ≥ b(tree) (0.14) → continue

R_bestsofar < b(tree)
→ remove this tree and all extensions from the search

How it works

b(tree) is the smallest possible error this tree can achieve — the best-case floor. If even that floor is worse than a tree we've already found, this entire family is hopeless.

Think of it like the 2048 game: if your current score can't possibly beat your personal best even in the best case, you click "New Game."

Decision

Keep exploring

This family of trees might contain a better solution — keep searching.

These bounds work together. As R_bestsofar decreases over the search, bounds become tighter and more families get eliminated — making the global search practical.

⚠

Optimal is conditional

The result is optimal for the objective, data, feature encoding, and search constraints. It is not the one universally best tree for the domain. Change the complexity penalty or binarization and the optimum can change.

Checkpoint

What happens when the leaf penalty λ increases?

Checkpoint

A six-leaf tree is 1% more accurate than a three-leaf tree. What information would you need before choosing between them?

←PreviousDecision TreesTrees and Rules Next→Decision RulesTrees and Rules