Decision Tree

A decision tree classifies by asking one thresholded question at a time — is this coordinate ≤ this value? — and choosing each question greedily, as the argmax of information gain over every candidate cut. Training recursively splits the data into purer and purer regions; prediction just walks the questions from root to leaf and returns that leaf's majority vote.

The model you end up with is a flowchart, and that is not an insult. Twenty questions is a decision tree: a well-balanced question can rule out roughly half the remaining possibilities, and a good question is precisely one that removes the most uncertainty. The tree plays twenty questions against a scatter plot, with entropy as the referee scoring every question it could ask — and because every question it is allowed to ask is axis-aligned, the map it carves is always a set of axis-aligned rectangles. That constraint, and the depth budget that stops the recursion, are the two facts this lesson exists to make visible.

How a Decision Tree Works

Start with the referee. A region holding a A-points and b B-points has entropy H = −p_A·log₂ p_A − p_B·log₂ p_B, measured in bits: 0 when the region is pure, a full 1 bit at a 50/50 mix. Entropy is the tree's definition of disorder, and a split's score — its information gain — is the disorder it removes: the parent's entropy minus the size-weighted entropy of the two children.

Which splits are even on the ballot? For each axis, sort the distinct coordinate values and take the midpoint between each consecutive pair. Nothing else is worth trying: sliding a threshold anywhere between the same two data points partitions the data identically, so scoring one midpoint per gap covers every distinguishable cut. Eleven points might offer a dozen or so candidates in total — small enough to try all of them, which is exactly what the tree does. That exhaustive scan is the honest cost of training: naively O(d·n²) per node for d axes (the animation's two), against O(depth) per prediction — the asymmetry that makes trees cheap to deploy. Those candidate scans are the two amber bar-profiles you see riding the bottom and left edges of the region in the animation, one bar per midpoint, height proportional to gain.

Then greed: keep the single best cut, split the data, and recurse into each side separately — the two halves never see each other's points again. Two things stop the recursion. A pure region has entropy 0, so no cut can improve it: it becomes a leaf answering its one class. And a region at depth == max_depth is out of questions: it becomes a leaf answering its majority class, mixed or not. Both stops return through the same guard, and the second one is where all of a tree's training errors live.

Three conventions, stated once so every number below is reproducible. "Yes" always means ≤, and the yes-branch is the left child. Ties in gain keep the earlier candidate — lower axis first, then lower threshold — because the loop only replaces the champion on a strictly greater score. A tied majority vote answers class A.

One more property is easy to miss and worth staring at: the rectangles are derived, never drawn. Each split line spans only the region of the node that chose it, because that node never saw any other region's points. Stack up the cuts and the rectangle map falls out — the map IS the model.

Decision Tree Step by Step

The default run: eleven points, six of class A and five of class B, max_depth = 2, query x = (3, 3). Four A's sit in a left block, four B's in the bottom-right, and the top-right holds two A's plus one B at (3, 4) — a planted noise point. Keep an eye on it.

1. Root impurity. 6 A vs 5 B — nearly a coin flip. H = 0.99 bits.
2. Scan x₁. Six vertical candidates. The best is x₁ ≤ −0.5: gain = 0.99 − (4/11)·0 − (7/11)·0.86 = 0.44 bits, because its left side would be pure A.
3. Scan x₂. Seven horizontal candidates. The best, x₂ ≤ −2.5, gains only 0.24 — a real contest, and x₁ wins it.
4. Split. Commit x₁ ≤ −0.5. The plane becomes two rectangles; the tree gets its root question.
5. Left child. All four points are A — entropy 0, pure leaf, answer A. The rectangle takes A's color for good.
6. Right child. 2 A, 5 B, H = 0.86. Its own scan: x₁'s best manages 0.08, x₂ ≤ 0.5 gains 0.47. Commit x₂ ≤ 0.5 — a line that spans only the right rectangle, which is the "derived, not drawn" rule paying off on screen.
7. Bottom-right leaf. Four B's, pure, answer B.
8. Top-right leaf. 2 A and 1 B — still mixed, but its depth is 2 and the budget says stop. Majority vote: A. The noise point (3, 4) is now inside an A rectangle, and it is simply, permanently wrong. Final score: 3 leaves, 1 error out of 11.
9. Predict x = (3, 3). Root: x₁ = 3 > −0.5, go right. Next: x₂ = 3 > 0.5, go up — into the impure leaf. Answer: A, by 2 votes to 1. A tree's confidence is nothing deeper than the leaf's training count.

Why Decision Trees Overfit

That mis-covered point at (3, 4) is the whole overfitting story in one pixel. Re-run the same data with max_depth = 3 — the "One more level" recipe — and the greedy scan inside the top-right region finds x₂ ≤ 3.5: gain 0.92, a numerically perfect split. What it buys is a sliver of the plane whose only inhabitant is that single noise point. Training errors drop to zero — but the new leaf rests on one supporting point. That is memorization: a region whose entire evidence is a single observation, answering with full confidence for every future point that lands in it.

So depth is the memorize/generalize dial, and you can turn it both ways from the default. At depth 1 the whole right half becomes one majority-B leaf and the two honest top-right A points get sacrificed: 2 errors of underfitting. At depth 2 the tree accepts 1 error to keep its regions supported by several points each. At depth 3 it reaches 0 training errors by giving noise its own real estate. Nothing inside training can tell you which of those trees is right — training error cannot increase as this fixed greedy tree is extended, but it may stay unchanged. The instrument that can tell is a held-out test set, and that diagnostic belongs to the training loop lesson. Real systems shorten the argument by pruning, requiring a minimum number of samples per leaf, or averaging many trees into a forest — all of which are just this dial with better hands on it.

Rectangles Against Straight Lines

Every model family refuses some shapes and gets others for free — inductive bias is a trade, not a ranking, and the two dataset presets stage one round each.

The islands preset reuses the point layout that ends the linear classifier lesson, with its three classes collapsed to two: one class living in two opposite corners, everyone else in between. A linear model provably cannot own both corners — its regions are convex, and the corridor between the islands belongs to someone else. The tree does not even notice the difficulty. Its first cut, x₁ ≤ −1.5, fences off one island; the second, x₂ ≤ 1.5, fences off the other. Two questions, zero errors, done — because a union of rectangles was never required to be convex. (This run also shows the tie-break live: both axes' best cuts gain exactly 0.31, and the earlier axis keeps it.)

The diagonal preset reverses the beating. Eight points split perfectly by the slanted line x₂ = x₁ — one cut for a linear model, drawn as a dashed ghost on the finished map. The tree cannot ask a slanted question. Greedy does its best with straight ones and builds a staircase — x₁ ≤ −3, then x₂ ≤ −1, then x₁ ≤ 1 — and after all three cuts, at depth 3, one point still sits on the wrong side. Approximating one diagonal line costs a tower of rectangles and still leaves change. Same tree, same greed; the only thing that changed is whether the data's true boundary was shaped like the questions the model is allowed to ask.

Edge Cases

• Pure region before the depth budget runs out — the entropy-0 guard fires first and the leaf commits early; the default run's left block does this at depth 1.
• Depth stop on a mixed region — majority vote, minority points wrong; the top-right leaf at depth 2, or the entire right half at depth 1.
• An axis with one distinct value — no midpoints, no candidates; the other axis must carry the node, and if neither axis offers a cut a general implementation must return a majority leaf even when labels conflict at identical coordinates; these datasets contain no such conflicting duplicates.
• Tied gains — kept deterministic: lower axis, then lower threshold. The islands root is a genuine on-screen tie.
• Tied majority vote — answers class A, by convention, stated rather than hidden.

Common Mistakes

• Reading the rectangle map as something the tree stores. It stores questions; the map is what the questions imply. That is why a split line never crosses into a sibling's territory.
• Trusting a leaf that one point built. Gain 0.92 looked like the best split of the entire run — and it was pure memorization. Support (how many points back a leaf) matters more than the gain that created it.
• Treating zero training error as success. Any tree reaches it with enough depth, on any consistent data. The number is a property of capacity, not of learning.
• Expecting greed to find the smallest tree. Greedy locks in the locally best cut; on the diagonal data it opens with a cut that shaves a single point because nothing better exists among straight questions. Optimal tree construction is NP-hard — greed is the standard compromise, not the truth.
• Reading leaf proportions as probabilities. "A, 2 of 3" is a training count over a tiny region, not a calibrated 67%.

A Note on Simplification

This is a textbook ID3-style tree, kept small enough to check every number by hand: entropy and information gain (some libraries instead use Gini impurity, which can rank candidate cuts differently), midpoint thresholds on two features, a depth cap as the only regularizer, and eleven integer points. None of it is two-dimensional in spirit: with d features every question is still one coordinate against one threshold, so the regions become axis-aligned hyperrectangles in d dimensions — which is why trees are a first choice on tabular data, where features arrive mixed and unscaled and a root-to-leaf path reads as a rule a human can audit. Production trees (CART, sklearn) handle continuous targets, missing values, cost-complexity pruning, and minimum-leaf-size rules — and are usually deployed in ensembles (random forests, gradient boosting) precisely to average away the single tree's variance you watched the depth dial create.