Decision trees
Twenty questions, played by an algorithm that chooses each question by how much it cleans up the labels.
Nearest neighbors classifies by geometry. Decision trees classify by question rules: pick a feature and a threshold — "is age > 19?" — split the data on the answer, and recurse into each half. The trained model is a tree of these questions; the leaves hold the answers.
What greedy means here
At every node the algorithm slides an imaginary question along each feature and asks: which single question, right now, most lowers the mixed-up-ness of the two halves? Pick it, split, recurse. It never plans ahead — greedy, like gradient descent is locally greedy.
One feature, 10 points — find the question (“…> t?”) up the labels up the labels
left: 5 pts, gini 0.32right: 5 pts, gini 0.32weighted impurity 0.32
The data has one clean cut: t just past 3.7 makes both sides pure (weighted impurity 0.00). One click is one split; a real tree recurses on impure nodes across all features, but when one clean cut exists greedy finds it. Slide to t ≈ 3.4 or 4.8 and watch the classes smear across each side — worse tree, and the number agrees with your eyes. Watch the boundary color flip as classes smear across each side: that is a worse tree, and the number agrees with your eyes.
What the split is scored by
Mixed-up-ness is measured with the Gini impurity: the chance that two random samples from the node disagree on the label (1 − Σ p² per side, weighted by split size). Each candidate threshold has a score; the best wins; the tree grows node by node. Inside the artifact, try deliberately-bad thresholds — the score displays exactly why the greedy pass would never choose them.
Why trees conquered the real world anyway
Individually, a tree is usually the worst high-performing model: axis-aligned boxes are an absurd class of shapes (they can't even draw the logistic regression's clean diagonal). And yet — random forests and gradient boosting (chapter 4) are trees at scale, and they win most tabular-data competitions to this day. The cases for the tree family:
- A split needs no scaling, no linearity assumption, tolerates irrelevant features, and natively handles missing values in production-style data.
- The learned structure is inspectable: a path is a rule a doctor, banker, or teacher can audit — the artifact's readout above is literally the explanation.
- Trained greedily node-by-node with sample counts (chapter 3's batching), it needs no gradient, no learning rate, no convexity.
The costs are just as concrete: the sharp rectilinear boundaries bundles overfit dramatically (fully grown, each leaf memorizes its few points), and tiny data changes can, brittly, restructure the tree. Both costs are handleable at ensemble scale — that's chapter 4, where thousands of overfit trees average each other's noise away.
Illustrative vs real
One feature, one depth, hand-run splits here — a stump-grade toy. Real trees split all features recursively with regularized growth limits, and no human ever clicks the thresholds.
Where next: margins and support vectors — the geometry the tree abandoned, done rigorously.