Data 311: Machine Learning

Lecture 14: Bootstrap Aggregating (Bagging) and Random Forests

Dr. Irene Vrbik

University of British Columbia Okanagan

Introduction

• We’ve just wrapped up some discussion on decisions trees, or CARTs which suggests that they are not particularly “good” models in many scenarios.

• Why? Bushy trees tend to have high variance and pruned trees have high bias

• Bagging is a procedure for reducing the variance of a statistical learning method but as with all model improvements, we will have to accept some drawbacks…

• Cons: don’t do very well in prediction: why?bushy tree had high variance pruned trees have high bias
• Pros: Easy to interpret

Preface

Trees have one aspect that prevents them from being ideal tool for predictive learning, namely inaccuracy. - ESL

Today we’ll be looking at some ensemble methods to make them more competitve

“Two heads are better than one only if they contain different opinions” - Kenneth Kaye (January 24, 1946 – May 26, 2021[1]) was an American psychologist and writer whose research, books, and articles connect the fields of human development, family relationships and conflict resolution.

• Trees are easy to build, easy to use, and easy to interpret.

We’ll look at some ensemble methods to make them more competitve

This lecture correspondes to ISLR Chapter 8.2.1, 8.2.2, 8.2.3. More details can see: Random Forests with R by Robin Genuer, Jean-Michel Poggi (2020)

Ensemble Methods

• Ensemble methods are machine learning techniques that combine the predictions of multiple models to improve overall predictive performance.

• They can be divided in two groups:

  • Parallel learners, e.g. Random Forests and Bagging
  • Sequential learnins, e.g. Boosting (topic of next lecture)

Today we’ll focus on parallel learners …

The idea behind ensemble methods is that by combining the strengths of different models, the ensemble can often outperform individual models and provide more accurate and robust predictions. Some common ensemble methods include:

Bagging

• Bagging (or bootstrap-aggregating) can be thought of as applying the bootstrap to an entire model-fitting process, rather than just to estimate standard errors of estimators.

• By generating \(B\) bootstrapped samples, we can train \(B\) models, \(\hat f^{*b}\) for \(b = 1, \dots B\), and average their predictions \[\begin{equation} \hat f_{bag}(x) = \frac{\sum_{b=1}^B f^{*b}(x^*_b)}{B} \end{equation}\]

• Bagging method introduced by Breiman (1996)
• Recall a bootstrap sample is a sample of size n with replacement
• instead of just using the bootstrap models to estimate SE, we use them in our predictions (average each one to obtain one prediction)
• averaging a set of observations reduces variance: why? think of iid \(Xi\)s; \(\overline X\) will have less variance (\(\sigma^2/n\)) than \(X_i\) (\(\sigma^2\)).
• for each bootstrap sample we build a tree, and find \(\hat f^{*b}\) we average those values (or majority vote for classification)

Bye bye pruning

• These trees for each bootstrap sample are grown deep (i.e. “bushy”), and are not pruned.

• Consequently, each individual tree will have high variance, but low bias

• Averaging these \(B\) trees reduces the variance thus improving predictions and stability.

• Why? Think of independent observations \(X_1, …, X_n\) having variance \(\sigma^2\); Central Limit Theorem tells us that their average value, i.e. \(\overline{X}\) will have variance \(\frac{\sigma^2}{n} (<\sigma^2\))$

• there is no need for pruning anymore cuz averaging will take care of that for us
• we use an average of trees to improve their prediction error
• 2 heads are better than one…

Comments

• Bagging is considered an ensemble method since it combines many simple models (“weak” learners) in order to obtain a single and potentially very powerful model.

• The textbook suggests \(B=100\) as generally sufficient, but probably 500 to 1000 is safer (500 is the default).

• While bagging can improve predictions for many regression methods, it is particularly useful for decision trees.

• For classification trees, we take a majority vote, i.e. the most commonly occurring prediction.

• simple models are the “building block”
• no harm in using more since we can’t overfit

General Idea

The main idea is to pool a collection of random decision trees

Source

1. Create B Bootstrap samples (sample with replacement of size \(n\))
2. Fit a (bushy) tree to each one
3. Each decision tree is used to make predictions
4. Aggregate the predictions (for regression the individual tree predictions are typically averaged, for classification we use a majority vote).

