8. Tree-based Methods

Table of Contents

The Basics of Decision Trees

Regression Trees

Overview

• There are two main steps:
  • Partition predictor space $\mathbb{R}^p$ into regions $R_1, \dots, R_M$.
  • For all $X = (X_1, \dots, X_p) \in R_m$, predict the average over the responses in $R_m$ $\hat{f}(X) = \hat{y}_{R_m} := \frac{1}{N_m}\sum_{i: y_i\in R_m} y_i$ where $N_m = |\{y_i\ |\ y_i \in R_m\}|$
• In practice, we take the regions of the partition to be rectangular for simplicity and ease of interpretation.
• We choose the partition to minimize the RSS $\sum_{m = 1}^M \sum_{i: y_i \in R_m} (y_i - \hat{y}_{R_m})^2$
• We search the space of partitions using a recursive binary splitting¹ strategy.

Algorithm: Recursive Binary Decision Tree for Linear Regression

1. Start with top node $\mathbb{R}^p$
2. While a stopping criterion is unsatisfied:
   1. Let

   $(\hat{i}, \hat{j}) = \underset{(i, j)}{\text{argmin}}\left( \sum_{i: x_i\in R_1} (y_i - \hat{y}_{R_1})^ 2 + \sum_{i: x_i\in R_2} (y_i - \hat{y}_{R_2})^ 2\right)$ where

   $R_{1} = \{X| X_j < x_{i,j}\}$ $R_{2} = \{X| X_j \geqslant x_{i,j}\}$

   1. Add nodes

      $\hat{R}_{1} = \{X| X_{\hat{j}} < x_{\hat{i},\hat{j}}\}$ $\hat{R}_{2} = \{X| X_{\hat{j}} \geqslant x_{\hat{i},\hat{j}}\}$

      to the partition, and recurse on one of the nodes

Tree-pruning

• Complex trees can overfit, but simpler trees may avoid it ²
• To get a simpler tree, we can grow a large tree $T_0$ and prune it to obtain a subtree.
• Cost complexity or weakest link pruning is a method for finding an optimal subtree ³. For $\alpha > 0$, we obtain a subtree $T_\alpha = \underset{T\ \subset T_0}{\text{argmin}} \left(\sum_{m=1}^{|T|} \sum_{i: x_i \in R_m} \left(y_i - \hat{y}_{R_m}\right)^2 + \alpha|T|\right)$ where $|T|$ is the number of terminal nodes of $T$, $R_m$ is the rectangle corresponding to the $m$-th terminal node, and $\hat{y}_{R_m}$ is the predicted response (average of $y_i\in R_m$) ⁴.

Algorithm: Weakest link regression tree with $K$-fold cross-validation

1. For each ⁵ $\alpha > 0$:

   1. For $k = 1, \dots K$:
      1. Let $\mathcal{D}_k = \mathcal{D} \backslash \{k-\text{th fold}\}$
      2. Use recursive binary splitting to grow a tree $T_{k}$, stopping when each node has fewer than some minimum number of observations $M$ is reached ⁶
      3. Use weakest link pruning to find a subtree $T_{k, \alpha}$
   2. Let $CV_{(k)}(\alpha)$ be the $K$-fold cross-validation estimate of the mean squared test error
2. Choose $\hat{\alpha} = \underset{\alpha}{\text{argmin}}\ CV_{(k)}(\alpha)$
3. Return $\hat{T} = T_{\hat{\alpha}}$

Classification Trees

• Classification trees are very similar to regression trees, but they predict qualitative responses. The predicted class for an observation $(x_i, y_i)$ in $R_m$ is ⁷ is $\hat{k}_m = \underset{k}{\text{argmax}}\ \hat{p}_{m,k}$ where $\hat{p}_{m,k}$ is the fraction of observations $(x_i, y_i)$ in the region $R_m$ such that $y_i = k$.
• One performance measure is the Classification error rate ⁸ for the region $R_m$ is $E_m = 1 - \hat{p}_{m, \hat{k}}$
• A better performance measure is the Gini index for the region $R_m$, a measure of total variance ⁹ across classes $G_m = \sum_{k = 1}^K \hat{p}_{m,k}(1 - \hat{p}_{m,k})$
• Another better performance measure is the entropy for the region $R_m$ ¹⁰ $D_m = \sum_{k = 1}^K - \hat{p}_{m,k}\log(\hat{p}_{m,k})$
• Typically the Gini index or entropy is used to prune, due to their sensitivity to node purity. However, if prediction accuracy is the goal then classification error rate is preferable.

