Classical Machine Learning, lesson 9
Random forests and gradient boosting
Many trees voting, or small trees that each fix the last one's mistakes.
"Decision trees": how a tree chooses its splits, and why a deep one changes a lot with the rows it's given. "Cross-validation and tuning": scoring a model on k folds.
Part 1. One tree wobbles
In "Decision trees" a deep tree kept splitting until its leaves were nearly pure, and a slightly different set of rows could grow a quite different tree. Each tree is part pattern and part accident of the rows it got. Used well, many trees let the accidents cancel out.
Take one customer: 4 months in, a $95 bill, two support tickets in the last 90 days, last login 20 days ago, no autopay. Say you grow ten deep trees, each on a different random sample of the same customer table, and ask each about her. Seven say she'll cancel and three say she'll stay. The vote, 0.7, is far steadier than any one tree.
Example 1.1
Averaging guesses that wobble
- one treespread 0.30
Say one tree's guess for a customer has a spread (standard deviation) of 0.30 across different training samples. That wobble is the variance from "Training, validation and test sets".
- 100 trees, all alike→spread 0.30
If all 100 trees made the same mistakes (correlation 1), averaging them would change nothing.
- 100 trees, correlation 0.5→spread 0.21
With trees half alike, the spread of the average is √(0.5 × 0.30² + 0.5 × 0.30² ÷ 100) = 0.21. The shared half of the mistakes never averages away.
- 100 trees, correlation 0.2→spread 0.14
Make the trees less alike and the average gets steadier. The rule: spread² of the average = correlation × spread² + (1 − correlation) × spread² ÷ number of trees.
Your turn
You already have 100 trees with correlation 0.5. What steadies their average more?
The first way to make trees differ is to train each on its own sample of rows. To get a sample as big as the table, draw rows at random with replacement: pick a row, put it back, pick again, 1,000 times for a table of 1,000 customers. Some customers come up twice or three times, and some never.
Bagging
Training many models, each on its own bootstrap sample of the rows (drawn at random with replacement, as many rows as the table has), and averaging their predictions. Short for bootstrap aggregating.
Your turn
You draw a bootstrap sample of 1,000 rows from a table of 1,000 customers. About how many different customers does it contain?
Bagging alone leaves the trees too alike. If one column is by far the most useful, say days since last login, nearly every tree splits on it first, and their mistakes line up. A random forest adds a second source of difference: each split may only choose among a random handful of columns. With nine columns, scikit-learn's forest classifier offers each split three, the square root of nine.
Random forest
Bagged decision trees in which each split may only use a random subset of the columns. The forest's prediction is the average of its trees' predictions (for classes, the average probability).
The left-out rows give you a free score. Each customer was left out of about 37% of the trees, so ask only those trees about her and compare with what happened. Do that for every row and you have a validation score without setting rows aside.
Out-of-bag score
A forest's score in which each row is predicted only by the trees that never trained on it. In scikit-learn, pass oob_score=True and read oob_score_ after fitting.
Part 2. Boosting: each tree fixes what's left
Keep going with Pro
You've done the first part. Pro opens the rest of this lesson, and every other one.
- Boosting: each tree fixes what's left
- Why they win on tables
- Settings that matter, and reading the result
Classical Machine Learning overviewSpotted a mistake? Tell us.