Random Forests

Today

  • Data
  • Bagging
    • Unstable trees
    • Averaging
    • Bootstrap samples
    • Bagged trees
  • Out-of-bag error
    • Out-of-bag prediction
    • Out-of-bag and test error
  • Random forests
    • Definition
    • Correlated trees
    • Split restriction
    • Fitting a random forest
    • Forest size
    • Choosing \(m\)
  • Variable importance
    • Two measures
    • Interpretation
  • Comparison
    • Test error
    • Extrapolation
    • Interpretability and cost

Data

Concrete specimens

  • Response: compressive_strength
  • Explanatory variables:
    • cement
    • blast_furnace_slag
    • fly_ash
    • water
    • superplasticizer
    • coarse_aggregate
    • fine_aggregate
    • age
  • Training specimens: 700
  • Test specimens: 305

Bagging

Unstable trees

Averaging

\[ \begin{aligned} Var\left[\frac{1}{B}\sum_{b=1}^B \widehat f_b(x)\right] &= \frac{1}{B^2}\left\{\sum_{b=1}^B Var\left[\widehat f_b(x)\right] + \sum_{b \ne b'} Cov\left[\widehat f_b(x), \widehat f_{b'}(x)\right]\right\} \\ &= \frac{B\sigma^2 + B\left(B - 1\right)\rho\sigma^2}{B^2} = \rho\sigma^2 + \frac{1 - \rho}{B}\sigma^2. \end{aligned} \]

  • \(B\) — number of predictions averaged, \(b = 1, \ldots, B\)
  • \(\sigma^2\) — variance of one prediction at \(x\)
  • \(\rho\) — correlation between two of them

Bootstrap samples

  • Bootstrap sample
    • \(n\) training observations
    • \(n\) draws
    • with replacement
  • Probability that a given observation is missed by all \(n\) draws

    \[\left(1 - \frac{1}{n}\right)^n \to e^{-1} \approx 0.368\]

Appearances in a bootstrap sample

Bagged trees

\[\widehat f_{\text{bag}}(x) = \frac{1}{B}\sum_{b=1}^B \widehat f^{*b}(x),\]

  • \(\widehat f^{*b}(x)\) — prediction at \(x\) of the tree fit to bootstrap sample \(b\)
  • \(\widehat f_{\text{bag}}(x)\) — bagged prediction
  • Trees grown full, not pruned

Bagging from scratch

# Bagging from scratch: B full trees, each fit to a bootstrap sample.
B <- 300
grow <- rpart.control(cp = 0, minsplit = 2, minbucket = 1, xval = 0)
boots <- map(seq_len(B), \(b) sample(n_train, replace = TRUE))
trees <- map(boots, \(boot) {
  rpart(compressive_strength ~ ., data = train[boot, ], control = grow)
})
tree_pred <- sapply(trees, predict, newdata = test)
c(test_mse = mean((y_test - rowMeans(tree_pred))^2))
test_mse 
26.76253 

Bagged trees: test MSE

Out-of-bag error

Out-of-bag prediction

\[\text{MSE}_{\text{OOB}} = \frac{1}{n}\sum_{i=1}^n \left(y_i - \widehat f_{\text{OOB}}(x_i)\right)^2,\]

\[\widehat f_{\text{OOB}}(x_i) = \frac{1}{\left|\mathcal{O}_i\right|}\sum_{b \in \mathcal{O}_i} \widehat f^{*b}(x_i),\]

  • \(\mathcal{O}_i\) — bootstrap samples that leave out observation \(i\); \(\left|\mathcal{O}_i\right|\) — their number
  • \(\widehat f_{\text{OOB}}(x_i)\) — OOB prediction of observation \(i\)

Out-of-bag prediction in R

# Each tree's predictions for the training specimens; each specimen's OOB
# prediction averages the trees that left it out.
train_pred <- sapply(trees, predict, newdata = train)
oob_pred <- rowSums(train_pred * out_of_bag) / rowSums(out_of_bag)
c(oob_mse = mean((y_train - oob_pred)^2))
 oob_mse 
