Chapter 8: Tree-based Models

class: center, middle, inverse, title-slide

.title[
# Chapter 8: <br>Tree-based Models
]
.author[
### Jeremy Selva
]

---

# Introduction

This chapter introduces tree-based methods for regression and classification

- Decision Trees
- Bagging
- Random Forest
- Boosting
- Bayesian Additive Regression Trees

---

# 8.1.1 Regression Trees

1. Divide the predictor space — that is, the set of possible values
for `$X_1,X_2, . . . ,X_p$` — into `$J$` distinct and .blue[**non-overlapping**] regions,
`$R_1,R_2, . . . ,R_J$` .

2. For every observation that falls into the region `$R_j$`, where `$1 \le j\le J$`, take the .blue[**mean**] of the response values for the training observations in `$R_j$`.

---

# 8.1.1 Regression Trees

The goal is to find boxes `$R_1, . . . ,R_J$` that .blue[**minimize**] the `$RSS$`, given by

`$$\mathrm{RSS}=\sum_{j=1}^{J}\sum_{i{\in}R_j}^{}(y_i - \hat{y}_{R_j})^2$$`

where `$\hat{y}_{R_j}$` is the .blue[**mean**] response for the training observations within the `$j$`th box.

Unfortunately, it is .red[**computationally infeasible**] to consider every
possible partition of the feature space into `$J$` boxes.

---

# 8.1.1 Regression Trees

One way is given all predictors `$X_1,X_2, . . . ,X_p$`, find the .blue[**best**] cut off point `$s$` for a given predictor `$X_k$`, where `$1 \le k\le p$` such that the resulting two regions

.center[
`$R_1(k,s)=\left\{X|X_k<s\right\}$` and `$R_2(k,s)=\left\{X|X_k{\ge}s\right\}$`
]

have the .blue[**least**] `$RSS$` for all predictors

`$$RSS=\sum_{i:x_i{\in}R_1(k,s)}(y_i-\hat{y}_{R_1})^2 +  \sum_{i:x_i{\in}R_2(k,s)}(y_i-\hat{y}_{R_2})^2$$`
where `$\hat{y}_{R_1}$` is the .blue[**mean**] response for the training observations in `$R_1(k,s)$`, and `$\hat{y}_{R_2}$` is the .blue[**mean**] response for the training observations in `$R_2(k,s)$`.

.blue[**Repeat**] the process until no region contains more than five observations.

---

# 8.1.1 Regression Trees

See https://bookdown.org/tpinto_home/Beyond-Additivity/regression-and-classification-trees.html for animation.

.center[![DecisionTree](DecisionTree.gif)]

---

# 8.1.1 Regression Trees

