Random Forest

Definition

A spatial decision tree splits cells recursively along axis-parallel directions (the split with the smallest error, for example the sum of squared deviations from the cell means) until a leaf size is reached; it predicts the cell mean or majority. A random forest averages $B$ such trees, each grown on a random subsample, where every split chooses the best among $m\approx d/3$ random dimensions.

Formula

A single tree is consistent if $\mathrm{diam}(\text{cell})\to 0$ and $\#\text{points per cell}\to \infty$.

• Deep trees ($n_{min}=1$) overfit individually, but a forest of them can still be consistent (Scornet 2016); shallow trees use $n_{leaf}\approx \log n$.
• The randomness decorrelates the trees, which lowers $\rho$ in the bagging variance.
• Results assume data-independent partitions only for simple estimators; forests need other techniques. Comparison-based forests work without coordinates.

Appears in

• Lecture 6, bagging decision trees
• Lecture 6, spatial decision trees
• Lecture 6, algorithm and parameters
• Lecture 6, consistency
• Lecture 6, forests vs. boosted trees
• Lecture 3, partitioning estimators with fixed cells

Related concepts

• Bagging
• Consistency