Regression trees

Decision trees were on both the 2024 and 2025 papers (25 marks each time), and the lecturer’s week 4 matches 2025 Q1 almost exactly. Stages 13 to 15 take you through every part.

1. Boxes from yes/no questions

A tree splits the input space with questions “is \(X_j < s\)?”. Each answer sends you left (yes) or right (no) until you reach a leaf:

             Years < 4.5 ?
            /             \
          yes              no
       R1: 5.11      Hits < 117.5 ?
                     /           \
                   yes            no
                R2: 6.00       R3: 6.74

This is ISLP Fig. 8.1: a baseball player’s log salary from Years and Hits. The leaf value is the average of the training players in it. The regions are boxes with edges parallel to the axes (\(R_1 = \{\text{Years} < 4.5\}\), \(R_2 = \{\text{Years} \ge 4.5, \text{Hits} < 117.5\}\), \(R_3 = \{\text{Years} \ge 4.5, \text{Hits} \ge 117.5\}\)); they don’t overlap and they cover everything.

Vocabulary: the root is the first question; internal nodes are questions; leaves (terminal nodes) are the regions; the depth is the number of questions on the longest path.

Predicting: follow the questions to a leaf \(R_x\) and output the average \(\hat y = \frac{1}{|R_x|}\sum_{i \in R_x}y_i\) of its training responses. As a formula, \(f(X) = \sum_m c_m\mathbb 1(X \in R_m)\): piecewise constant.

Why people like trees: you can read them like a flow chart (Years is the most important input; for inexperienced players Hits barely matters), they handle categorical inputs easily, and they need no scaling (rescaling an input just rescales its thresholds). Weakness: high variance; a small change in the data can change the whole tree.

2. Growing a tree: greedy splitting by RSS

Score a tree \(T\) with leaves \(R_1, \dots, R_J\) by its training RSS:

\[\mathrm{RSS}(T) = \sum_{m=1}^{J}\sum_{i \in R_m}(y_i - \hat y_{R_m})^2.\]

(The leaf average is the best constant: \(\frac{d}{dc}\sum(y_i - c)^2 = 0\) gives \(c = \bar y\).)

Trying every possible tree is impossible, so recursive binary splitting works top-down and greedily:

1. Start with one region holding all the data.
2. Try every input \(j\) and every cutpoint \(s\), splitting into \(\{x_j < s\}\) and \(\{x_j \ge s\}\). Keep the split with the smallest RSS.
3. Then try every split of any current region; keep the one with the smallest total RSS (= the biggest drop). Repeat.

Only the gaps between neighbouring data values matter, so the candidate cutpoints are the midpoints of neighbouring distinct values. Greedy means a split is never revisited, even if a different early split would have allowed a better tree later.

3. When to stop, and why it matters

Keep splitting until a stopping rule: a maximum depth (max_depth) or a minimum number of points per leaf (\(n_{\text{stop}}\)). With \(n_{\text{stop}} = 1\) every leaf holds one training point, predicts it exactly, and the training RSS is 0: the tree has memorised the data, noise included. That’s extreme overfitting. More leaves = more flexible (stage 15 controls this with pruning).

Trees vs linear models (ISLP 8.1.3): if the truth is close to a straight line, a tree must approximate it with a staircase and linear regression wins. If the truth is very non-linear or box-shaped, the tree wins.

In sklearn: DecisionTreeRegressor(max_depth=10).fit(X, y), and plot_tree shows each node’s split (sklearn sends “\(\le\)” left), its squared_error (MSE = RSS/n), samples, and value (the mean).

Stage test