See [StatQuest with Josh Starmer](https://www.youtube.com/watch?v=g9c66TUylZ4) 22 min animation.

.center[
<iframe width="853" height="480" src="https://www.youtube.com/embed/g9c66TUylZ4" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>]

---

# 8.1.1 Regression Trees

However, the previous method may result in a tree that .red[**overfits**] the data.

A better strategy is to

1. grow a very large tree `$T_0$` as before 
2. tune `$\alpha$` in the cost complexity pruning formula to prune/penalise `$T_0$` to give .blue[**a sequence**] of sub trees `$T$`s. 
3. apply cross validation or validation set on those sub trees `$T$`s and pick `$\alpha$` that gives the .blue[**best sub tree**] (smallest `$RSS$`).

The cost complexity pruning formula is

`$$\sum_{m=1}^{|T|}\sum_{x_i{\in}R_m}(y_i-\hat{y}_{R_m})^2 + \alpha|T|$$`
where `$\alpha\ge0$`, `$|T|$` is the number of .blue[**terminal nodes**] the sub tree `$T$` holds. `$R_m$` is the .blue[**box/region**] corresponding to the `$m$`th terminal node and `$y_i-\hat{y}_{R_m}$` is the .blue[**mean**] response for the training observation in `$R_m$`

---

# 8.1.1 Regression Trees

`$$\sum_{m=1}^{|T|}\sum_{x_i{\in}R_m}(y_i-\hat{y}_{R_m})^2 + \alpha|T|$$`

When `$\alpha = 0$`, the sub tree `$=T_0$` as the cost complexity pruning formula equals to the `$RSS$`.

The cost complexity .red[**penalises**] complex trees with a lot of terminal nodes.

Similar to lasso, as `$\alpha$` increase, some terminal nodes will not be used.

---

# 8.1.1 Regression Trees

See [StatQuest with Josh Starmer](https://www.youtube.com/watch?v=D0efHEJsfHo) 16 min animation.

.center[
<iframe width="853" height="480" src="https://www.youtube.com/embed/D0efHEJsfHo" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>]

---

# 8.1.2 Classification Trees

In the case of classification, instead of taking the mean of a given region, we take the .blue[**most commonly occurring class**] (or mode) of training observations in the region to which it belongs.

For the measurement of error, instead of `$RSS$`, one way is to use the fraction of the training observations in that region that do not belong to the most common class.

`$$E = 1 - \max_k(\hat{p}_{mk})$$`
where `$\hat{p}_{mk}$` the .blue[**proportion of training observations**] in the `$m$`th region that are from the `$k$`th class. Hence, `$0\le\hat{p}_{mk}\le1$`

However, this error rate is unsuited for tree-based classification because `$E$` does not change much as the tree grows (.red[**lack sensitivity**]).

Instead, .green[**more sensitive**] classification error measurements like the Gini index or the entropy are used.

---

# 8.1.2 Classification Trees

The Gini index and the entropy are very similar measures, where .green[**small values**] indicate that the node contains .blue[**large number of observations from a single class**].

The Gini index is defined by

`$$G = \sum_{k=1}^{K}\hat{p}_{mk}(1-\hat{p}_{mk})$$`
The value varies between `$0$` and `$1$`,
where, `$0$` denotes that .blue[**all**] observations belong to a certain class, `$1$` denotes that the observations are .blue[**randomly**] distributed across various classes and
`$0.5$` denotes .blue[**equally**] distributed observations into some classes.

The entropy is defined by

`$$D = - \sum_{k=1}^{K}\hat{p}_{mk}\log(\hat{p}_{mk})$$`

Both Gini index and Entropy are .blue[**small**] when all of the `$\hat{p}_{mk}$`'s are close to .blue[**zero**] or .blue[**one**].

---

# 8.1.2 Classification Trees

See https://bookdown.org/tpinto_home/Beyond-Additivity/regression-and-classification-trees.html

---

# 8.1.3 Trees Versus Linear Models

In terms of prediction accuracy, ... it depends

---

# 8.1.3 Trees Versus Linear Models

Compared to linear models, decision trees are .green[**easier to explain**] to others because they mirror human decision-making. They can be displayed graphically and easily interpreted by non-experts.

However, it is .red[**less robust**] than the linear models. A small change in the data set can cause a large change to the decision tree. This may hurt the decision trees performance in prediction.

To improve its performance, methods like bagging, random forests, and boosting are used (sometimes at the cost of interpretability).

---

# 8.2.1 Bagging

Bagging is an approach that tries to “stabilise”(make it more robust to change of data) the predictions from trees

The idea is to generate `$B$` different .blue[**bootstrapped training datasets**] to create `$B$` different regression trees `$\hat{f}^{*b}$` respectively for `$1\le b \le B$`. Given a new observation to predict called `$x$`, we use the `$B$` regression trees to create `$B$` predictions. The final prediction value is calculated by .blue[**averaging**] all the predictions.

`$$\hat{f}_{bag}(x) = \frac{1}{B}\sum_{b=1}^B\hat{f}^{*b}(x)$$`

In the case of classification, we record the class predicted by each of the `$B$` trees, and take a .blue[**majority**] vote.

What is missing is how do we estimate the test error rate (without using the test data) to pick the best `$B$` value or number of bagged trees ?

---

# 8.2.1 Bagging

Each bagged tree is trained using .blue[**two-thirds**] of the training data. The other one-third of the training data, known as .blue[**out-of-bag**] or `$OOB$` observations are then used.

Given an `$OOB$` observation, we first predict its response .blue[**using only bagged trees**] that do not use this `$OOB$` observation in its training. An `$OOB$` prediction is made by averaging the predicted response (regression) or a majority vote (classification) among these specific bagged trees.

As each `$OOB$` observation has an `$OOB$` prediction and a true response, the `$OOB$` error can be computed via the overall `$OOB$` `$RSS$` (regression) or classification error like Gini index. The `$B$` value that gives the .blue[**least**] `$OOB$` error will be taken.

---

# 8.2.1 Bagging

.pull-left[
Bagging usually improves prediction accuracy at the expense of interpretability.

It is no longer clear which predictors are more important as we now have more than one tree (which may gives differing views on the importance of a given predictor).

An overall summary of the importance of each predictor can be achieved by recording how much the average `$RSS$` or Gini index .blue[**improves (or decreases)**] when each tree is splitted over a given predictor.
]

.pull-right[
<img src="img/figure_8_9.jpg" width="110%" style="display: block; margin: auto;" />
]

---

# 8.2.2 Random Forests

One problem with bagging is that each bagged tree may be .red[**highly similar**] to one another.

This happens if there is a strong predictor in the data set. By the greedy principle, most of the bagged trees will .red[**use this strong predictor**] in the top split, regardless of changes in the training set led by bootstrapping.

This may cause the tree model to be .red[**less robust**] to changes in the data over time.

To further improve the robustness of the model, a .blue[**change**] is made during the creation of a split in a given bagged tree on bootstrapped training samples.

Instead of using the full set of `$p$` predictors as split candidates, only .blue[**a random sample**] of `$m \approx \sqrt{p}$` predictors are used instead.

This reduces the odds of the strong predictor being selected during the split and provide other predictors a chance.

---

# 8.2.2 Random Forests

See [StatQuest with Josh Starmer](https://www.youtube.com/watch?v=J4Wdy0Wc_xQ) 10 min animation.

.center[
<iframe width="853" height="480" src="https://www.youtube.com/embed/J4Wdy0Wc_xQ" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>]

---

# 8.2.2 Random Forests

---

# 8.2.3 Boosting

Recall in bagging, each tree is built on a bootstrap training data set.

On the other hand, in boosting, each tree is built on information that the previous trees are unable to catch. That is, we fit a tree using .blue[**the current residuals**], rather than the response.

This is similar to the partial least square components in which each component is build based on the response's residual left by the model created from the previous partial least square components.

The key is to make each tree .blue[**small**] (with a few terminal nodes) but still "different" from one another.

For simplicity, only boosting regression trees are described in the book.

---

# 8.2.3 Boosting

.pull-left[
Boosting has three tuning parameters.

1. The .blue[**number of trees**] `$B$`

2. The maximum number of .blue[**splits/depth**] `$d$` each tree is allow to have. (to make each tree small)

3. A .blue[**shrinkage parameter or learning rate**] `$\lambda$` (to make each tree "different" from one another)
]

.pull-right[
<img src="img/algorithm_8_2.jpg" width="120%" style="display: block; margin: auto;" />
]

---

# 8.2.3 Boosting

See [StatQuest with Josh Starmer](https://www.youtube.com/watch?v=3CC4N4z3GJc) 16 min animation.

.center[
<iframe width="853" height="480" src="https://www.youtube.com/embed/3CC4N4z3GJc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>]

---

# 8.2.3 Boosting

---