KEY: Using a bootstrap sample and considering only a subset of variables at each step results in a wide variety of trees. The variety is what makes random forests more effective than individual decision trees

Steps for Bagging

1. Create \(B\) bootstrap samples¹
2. Fit a (bushy) tree to each bootstrap sample
3. Each decision tree is used to make a prediction.
4. Aggregate the \(B\) predictions:
   • for regression predictions are typically averaged
   • for classification we use a majority vote.

1. a random sample of size \(n\) taken with replacement from a given dataset

Model Assessment

We could get an estimate of error using the validation approach, however, we can get a different estimate “for free”

• Recall: a bootstrap sample consists of sampling \(n\) observations¹ with replacement from our dataset

• As we are sampling with replacement, some observations are randomly left out while others are duplicated.

• It can be shown that for each bootstrap sample, on average roughly² \(\frac{1}{3}\) of the observations will not appear …

How do we know if our model is any good?

• We could get an estimate of error using the validation approach or CV, however, will help us estimate error

1. where \(n\) is equal to the number of observations in your original data set

2. For example when \(n\) = 100 = 0.366; when \(n\) = 25 = 0.360 (see eq. on next slide)

Probability calculations

\[\begin{align} P(x_i &\text{ is not selected}) =\left(1 - \frac{1}{n}\right)^n \\ & = P(x_i \text{ is not selected on first draw}) \times \dots\\ &\quad \dots \times P(x_i \text{ is not selected on $n^{th}$ draw}) \\ &= \left(\frac{n-1}{n}\right)\times \dots \times \left(\frac{n-1}{n}\right)\\ &= \lim_{n \to -\infty} \left(1 - \frac{1}{n}\right)^n = \frac{1}{e} \end{align}\] where \(e\) is the exponential constant approximately 2.718.

Bootstrap Visualization

Image source: rasbt.github

The figure above illustrates how three random bootstrap samples drawn from an ten-sample dataset \((x_1,x_2,...,x_{10})\) and their ‘out-of-bag’ sample for testing may look like.

• In the first bootstrap sample, \(x_3, x_7, x_{10}\) are not selected
• In the second bootstrap sample, \(x_6, x_9\) are not selected
• In the third bootstrap sample, \(x_3, x_7, x_8, x_{10}\) are not selected

Recall 5-fold CV Visualization

Similarities - training and testing/validation sets Differences - in CV fold training set \(<n\) (\(= n - n/k\)) whereas bootstrap training set is size \(n\) - in CV each observation appears exactly one in the validation sets whereas in bootstrap, the can appear in multiple validation sets - in bootstrap the same observation may appear multiple times in a given trainging set

Out of Bag (OOB)

• Observations left out of a model fit are called out of bag or OOB observations.

• These OOB observations are being “hidden” from the model fitting process in the same way our validation set was in CV

• For bagging, the “OOB validation/test set” will contain roughly two thirds of the observations and the training set will contain n observations¹

• It turns out that we can use these CV-like validation sets to produce CV-like test errors of a bagged model!

• OOB can think as out of the Bootstrap
• our training set for cv will be the other 2/3 (0.666*n)
• Consequently, we can estimate things like test error “for free”.
• This leads us to an interesting option for bootstrap-aggregated models…

1. composed of the other \(\approx\) 2/3 observations (some appearing more than once)

OOB Estimation

• We predict the response for the \(i\)th observation using each of the trees in which \(i\) was left out

• This will yield approximately \(B/3\) predictions for the \(i\)th observation, which we average.

• The respective OOB error estimates¹ for regression and classification, are: \[\begin{align} \text{RSS} & = \sum_{i=1}^n (y_i - \hat y_i)^2 & &\frac{1}{n} \sum_{i=1}^n I(y_i \neq \hat y_i ) \end{align}\]

• bagging is fairly robust to overfitting (since it is already averaging across many varied model fits)
• alternatively we can use MSE but RSS is easier to access sometimes
• We can measure how accurate our RF is for a classification as the proportion of out-of-bag samples that were correctly

1. akin to the LOO cross-validation error for bagging, if \(B\) is large.

So if we wanted to predict the response for \(x_3\) we would use the trees fitted to Bootstrap sample 1 and Boostrap sample 3 and average the result.

