Exercises — Decision tree structure and terminology

The root node. It is the only node that holds the entire dataset, and the first split happens there. Why not "internal node"? Every root is an internal node in behaviour (it asks a question), but "root" is the special name for the one with no parent.

• "branch" = the edge (the True/False outcome of a test).
• "leaf" = the node (the terminal endpoint that outputs a prediction). A branch is a line in the drawing; a leaf is a box.

A class label (e.g. "cat"). Classification leaves output categories; only regression leaves output numbers.

Count each class: Dog $=3$, Cat $=2$, Bird $=1$ (total $=6$). The majority class is Dog, so $\hat{y}=\text{Dog}$. Choosing Dog is "wrong" for every sample that is not a Dog: that is $2+1=\boxed{3}$ misclassified. Why majority? Any label we pick is wrong for every sample of a different class; the biggest group leaves the fewest wrong. In symbols — where $\ell$ names one leaf, $i$ runs over the samples in that leaf, $y_i$ is sample $i$'s true label, and $c$ ranges over the possible classes — this is ${\hat{y}}_{\ell }=\arg {\max }_c|\{i:y_i=c\}|,$ i.e. "pick the class $c$ whose group of samples is largest." No tie here: Dog (3) is a clear single winner, so the tie-break rule never fires.

The regression leaf predicts the mean: $\hat{y}=\frac{4+8+8+20}{4}=\frac{40}{4}=10.$ Why the mean? We minimize squared error ${\sum }_i(y_i-\hat{y}{)}^2$. Setting the derivative to zero, $-2{\sum }_i(y_i-\hat{y})=0$, gives $\hat{y}=\frac{1}{n}{\sum }_i{y}_i$ — the average.

Follow each edge and AND the conditions. The False branch of Income ≤ 30k? means Income > 30k. $\text{IF }\text{Age}\le 40\text{AND}\text{Income}>30\text{k}\text{THEN}\text{Approve}.$ Why AND? A single path forces all its tests to hold at once, so the conditions chain with AND.

Count: $A=2$, $B=2$ — a tie. Either choice misclassifies the other 2 samples, so both give the same minimum training error of $\boxed{2}$. Because we need a deterministic answer, we apply the tie-break rule (first class in order): predict ==$A$==. Why it doesn't matter for the loss: on a tie, no class is "more correct"; the tie-break only makes the model reproducible, it does not lower the error.

Depth = the number of edges on the longest root-to-leaf path. $\text{depth}=\max (2,4,3)=\boxed{4}.$ Why the max? Depth measures the worst-case number of questions the tree can ask before answering.

The first test $x_1\le 5$ is a vertical line splitting the plane into left/right. The second test $x_2\le 3$ is a horizontal line applied only to the right piece, splitting it into bottom/top. Result: $\boxed{3}$ rectangular boxes. What "rectangular box" means here: in a 2-feature space each leaf is an ordinary rectangle whose sides are parallel to the axes. If there were $d$ features instead of 2, the same idea gives a $d$-dimensional box (a "box" in $d$ directions) — the general name for that is a hyper-rectangle (just "rectangle" stretched to more than 2 dimensions; the "hyper-" prefix only means "in higher dimensions"). On this 2-D page you can safely picture plain rectangles. Why rectangles? Each test is perpendicular to one axis, so stacking them can only ever cut out axis-aligned boxes — never a diagonal. Predictions are constant inside each box, giving the staircase surface described in the parent's splitting section.

Every split is of the form $x_j\le t$ — a line perpendicular to one axis (horizontal or vertical), never slanted. To follow the diagonal, the tree must chain many small horizontal + vertical cuts, producing a staircase of tiny boxes that hugs the diagonal. The more splits (the deeper the tree), the finer the steps — but it is always piecewise-constant, never a true slanted line. See the red staircase tracking the green diagonal in the figure.

Split on $x\le 2$:

