\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

ML02.2 · Bagging and random forests

A free, illustrated module of 4 lessons and one interactive in ML02 Supervised Learning: Trees, Ensembles and Kernels: Why averaging helps; Bootstrap aggregating; Random forests: decorrelating the trees; Out-of-bag error and feature importance.

ML02.2 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of ML02 Supervised Learning: Trees, Ensembles and Kernels in the Machine Learning track.

A single deep tree is accurate on average but changes completely when the data change a little. Average many of them and most of that wobble cancels. These four lessons derive how much an average gains when its members are correlated, build bagging from bootstrap samples on the course’s twelve points and eight-point set, decorrelate the trees with random feature subsets to get a random forest, and read off an honest error estimate and feature importances from the points each tree never saw.

What you need first. Decision trees grown greedily with the Gini impurity (ML02.1), the bias and variance of a learning method (ML01.8), cross-validation (ML01.9), and the variance of a sum of correlated quantities (M06.10). The binomial distribution helps in the first lesson.

Lessons

1. Why averaging helps ML02.2.1 25 min

   Average B predictors and the variance of the average is rho sigma squared plus (1 - rho) sigma squared over B. Derive it, see why a shared error never averages away, and compute how often a majority vote of independent classifiers is right.

2. Bootstrap aggregating ML02.2.2 25 min

   Bagging grows a deep tree on each bootstrap sample of one data set and lets the trees vote or average. Derive why a bootstrap sample holds about 63.2 % of the points, bag trees by hand and in NumPy, and see why it helps trees but not a straight line.

3. Random forests: decorrelating the trees ML02.2.3 25 min

   Bagged trees stay alike because the same strong feature wins their top split. A random forest lets each split choose from a random subset of features, which makes the trees disagree. Measure the effect on load_breast_cancer and see why adding trees never overfits.

4. Out-of-bag error and feature importance ML02.2.4 25 min

   Every point is left out of about 37 % of the bootstrap samples, so the trees that never saw it give an honest prediction for it. Compute the out-of-bag error by hand and from scratch, then measure feature importance by impurity and by permutation, and see why the first can mislead.

The interactive

ML02.2-X1 · Vote grid. Grow up to fifty deep trees, each on its own bootstrap sample, and watch the plane shade by the share of trees voting for each class. Turn feature subsampling on, show one tree with its sample, and read the training and out-of-bag errors of the vote. It lives in Bootstrap aggregating.