Example: Beer

Recall the beer data from last lecture (names removed):

69 observations and 7 columns

Example: Beer OLS Regression

OLS Regression:

beerdat <- beerdat[,-1] 
attach(beerdat)
# linear model
beerlm <- lm(price~., data=beerdat)

Regression tree

library(tree);  par(mar=c(0,0,0,0))
beert <- tree(price~., data = beerdat) 
plot(beert)
text(beert, digits=4)

for a means of comparison we’ll fit a Ordinarly Least squares regression model…

• First rule: BITTER, Second rule: BITTER, Third rule: BITTER
• we see bitter, qlty, bitter, cal, malty but we don’t see alcohol
• notably bitter seems to be a pretty important predictor

Cross-validation Errors

Let’s calculate the CV RSS error for OLS Regression:

library(DAAG)
beercv<-cv.lm(data=beerdat, beerlm, m=10,printit=FALSE)

sum((beercv$price-beercv$cvpred)^2) # 10-fold CV RSS for lm

[1] 57.33652

and the (actual) CV RSS error estimate for Regression Trees…

library(tree); set.seed(456); 
cv.beert <- cv.tree(beert); 
#10-fold CV RSS for 6 terminal tree
min(cv.beert$dev) 

[1] 77.56593

• so the linear model is a better model
• now lets get the OOB estimate

Bagging Regression Tree

library(randomForest); set.seed(134891)
p = 5 # number of predictors
(beerbag <- randomForest(price~., data=beerdat, ntree=500, mtry = p)) 

...
               Type of random forest: regression
                     Number of trees: 500
No. of variables tried at each split: 5

          Mean of squared residuals: 0.9338468
                    % Var explained: 54.71
...

MSE = RSS/n \(\implies\) RSS = MSE \(\times\) \(n\) = 0.93 \(\times\) 69 = 64.44.

Bagging has an improvement over the single tree (CV RSS of 77.57), but not over OLS regression (CV RSS of 57.34)!

• ntree = 500 is the default
• mtry = p, the number of predictors
• foreshadow: random forest is to come
• %var explained (like a \(R^2\))

Error Comments

• It’s worth noting that comparison we just made…

• Technically, we have not performed cross validation on our bagged trees, and yet we are comparing the (OOB) error to properly cross-validated errors for LM and CART

• OOB estimation is a similar (and more efficient) way for providing realistic long term error estimates

• Takeaway: For practical purposes, OOB error from bagged models can be compared to CV error from other models.

Variable Importance

• We can obtain an overall summary of the importance of each predictor if requested using:

beer2 <- randomForest(price~., data=beerdat, ntree=500, 
      mtry = 5, importance = TRUE)

• Two measures are provided for variable “importance”¹.

• The plot and values are produced using the following:

varImpPlot(beer2)   # plot
importance(beer2)   # values (not shown in slides)

1. they may not completely agree

Bagging Variable Importance Plots

Jump to RF varImpPlot

• as expected, bitter is imporant, and alcohol content is not important
• note there is a difference in ordering between cal and qlty

%IncMSE

1. Calculate the OOB MSE for the full set of \(B\) trees in your random forest, say, \(\text{MSE}_{full}\)

2. For the variable in question, randomly shuffle the observations (leave the order correct for the other columns).

3. Carry out predictions, calculate \(\text{MSE}_{shuff}\) then check the change from the full version for the variable in question: \[\begin{align} \text{%IncMSE} = \frac{\text{MSE}_{{shuff}}-\text{MSE}_{full}}{\text{MSE}_{full}} \end{align}\]

Higher values indicates that the variable is more important

• when I shuffle on that predictor, does it increase my MSE?
• If a predictors is not imporant (eg alcohol) shuffling it shouldn’t make a huge difference in MSE, so in the numerator you get something close to 0.
• If the variable is very important
• a useless predictor will have very little effect on the end predictions so if we shuffle that column the MSE shouldn’t change much
• can extend to misclassication %IncMSE is simply the average increase in squared residuals of the test set when variables are randomly permuted (little importance = little change in model when variable is removed or added)

IncNodePurity

• IncNodePurity is the total increase in node purity obtained from splitting on the variable, averaged over all trees in the forest.

