Continuous Function

Machine Learning

Decision Trees

Decision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

status: reviewimportance: importantdifficulty 3/5math: undergraduateread: 18mlive demo
Back to Machine LearningNext: Random Forests (review)

Concept Structure

Decision Trees

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

1prerequisites
3next concepts
3related links

Learner Contract

What this page should let you do.

You are here becauseDecision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

This Machine Learning concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextRandom Forests (review)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Random Forests (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources3 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptDecision TreesMachine LearningEquationDecision Trees equation 1Exact equationCodeDecision Trees runnable code 1Exact runnable codeDemoDecision Trees interactive demoInteractive demoClaimA classification tree greedily chooses axis-aligned splits that reduc...Exact claim checkSourceCS229 Decision TreesExact source
ConceptDecision TreesMachine Learning
3 sources attachedLocal snapshot ready
concept:machine-learning/decision-trees
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

A decision tree learns by asking a sequence of small questions:

If I cut the data here, do the two child regions become easier to label?

Each internal node is a test such as x1≤0.47x_1 \le 0.47. Each leaf is a region of feature space. For classification, the leaf usually predicts the majority class among the training examples that landed there.

That makes trees feel wonderfully concrete. You can trace a prediction through visible rules. But this is also the trap: readable rules are not automatically reliable rules. The split is chosen by a local score, not by global understanding. A tiny change near an early split can change the first question, and then every downstream branch sees a different training subset.

So the core mechanism is:

  1. measure impurity in the parent node,
  2. test candidate splits,
  3. compute the weighted impurity of the children,
  4. pick the split with the largest reduction,
  5. repeat until a stopping or pruning rule says enough.

The first split matters because it reshapes the rest of the problem.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1p^k(R)=1∣R∣∑i∈R1[yi=k],\hat p_k(R)=\frac{1}{|R|}\sum_{i\in R}\mathbf 1[y_i=k],Equation 2G(R)=∑k=1Kp^k(R)(1−p^k(R))=1−∑k=1Kp^k(R)2.G(R)=\sum_{k=1}^K \hat p_k(R)(1-\hat p_k(R)) =1-\sum_{k=1}^K \hat p_k(R)^2.

Let a node contain a set of training indices RR. For a KK-class classification problem, define

p^k(R)=1∣R∣∑i∈R1[yi=k],\hat p_k(R)=\frac{1}{|R|}\sum_{i\in R}\mathbf 1[y_i=k],

the fraction of examples in region RR whose class is kk.

One common impurity score is the Gini impurity:

G(R)=∑k=1Kp^k(R)(1−p^k(R))=1−∑k=1Kp^k(R)2.G(R)=\sum_{k=1}^K \hat p_k(R)(1-\hat p_k(R)) =1-\sum_{k=1}^K \hat p_k(R)^2.

A pure node has all examples in one class, so one p^k\hat p_k is 11 and G(R)=0G(R)=0. A mixed node has larger impurity.

Another common score is entropy:

H(R)=−∑k=1Kp^k(R)log⁡2p^k(R),H(R)=-\sum_{k=1}^K \hat p_k(R)\log_2 \hat p_k(R),

with the convention that 0log⁡0=00\log 0=0.

Now consider a candidate split ss. It sends the parent region RR into two children:

RL(s)={i∈R:xij≤t},RR(s)={i∈R:xij>t}.R_L(s)=\{i\in R: x_{ij}\le t\}, \qquad R_R(s)=\{i\in R: x_{ij}>t\}.

For an impurity function II, the weighted child impurity is

Ichildren(s)=∣RL(s)∣∣R∣I(RL(s))+∣RR(s)∣∣R∣I(RR(s)).I_{\text{children}}(s) = \frac{|R_L(s)|}{|R|}I(R_L(s)) + \frac{|R_R(s)|}{|R|}I(R_R(s)).

The split gain is

ΔI(s)=I(R)−Ichildren(s).\Delta I(s)=I(R)-I_{\text{children}}(s).

A greedy tree chooses

s⋆=arg⁡max⁡sΔI(s).s^\star=\arg\max_s \Delta I(s).

After the split, a classification leaf predicts

y^(R)=arg⁡max⁡kp^k(R).\hat y(R)=\arg\max_k \hat p_k(R).

This is precise but local. The optimization over full tree structures is combinatorial, so practical trees use greedy recursive splitting plus controls such as maximum depth, minimum leaf size, or cost-complexity pruning. Interpretability comes from the rule trace; reliability still has to be checked with held-out evaluation, cross-validation, and sensitivity to data changes.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1import math points = [ (0.14, 0.78, 1), (0.18, 0.30, 1), (0.25, 0.62, 1), (0.36, 0.21, 1), (0...python
import math

points = [
    (0.14, 0.78, 1), (0.18, 0.30, 1), (0.25, 0.62, 1),
    (0.36, 0.21, 1), (0.42, 0.50, 0), (0.52, 0.82, 1),
    (0.63, 0.26, 0), (0.70, 0.60, 1), (0.82, 0.74, 0),
    (0.88, 0.38, 0), (0.48, 0.46, 0), (0.56, 0.58, 0),
]

splits = [("x <= 0.47", 0, 0.47), ("y <= 0.55", 1, 0.55), ("x <= 0.70", 0, 0.70)]

def impurity(labels, criterion="gini"):
    n = len(labels)
    ps = [labels.count(k) / n for k in set(labels)]
    if criterion == "entropy":
        return -sum(p * math.log2(p) for p in ps)
    return 1 - sum(p * p for p in ps)

def gain(split, criterion="gini"):
    _, axis, threshold = split
    left = [label for *xy, label in points if xy[axis] <= threshold]
    right = [label for *xy, label in points if xy[axis] > threshold]
    parent = impurity([label for *_, label in points], criterion)
    weighted = (len(left) / len(points)) * impurity(left, criterion)
    weighted += (len(right) / len(points)) * impurity(right, criterion)
    return parent - weighted, left, right

for split in splits:
    score, left, right = gain(split)
    print(split[0], round(score, 3), "left", left, "right", right)

The code is the root-split ledger in miniature: compute parent impurity, split the rows, weight the child impurities, and choose the largest reduction.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the lab as a split-selection microscope. First choose the criterion and dataset case. Then predict which candidate root split wins before revealing the impurity ledger. In the perturbed case, one ambiguous label changes the root split, which is the point: a tree can be easy to read and still sensitive.

Live Concept Demo

Explore Decision Trees

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 3/5undergraduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Decision Trees should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Decision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Decision Trees should make visible.

Visual Inquiry

Make the image answer a mathematical question

Decision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Decision Trees easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

course-notes · 2021CS229 Decision TreesStanford CS229

Supports decision trees as nonlinear classifiers, entropy and Gini splitting losses, and the warning that trees are high-variance and prone to overfitting.

Open source
book · 2023An Introduction to Statistical Learning, Chapter 8James, Witten, Hastie, Tibshirani, and Taylor

Supports recursive binary splitting, partitioning predictor space into regions, classification-tree majority-class prediction, Gini/entropy node purity, cost-complexity pruning, and tree instability.

Open source
book · 2009The Elements of Statistical Learning, Chapter 9Hastie, Tibshirani, and Friedman

Supports CART-style recursive partitions, node impurity measures, Gini and cross-entropy/deviance, greedy region search, pruning, and the bridge from trees to ensembles.

Open source

Claim Review

Decision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources3 references

cs229-2021-decision-trees, james-2023-islr-tree-based-methods, hastie-2009-esl-trees

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedA classification tree greedily chooses axis-aligned splits that reduce weighted child impurity, predicts the majority class in each terminal region, and can be interpretable while still being high-variance and sensitive to small data changes.Claim metadata: source checked

The sources support the split-by-impurity framing, region/leaf prediction interpretation, Gini and entropy formulas, greedy recursive construction, pruning/regularization need, and the caveat that single trees can be unstable.

Sources: CS229 Decision Trees, An Introduction to Statistical Learning, Chapter 8, The Elements of Statistical Learning, Chapter 9The interactive lab is a one-level classification split witness. It does not implement a full CART search over all thresholds, cost-complexity pruning, categorical/surrogate splits, missing-value handling, oblique trees, statistical consistency, or ensemble methods.A bounded review summary is present; still check caveats and exact reference scope.

Checked Stanford CS229 decision-tree notes, ISLR Chapter 8, and ESL Chapters 9-10 for recursive binary splitting, partition regions, majority-class leaves, Gini and entropy/cross-entropy impurity criteria, greedy approximate optimization, pruning/regularization, high variance, and ensemble motivation. GPT Pro critique remains pending because the browser lane at 127.0.0.1:51672 was unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-02
source-span-cs229-2021-decision-treessource-span-james-2023-islr-tree-based-methodssource-span-hastie-2009-esl-treesEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

course-notes 2021CS229 Decision Trees

Supports decision trees as nonlinear classifiers, entropy and Gini splitting losses, and the warning that trees are high-variance and prone to overfitting.

book 2023An Introduction to Statistical Learning, Chapter 8

Supports recursive binary splitting, partitioning predictor space into regions, classification-tree majority-class prediction, Gini/entropy node purity, cost-complexity pruning, and tree instability.

book 2009The Elements of Statistical Learning, Chapter 9

Supports CART-style recursive partitions, node impurity measures, Gini and cross-entropy/deviance, greedy region search, pruning, and the bridge from trees to ensembles.

Mechanism checks

Equation 1
p^k(R)=1∣R∣∑i∈R1[yi=k],\hat p_k(R)=\frac{1}{|R|}\sum_{i\in R}\mathbf 1[y_i=k],
Equation 2
G(R)=∑k=1Kp^k(R)(1−p^k(R))=1−∑k=1Kp^k(R)2.G(R)=\sum_{k=1}^K \hat p_k(R)(1-\hat p_k(R)) =1-\sum_{k=1}^K \hat p_k(R)^2.
Runnable code 1import math points = [ (0.14, 0.78, 1), (0.18, 0.30, 1), (0.25, 0.62, 1), (0.36, 0.21, 1), (0...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Decision trees split feature space into simple regions; the split rule is local impurity reduction, not a guarantee of robust understanding.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Decision Trees.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptDecision TreesMachine Learning
Runnable code comparisonDecision Trees runnable code 1points = [Prediction before revealDecision Trees interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Decision Trees click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptMachine Learning

Decision Trees

Attached question

What is the smallest example that makes Decision Trees click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Decision Trees Selected item key: recorded for copy. Context: Machine Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes Decision Trees click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/machine-learning/decision-trees concept:machine-learning/decision-trees