Trees and random forests

Questions in a row, and many trees

A decision tree asks a chain of yes-or-no questions about the features, such as whether momentum is above a value, and ends in a leaf that predicts the average (or the majority class) of the training rows that reached it. It picks each question greedily: of all features and cut points, it takes the one that makes the two child groups purest. For classes, purity is measured by the Gini impurity $1-\sum p_k^{2}$, which is $0$ for a pure group. The gain of a split is the parent impurity minus the size-weighted impurity of the children. A tree can fit anything, so a deep tree memorises the noise in the training rows.

A random forest averages many trees. Each tree is grown on a bootstrap sample of the rows and, at each split, looks at only a random subset of the features, so the trees differ. If $B$ trees each have variance $\sigma^{2}$ and pairwise correlation $\rho$, their average has variance $\rho\sigma^{2}+(1-\rho)\sigma^{2}/B$: averaging kills the part that is independent between trees and keeps only the shared part. A forest therefore overfits less than one deep tree, but it still fits noise when the true signal is weak, as in returns. Always judge it on later data.

• Greedy purity: each split is the one that lowers impurity the most right now.
• Averaging cuts variance: a forest has the shared part $\rho\sigma^{2}$ left, however many trees you add.
• Flexible models overfit weak signals: in-sample skill can be real and out-of-sample skill zero.

Lab · what's graded

• Impurity of a node10 pts
• Impurity of a child10 pts
• The weighted impurity15 pts
• The gain of the split15 pts
• The variance of a forest15 pts
• Why averaging trees helps10 pts
• Match the vocabulary10 pts
• Good in sample, poor later15 pts