• In other words, IncNodePurity is the increase in homogeneity in the data partitions.

• For regression, it is measured by residual sum of squares.

• A higher increase of node purity indicates that the variable is more important.

N.B. For classification, MeanDecreaseAccuracy and MeanDecreaseGini are used in place of %IncMSE and IncNodePurity.

• the documentation isn’t great for these measures so i wouldn’t get so bogged down in the details on how they are calculated
• takeaway is that bigger is better

Prediction vs Inference Tradeoff

Cons

• We no longer have one model, but an average of many models!
• Bagging loses the interpretability of our model
  
• It is comparatively slower than fitting a single tree

Pros

• We get an OOB error estimate “for free”
• improves prediction over using a single tree
• Variable importance
• Averaging prevents overfiting

• no more flowchart, more like a black box
• varaible importance - A large value indicates an important predictor
• Bagging improves prediction accuracy at the expense of interpretability.

Random forests

• Bagging has a close relationship with random forests (RF)

• Like bagging, RF build a number of trees on bootstrapped training samples; however, each time a split in a tree is considered, a random sample of \(m\) predictors (where \(m < p\) = the total number of predictors) is considered.

• Typically we choose \(m = \sqrt{p}\) and obtain a new sample of \(m\) predictors at each split.

• get it? “forests” have many trees
• “random” because a random sample of \(m\) predictors are considered at each split
• (introduced by Leo Breiman in 2001 [paper])
• During tree growth for all \(B\) samples, at each split a number of the predictors is randomly removed from consideration
• In other words, in building a random forest, at each split in the tree, the algorithm is not even allowed to consider a majority of the available predictors.

Motivating example

• Suppose that there is one very strong predictor in the data set (eg. bitter in the beer example)

• In the collection of bagged trees, most or all of the trees will likely use this strong predictor in the top split, hence, all of the bagged trees will look quite similar to each other.

• As discussed in our CV lecture, averaging highly correlated models does not lead to as large of a reduction in variance as averaging many uncorrelated quantities.

• decorelates the trees: Tropical forests rather than tundra biome
• During tree growth for all \(B\) samples, at each split a number of the predictors is randomly removed from consideration
• “The general idea of this method is that the random perturbation on individuals, brought by bootstrap sample draws, is not sufficient to promote diversity among trees and that it is also necessary to perturb the construction of trees at the variable level.” (RF with R book)

Why it works

• Random forests provide an improvement over bagged trees by way of a small tweak that decorrelates the trees.

• This decreases the dependency (or correlation) across the \(B\) trees, decreasing the variance of the averaged model (think back to LOOCV) and therefore increasing stability.

• As with bagging, we still loose interpretability over simple trees, but still gain the variable importance measure.

• Bagging is a special case of random forests when \(m = p\)

• LOOCV has higher variance than k-fold because there’s a lot of correlational among the model fits
• random forest makes a more diverse ecosystem
• “Since individual trees are randomly perturbed, the forest benefits from a more extensive exploration of the space of all possible tree predictors, which, in practice, results in better predictive performance”. (random forests with r book)
• small m will typically be helpful when we have a large number of correlated predictors.

Steps for RF

1. Create \(B\) bootstrap samples

2. Fit a tree* to each bootstrap sample,

   * when creating nodes in each decision tree, only a random subset of features is considered for splitting at each node.

3. Each decision tree is used to make a prediction.

4. Aggregate the \(B\) predictions.

*helps to decorrelate the trees

R function

We use the randomForest function from the randomForest package to implement bagging and RF. Usage:

randomForest(formula, data=NULL, ntree=500, mtry, importance=FALSE)

• ntree: the number of trees to grow (default = 500)
• mtry: the number of variables randomly selected at each node (default in classification is \(\sqrt{p}\) and \(p/3\) in regression; where \(p\) is the number of predictors).
• importance Should importance of predictors be assessed?

• ntree should not be set to too small a number, to ensure that every input row gets predicted at least a few times.

Optimizing the RF

• How do we determine how many subsets of features to consider at each split?

• mtry is a hyperparameter of our model and it’s choice can significantly impact the performance of our random forest.

• In practice the default values are reasonable starting point and often works well in practice.

