Latent

Grow a decision tree

Watch a tree split the plane one question at a time, and find the depth where it stops learning and starts memorizing.

BeginnerExplained in Decision trees

Grow a decision tree

Each split asks one yes or no question about a point's position. Shading shows the share of class B training points in each leaf.

  • Class A
  • Class B
  • Split

Dashed rings mark points whose label was flipped on purpose.

Tap the plane to follow one point's questions down the tree.

3
Data
Labels flipped at random
Impurity measure
Show
Splits shown7 of 7
Depth reached3
Leaves8
Training accuracy90%
Test accuracy82%

Challenges

0 of 3 complete

  1. With label noise on, grow a tree that gets every training point right. (not yet)
  2. On Circle with 10% noise, find the depth that gets the most test points right. (not yet)
  3. On XOR with no noise, find the smallest depth that gets at least 90% of test points right. (not yet)

Try this

  • Press Grow split by split and watch the order of the questions: the biggest drop in impurity comes first.
  • Raise the maximum depth to 12 with 20% noise and look at the tiny boxes around the ringed points.
  • Switch to test points at depth 12. Which boxes were wrong?
  • Tap a point on the plane to see the questions it answers on the way to its leaf.
Growing a tree by the best Gini splitPython with NumPy
import numpy as np

# Ten points on a plane (across, up) with labels 0 = class A, 1 = class B.
X = np.array([[0.1, 0.2], [0.3, 0.8], [0.2, 0.5], [0.4, 0.3], [0.35, 0.9],
              [0.7, 0.2], [0.8, 0.6], [0.6, 0.85], [0.9, 0.4], [0.55, 0.15]])
y = np.array([0, 1, 0, 0, 1, 1, 1, 1, 1, 0])

def gini(labels):
    p = np.mean(labels) if len(labels) else 0.0
    return 1 - p**2 - (1 - p)**2

def best_split(X, y):
    best = (0.0, None, None)
    for f in range(X.shape[1]):
        values = np.unique(X[:, f])
        for t in (values[:-1] + values[1:]) / 2:  # midpoints between values
            left, right = y[X[:, f] <= t], y[X[:, f] > t]
            after = (len(left) * gini(left) + len(right) * gini(right)) / len(y)
            if gini(y) - after > best[0]:
                best = (gini(y) - after, f, t)
    return best

def grow(X, y, depth, level=0, answer=""):
    pad = "    " * level + answer
    gain, f, t = best_split(X, y)
    if depth == 0 or f is None:  # out of depth, or no split lowers impurity
        print(f"{pad}leaf: {np.sum(y == 0)} A, {np.sum(y == 1)} B")
        return
    print(f"{pad}is {['across', 'up'][f]} <= {t:.3f}? (gain {gain:.3f})")
    mask = X[:, f] <= t
    grow(X[mask], y[mask], depth - 1, level + 1, "yes -> ")
    grow(X[~mask], y[~mask], depth - 1, level + 1, "no  -> ")

grow(X, y, depth=2)
is across <= 0.575? (gain 0.213)
    yes -> is up <= 0.650? (gain 0.444)
        yes -> leaf: 4 A, 0 B
        no  -> leaf: 0 A, 2 B
    no  -> leaf: 0 A, 4 B

Try "embedding", "softmax", "overfitting", or "backpropagation".