Decision trees and boosting: twenty questions, then many small fixes

A doctor's checklist, a bank's loan rules, the game of twenty questions: each asks one simple question, then picks the next question based on the answer. A decision tree learns such a checklist from data, and anyone can read the result.

One tree is easy to understand but easy to fool. Add up hundreds of tiny trees, each fixing the mistakes of the ones before, and you get gradient boosting, the method that wins most competitions on tabular data.

split

A yes/no question about one feature, like $x \lt 0.4$. It cuts a region of the plane into two boxes.

Gini impurity

$1 - \sum_c p_c^2$ for the class shares $p_c$ in a region: 0 when it is pure, ½ for an even two-class mix.

leaf

A region that isn't split any further. It predicts its majority class.

residual

In boosting, what the model still gets wrong: $y - F(x)$.

stump

A tree with a single split: a step, with one value on each side.

The tree is grown greedily. For a region it tries every threshold on each axis, scores each split by the Gini impurity of the two halves (weighted by their sizes), and keeps the lowest. A single question can't separate XOR, since every cut leaves both classes on both sides, but two levels of questions can: this tree gets 95% of the points right at depth 2.

Deeper isn't always better, though:

Boosting starts from a flat guess, the mean of $y$. Each round it looks at the residuals, fits one stump to them, and adds $\eta$ times that stump to the model:

Each stump is weak, just one step, but together they build a staircase that follows the curve. Because each one is fitted to the current errors, the training error can only fall.

Use the slider to change the maximum depth, and the buttons to change the data:

• Moons or circles at depth 1, 3 and 5: training accuracy climbs, but the boundary turns into a staircase of tiny boxes.
• Overlapping classes: deeper trees chase individual points into their own leaves.

For boosting, compare Small learning rate (η = 0.2) with Learning rate 1: the small rate falls more slowly but each stump changes the model gently; the full rate fixes big errors fast, then starts chasing noisy points.

• A decision tree asks one question about one feature at a time; each split is the one with the lowest weighted Gini.
• Deep trees fit their training data perfectly and overfit; limit depth and judge on new data.
• Gradient boosting adds shrunk stumps fitted to the residuals, so the training error only falls.
• Small learning rates with more rounds are the usual recipe.