Learn machine learning · deep dive D2 · optional
Cost-complexity pruning
Put a price on a leaf and a tree prunes itself. Work out the price at which each subtree stops paying for itself, then read the staircase that falls out of it.
Optional, and it blocks nothing. It opens because 2.4 Pruning and instability is done. The gate is three prices within 0.0005 plus the correct minimum marked in all four columns.
01 · brief
Session 2.3 limited a tree by depth and 2.4 watched what a small change in the rows did to its shape. Depth is a blunt control: it caps every branch at the same length whether or not that branch was earning anything.
The alternative charges for size instead. Score a tree as R-alpha(T) = R(T) + alpha x leaves(T), where R is the training error rate and alpha is a price per leaf. At alpha zero the largest tree wins. Raise the price and at some point a subtree's extra leaves cost more than the error they save, so it collapses.
The question you cannot answer yet: how many different trees does that price actually produce as it rises from zero, and who picks which one.
02 · commit
Before anything runs
Before any arithmetic: as the price per leaf rises from zero to a large number, how many distinct trees does this sequence of four produce?
Choose something first.
03 · work
For two nested subtrees the price is the extra training error divided by the leaves given up: alpha = (R of the smaller - R of the larger) / (leaves of the larger - leaves of the smaller). Collapsing all the way to a single leaf is the textbook case, where the denominator is leaves - 1.
To four decimals or better, within 0.0005.
Attempts: 0
To four decimals or better, within 0.0005.
Attempts: 0
To four decimals or better, within 0.0005.
Attempts: 0
0 of 3 prices accepted.
The four subtrees
illustrativeauthored fixture| subtree | leaves | training error | validation accuracy |
|---|---|---|---|
| T0 | 8 | 0.150 | 0.771 |
| T1 | 5 | 0.166 | 0.796 |
| T2 | 3 | 0.192 | 0.788 |
| T3 | 1 | 0.300 | 0.702 |
These four are a fixture, chosen so every number on this page can be checked with a pencil. They are not a fit on the loan rows.
Mark the smallest R-alpha in each column
R-alpha(T) = R(T) + alpha x leaves(T). One radio group per column: choose the row with the smallest value.
| subtree | alpha 0.004 | alpha 0.010 | alpha 0.020 | alpha 0.060 |
|---|---|---|---|---|
| T0 | ||||
| T1 | ||||
| T2 | ||||
| T3 |
Mark one row in every column first.
Four columns of R-alpha, one per price per leaf, and four rows, one per subtree. Each column holds the four trees scored at that price; one of the four is the smallest.
Show the grid as a table
| subtree | leaves | error | alpha 0.004 | alpha 0.01 | alpha 0.02 | alpha 0.06 |
|---|---|---|---|---|---|---|
| T0 | 8 | 0.150 | 0.1820 | 0.2300 | 0.3100 | 0.6300 |
| T1 | 5 | 0.166 | 0.1860 | 0.2160 | 0.2660 | 0.4660 |
| T2 | 3 | 0.192 | 0.2040 | 0.2220 | 0.2520 | 0.3720 |
| T3 | 1 | 0.300 | 0.3040 | 0.3100 | 0.3200 | 0.3600 |
The alpha path prints here once the three prices above are accepted. They are the three numbers it is made of, so it stays shut until you have worked them out.
Which tree a given price keeps
Ask for a hint
Rungs open as you run the session, not as time passes. You have run it 0 times.
1. A question: available after 3 evaluated runs.
2. The answer: available after 5 evaluated runs.
04 · verdict
Work the three prices above and the verdict states the path against what you committed to.
05 · gate
Your check: an outcome you produce
not yetThe three prices within 0.0005, and the smallest R-alpha marked correctly in all four columns of the grid.
Not met yet. Keep working the session.
The validation block scores highest on T1 at 0.796, and the training error alone would have kept the largest tree. Which prices keep T1 is the arithmetic above.
carry
Your takeaway
Edit it into your own words, or keep the line as it is.