Decision tree structure and terminology

WHAT is a decision tree?

WHY do we care? Because trees are:

Interpretable — you can read the decision path as plain English rules.
Non-parametric — they make no assumption that the boundary is a straight line.
The building block for Random Forests and Gradient Boosting (the workhorses of tabular ML).

The anatomy (terminology)

Figure — Decision tree structure and terminology

Formula What a leaf predicts (derived, not dumped)

A leaf $\ell$ owns a set of training samples $R_\ell$ . We must pick one prediction $\hat y_\ell$ to minimize training loss on that leaf.

Classification — minimize misclassifications $\sum_{i\in R_\ell}\mathbb{1}[y_i \ne \hat y_\ell]$ . This is minimized by choosing the most frequent class (the majority vote): $\hat y_\ell = \arg\max_c \; |\{i \in R_\ell : y_i = c\}|$ Why? Any label you pick is "wrong" for every sample not of that label; picking the biggest group leaves the fewest wrong.

Regression — minimize squared error $\sum_{i\in R_\ell}(y_i - \hat y_\ell)^2$ . Take derivative w.r.t. $\hat y_\ell$ and set to $0$ :

\;\Rightarrow\; \hat y_\ell = \frac{1}{|R_\ell|}\sum_{i\in R_\ell} y_i$$ So a regression leaf predicts the ==mean== of its samples.

HOW a tree carves up space

WHY axis-aligned? Testing one feature at a time keeps splits cheap to search (just sort each feature and try thresholds) and keeps the rules human-readable.

Worked examples

Steel-manned mistakes

Flashcards

What node holds the entire dataset before any split?

The root node.

A node with no children that outputs a prediction is called?

A leaf (terminal) node.

What kind of test does a standard CART internal node use?

An axis-aligned test, "

x_j \le t

?".

What does a classification leaf predict, and why?

The majority class — it minimizes the number of misclassified samples in that leaf.

What does a regression leaf predict, and why?

The mean of its samples — it minimizes squared error (derivative of

\sum(y_i-\hat y)^2

set to 0).

Define tree depth.

The number of edges on the longest root-to-leaf path.

Why is a single tree's decision surface a "staircase"?

Axis-aligned splits partition space into rectangles; predictions are constant per box → piecewise-constant.

What is pruning and why do it?

Cutting subtrees to reduce overfitting / lower model complexity.

Difference between a branch and a leaf?

A branch is an edge (test outcome); a leaf is a terminal node (prediction).

Why does growing a tree very deep hurt generalization?

It memorizes noise (overfits), so training error drops but test error rises.

Recall Feynman: explain to a 12-year-old

Imagine a game of "20 Questions" to guess an animal. The first question ("Does it have fur?") is the root. Each answer sends you down a path with more questions (internal nodes). When you're sure enough — "It's a cat!" — you stop; that ending is a leaf. A decision tree is a computer playing this game with your data. If you ask too many tiny questions you start "guessing" based on flukes — that's overfitting, so smart players stop early (pruning).

Connections

Gini impurity and entropy — how the best question is chosen at each split.
CART algorithm — the greedy recursive procedure that builds the structure above.
Overfitting and pruning — controlling depth and subtree removal.
Random Forests — many trees averaged to smooth the staircase.
Gradient Boosted Trees — trees stacked to correct each other's errors.
Bias-variance tradeoff — deep tree = low bias, high variance.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, decision tree basically ek "20 questions" wala game hai. Sabse upar hota hai root node jahan poora data rehta hai — yahin se pehla sawaal poocha jaata hai, jaise "Age 30 se kam hai kya?". Har answer ke hisaab se data do hisson me bat jaata hai (ye hai branch ya edge). Beech ke jo nodes aur sawaal poochte hain unhe internal/decision node kehte hain, aur jab hum kaafi confident ho jaate hain toh rukh jaate hain — us end point ko leaf kehte hain, jo final prediction deta hai.

Ab prediction kaise banti hai? Agar classification hai, toh leaf me jo class sabse zyada baar aayi hai wahi predict hoti hai (majority vote), kyunki isse sabse kam samples galat classify hote hain. Regression me leaf apne saare samples ka mean predict karta hai, kyunki mean squared error ko minimize karta hai (calculus se derivative zero karke nikalta hai). Ye simple ideas hi poore tree ka core hain — 80% samajh in 20% cheezon me hai.

Ek important baat: tree ke splits axis-aligned hote hain, matlab ek time pe ek hi feature check hota hai (" $x_j \le t$ "). Isliye feature space chhote-chhote rectangles (boxes) me bat jaata hai aur boundary seedhi diagonal nahi, balki seedhi-tikoni "staircase" jaisi banti hai. Isko yaad rakhna important hai warna Random Forest aur Boosting samajhne me dikkat hogi.

Aur ek warning: "zyada deep tree = better" ye galat soch hai. Deep tree training data ratt leta hai (overfitting), test pe fail ho jaata hai. Isiliye hum max_depth, min_samples_leaf set karte hain ya pruning karte hain. Mantra yaad rakho: "Roots Ask, Leaves Answer."

Decision tree structure and terminology

WHAT is a decision tree?

The anatomy (terminology)

HOW a tree carves up space

Worked examples

Steel-manned mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Tree-Based & Instance Methods

Connections