27.03195 

Out-of-bag and test error

Random forests

Definition

  • Bootstrap samples: each tree is fit to its own bootstrap sample of the training data
  • Averaging: the forest predicts with the average of its trees’ predictions
  • Random variable inclusion: at each split, the tree chooses among only a random subset of the explanatory variables
  • Bagged trees have the first two; the third is the change a random forest makes

Correlated trees

Split restriction

  • At each split, a tree may use only \(m\) of the \(p\) explanatory variables, chosen at random anew for that split
    • \(p\) — number of explanatory variables
    • \(m \le p\) — number tried at each split
  • \(m = p\) is bagging
  • Default randomForest(): \(m = \lfloor p/3 \rfloor\) for a numeric response

Split restriction: correlation

Method \(m\) \(\widehat\sigma^2\) \(\widehat\rho\) \(\widehat\rho\widehat\sigma^2\)
Bagging 8 62 0.09 5.8
Random forest 2 105 0.04 4.4
  • \(\widehat\sigma^2\) and \(\widehat\rho\widehat\sigma^2\): averages over the 305 test specimens of values at one \(x\)
  • Restriction: lower \(\widehat\rho\), higher \(\widehat\sigma^2\)

Fitting a random forest

# A random forest with the default m and number of trees, and its test MSE.
rf_fit <- randomForest(compressive_strength ~ ., data = train,
                       importance = TRUE)
rf_fit
c(test_mse = mean((y_test - predict(rf_fit, test))^2))

Call:
 randomForest(formula = compressive_strength ~ ., data = train,      importance = TRUE) 
               Type of random forest: regression
                     Number of trees: 500
No. of variables tried at each split: 2

          Mean of squared residuals: 32.1988
                    % Var explained: 88.07
test_mse 
34.24721 

Forest size

Choosing \(m\)

Variable importance

One tree

# The default tree on all eight explanatory variables, and the number of
# its splits on each variable.
one_tree <- rpart(compressive_strength ~ ., data = train)
split_vars <- as.character(one_tree$frame$var)
table(split_vars[split_vars != "<leaf>"])

               age blast_furnace_slag             cement              water 
                 5                  2                  4                  3 

Two measures

  • Decrease in RSS (IncNodePurity)
    • total decrease from the splits on the variable in a tree, averaged over the trees
  • Permutation importance (%IncMSE)
    • increase in a tree’s OOB MSE when the variable is shuffled among its OOB observations, averaged over the trees

Two measures in R

# Both importance measures, the permutation increase in MPa squared.
importance(rf_fit, scale = FALSE)
                     %IncMSE IncNodePurity
cement             128.80824     38055.659
blast_furnace_slag  40.40708     10765.080
fly_ash             30.74548      9337.777
water               95.72834     22962.469
superplasticizer    68.02636     15163.163
coarse_aggregate    32.06984     13284.344
fine_aggregate      44.18691     14802.340
age                164.19623     54983.954

Importance by variable

Interpretation

  • Importance ranks the variables
  • No direction
  • No effect size

Comparison

Test error

Method Test MSE
Least squares, main effects 106.4
Least squares, main effects, log(age) 48.5
Default tree 86.8
Pruned tree 42.2
Full tree 40.3
Bagging, rpart() loop 26.8
Bagging, randomForest() 27.1
Random forest, m = 2 34.2
Random forest, m = 5 26.7
  • Least squares: no interactions or polynomial terms

Extrapolation

Interpretability and cost

  • Gives up the single tree’s interpretability: importance rankings only
  • Hundreds of trees to store and evaluate
  • Predictions still made of steps

Conclusion

  • Averaging removes variance, but not \(\rho\sigma^2\)
  • Bagging averages full trees; more trees do not overfit
  • Out-of-bag error estimates test error
  • A random forest decorrelates trees; choose \(m\) by out-of-bag error
  • Importance ranks variables, with no direction or effect size
  • Forests lose interpretability and cannot extrapolate