Trees Versus Linear Models

• A linear regression model is of the form

  $f(X) = \beta_0 + \sum_{j = 1}^p \beta_j X_j$

  while a regression tree model is of the form

  $f(X) = \sum_{m = 1}^M c_m I(X \in R_m)$

• Linear regression will tend to perform better if the relationship between features and response is well-approximated by a linear function, whereas the regression tree will tend perform better if the relationship is non-linear or complex.

Advantages and Disadvantages of Trees

Advantages

• Conceptual simplicity
• May mirror human decision-making better than previous regression and classification methods
• Readily visualizable and easily interpreted
• Can handle qualitative predictors without the need for dummy variables

Disadvantages

• Less accurate prediction than previous regression and classification methods
• Non-robust to changes in data – small changes in data lead to large changes in estimated tree.

Bagging, Random Forests, Boosting

These are methods for improving the prediction accuracy of decision trees.

Bagging

• The decision trees in § 8.1 suffer from high variance.

• Bagging is a method of reducing the variance of a statistical learning process ¹¹. The bagging estimate of the target function of the process with dataset $\mathcal{D}$ is

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

  where $\hat{f^*}^b(x)$ is the estimate of target function on the boostrap dataset $\mathcal{D}_b$ ¹².

• Bagging can be used for any statistical learning method but it is particularly useful for decision trees ¹³

Out-of-bag Error Estimation

• On average, a bagged tree uses about 2/3 of the data – the remaining 1/3 is the out-of-bag (OOB) data.
• We can predict the response for each observation using the trees for which it was OOB, yielding about B/3 prediction.
• If we’re doing regression, we can average these predicted responses, or if we’re doing classification, take a majority vote, to get a single OOB prediction for each observation.
• Test error can be estimated using these predictions.

Variable Importance Measures

• Bagging typically results in improved prediction accuracy over single trees, at the expense of interpretability
• The RSS (for bagging regression trees) and Gini index (for bagging classification trees) can provide measures of variable importance.
• For both loss functions (RSS/Gini) the amount the loss is decreases due to a split over a given predictor, averaged over the B bagged trees. The greater the decrease, the more important the predictor

Random Forests

• Random forests works as follows: at each split in the tree, choose a predictor from among a new random sample of $1 \leqslant m \leqslant p$ predictors.
• The random predictor sampling overcomes the tendency of bagged trees to look similar given strong predictors (e.g. the strongest predictor will be at the top of most or all of the bagged trees).
• On average, $\frac{p-m}{p}$ of the splits will not consider a given predictor, giving other predictors a chance to be chosen. This decorrelation of the trees improves the reduction in variance achieved by bagged.
• $m=p$ corresponds to bagging. $m << p$ is useful when there is a large number of correlated predictors. Typically we choose $m \approx \sqrt{p}$

Boosting

• Boosting is another method of improving prediction accuracy that can be applied to many statistical learning methods.
• In decision trees, each tree is build using information from the previous trees. Instead of bootstrapped datasets, the datasets are modified based on the previously grown trees.
• The boosting approach learns slowly, by slowly improving in areas where it underperforms. It has 3 parameters:
  • Number of trees $B$. Unlike bagging and random forests, boosting can overfit if $B$ is too big, although this happens slowly.
  • The shrinkage parameter $\lambda > 0$. Typical values are $\lambda = 0.01, 0.001$. Very small $\lambda$ can require very large $B$ to get good performance.
  • The number of tree splits $d$, which controls the complexity of the boosted ensemble. Often $d$ works well (the resulting tree is called a stump) ¹⁴

Algorithm: Boosting for Regression Trees

1. Set $\hat{f}(x) = 0$ and $r_i = y_i$, $1 \leqslant i \leqslant n$
2. For $b = 1, 2, \dots, B$:
   1. Fit a tree $\hat{f}^b$ with $d$ splits to $(X, r)$
   2. Update the model $\hat{f}$ by adding a shrunk version of the new tree: $\hat{f}(x) \leftarrow \hat{f}(x) + \lambda \hat{f}^b(x)$
   3. Update the residuals: $r_i \leftarrow r_i - \lambda \hat{f}^b(x)$

3. Output the boosted model

   $\hat{f}(x) = \sum_{b = 1}^B \lambda \hat{f}^b(x)$

---

Footnotes