Regression trees
Ask a short list of yes/no questions about the inputs ("has this player been in the league less than 4.5 years?"). Each answer path ends in a box of similar training points, and the prediction is simply their average.
Question type: regression (the answer is a number). Classification trees are on their own page.
Week: 4.
Book: ISLP 8.1.1 (and 8.1.3, 8.1.4).
Techniques on this page: splitting the input space into boxes, predicting the box average, scoring a tree by its RSS, recursive binary splitting (top-down and greedy), stopping rules.
The problem it solves
Linear regression uses one formula everywhere. But some relationships are more like a set of rules: “new players earn little whatever they do; experienced players earn more, especially if they hit a lot”. A single sloped line can’t say that. KNN can bend, but you can’t read it, and it needs every input on the same scale.
A tree learns the rules themselves. It’s as readable as a flow chart, handles inputs on any scale (each question looks at one input), and can capture jumps and interactions that a straight line misses. The price: one tree is jumpy. A slightly different training set can give a very different tree (high variance), which is why pruning exists.
Words you’ll hear
| Word | Plain meaning |
|---|---|
| split, internal node | one yes/no question “is \(X_j < s\)?” |
| cutpoint, threshold \(s\) | the number in the question |
| leaf, terminal node, region \(R_m\) | where a path of answers ends: a box of training points |
| root | the first question; every point passes through it |
| depth | how many questions on the longest path |
| recursive binary splitting | build the tree one two-way split at a time |
| greedy | take the best split now, without planning ahead |
| \(\lvert R_m\rvert\) | the number of training points in box \(m\) |
Technique 1: boxes and box averages
Problem it solves: making a prediction once the space has been cut up.
Each question compares one input with a threshold, so the regions are rectangles (“boxes”) with edges parallel to the axes. ISLP’s baseball example (log-salary from Years and Hits) has three:
Years < 4.5 ?
/ \
yes no
R1: 5.11 Hits < 117.5 ?
/ \
R2: 6.00 R3: 6.74To predict for a new player, answer the questions from the top until you reach a leaf, and output the average response of the training players in that leaf. 6 years and 130 hits: right, right, 6.74. The tree also reads as a story: experience matters most; for newcomers hits barely matter.
Why the average? Within one box, the single number \(c\) that makes \(\sum(y_i - c)^2\) smallest is the mean.
Technique 2: score a tree by its RSS
Problem it solves: deciding which tree is “best” on the training data.
\[\text{RSS}(T) = \sum_{m=1}^{J}\;\sum_{i \in R_m}(y_i - \hat y_m)^2,\qquad \hat y_m = \text{average of the } y_i \text{ in box } m\]
The same score as linear regression: add up the squared misses. A good tree has boxes whose responses are close to each other.
Technique 3: recursive binary splitting (greedy)
Problem it solves: there are far too many possible trees to try them all.
- Start with all the data in one box.
- For every box, every input \(X_j\) and every cutpoint \(s\) (midpoints between neighbouring values), compute the RSS you’d get by splitting that box in two at \(X_j < s\).
- Make the single split with the lowest RSS. You now have one more box.
- Repeat from step 2.
It’s greedy: it never goes back to change an earlier split, and it doesn’t look ahead.
Worked example. Years \(x = (1, 2, 3, 5, 7, 8)\), salary \(y = (2, 3, 5, 8, 9, 12)\). One box: mean 6.5, RSS 73.5.
| cut \(s\) | left | right | total RSS |
|---|---|---|---|
| 1.5 | {2} | {3, 5, 8, 9, 12} | 49.2 |
| 2.5 | {2, 3} | {5, 8, 9, 12} | 25.5 |
| 4 | {2, 3, 5} mean 3.33 | {8, 9, 12} mean 9.67 | 13.33 |
| 6 | {2, 3, 5, 8} | {9, 12} | 25.5 |
| 7.5 | {2, 3, 5, 8, 9} | {12} | 37.2 |
Split at 4. Next round, the best split of the left box saves 4.17; the best of the right box (at 7.5) saves 8.17. So split the right box at 7.5. Three leaves: \(x < 4 \to 3.33\); \(4 \le x < 7.5 \to 8.5\); \(x \ge 7.5 \to 12\). RSS 5.17.
Technique 4: when to stop
Problem it solves: without a rule, splitting goes on until every leaf holds one point.
Stop when the leaves are small (at most \(n_{\text{stop}}\) points) or the tree reaches a maximum depth (max_depth in sklearn). With \(n_{\text{stop}} = 1\) every leaf predicts its own training point exactly: training RSS 0, memorised noise, poor test error. The better fix is to grow big and then prune.
Lab habit to avoid: the lab standardises training, validation and test sets each with their own mean and sd. Use the training mean and sd for all three. (Trees don’t care about scaling, but the networks later in the lab do.)
Trees vs linear regression
| linear regression | regression tree | |
|---|---|---|
| shape | one sloped plane | flat steps on boxes |
| best when | the truth is roughly linear | the truth has jumps, thresholds, interactions |
| needs scaling? | for gradient descent | no |
| readable? | coefficients | a flow chart |
| variance | low | high |
This is exactly lab Q1. ISLP 8.1.3 (one page) is the argument to use in your answer.
What to read in the book
| Section | Read? | Why |
|---|---|---|
| 8.1.1 Regression trees, up to “Tree pruning” (p331–335) | Read | Core: Hitters, RSS of boxes (8.1), recursive binary splitting (8.2–8.3) |
| 8.1.3 Trees versus linear models | Read | Not on the slides, but it’s lab Q1’s comparison |
| 8.1.4 Advantages and disadvantages | Read | Matches slides 7–8 |
| 8.2 Bagging, random forests, boosting | Skip | Only named on slide 8 |
Practice prompt
I'm studying CS5100 Data Analysis (textbook ISLP, section 8.1.1). I want practice questions on REGRESSION TREES, done by hand:
- reading a small tree diagram: which leaf a new point lands in and what it predicts
- describing the regions of a tree as sets / boxes in the input plane
- computing the RSS of a leaf and of a whole tree
- finding the best first split of a tiny 1D data set by trying every midpoint
- choosing between splitting one region or another in the second round (greedy, biggest RSS drop)
- what n_stop = 1 or a maximum depth does, and why a fully grown tree overfits
- why trees don't need standardised inputs, and when a tree beats linear regression
Please:
1. Use plain, everyday language and explain any technical term in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.