• True ($x\in \{1,2\}$): both labels are $A$ → leaf predicts ==$A$== (majority is unanimous).
• False ($x\in \{3,4\}$): both labels are $B$ → leaf predicts ==$B$==. All four points correct; training error $=0$. Depth $=\boxed{1}$ (one edge from root to each leaf). Why $x\le 2$? The threshold must land between the last $A$ ($x=2$) and the first $B$ ($x=3$). Any $t$ with $2\le t<3$ works; $t=2$ is the standard "$\le$" choice.

With split $x\le 2$, the True leaf now owns $x\in \{1,1.5,2\}$ with labels $\{A,B,A\}$ — impure, because the noisy $B$ at $x=1.5$ sits between the two $A$'s. To reach $0$ training error the tree must isolate that lone $B$ with extra cuts inside the True region, carving $x\le 1$ (labels $\{A\}$), $1<x\le 1.5$ (labels $\{B\}$), and $1.5<x\le 2$ (labels $\{A\}$). Together with the untouched False leaf ($x\in \{3,4\}$, all $B$), the tree ends with $\boxed{4}$ leaves and training error $0$. Why dangerous? A future point near $x=1.5$ is probably really an $A$; the tree confidently says $B$. That is overfitting — the deep tree fits a fluke, so test error rises. This is the low bias, high variance regime.

The merged leaf owns $A=2$, $B=1$. Majority vote → predict ==$A$==. Predicting $A$ is wrong only for the single noisy $B$ at $x=1.5$, so training error on this leaf $=\boxed{1}$ sample. Why accept a training error? We trade one memorized fluke for a much simpler tree that generalizes better — the whole point of pruning. Predicting the majority $A$ treats the lone $B$ as the noise it almost certainly is.

(a) Classification. Counts: $A=3,B=2,C=1$. Majority → predict ==$A$== (clear single winner, no tie). Misclassified = all non-$A$ = $2+1=\boxed{3}$. (b) Regression. Mean: $\hat{y}=\frac{2+2+5+6+9+12}{6}=\frac{36}{6}=6.$ SSE $={\sum }_i(y_i-6{)}^2=(-4{)}^2+(-4{)}^2+(-1{)}^2+0^2+3^2+6^2=16+16+1+0+9+36=\boxed{78}$. Why these choices? Majority minimizes misclassifications; the mean minimizes SSE (derivative $-2\sum (y_i-\hat{y})=0$). Both come straight from the parent's leaf-prediction derivation.

Split first on $x_1\le 0$ (i.e. "$x_1=0$?"):

• True ($x_1=0$): rows 1–2 are both $\text{No}$ → pure leaf: No.
• False ($x_1=1$): rows 3–4 are $\{\text{No},\text{Yes}\}$ → not pure, split again on $x_2\le 0$:
  • True ($x_2=0$): row 3 → leaf: No.
  • False ($x_2=1$): row 4 → leaf: Yes.

All 4 rows correct. Longest path Root → ($x_2$ node) → leaf crosses 2 edges, so depth $=\boxed{2}$. Why split $x_1$ first? $x_1=0$ alone fully decides "No" (2 pure samples in one cut), so it's the cheapest question that purifies the most data — exactly the greedy logic CART follows using impurity.

A single tree's staircase has high variance — small data changes reshuffle the boxes. Random Forests grow many de-correlated trees on bootstrapped samples and average their predictions; averaging more independent trees cancels out their random wiggles, smoothing the staircase and cutting variance (the variance side of the tradeoff) without much added bias. Gradient Boosted Trees instead grow shallow trees in sequence, each new tree predicting the residual errors of the ensemble so far — chipping away at bias step by step. Both keep the axis-aligned box structure of a single tree, but combine many of them to escape the overfit/underfit trap that a lone tree falls into.

Root holds the whole dataset? ::: Yes — the only node with no parent. Classification leaf predicts…? ::: The majority class (minimizes misclassifications). On a tie between classes, what happens? ::: Both give the same error; a fixed tie-break (first class in order) is used for determinism. Regression leaf predicts…? ::: The mean (minimizes squared error). Depth counts nodes or edges? ::: Edges, on the longest root-to-leaf path. 0 training error is good or a warning? ::: A warning — likely overfitting. Random Forest fixes which error, how? ::: Variance, by averaging many de-correlated trees.