Skip to content

Classical ML

Decision Trees

Twenty questions, played by a machine. A tree asks "is x less than this?" over and over until it can name the class. Let it ask too many and it memorises the answers instead of learning them. This module is about knowing when to stop.

difficulty
medium
time
35 min
xp available
720

02briefing

One question at a time

A decision tree asks about the data the way you would play twenty questions. Is x less than 0.8? Yes, go left. No, go right. On each side it asks another question, and it keeps going until it reaches a leaf. The leaf says which class most of the training points that landed there belonged to.

Two features, x and y, means every question is a vertical or horizontal line on the map. The regions the tree carves out are rectangles. Watch the heat map in the demo and you will see them.

Which question first

Every candidate split gets a score: how much purer are the two sides than the whole was? Purity is measured by Gini impurity:

gini = 1 - p0² - p1²

A group that is all one class scores 0. A fifty-fifty mix scores 0.5. The gain of a split is the impurity before it minus the impurity after, weighted by how many points went each way. The engine tries every threshold on both features and keeps the biggest gain. Then it does the same on each side.

Deeper is not better

Given enough depth, a tree can fit any training set perfectly. It just keeps asking until every leaf is pure, even if that means carving a region around a single point whose label was flipped by noise. On the training set that looks like a win: 100 percent. It has not learned the shape of the data. It has memorised the list.

That is why the demo keeps a test set the tree never sees. Filled points are training data. Hollow points are test data. Press sweep depths and read the two lines:

  • Train accuracy only ever goes up with depth. It has to.
  • Test accuracy climbs to a peak around depth 2 or 3, then slides.

The gap between the lines is the overfit. The depth where test peaks is where you stop.

Where it goes wrong

  1. Depth 0. One leaf, no questions, majority class for everyone. A coin flip on balanced data.
  2. Depth 12 on noisy data. Perfect on train, worse than depth 2 on test. The tree is fitting the flipped labels.
  3. Noise going up. Raise the label noise slider and the best depth moves down. Noisy data wants simpler models. That is not a tree rule, it is a modelling rule.

Grow the tree at depth 1, 3 and 12, and look at the map each time. Smooth borders are learning. Jagged islands around single points are memorising.

03live demo

04missions

Predict

Which split comes first?

Read the state, call the outcome before the engine does.

unranked
up to 120 xpclear Logistic Regression first
Tune

Set the depth

Turn the knobs until the loss behaves.

unranked
up to 160 xpclear Logistic Regression first
Debug

It memorised the training set

Something is wrong on purpose. Find it.

unranked
up to 200 xpclear Logistic Regression first
Code

Write gini()

Write the function. The tests are the judge.

unranked
up to 240 xpclear Logistic Regression first

05in production

Fraud checks and loan decisions

When a bank has to explain why a transaction was flagged, a tree can show the exact path: amount above this, country not in the usual list, time after midnight. Each split is a question a human can read. That is why trees, and the forests built from hundreds of them, are everywhere decisions have to be justified, not just made.

The forest behind most tabular models

Gradient-boosted trees, the engine behind a huge share of winning models on spreadsheet-shaped data, are thousands of small trees added together. Every one of them is grown exactly the way the demo grows one: pick the split with the best Gini gain, recurse, stop at a depth. Learn the single tree and the forest is repetition.

06code samples

engine/cpp/decision_tree.hc++
// A binary classification tree on two features, grown greedily by Gini gain.
//
// The tree is a flat array of nodes, 8 floats each, node 0 the root:
//   [0] feature   0 or 1, or -1 for a leaf
//   [1] threshold go left when x[feature] < threshold
//   [2] left      index of the left child (leaves: -1)
//   [3] right     index of the right child (leaves: -1)
//   [4] p1        fraction of class 1 among the node's points
//   [5] depth     root is 0
//   [6] n         points that reached the node
//   [7] unused    0
// Flat floats so the page can read it straight out of wasm memory and draw it.
#pragma once

namespace ne {

constexpr int TREE_NODE_FLOATS = 8;

/** Gini impurity of binary labels: 1 - p0^2 - p1^2. 0 when n <= 0. */
double gini(const float* y, int n);

/**
 * The split with the largest Gini gain over all points. out3 = feature, threshold, gain.
 * Returns true when some split has positive gain with at least one point on each side.
 */
bool tree_best_split(const float* x2, const float* y, int n, float* out3);

/**
 * Grow a tree to max_depth with at least min_leaf points per leaf, into out_nodes (holding
 * max_nodes * 8 floats). Returns the node count, 0 for bad input. When max_nodes runs out
 * the remaining nodes stay leaves.
 */
int tree_grow(const float* x2, const float* y, int n, int max_depth, int min_leaf,
              float* out_nodes, int max_nodes);

/** P(class 1) at (x, y). NaN for an empty tree. */
double tree_predict(const float* nodes, int count, double x, double y);

/** P(class 1) on a grid, y outer, same layout as surface_grid. Returns nx * ny. */
int tree_grid(const float* nodes, int count, double xmin, double xmax, double ymin, double ymax,
              int nx, int ny, float* out);

/** Fraction of points where (p >= 0.5) matches y. 0 when n <= 0. */
double tree_accuracy(const float* nodes, int count, const float* x2, const float* y, int n);

}  // namespace ne

07debrief

module tier

unranked

0 xp earned here

PredictWhich split comes first?unranked
TuneSet the depthunranked
DebugIt memorised the training setunranked
CodeWrite gini()unranked

Run the demo for Bronze. Pass the quiz for Silver.

08share kit

A decision tree is twenty questions played by a machine. Let it ask too many and it cheats. Here is where to stop.

  1. Slide 1. A tree asks one question at a time. Is x less than 0.8? Yes, go left. No, go right. Keep asking until it can name the class.
  2. Slide 2. Which question first? The one that makes the two sides purest. That purity score has a name, Gini, and you will write it.
  3. Slide 3. Depth 0 is a coin flip. Depth 2 is decent. Depth 12 gets the training set perfect and gets new data wrong. That is overfitting.
  4. Slide 4. The chart tells the truth. Train accuracy only goes up with depth. Test accuracy peaks, then falls. Stop at the peak.
  5. Slide 5. Fraud flags, loan decisions, and the forests behind most tabular models. Same tree, thousands of times. Grow one yourself, link in bio.

story

  1. Frame 1. Two crescents of points, one tiny tree. Text: three questions, 85 percent right.
  2. Frame 2. A huge tangled tree, jagged regions. Text: fifty questions, 100 percent on train, 75 on test. Memorised.
  3. Frame 3. The skill tree with Decision Trees lit. Text: set the depth, earn the XP. NEURAL//RUN.

#machinelearning #decisiontrees #overfitting #datascience #learntocode #ai #python #cplusplus #webassembly #randomforest #developer #mlengineer #dataviz #learnml #techeducation #cyberpunk #interactivelearning #codinglife

completion card

run the demo to earn a card
+50 credits, once
back to the tree