Foundations — Decision tree structure and terminology

This page assumes you know how to count and read a graph with an $x$ and $y$ axis. Nothing more. We build every symbol the parent note throws at you, in an order where each piece stands on the one before it.

0. The raw ingredients: samples, features, targets

Before any tree exists, we have a table of data. Picture a spreadsheet.

How to read this figure: each dot is one sample. Its horizontal position is Feature 1 (Income) and its vertical position is Feature 2 (Age) — the two axes. Its colour is the target: magenta dots are class A, violet dots are class B. Notice the two colours already sit in different corners of the grid — that separation is exactly what a tree will try to fence off with straight cuts. The orange arrow points at one single dot to remind you: one dot = one row of the spreadsheet = one sample.

Why the topic needs this: a decision tree's entire job is to look at where the dots sit (features) and predict their colour or number (target). No dots, no tree.

1. Subscripts and indexing: $x_j$, $y_i$

The parent note writes things like $x_j$ and $y_i$. These little lowered letters are just labels that say "which one".

We meet one more symbol, $\in$, in section 3 — but only after we have defined the box $R_{\ell }$ that a dot can belong to. We build the box first.

Why the topic needs this: the leaf-prediction formulas point at individual dots ($y_i$) and individual features ($x_j$); without subscripts you can't say which one.

2. The test $x_j\le t$: a question that draws a line

This is the heart of the whole topic.

Here is the visual that makes "axis-aligned" click:

Why the topic needs this: every internal node in the parent note is one of these tests. Stack a few and you carve the grid into boxes (next section).

3. Regions, boxes, and membership: $R_{\ell }$, hyper-rectangles, and $\in$

Now that a box $R_{\ell }$ exists, the membership symbol has something to point into:

4. The tools inside the leaf formulas

The parent derives two leaf predictions. Let's arm every symbol first. Throughout, every sum runs over $i\in R_{\ell }$ — only the dots inside this leaf's box, never all samples.

4a. $\hat{y}$ — "the predicted answer"

4b. $\sum$ — "add them all up"

4c. $1[\cdot ]$ — "the yes/no counter"

4d. $\arg \max$ — "which choice wins?"

4e. The derivative $\frac{d}{d{\hat{y}}_{\ell }}$ — the tool that finds the best number

For regression the parent takes a derivative. Here is why that tool and not another.

4f. $|R_{\ell }|$ — "how many"

5. Family words: root, parent, child, depth

These are relationship words, not new maths.

Prerequisite map

Where each piece is used next

• The test $x_j\le t$ and regions feed CART algorithm (how splits are searched) and Gini impurity and entropy (how a split is scored).
• Depth and subtree feed Overfitting and pruning.
• The staircase boundary is smoothed by Random Forests and corrected by Gradient Boosted Trees; the depth/complexity story connects to Bias-variance tradeoff.
• Return to the parent: parent topic.

Equipment checklist

Self-test: can you answer each before revealing?