• Alternatively you could use cross-validation to choose; e.g. build a random forest with mtry = \(\sqrt{p}-5\), \(\sqrt{p}\), \(\sqrt{p}+5\) and select the RF with highest accuracy

Random Forest on beer

mtry = \(\sqrt{p}\) by default¹

(beerRF <- randomForest(price~., mtry = sqrt(5), # default
            data=beerdat, importance=TRUE))

...
               Type of random forest: regression
                     Number of trees: 500
No. of variables tried at each split: 2

          Mean of squared residuals: 0.8469584
                    % Var explained: 58.93
...

OOB estimate or RSS = MSE\(\times n\) = 0.847 * 69 = 58.44

\(\sqrt{5} = 2.236068\)

1. actually its floor(sqrt(p)) (which rounds down to the nearest integer).

Comparison

Rank	Method	RSS estimate
1	OLS	57.34
2	RF	58.44
3	Bagging	64.44
4	Single Tree	77.57

For the beer data set, RF does better than single tree and bagging; however, it does still not outperform OLS!

general simple Tree < Bagged tree < RF

RF Variable Importance Plot

Jump to Bagging varImpPlot

• notice how the ordering is not the same
• same pros and cons as bagging however RF is improved version of bagging

Classification Example

• The smaller (more common) Italian red wine data set

• 178 samples of wine from three varietals (Barolo, Barbera, Grignolino) grown in the Piedmont region of Italy.

• 13 chemical measurements, i.e. \(p=13\)

• Let’s compare a single classification tree to a tree found using bagging and random forests …

Single Decision Tree

winetree <- tree(factor(Class)~., data=wine)
plot(winetree); text(winetree)

• splits that are non-sense (same class predictions with splits)
• by-product of growing trees with Gini

Cost-complexity pruning

Pruned Classification Tree

Cross-validation error estimate

• Obtain the test error (in this case misclassificaiton rate) that was found by cross-validation at the minimum value of \(\alpha\):

n <- nrow(wine)
min.idx <- which.min(winetreecv$dev)
# Misclassification rate
(mscr <- winetreecv$dev[min.idx]/n)

[1] 0.08426966

15/178 \(\implies\) 8.43% misclassifications in the long-run.

• pretty good for such a simple model!
• k-means only misclassifies 6 of the 178 wines 3.37%
• whereas HC misclassifies 29 of them 16.29%

Single pruned tree results

not bad but can bagging improve it?

Bagging wine

library(randomForest); set.seed(41351); 
winebag <- randomForest(factor(Class)~., mtry=13, 
                        data=wine, importance=TRUE)

• Here we are saying we want to do bagging mtry = \(m = p\)

• The importance argument tells the aglorithm that we want it to compute variable importance.

Note that now, we don’t have a single tree which we can plot.

Bagging Results

winebag

Call:
 randomForest(formula = factor(Class) ~ ., data = wine, mtry = 13,      importance = TRUE) 
               Type of random forest: classification
                     Number of trees: 500
No. of variables tried at each split: 13

        OOB estimate of  error rate: 3.37%
Confusion matrix:
   1  2  3 class.error
1 57  2  0  0.03389831
2  1 68  2  0.04225352
3  0  1 47  0.02083333

The OOB error rate of 3.37% versus 8.427% for a standard tree

• 2/(57+2) = 0.0338983
• (1+2)/( 1 +68 +2) 0.0422535
• 1/(47+1) 0.0208333

• this is an OOB confusion matrix (majority vote)

Bagging varImpPlot wine

Jump to RF varImpPlot

Random Forests

# use default: mtry = floor(sqrt(p)) = floor(sqrt(13)) = floor(3.605551)
(wineRF <- randomForest(factor(Class)~.,  # ntree = 500,
              data=wine, importance=TRUE))

...
                     Number of trees: 500
No. of variables tried at each split: 3
        OOB estimate of  error rate: 1.12%
Confusion matrix:
   1  2  3 class.error
1 59  0  0  0.00000000
2  1 69  1  0.02816901
3  0  0 48  0.00000000
...

\(\quad\) Simple Tree (8.43%) < Bagging (3.37%) < RF (1.12%)

sqrt(13) = 3.605551

RF varImpPlot wine

Jump to bagging varImpPlot